math QAs

MA 341 Final, due Friday, May 5

You’ll be graded on the quality of your writing along with the mathe- matical content. You are not allowed to discuss these problems with anyone else. Hand in your solutions to the math department office, MCS 142, in my mailbox, by 5 pm on Friday May 5.

1. Prove that if n is odd and not divisible by 3, then 24|n2 − 1.

2. Prove that if a,b ∈ Z are relatively prime and ab is a perfect cube (that is, the third power of another integer), then a and b are both perfect cubes.

3. Does the Diophantine equation x2 − 101y = 14 have a solution?

4. Find four solutions (x,y,z) to the Diophantine equation 2x2 + 3y2 = 5z2, where x,y,z are relatively prime positive integers.

5. Find (1 + 2i)482 (mod 11). Leave your answer in the form a+bi, where 0 ≤ a,b < 11.

6. 7001 is prime. How many primitive roots are there modulo 7001?

7. In RSA cryptography, Alice chooses a modulus n and a public key e; she makes n and e available for all to see. When Bob wants to send Alice a secret message m (which is an integer smaller than n and relatively prime to it), he computes me (mod n) and sends it to Alice. Then Alice can compute m from me. Explain why would it be a bad idea to use the modulus n = 10100.

8. Let a1 and a2 be units modulo m which have orders d1 and d2, re- spectively. (a) Prove that the order of a1a2 divides [d1,d2]. (b) Use a counterexample to show that the order of a1a2 is not always equal to [d1,d2].

1

9. Let π be a Gaussian prime whose norm is a prime p ≡ 1 (mod 4). (Example: π = 1 + 2i, p = 5.) Show that for all Gaussian integers α, αp ≡ α (mod π).

2