1 of 22

PRIME NUMBERS �

312706023 何忻

4.3

The Division Algorithm:

2 of 22

OUTLINE

Prime & Composite number

Division algorithms

Digit represent in computer

3 of 22

DEFINITION 4.1

If a, b ∈ Z and b ≠ 0, we say that b divides a, and write b|a, if there is an integer n such that a = bn.
When this occurs we say that b is a divisor of a, or a is a multiple of b. （ b 是 a 的除數； a 是 b 的乘數）

When ab = 0 for a, b ∈ Z, then either a = 0 or b = 0, and we say that Z has no proper divisor of 0.

（不存在除了自己或 1 之外的因數）

a mod b = 0＿

1

4 of 22

THEOREM 4.3

For a, b, c ∈ Z

(a) 1|a and a|0.

(b) [(a|b) ∧ (b|a)] ⟹ a = ± b.

(c) [(a|b) ∧ (b|c)] ⟹ a|c.

(d) a|b ⟹ a|bx, for all x ∈ Z.

(e) If x = y + z, for x, y, z ∈ Z, and a divides two of the three integer x, y, z, then a divides the remaining integer.

(f) [(a|b) ∧ (a|c)] ⟹ a|(bx + cy), for all 𝑥, y ∈ Z.

(The expression bx + cy is called a linear combination of b, c.)

(g) For 1 ≤ i ≤ n, let c_i∈ Z. If a divides each c_i, then a|( c₁x₁+c₂x₂ + … + c_nx_n ), where 𝑥_𝑖 ∈ Z , 1 ≤ i ≤ n.

2

5 of 22

[(a|b) ∧ (a|c)] ⟹ a|(bx + cy), for all 𝑥, y ∈ Z.

(The expression bx + cy is called a linear combination of b, c.)

3

1. If a|b and a|c, then b = am and c = an, for some m, n ∈ Z.

2. So bx + cy = (am)x + (an)y = a(mx + ny)

Associative Law of Mulitplication
Distributive Law of Multiplication over Addition

Part (f):

Proof

Since bx + cy = a(mx + ny), with mx + ny ∈ Z

⟹ It follows that a|(bx + cy)

6 of 22

EXAMPLE 4.23

Do there exist integers x, y, z so that 6x+9y+15z=107?

4

Step 1: Since 3|6 and 3|9 and 3|15

Step 2: 3 is a divisor of 6x + 9y + 15z

Step 3: 3 is a divisor of 107 (?)

(g) For 1 ≤ i ≤ n, let c_i∈ Z. If a divides each c_i,

then a|( c₁x₁+c₂x₂ + … + c_nx_n ), where 𝑥_𝑖 ∈ Z , 1 ≤ i ≤ n.

NO!

So there doesn’t exist such integers x, y, z

7 of 22

EXAMPLE 4.24

Let a, b ∈ Z so that 17 | (2a+3b). Prove 17 | (9a+5b)

5

Step 1: 17 | (2a + 3b) ⟹ 17 | (−4)∗(2a + 3b)

Step 2: 17 | (17a + 17b)

Step 3: 17 | [(17a + 17b) + (−4)∗(2a + 3b)]

⟹ 17 | 9a + 5b

(d) a|b ⟹ a|bx, for all x ∈ Z.

(f) [(a|b) ∧ (a|c)] ⟹ a|(bx + cy), for all 𝑥, y ∈ Z.

(e) If x = y + z, for x, y, z ∈ Z, and a divides two of the three integer x, y, z, then a divides the remaining integer.

8 of 22

LEMMA 4.1

If n ∈ 𝐙⁺and n is composite,

then there is a prime p such that p|n

Proof

(d) a|b ⟹ a|bx, for all x ∈ Z.

與 m 的假設相互矛盾 ⟹ 可知 S = ∅

必定存在質數 p 可整除 n

6

9 of 22

There are infinitely many primes.

THEOREM 4.4 EUCLID

Proof

