Test 2

• Give complete, concise answers to the following prompts. Be sure to include all hypotheses.
  • State either Gauss' Lemma or Eisenstein's Lemma; be sure to indicate which lemma you have chosen to state.
  • Mobius inversion says that…
• Answer the following questions either “true” or “false.” In all the following problems, a,b and m are arbitrary integers, and p is a prime.
  • Suppose that $(a,m) = (b,m) = 1$. If neither $x^2 \equiv a \mod{m}$ nor $x^2 \equiv b \mod{m}$ has solutions, then $x^2 \equiv ab \mod{m}$ \emph{does} have a solutions.
  • The number of primitive roots mod $m$ is $\phi(\phi(m))$.
  • No integer with $(a,100)=1$ has $\mbox{ord}_{100}(a) = 6$.
  • If $(a,p) = 1$, then $a^i \equiv a^j \mod{p}$ if and only if $i \equiv j \mod{\phi(p)}$.
  • The number $2^{p-1}(2^p-1)$ is not necessarily perfect.
• Compute $(\mu*\sigma)(18)$.
• Use Euler's Criterion to determine how many solutions $x^2 \equiv 6 \mod{11}$ has.
• How many solutions does $x^{10} \equiv 5 \mod{31}$ have?
• Give congruence conditions which describe exactly those prime numbers for which 10 is a square.
• Explain why 10 is not a primitive root modulo the prime number 41. (Hint: You don't need to compute any powers of 10.)
• 7 is a primitive root of the prime 101, and $7^{67} \equiv 8 \mod{101}$.
  • Solve for x in the equation $7^x \equiv 2 \mod{101}.$
  • Is 28 a primitive root mod 101? (Hint: You don't need to compute any powers of 28.)