Due at the prelim on 10/9/03.
With the limitations of ascii, we'll use = to mean 'equivalent' if the equation is written 'mod n'.
1. Let a, b, and c be positive integers with a and b being coprime.
(i) prove that a|bc ==> a|c
(ii) prove that a|c and b|c ==> ab|c
(iii) prove that a^(-1) = s mod b if as + bt = 1
2. (i) Use the matrix layout algorithm shown in class to find gcd(7245,4784), and express it in the form 7245s + 4784t
(ii) if it exists, give the value of the multiplicative inverse or 91 modulo 237
3. Prove that for any integers a and b, ab = gcd(a,b).lcm(a,b)
4. Let p be prime. Prove that (p-1)! = -1 (mod p)
5. Solve each of the following for x.
(i) 432x = 2 mod 91
(ii) 23x = 16 mod 107
(iii) 3x = 1 mod 5 with 2x = 6 mod 8
6. A hoard of gold pieces "comes into the possession of" a band of 15 pirates. When they come to divide up the coins, they find that three are left over. Their discussion of what to do with these extra coins becomes animated, and by the time some semblance of order returns, there remain only 7 pirates capable of making an effective claim on the hoard. When however the hoard is divided between these seven it is found that two pieces are left over. There ensues an unfortunate repetition of the earlier disagreement, but this does at least have the consequence that the four pirates who remain are able to divide up the hoard evenly between them. What is the minimum number of gold pieces that could have been in the hoard? (from Humphreys and Prest, "Numbers, groups and codes", CUP 1989)