Section9.6Exercises

  1. Prove Fermat's Little Theorem as a corollary of Euler's Theorem.
  2. Prove that if \(p\) is prime, then \(a^p\equiv a\) mod (\(p\)) for every integer \(a\).
  3. Formally prove that \(\phi(p)=p-1\) for prime \(p\), by deciding which \([a]\in \{[0],[1],[2],\ldots,[p-2],[p-1]\}\) have \(gcd(a,p)=1\).
  4. Verify Euler's Theorem by hand for \(n=15\) (note that \(\phi(15)=8\), and remember that \(a^8=((a^2)^2)^2\) so we can use modulo reduction at each squaring).
  5. Get the inverse of 29 modulo 31, 33, and 34 using Euler's Theorem.
  6. Evaluate without a calculator \(11^{49}\) mod (15) and \(139^{112}\) mod (27).
  7. Solve the congruence \(33x\equiv 29\) mod (127) and mod (128).
  8. Solve as many of the simple linear congruences we already did in earlier homework using Euler's Theorem as you need to in order to understand how it works. Follow the models above closely if necessary.
  9. Solve as many of the systems of congruences we already did in earlier homework using the CRT and Euler's Theorem as you need in order to understand how it works. Follow the models above closely if necessary.
  10. Create a general formula for \(\phi(N)\) where \(N=\prod_{i=1}^k p_i^{e_i}\) and prove it by induction.
  11. Compute the \(\phi\) function evaluated at 1492, 1776, and 2001.
  12. Let \(f(n)=\phi(n)/n\).
    • Show that \(f(p^k)=f(p)\) if \(p\) is prime.
    • Find the smallest \(n\) such that \(f(n)<1/5\).
    • Find all \(n\) such that \(f(n)=1/2\).
  13. Prove whether there are infinitely many values of \(\phi\) that end in zero.
  14. Conjecture whether there are any relations between \(m\) and \(n\) that might lead \(\phi(m)\) to divide \(\phi(n)\).