Chapter 23

If \(p\) is a prime, find \(\phi(p)\). Use this to deduce Fermat's theorem from Euler's theorem.

Prove the following for all integers \(a, b, c\) and all positive integers \(\mathrm{m}\) and \(\mathrm{n}\). If \(a c \equiv b c(\bmod n)\), and \(\operatorname{gcd}(c, n)=d\), then \(a \equiv b(\bmod n / d)\).

Solve each of the following pairs of simultaneous congruences: (a) \(x \equiv 7(\bmod 8) ; x \equiv 11(\bmod 12)\) (b) \(x \equiv 12(\bmod 18) ; x \equiv 30(\bmod 45)\) (c) \(x \equiv 8(\bmod 15) ; x \equiv 11(\bmod 14)\)

Solving Single Congruences For each of the following congruences, find \(m\) such that the congruence has a unique solution modulo \(m\). If there is no solution, write "none." (a) \(60 x \equiv 12(\bmod 24)\) (b) \(42 x \equiv 24(\bmod 30)\) (c) \(49 x \equiv 30(\bmod 25)\) (d) \(39 x \equiv 14(\bmod 52)\) (e) \(147 x=47(\bmod 98)\) (f) \(39 x \equiv 26(\bmod 52)\)

\((p-2) !=1(\bmod p)\) for any prime number \(p\).

Prove the following for all integers \(a, b, c\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod n)\), then \(\operatorname{gcd}(a, n)=\operatorname{gcd}(b, n)\).

Prove the following for all integers \(a, b, c, d\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod n)\), then \(a+c \equiv b+c(\bmod n)\).

Solve each of the following pairs of simultaneous congruences: (a) \(10 x \equiv 2(\bmod 12) ; 6 x \equiv 14(\bmod 20)\) (b) \(4 x \equiv 2(\bmod 6) ; 9 x \equiv 3(\bmod 12)\) (c) \(6 x \equiv 2(\bmod 8) ; 10 x \equiv 2(\bmod 12)\)

Solve the following linear congruences: (a) \(12 x \equiv 7(\bmod 25)\) (b) \(35 x \equiv 8(\bmod 12)\) (c) \(15 x \equiv 9(\bmod 6)\) (d) \(42 x \equiv 12(\bmod 30)\) (e) \(147 x \equiv 49(\bmod 98)\) (f) \(39 x \equiv 26(\bmod 52)\)

Find primitive roots of the following integers (if there are none, say so): \(6,10,12\), \(14,15 .\)

(p-1) !+1 \equiv 0(\bmod p)\( for any prime number \)p .$ This is known as Wilson's Theorem.

If \(\operatorname{gcd}(m, n)=\operatorname{gcd}(a, m n)=1\), then \(a^{\phi(m) \phi(n)} \equiv 1(\bmod m n)\).

Let \(p\) be a prime \(>2\). If \(p \equiv 3(\bmod 4)\), then \((p-1) / 2\) is odd. (b) Let \(p>2\) be a prime such that \(p \equiv 3\) (mod 4). Then there is no solution to the congruence \(x^{2}+1 \equiv 0(\bmod p) .\) [HiNT: Raise both sides of \(x^{2} \equiv-1(\bmod p)\) to the power \((p-1) / 2\), and use Fermat's little theorem.]

Prove the following for all integers \(a, b, c, d\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod n)\), then \(a c \equiv b c(\bmod n)\)

Suppose \(a\) is a primitive root of \(m\). If \(b\) is any integer which is relatively prime to \(m\), then \(b \equiv a^{k}(\bmod m)\) for some \(k \geq 1\).

For any composite number \(n \neq 4,(n-1) ! \equiv 0(\bmod n)\). [HINT: If \(p\) is any prime factor of \(n\), then \(p\) is a factor of \((n-1) !\) Why?] Before going on to the remaining exercises, we make the following observations: Let \(p>2\) be a prime. Then $$ (p-1) !=1 \cdot 2 \cdots \frac{p-1}{2} \cdot \frac{p+1}{2} \cdots(p-2) \cdot(p-1) $$ Consequently, $$ (p-1) !=(-1)^{(p-1 N 2}\left(1 \cdot 2 \cdots \frac{p-1}{2}\right)^{2}(\bmod p) $$ REASON \(p-1 \equiv-1(\bmod p), p-2 \equiv-2(\) mod \(p), \cdots,(p+1) / 2 \equiv-(p-1) / 2\) \((\bmod p)\) With this result, prove the following:

If \(p\) is a prime, \(\phi\left(p^{n}\right)=p^{n}-p^{n-1}=p^{n-1}(p-1)\). (HINT: For any integer \(a, a\) and \(p^{n}\) have a common divisor \(\neq \pm 1\) iff \(a\) is a multiple of \(p .\) There are exactly \(p^{n-1}\) multiples of \(p\) between 1 and \(p^{n}\).)

Solve the following quadratic congruences (if there is no solution, write "none"): (a) \(6 x^{2} \equiv 9(\bmod 15)\) (b) \(60 x^{2} \equiv 18(\bmod 24)\) (c) \(30 x^{2} \equiv 18(\bmod 24)\) (d) \(4(x+1)^{2} \equiv 14(\bmod 10)\) (f) \(3 x^{2}-6 x+6 \equiv 0(\bmod 15)\)

Suppose \(m\) has a primitive root, and let \(n\) be relatively prime to \(\phi(m) .\) (Suppose \(n>0 .\) Prove that if \(a\) is relatively prime to \(m\), then \(x^{n} \equiv a(\bmod m)\) has a solution.

Prove: if \(a \equiv b(\bmod p)\), then \(\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)\). In particular, \(\left(\frac{a+k p}{p}\right)=\left(\frac{a}{p}\right)\).

(p-1) / 2] !^{2} \equiv(-1)^{(p+1) / 2}(\bmod p)\(, for any prime \)p>2 .$ (HINT: Use Wilson's theorem.)

Prove the following for all integers \(a, b, c\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod m\) ) and \(a \equiv b(\bmod n)\) where \(\operatorname{gcd}(m, n)=1\), then \(a \equiv b(\bmod m n)\).

