Midterm 3 Study Guide

1. Be able to do general versions of the following:
   1. Determine the last digit in the decimal expansion of \(23^{123}\).
   2. Show that \({17}^{24} - {36}^{12}\) is divisible by \(11\).
   3. Find all solutions to the equation \(5x=10\mod 35\) and the equation \(5x=6\mod 21\).
   4. Find the order of various elements modulo a prime.
   5. Determine if a number \(a\) is a quadratic residue modulo a prime \(p\).
   6. Compute \(g\) and \(T(a,p)\).
2. State in mathematical terms and either prove or provide a counterexample:
   1. Every natural number is congruent, modulo \(n\), to exactly one number from \(\{0,1,2,\ldots, n-1\}\)
   2. Any set of \(n\) integers, any two of which are incogruent modulo \(n\), forms a complete residue system modulo \(n\).
   3. If modulo \(n\) a number \(a\) has order \(3\) and a number \(b\) has order \(5\), then their product \(ab\) must have order dividing \(15\).
   4. If modulo \(n\) a number \(a\) has order \(3\) and a number \(b\) has order \(5\), then their product \(ab\) must have order \(15\).
   5. For every natural numbers \(a\) and \(n\) there is a positive integer \(k\) such that \(a^k=1\mod n\).
   6. For every natural numbers \(a\) and \(n\) there are distinct positive integers \(k,j\) such that \(a^k=a^j\mod n\).
   7. If two numbers are inverses modulo \(n\), then they must have the same order.
3. State and prove:
   1. The various parts of theorem 3.24 about the solution to the equation \(ax=b\mod n\).
   2. Theorems 3.27 and 3.28 about simultaneous solution to two congruence equations (chinese remainder theorem).
   3. Fermat’s little theorem (4.14)
4. State/Define:
   1. The \(\phi(n)\) function.
   2. Euler’s theorem (4.32).
   3. What it means for a number to be a quadratic residue modulo another number
   4. The Legendre symbol.
   5. Euler’s criterion (7.9).
   6. Gauss’ lemma (7.14), and the definition of \(g\).
   7. The three laws for computing quadratic residues