Section7.6Exercises

  1. Write down two linear congruences which do not have solutions modulo \(15\), but do have solutions modulo \(16\). (You do not have to solve them.)
  2. Write out the multiplication table for \(\mathbb{Z}_{11}\) completely, by hand.
  3. Show that Wilson's Theorem fails for \(p=10\) and check that it works for \(p=11\) by hand.
  4. Pick one, and really do some exploration and write about it.
    • Do exploration to try to find a criterion for which primes \(p\) there are square roots of \(-1\). You will have to examine primes less than 10 by hand to make sure you are right!
    • Do exploration to find out anything you can about how many square roots of \(1\) there are for a given \(n\).
  5. Find some conjecture/pattern to state about values of \(a^n\) mod (\(p\)), for \(p\) prime and \(0\leq n < p\) you discovered using the Sagelet which we did not talk about in class. This could be anything profounder than \[a^0\equiv 1\text{ mod }(p)\text{ or }1^n\equiv 1\text{ mod }(p)\] for all prime \(p\) and for all \(n\), but should at least be some pattern you tested for a number of values.
  6. Use Fermat's Little Theorem to help you calculate each of the following very quickly:
    • \(512^{372}\) mod (13)
    • \(3444^{3233}\) mod (17)
    • \(123^{456}\) mod (23)
  7. Prove Fermat's Little Theorem using the steps above, or any way you would like.
  8. Prove that Wilson's Theorem always fails if the modulus is not prime. Hint: use the fact that the modulus \(n\) then has factors \(m\) other than \(1\) or \(n\).
  9. Keep on trying to figure out the pattern (if there is one) for square roots of negative one modulo a prime. We now know there can be at most two!
  10. Find solutions to \(3x-4\equiv 0\) mod (\(343\)) and \(x^2+8\equiv 0\) mod (\(121\)) using the method above (Hensel's Lemma).
  11. Solve \(f(x) = x^3-x-1\equiv 0\) mod (\(5^e\)) for \(e=1,2,3\). (Jones and Jones)
  12. Prove that it is impossible for \(p\mid x^2+1\) if a prime \(p\) has \(p\equiv 3\) mod (\(4\)) – that is, if \(p\) is of the form \(4n+3\). (Hint: look at everything modulo 4.)
  13. Prove that \(x^2+y^2=p\) has no (integer) solutions for prime \(p\) with that same form.
  14. Show that \(y^2=x^3+999\) has no (integer) solutions.