Prove the following for all integers \(a, b, c, d\) and all positive integers \(m\) and \(n .\) If \(a b \equiv 0(\bmod p)\), where \(p\) is a prime, then \(a \equiv 0(\bmod p)\) or \(b \equiv 0(\bmod p)\).

Solve each of the following systems of simultaneous linear congruences; if there is no solution, write "none." \((a) x \equiv 2(\bmod 3) ; x \equiv 3(\bmod 4) ; x \equiv 1(\bmod 5) ; x \equiv 4(\bmod 7)\) \((b) 6 x \equiv 4(\bmod 8) ; 10 x \equiv 4(\bmod 12) ; 3 x \equiv 8(\bmod 10)\) (c) \(5 x \equiv 3(\bmod 6) ; 4 x \equiv 2(\bmod 6) ; 6 x \equiv 6(\bmod 8)\)

Solve the following congruences: (a) \(x^{4} \equiv 4(\bmod 6)\) \(\left(\right.\) b) \(2(x-1)^{4} \equiv 0(\bmod 8)\) (c) \(x^{3}+3 x^{2}+3 x+1 \equiv 0(\bmod 8)\) \(\left(\right.\) d) \(x^{4}+2 x^{2}+1 \equiv 4(\bmod 5)\)

Let \(p>2\) be a prime. Every primitive root of \(p\) is a quadratic nonresidue, modulo p. (HINT: Suppose a primitive root \(a\) is a residue; then every power of \(a\) is a residue.)

Prove the following for all integers \(a, b, c\) and all positive integers \(m\) and \(n\). If \(a b \equiv 1(\bmod c), a c \equiv 1(\bmod b)\) and \(b c \equiv 1(\bmod a)\), then \(a b+b c+a c \equiv 1\) (mod \(a b c)\). (Assume \(a, b, c>0 .)\)

Solve the following Diophantine equations (if there is no solution, write "none"): (a) \(14 x+15 y=11\) (b) \(4 x+5 y=1\) (c) \(21 x+10 y=9\) (d) \(30 x^{2}+24 y=18\)

A prime \(p\) of the form \(p=2^{m}+1\) is called a Fermat prime. Let \(p\) be a Fermat prime. Every quadratic nonresidue mod \(p\) is a primitive root of \(p\). (HINT: How many primitive roots are there? How many residues? Compare.)

If \(p=3(\bmod 4)\), then \(\frac{p+1}{2}\) is even. (Why?) Conclude that $$ \left(\frac{p-1}{2}\right) !^{2}=1(\bmod p) $$.

Prove the following for all integers \(a, b, c\) and all positive integers \(m\) and \(n\). If \(a^{2} \equiv 1(\bmod 2)\), then \(a^{2} \equiv 1(\bmod 4)\)

Prove the following for all integers \(a, b, c, d\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod m)\), then \(a+k m \equiv b(\bmod m)\), for any integer \(k .\) In particular, $$ a+k m \equiv a(\bmod m) $$

Prove the following for all integers \(a, b, c\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod n)\), then \(a^{2}+b^{2} \equiv 2 a b\left(\bmod n^{2}\right)\); and conversely.

Prove the following for all integers \(a, b, c, d\) and all positive integers \(m\) and \(n\). If \(a c \equiv b c(\bmod n)\) and \(\operatorname{gcd}(c, n)=1\), then \(a \equiv b(\bmod n)\)

Which of the following congruences is solvable? (a) \(\mathrm{x}^{2} \equiv 30(\bmod 101)\) (b) \(x^{2} \equiv 6(\bmod 103)\) (c) \(2 x^{2} \equiv 70(\bmod 106)\) [NoTE: \(x^{2} \equiv a(\bmod p)\) is solvable iff \(a\) is a quadratic residue modulo \(p\) iff $$ \left.\left(\frac{a}{p}\right)=1 .\right] $$

Find the following integers \(x\) : (a) \(x \equiv 8^{38}(\bmod 210)\) (b) \(x \equiv 7^{57}(\bmod 133)\) (a) \(x \equiv 5^{73}(\bmod 66)\)

Prove the following for all integers \(a, b, c\) and all positive integers \(m\) and \(n .\) If \(a \equiv 1(\bmod m)\), then \(a\) and \(m\) are relatively prime; and conversely.

Prove the following for all integers \(a, b, c, d\) and all positive integers \(m\) and \(n\). If \(a \equiv b(\bmod n)\), then \(a \equiv b(\bmod m)\) for any \(m\) which is a factor of \(n\)