NTIC Exercises

Exercises 7.7 Exercises

1.

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

2.

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

3.

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?

4.

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

5.

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

6.

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*}

7.

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.

8.

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?

9.

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

10.

Prove Fermat's Little Theorem using the steps in Theorem 7.5.3 (a standard one in many texts), or any way you would like.

11.

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

12.

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

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.

13.

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

14.

Show that \(y^2=x^3+999\) has no (integer) solutions (See [E.2.13, Chapter 10 Review Exercise 5], Exercise 15.7.7). You may assume Fact 13.3.2.

15.

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