Integers
Integers
Integers
Integers
Well-Ordering Principle
Every nonempty subset of the natural numbers contains a least
element
Definition
Let a and b be integers. If b = ak for some integer k, we say
a divides b or a is a divisor of b or b is a multiple of a and
write a|b.
Integers
Division Algorithm
The Division Algorithm
Let a and b be integers, with b > 0. Then there exist unique
integers q and r such that
a = bq + r
where 0 ≤ r < b.
Note
We must first prove that the numbers q and r actually exist. Then
we must show that the numbers q and r are unique i.e. if q 0 and r 0
are two other such numbers, then q = q 0 and r = r 0 .
Integers
Division Algorithm
Division Algorithm
proof
We first show existence of q and r .
Let S = {a − bk : k ∈ Z, a − bk ≥ 0}. If 0 ∈ S, then b divides a,
and we can let q = ba and r = 0. Suppose 0 ∈ / S, we first show
that S is nonempty. If a > 0, then a − b0 ∈ S. If a < 0, then
a − b(2a) = a(1 − 2b) ∈ S. In either case S 6= ∅.
By the Well-Ordering Principle, S must have a smallest member,
say r = a − bq. Therefore, a = bq + r with r ≥ 0.
We now show that r < b. Suppose that r > b. Then we have
r − b > 0 and in particular r − b = a − bq − b = a − b(q + 1) ∈ S.
But then r − b = a − b(q + 1) < a − bq = r , which contradicts the
fact that r = a − bq is the smallest member of S. So r ≤ b. Now
since 0 ∈
/ S, then r 6= b (otherwise from a = bq + r we woud have
a = bq + b = b(q + 1) = bq 0 + 0 ) and so r < b.
Integers
Division Algorithm
Division Algorithm
proof
To prove uniqueness of q and r , suppose there exist integers
r , r 0 , q, q 0 such that a = bq + r , 0 ≤ r < b and a = bq 0 + r 0 ,
0 ≤ r 0 < b. Then bq + r = bq 0 + r 0 . Assume that r 0 ≥ r . From
the last equation we have bq − bq 0 = r 0 − r from which
b(q − q 0 ) = r 0 − r ; therefore, b must divide r 0 − r and
0 ≤ r 0 − r ≤ r 0 < b. This is possible only if r 0 − r = 0. Hence,
r = r 0 and q = q 0 .
Integers
Greatest Common Divisors
Definition
An integer d is called a common divisor of a and b if d|a and
d|b.
The greatest common divisor of integers a and b is a positive
integer d such that d is a common divisor of a and b and if d 0
is any other common divisor of a and b, then d 0 |d. We write
d = gcd(a, b)
We say that two integers a and b are relatively prime or
coprime if gcd(a, b) = 1.
Integers
Greatest Common Divisors
Greatest Common Divisors
Theorem
Let a and b be nonzero integers. Then there exist integers r and s
such that
gcd(a, b) = ar + bs
. Furthermore, the greatest common divisor of a and b is unique.
Integers
Greatest Common Divisors
Greatest Common Divisors
Proof
Let
S = {am + bn : m, n ∈ Z, am + bn > 0}
. Clearly, the set S is nonempty; hence, by the Well-Ordering
Principle S must have a smallest member, say d = ar + bs. We
claim that d = gcd(a, b). To show that d = gcd(a, b), we show
that
d is a common divisor of a and b
if d 0 is another common divisor of a and b then d 0 |d
By the division algorithm we can write a = dq + r 0 where
0 ≤ r 0 < d.
Now either r 0 > 0 or r 0 = 0. If r 0 > 0 then
r 0 = a − dq
= a − (ar + bs)q
= a − arq − bsq
= a(1 − rq) + b(−sq)
Integers
Greatest Common Divisors
Greatest Common Divisors
Proof
which takes the form am + bn and so is in S. But this would
contradict the fact that d is the smallest member of S. Hence,
r 0 = 0 from which d divides a. A similar argument shows that d
divides b. Therefore, d is a common divisor of a and b.
Suppose that d 0 is another common divisor of a and b, and we
want to show that d 0 |d.
If we let a = d 0 h and b = d 0 k, then
d = ar + bs = d 0 hr + d 0 ks = d 0 (hr + ks). So d 0 must divide d.
Hence, d must be the unique greatest common divisor of a and b
Corollary
Let a and b be two integers that are relatively prime. Then there
exist integers r and s such that ar + bs = 1.
Integers
Euclidean Algorithm
The Euclidean Algorithm
To compute gcd(a, b) = d, we repeatedly use the division
algorithm to obtain a decreasing sequence of positive integers
r1 > r2 > · · · > rn = d; that is,
b = aq1 + r1
a = r1 q2 + r2
r1 = r2 q3 + r3
..
.
rn−2 = rn−1 qn + rn
rn−1 = rn qn+1 .
Integers
Euclidean Algorithm
Euclidean Algorithm
The Euclidean Algorithm
To find r and s such that ar + bs = d, we begin with this last
equation and substitute results obtained from the previous
equations:
d = rn
= rn−2 − rn−1 qn
= rn−2 − qn (rn−3 − qn−1 rn−2 )
= −qn rn−3 + (1 + qn qn−1 )rn−2
..
.
= ra + sb.
The algorithm that we have just used to find the greatest common
divisor d of two integers a and b and to write d as the linear
combination of a and b is known as the Euclidean algorithm
Integers
Euclidean Algorithm
Euclidean Algorithm
The Euclidean Algorithm : NOTE
The integers r and s are not unique. In particular for a particular
pair of integers, say r = r0 and s = s0 s.th. d = r0 a + s0 b, then
generally we have
bn an
r = r0 + , s = s0 −
d d
where n ∈ Z.
Thus since there infinitely many choices for n, then there are
infinitely many pairs of integers r , s such that
d = gcd(a, b) = ra + sb
Integers
Euclidean Algorithm
Euclidean Algorithm
The Euclidean Algorithm - Example
Let us compute the greatest common divisor of 945 and 2415.
First observe that
2415 = 945 × 2 + 525
945 = 525 × 1 + 420
525 = 420 × 1 + 105
420 = 105 × 4 + 0.
Therefore, gcd(945, 2415) = 105.
Integers
Euclidean Algorithm
Euclidean Algorithm
The Euclidean Algorithm - Example
If we work backward through the above sequence of equations, we
can also obtain numbers r and s such that 945r + 2415s = 105.
Observe that
105 = 525 + (−1) × 420
= 525 + (−1) × [945 + (−1) × 525]
= 2 × 525 + (−1) × 945
= 2 × [2415 + (−2) × 945] + (−1) × 945
= 2 × 2415 + (−5) × 945
So r = −5 and s = 2. Notice that r and s are not unique, since
r = 41 and s = −16 would also work.
Integers
Primes
Primes - Definition
Let p be an integer such that p > 1. We say that p is a prime
number, or simply p is prime, if the only positive numbers that
divide p are 1 and p itself. An integer n > 1 that is not prime is
said to be composite.
Lemma - Euclid
Let a and b be integers and p be a prime number. If p|ab, then
either p|a or p|b.
Proof
Suppose that p does not divide a. We must show that p|b. Since
gcd(a, p) = 1, there exist integers r and s such that ar + ps = 1.
So b = b(ar + ps) = (ab)r + p(bs). Since p divides both ab and
itself, p must divide (ab)r + p(bs) = b.
Integers
Fundamental theorem of arithmetic
Fundamental theorem of arithmetic
Let n be an integer such that n > 1. Then
n = p1 .p2 . · · · .pk
where p1 , p2 , · · · , pk are primes (not necessarily distinct),(that is n
is a prime or expressible as a product of a finite number of primes).
Furthermore this factorization is unique, that is, if
n = q1 .q2 . · · · .ql
then k = l and with a suitable re-ordering (if necessary) pi = qi .
Integers
Fundamental theorem of arithmetic
Fundamental theorem of arithmetic
Proof
Since we are assuming that n > 1, if n = 2 then n is trivially a
product of primes. So suppose the result is true for all integers m
such that 2 ≤ m ≤ n − 1 i.e. m is product of primes. We want to
prove that n is a product of primes. If n is prime then n is trivially
a product of primes and so the result holds. Otherwise if n is
composite, then n = n1 .n2 where n1 , n2 ∈ Z, 1 < n1 < n,
1 < n2 < n. By the induction hypothesis each of n1 and n2 is a
product of primes and so therefore is n.
Integers
Fundamental theorem of arithmetic
Fundamental theorem of arithmetic
Proof continued
To show uniqueness i.e. the factorization is unique we argue by
induction on n. The result is certainly true for n = 2 since in this
case n is prime. Now suppose that the result holds for all integers
m such that 1 < m < n and that
n = p1 p2 · · · pk = q1 q2 · · · ql (1)
where (for arguments’ sake) p1 ≤ p2 ≤ · · · ≤ pk and
q1 ≤ q2 ≤ · · · ≤ ql . By the lemma above p1 | qi for some
i = 1, 2, · · · , l and q1 | pj for some j = 1, 2, · · · , k. Since all pi ’s
and qj ’s are primes p1 = qi and q1 = pj .
Integers
Fundamental theorem of arithmetic
Fundamental theorem of arithmetic
Proof continued
Now since p1 ≤ pj = q1 ≤ qi = p1 i.e. p1 ≤ q1 ≤ p1 , we have
p1 = q1 . So equation (1) above yields
n0 = p2 · · · pk = q2 · · · ql (2)
Now n0 < n and so by the induction hypothesis n0 has a unique
factorization. Hence k = l and qi = pi for i = 1, · · · , k.
Integers
Infinitude of Primes
Theorem - Euclid
There exist an infinite number of primes.
Proof
We will prove this theorem by contradiction. Suppose that there
are only a finite number of primes, say p1 , p2 , · · · , pn . Let
P = p1 p2 · · · pn + 1. Then P must be divisible by some pi for
1 ≤ i ≤ n. In this case, pi must divide P − p1 p2 · · · pn = 1, which
is a contradiction. Hence, either P is prime or there exists an
additional prime number p 6= pi that divides P .