但不可能有p_j可整除1 ⟹ 與假設相互矛盾

有無限多的質數存在

(e) If x = y + z, for x, y, z ∈ Z, and a divides two of the three integer x, y, z, then a divides the remaining integer.

By LEMMA 4.1

7

10 of 22

If a, b ∈ Z, with b > 0, then there exist unique q, r ∈ Z

with a = qb + r, 0 ≤ r < b.

THEOREM 4.5 THE DIVISION ALGORITHM

UNIQUENESS唯一性

EXISTENCE

存在性

前提：If b|a the result follows with r = 0

⟹ so consider the case b does not divide a.

8

11 of 22

Proof

Existence 存在性

Step 1: Let S = {a – tb| t ∈ Z, a – tb > 0} ⊂ 𝐙⁺.

(a) If a > 0, let t = 0 ⟹ a ∈ S and S ≠ ∅

(b) If a ≤ 0, let t = a – 1 ⟹ a – tb

= a – (a – 1)b = a(1 – b) + b

Step 2: Because b ≥ 1 ⟹ (1 – b) ≤ 0 ⟹ a(1 – b) ≥ 0

⟹ a – tb = a(1 – b) + b > 0 and S ≠ ∅.

Hence, for any a ∈ Z, S is a nonempty subset of 𝐙+.

By WOP, S has a least element r, where 0 < r = a – qb, for some q ∈ Z.

(c) If r = b, then a = (q+1)b ⟹ b|a.

(d) If r > b, then r = b + c, for some c ∈ 𝐙⁺.

⟹ a – qb = r = b + c ⟹ c = a – (q+1)b ∈ S

This now establishes a quotient q and remainder r, 0 ≤ r < b, for the theorem.

與初始前提相互矛盾

符合形式 a – tb

9

這個證明是使用歸納法和反證法證明任意整數 a 除以一個固定的正整數 b 的時候，可以得到一個商數和餘數，並且餘數會小於除數。

1. **建立集合 S**：

- 定義集合 S 為所有形如 \(a - tb\) 的數，其中 \(t\) 為整數，且 \(a - tb > 0\)。這表示 S 是正整數的一個子集。

- 如果 \(a > 0\)，則取 \(t = 0\)，得到 \(a \in S\)，確保 S 不為空。

- 如果 \(a \leq 0\)，則取 \(t = a - 1\)，計算得 \(a - tb = a(1 - b) + b\)。

2. **確保 S 不為空**：

- 因為 \(b \geq 1\)，所以 \(1 - b \leq 0\)，進而 \(a(1 - b) \geq 0\)。

- 因此，\(a - tb = a(1 - b) + b > 0\)，保證 S 不為空。

3. **使用良序原理 (WOP) 來證明存在最小元素**：

- 假設 S 是正整數的非空子集，根據良序原理，S 中必有一最小元素 \(r\)，滿足 \(0 < r = a - qb\)，其中 \(q\) 為整數。

- 進行分情況討論：

- (c) 如果 \(r = b\)，則 \(a = (q+1)b\)，導致 \(b | a\)，矛盾。

- (d) 如果 \(r > b\)，則 \(r = b + c\)，其中 \(c > 0\)。

- 得到 \(a - qb = r = b + c\)，進一步得到 \(c = a - (q+1)b\)，發現 \(c\) 也屬於 S。

- 但由於 \(r > c\)，這違反了 \(r\) 是 S 中的最小元素。

4. **結論**：

- 由於分情況討論中沒有其他可能性，因此不存在 \(r\) 使得 \(0 < r < b\)，所以 \(r\) 必須滿足 \(0 \leq r < b\)。

- 因此，對於任意整數 \(a\) 和正整數 \(b\)，都存在整數 \(q\) 和 \(r\)，滿足 \(a = qb + r\) 且 \(0 \leq r < b\)，這就是帶餘除法的結論。

12 of 22

Proof

Uniqueness 唯一性

