Skip to main content
Logo image

Abstract Algebra: Theory and Applications

Thomas W. Judson

🔗

Section 2.2 The Division Algorithm

🔗
An application of the Principle of Well-Ordering that we will use often is the division algorithm.

Proof.

This is a perfect example of the existence-and-uniqueness type of proof. We must first prove that the numbers q and r actually exist. Then we must show that if q′ and r′ are two other such numbers, then q=q′ and r=r′.

Existence of q and r.

Let
S={a−bk:k∈Z and a−bk≥0}.
If 0∈S, then b divides a, and we can let q=a/b and r=0. If 0∉S, we can use the Well-Ordering Principle. We must first show that S is nonempty. If a>0, then a−b⋅0∈S. If a<0, then a−b(2a)=a(1−2b)∈S. In either case S≠∅. By the Well-Ordering Principle, S must have a smallest member, say r=a−bq. Therefore, a=bq+r, r≥0. We now show that r<b. Suppose that r>b. Then
a−b(q+1)=a−bq−b=r−b>0.
In this case we would have a−b(q+1) in the set S. But then a−b(q+1)<a−bq, which would contradict the fact that r=a−bq is the smallest member of S. So r≤b. Since 0∉S, r≠b and so r<b.

Uniqueness of q and r.

Uniqueness of q and r. Suppose there exist integers r, r′, q, and q′ such that
a=bq+r,0≤r<banda=bq′+r′,0≤r′<b.
Then bq+r=bq′+r′. Assume that r′≥r. From the last equation we have b(q−q′)=r′−r; therefore, b must divide r′−r and 0≤r′−r≤r′<b. This is possible only if r′−r=0. Hence, r=r′ and q=q′.
🔗
Let a and b be integers. If b=ak for some integer k, we write a∣b. 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′ is any other common divisor of a and b, then d′∣d. We write d=gcd(a,b); for example, gcd(24,36)=12 and gcd(120,102)=6. We say that two integers a and b are relatively prime if gcd(a,b)=1.

Proof.

Let
S={am+bn:m,n∈Z and 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). Write a=dq+r′ where 0≤r′<d. If r′>0, then
r′=a−dq=a−(ar+bs)q=a−arq−bsq=a(1−rq)+b(−sq),
which is in S. But this would contradict the fact that d is the smallest member of S. Hence, r′=0 and d divides a. A similar argument shows that d divides b. Therefore, d is a common divisor of a and b.
Suppose that d′ is another common divisor of a and b, and we want to show that d′∣d. If we let a=d′h and b=d′k, then
d=ar+bs=d′hr+d′ks=d′(hr+ks).
So d′ must divide d. Hence, d must be the unique greatest common divisor of a and b.
🔗

Subsection The Euclidean Algorithm

🔗
Among other things, Theorem 2.10 allows us to compute the greatest common divisor of two integers.
🔗

Example 2.12.

🔗
🔗
Let us compute the greatest common divisor of 945 and 2415. First observe that
2415=945⋅2+525945=525⋅1+420525=420⋅1+105420=105⋅4+0.
🔗
Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415. Hence, 105 divides both 945 and 2415. If d were another common divisor of 945 and 2415, then d would also have to divide 105. Therefore, gcd(945,2415)=105.
🔗
🔗
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.
🔗
🔗
To compute gcd(a,b)=d, we are using repeated divisions to obtain a decreasing sequence of positive integers r1>r2>⋯>rn=d; that is,
b=aq1+r1a=r1q2+r2r1=r2q3+r3⋮rn−2=rn−1qn+rnrn−1=rnqn+1.
🔗
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−1qn=rn−2−qn(rn−3−qn−1rn−2)=−qnrn−3+(1+qnqn−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.
🔗

Subsection Prime Numbers

🔗
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.

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 b=(ab)r+p(bs).

Proof.

We will prove this theorem by contradiction. Suppose that there are only a finite number of primes, say p1,p2,…,pn. Let P=p1p2⋯pn+1. Then P must be divisible by some pi for 1≤i≤n. In this case, pi must divide P−p1p2⋯pn=1, which is a contradiction. Hence, either P is prime or there exists an additional prime number p≠pi that divides P.

Proof.

Uniqueness.
To show uniqueness we will use induction on n. The theorem is certainly true for n=2 since in this case n is prime. Now assume that the result holds for all integers m such that 1≤m<n, and
n=p1p2⋯pk=q1q2⋯ql,
where p1≤p2≤⋯≤pk and q1≤q2≤⋯≤ql. By Lemma 2.13, p1∣qi for some i=1,…,l and q1∣pj for some j=1,…,k. Since all of the pi’s and qi’s are prime, p1=qi and q1=pj. Hence, p1=q1 since p1≤pj=q1≤qi=p1. By the induction hypothesis,
n′=p2⋯pk=q2⋯ql
has a unique factorization. Hence, k=l and qi=pi for i=1,…,k.
Existence.
To show existence, suppose that there is some integer that cannot be written as the product of primes. Let S be the set of all such numbers. By the Principle of Well-Ordering, S has a smallest number, say a. If the only positive factors of a are a and 1, then a is prime, which is a contradiction. Hence, a=a1a2 where 1<a1<a and 1<a2<a. Neither a1∈S nor a2∈S, since a is the smallest element in S. So
a1=p1⋯pra2=q1⋯qs.
Therefore,
a=a1a2=p1⋯prq1⋯qs.
So a∉S, which is a contradiction.
🔗

Subsection Historical Note

🔗
🔗
Prime numbers were first studied by the ancient Greeks. Two important results from antiquity are Euclid’s proof that an infinite number of primes exist and the Sieve of Eratosthenes, a method of computing all of the prime numbers less than a fixed positive integer n. One problem in number theory is to find a function f such that f(n) is prime for each integer n. Pierre Fermat (1601?–1665) conjectured that 22n+1 was prime for all n, but later it was shown by Leonhard Euler (1707–1783) that
225+1=4,294,967,297
🔗
is a composite number. One of the many unproven conjectures about prime numbers is Goldbach’s Conjecture. In a letter to Euler in 1742, Christian Goldbach stated the conjecture that every even integer with the exception of 2 seemed to be the sum of two primes: 4=2+2, 6=3+3, 8=3+5, …. Although the conjecture has been verified for the numbers up through 4×1018, it has yet to be proven in general. Since prime numbers play an important role in public key cryptography, there is currently a great deal of interest in determining whether or not a large number is prime.
PrevTopNext