Solutions to 104A  Midterm 1,  April 25, 2008
---------------------------------------------

(1)  The complete residue system has 6300 elements, and
the reduced residue system has phi(4)*phi(7)*phi(9)*phi(25) elements.
Simplifying, this product equals 2*6*6*20 = 1440.

(2)  Raise both sides to the 363 power.  (Note that 2*363 = 726,
which equals p-1 = phi(p).)  Then the right side
becomes 1 (mod 727) by Fermat's Little Theorem, so the left side
2^363 must also equal 1  mod 727.  Thus the order of 2  mod 727 is
LESS than  726.  Therefore 2 is not a primitive root mod 127.

(3A)  Use the Euclidean Algorithm, e.g.,  to see that the inverse
of 15  mod 157  equals 21.  Multiply both sides by 21 to get the
solution  x = 42  mod 157.

(3B) If this had a solution x, then 21x + 3000k = 25
for some integer k.  This is impossible, since 25 is not a multiple of 3.

(4A)  29  is not prime in S  because 29 = (3+2s)(3-2s) and neither factor
equals 1 or -1.


(4B)  2+3s is prime in S.  To prove this, assume 2+3s = (a+bs)(c+ds),
where neither factor is 1 or -1.  Multiply this equation by its complex
conjugate to get 49 = (a^2 + 5b^2)(c^2 + 5d^2).
Note that neither factor on the right can equal 1.
Moreover, neither factor can equal 7.
Thus the product on the right cannot possibly equal 49, a contradiction.

(5)  For brevity, let c denote the cube root of  n.
Assume for the the purpose of contradiction that all prime factors
of  n  exceed  c.  Then, since n has at least three prime factors,
n > c*c*c = n,  a contradiction.

(6)  Clearly p = 1 or p = 2  mod 3, otherwise p would be divisible by 3.
Squaring both sides, we see that p^2 = 1  mod 3.
Clearly p = 1 or p = 3 or p = 5 or p = 7  mod 8, otherwise p would be even.
Squaring both sides, we see that p^2 = 1 mod 8.  Since we have just shown
that (p^2 - 1) is divisible by both 3 and 8, and gcd(3,8) = 1,
it follows that (p^2 - 1) is divisible by 3*8  (i.e., by 24).