Step 1: Suppose there are q₁, q₂, r₁, r₂ ∈ Z

with a = q₁b + r₁ , 0 ≤ r₁ < b and a = q₂b + r₂, 0 ≤ r₂ < b

Step 2: Then q₁b + r₁ = q₂b + r₂

⟹ b ∙ |q₁ – q₂| = |r₂ – r₁| < b

(∵ 0 ≤ r₁ , r₂ < b )

10

13 of 22

Calculate 4 * 7

Step 1: 2 * 7 = 7 + 7 = 14

Step 2: 3 * 7 = (2 + 1)* 7 = 2 * 7 + 1* 7

= (7 + 7 ) + 7 = 21

Step 3: 4 * 7 = (3 + 1)* 7 = 3 * 7 + 1* 7

= ((7 + 7 ) + 7) + 7 = 21 + 7= 28

EXAMPLE 4.26

Repeated addition

11

14 of 22

Step 1: 37 - 8 = 29 ≥ 8

Step 2: 29 - 8 = (37 - 8) - 8 = 37 - (2・8) = 21 ≥ 8

Step 3: 21 - 8 = ((37 - 8) - 8) - 8 = 37 - (3・8) = 13 ≥ 8

Step 4: 13 - 8 = (((37 - 8) - 8) - 8) -8 = 37 - (4・8)

= 5 < 8

EXAMPLE 4.26

Repeated subtraction

q = 4, r = 5

12

15 of 22

Write 6137 in the octal system (base 8)

6137

8

767

8

95

11

8

1

8

0

1

7

3

1

6137 = (13771)₈

Remainders

Nonnegative integers r₀, r₁, r₂, … r_k, with 0 < r_k< 8

⟹ such that 6137 = (r_k … r₂r₁r₀)₈

r₄

r₃

r₂

r₁

r₀

Remainders

Concept

以此類推

EXAMPLE 4.27

8

13

16 of 22

Write 13,874,945 (base 16)

13,874,945

16

867,184

16

54,199

16

3,387

16

211

16

1

0

7

11 (= B)

3

13 (= D)

13

16

0

EXAMPLE 4.28

Remainders

r₄

r₃

r₂

r₁

r₀

r₅

13,874,945 = (D3B701)₁₆

14

17 of 22

Converting between base 2 and base 16

1010	0001	0011	1111
A	1	3	F

EXAMPLE 4.28

(A13F)₁₆= (1010000100111111)₂

15

18 of 22

EXAMPLE 4.29

1’s complement of \|n\|	2’s complement of n
Replace each 0/1 in the binary represented of \|n\| by 1/0	Add 1 too the result in 1’s complement

Step 1: Start with binary representation of 6.

Step 2: Interchange the 0/1

⟹ the result is 1’s complement of 0110.

Step 3: Add 1 to be the prior result.

6 ⟹ 0110

1001

1010

Obtain the 2’s complement of -6

16

19 of 22

EXAMPLE 4.29

obtain the four-bit pattern for the value -8 ≤ n ≤ -1

非負整數始於0

非負整數的 2 補數

= 直接轉換成二進制

負整數的 2 補數

⟹ 取其絕對值的 1 補數

⟹ 再加上 1

17

20 of 22

Step 1: 33 – 15 = 33 + (-15)

Step 2: 33 = (00100001)₂

Step 3: 15 = (00001111)₂

Step 4: -15 = 11110000 + 00000001 = 11110001

Step 5:

00100001

11110001

+

100010010

Discarded

EXAMPLE 4.30

Calculate 33 – 15 (base 2)

Step 6: (00010010)₂=18

18

21 of 22

01110101

01011000

+

11001101

117

88

+

EXAMPLE 4.30

Overflow error when adding 2 numbers

It means the ans is negative!

Range of N bits [−2^N⁻¹, 2^N⁻¹− 1]

19

22 of 22

EXAMPLE 4.31

Proof

By LEMMA 4.1

20