16.2. EXERCISES 375

16.2 Exercises1. Prove the Euclidean algorithm: If m,n are positive integers, then there exist integers

q,r ≥ 0 such that r < m andn = qm+ r

Hint: You might try considering

S≡ {n− km : k ∈ N and n− km < 0}

and picking the smallest integer in S or something like this.

2. ↑The greatest common divisor of two positive integers m,n, denoted as q is a positivenumber which divides both m and n and if p is any other positive number whichdivides both m,n, then p divides q. Recall what it means for p to divide q. It meansthat q = pk for some integer k. Show that the greatest common divisor of m,n is thesmallest positive integer in the set S

S≡ {xm+ yn : x,y ∈ Z and xm+ yn > 0}

Two positive integers are called relatively prime if their greatest common divisor is1.

3. ↑A positive integer larger than 1 is called a prime number if the only positive numberswhich divide it are 1 and itself. Thus 2,3,5,7, etc. are prime numbers. If m is apositive integer and p does not divide m where p is a prime number, show that p andm are relatively prime.

4. ↑There are lots of fields. This will give an example of a finite field. Let Z denotethe set of integers. Thus Z = {· · · ,−3,−2,−1,0,1,2,3, · · ·}. Also let p be a primenumber. We will say that two integers, a,b are equivalent and write a∼ b if a−b isdivisible by p. Thus they are equivalent if a−b = px for some integer x. First showthat a ∼ a. Next show that if a ∼ b then b ∼ a. Finally show that if a ∼ b and b ∼ cthen a∼ c. For a an integer, denote by [a] the set of all integers which is equivalentto a, the equivalence class of a. Show first that is suffices to consider only [a] fora = 0,1,2, · · · , p−1 and that for 0≤ a < b≤ p−1, [a] ̸= [b]. That is, [a] = [r] wherer ∈ {0,1,2, · · · , p−1}. Thus there are exactly p of these equivalence classes. Hint:Recall the Euclidean algorithm. For a > 0, a = mp+ r where r < p. Next define thefollowing operations.

[a]+ [b]≡ [a+b]

[a] [b] = [ab]

Show these operations are well defined. That is, if [a] = [a′] and [b] = [b′] , then [a]+[b] = [a′]+[b′] with a similar conclusion holding for multiplication. Thus for additionyou need to verify [a+b] = [a′+b′] and for multiplication you need to verify [ab] =[a′b′]. For example, if p = 5 you have [3] = [8] and [2] = [7] . Is [2×3] = [8×7]? Is[2+3] = [8+7]? Clearly so in this example because when you subtract, the result isdivisible by 5. So why is this so in general? Now verify that {[0] , [1] , · · · , [p−1]}with these operations is a Field. This is called the integers modulo a prime and iswritten Zp. Since there are infinitely many primes p, it follows there are infinitelymany of these finite fields. Hint: Most of the axioms are easy once you have shown