Test 2 from Last Semester

- 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.)

- Solve for