Skip to main content
Logo image

Exercises 7.7 Exercises


Before reading beyond Section 7.1, pick one of these, and really do some exploration and write about it. See Section 7.6 for another interactive applet for the first question.
  • Do exploration to try to find a criterion for which primes \(p\) there are square roots of \(-1\text{.}\) 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\text{.}\)


Figure out how many solutions \(x^2\equiv x\) (mod \(n\)) has for \(n=5,6,7\text{,}\) and then compute how many solutions there are modulo \(210\text{.}\)


Finish finding the solutions to the congruences in Examples 7.2.5–7.2.6. Do you notice anything about the answers that suggests a shortcut for finding these particular additional solutions?


Find all solutions to \(x^2+8\equiv 0\) (mod \(121\)) using the method above in Theorem 7.2.3.


Solve \(f(x) = x^3-x^2+2x+1\equiv 0\) (mod \(5^e\)) for \(e=1,2,3\text{.}\)


Use summation notation to properly prove
\begin{equation*} \left(x^k-b^k\right)=(x-b)\left(x^{k-1}+bx^{k-2}+\cdots+b^{k-1}\right)\text{.} \end{equation*}


Show that the conclusion of Wilson’s Theorem fails for \(p=10\text{,}\) and check that it holds for \(p=11\) by computing \(10!\) and then reducing.


Suppose we have the same setup as in Wilson’s Theorem, modulo a prime \(p\text{.}\) What is the value of \((p-2)!\) as a function of the modulus?


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


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\text{.}\)


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\text{.}\) (Hard 7 .)


Prove that \(x^2+y^2=p\) has no (integer) solutions for prime \(p\) with that same form \(4n+3\text{.}\)


In solving \(x^2-1\equiv 0\) (mod \(2^e\)) for \(e\gt 3\) for Fact 7.3.1, find the exact form of the two solutions other than \(\pm 1\text{.}\)
If you absolutely must know, see [E.2.13, Theorem 4.12] or [E.5.1, Theorem 8.6] for a somewhat more general statement proved using Fermat’s Little Theorem, which [E.2.13] later uses to prove Proposition 7.6.3.