1.18. EXERCISES 35

29. Prove the Euclidean algorithm: If m,n are positive integers, then there exist integersq,r ≥ 0 such that r < m and n = 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. It was done in the chapter,but go through it yourself.

30. Recall that two polynomials are equal means that the coefficients of correspondingpowers of λ are equal. Thus a polynomial equals 0 if and only if all coefficientsequal 0. In calculus we usually think of a polynomial as 0 if it sends every value ofx to 0. Suppose you have the following polynomial 1̄x2 + 1̄x where it is understoodto be a polynomial in Z2. Thus it is not the zero polynomial. Show, however, thatthis equals zero for all x ∈ Z2 so we would be tempted to say it is zero if we use theconventions of calculus.

31. Prove Wilson’s theorem. This theorem states that if p is a prime, then (p−1)!+1 isdivisible by p. Wilson’s theorem was first proved by Lagrange in the 1770’s. Hint:Check directly for p= 2,3. Show that p−1=−1 and that if a∈ {2, · · · , p−2} , then(a)−1 ̸= a. Thus a residue class a and its multiplicative inverse for a∈ {2, · · · , p−2}occur in pairs. Show that this implies that the residue class of (p−1)! must be −1.From this, draw the conclusion.

32. Show that in the arithmetic of Zp, (x+ y)p = (x)p + (y)p, a well known formulaamong students.

33. Consider (a) ∈ Zp for p a prime, and suppose (a) ̸= 1,0. Fermat’s little theoremsays that (a)p−1 = 1. In other words (a)p−1−1 is divisible by p. Prove this. Hint:Show that there must exist r ≥ 1,r ≤ p− 1 such that (a)r = 1. To do so, consider1,(a) ,(a)2 , · · · . Then these all have values in

{1,2, · · · , p−1

}, and so there must

be a repeat in{

1,(a) , · · · ,(a)p−1}, say p− 1 ≥ l > k and (a)l = (a)k . Then tell

why (a)l−k− 1 = 0. Let r be the first positive integer such that (a)r = 1. Let G ={1,(a) , · · · ,(a)r−1

}. Show that every residue class in G has its multiplicative inverse

in G. In fact, (a)k (a)r−k = 1. Also verify that the entries in G must be distinct. Nowconsider the sets bG≡

{b(a)k : k = 0, · · · ,r−1

}where b∈

{1,2, · · · , p−1

}. Show

that two of these sets are either the same or disjoint and that they all consist of relements. Explain why it follows that p−1 = lr for some positive integer l equal tothe number of these distinct sets. Then explain why (a)p−1 = (a)lr = 1.

34. Let p(x) and q(x) be polynomials. Then by the division algorithm, there exist poly-nomials l (x) , r (x) equal to 0 or having degree smaller than p(x) such that

q(x) = p(x) l (x)+ r (x)

If k (x) is the greatest common divisor of p(x) and q(x) , explain why k (x) mustdivide r (x). Then argue that k (x) is also the greatest common divisor of p(x) andr (x). Now repeat the process for the polynomials p(x) and r (x). This time, theremainder term will have degree smaller than r (x). Keep doing this and eventuallythe remainder must be 0. Describe an algorithm based on this which will determinethe greatest common divisor of two polynomials.