144
Proofs, Induction, and Number Theory
The Fundamental Theorem of arithmetic
We’ll start by expanding on a result we proved using the second principle of mathematical induction in Example 23, Section 2.2: For every integer n ≥ 2, n is a
prime number or a product of prime numbers.
In fact, a stronger statement can be made.
tHeoReM ThE FuNDaMENTal ThEorEM oF arIThMETIC
For every integer n ≥ 2, n is a prime number or can be written uniquely (ignoring
ordering) as a product of prime numbers.
The new part is that there is only one way to factor a composite number
into prime factors if we ignore the order in which we write the factors. Thus we
consider
2(3)(3) = 3(2)(3)
to be the same factorization of 18. We intuitively accept the uniqueness idea—
how else could you factor 18 into prime factors? A formal proof requires quite a
bit of preparation, and it begins with revisiting the idea of the greatest common
divisor of two positive integers.
The Euclidean algorithm to find gcd(a, b) was given in Section 2.3. It turns out
that if a and b are positive integers, then gcd(a,b) can always be written as a linear
combination of a and b; that is,
gcd(a, b) = ia + jb for some integers i and j
Although it’s easy to verify in Example 29 that 3(420) − 19(66) indeed has the
value 6, the coefficient values of 3 and −19 seem mysterious. They are not just
pulled out of the air, however; in fact they are derived from the successive divisions done by the Euclidean algorithm.
ReMinDeR
A prime number is an
integer > 1 that is divisible
only by itself and 1.
eXAMPLe 29
In Section 2.3 we learned, using the Euclidean algorithm, that gcd(420, 66) = 6.
And 6 can be written as a linear combination of 420 and 66:
6 = 3(420) − 19(66)
eXAMPLe 30
The successive divisions performed by the Euclidean algorithm in finding
gcd(420, 66) can be written as follows (see Example 27 in Section 2.3):
420 = 6 # 66 + 24
66 = 2 # 24 + 18
24 = 1 # 18 + 6
18 = 3 # 6 + 0
Proofs, Induction, and Number Theory
The Fundamental Theorem of arithmetic
We’ll start by expanding on a result we proved using the second principle of mathematical induction in Example 23, Section 2.2: For every integer n ≥ 2, n is a
prime number or a product of prime numbers.
In fact, a stronger statement can be made.
tHeoReM ThE FuNDaMENTal ThEorEM oF arIThMETIC
For every integer n ≥ 2, n is a prime number or can be written uniquely (ignoring
ordering) as a product of prime numbers.
The new part is that there is only one way to factor a composite number
into prime factors if we ignore the order in which we write the factors. Thus we
consider
2(3)(3) = 3(2)(3)
to be the same factorization of 18. We intuitively accept the uniqueness idea—
how else could you factor 18 into prime factors? A formal proof requires quite a
bit of preparation, and it begins with revisiting the idea of the greatest common
divisor of two positive integers.
The Euclidean algorithm to find gcd(a, b) was given in Section 2.3. It turns out
that if a and b are positive integers, then gcd(a,b) can always be written as a linear
combination of a and b; that is,
gcd(a, b) = ia + jb for some integers i and j
Although it’s easy to verify in Example 29 that 3(420) − 19(66) indeed has the
value 6, the coefficient values of 3 and −19 seem mysterious. They are not just
pulled out of the air, however; in fact they are derived from the successive divisions done by the Euclidean algorithm.
ReMinDeR
A prime number is an
integer > 1 that is divisible
only by itself and 1.
eXAMPLe 29
In Section 2.3 we learned, using the Euclidean algorithm, that gcd(420, 66) = 6.
And 6 can be written as a linear combination of 420 and 66:
6 = 3(420) − 19(66)
eXAMPLe 30
The successive divisions performed by the Euclidean algorithm in finding
gcd(420, 66) can be written as follows (see Example 27 in Section 2.3):
420 = 6 # 66 + 24
66 = 2 # 24 + 18
24 = 1 # 18 + 6
18 = 3 # 6 + 0