Determine which of the following congruences are solvable:
(a) $x^3 \equiv 89 \pmod {197}$
(b) $x^2 \equiv 89 \pmod {197}$
(c) $x^2 \equiv 197 \pmod {89}$
(d) $x^2 \equiv 218 \pmod {111}$
We will be using Proposition (6.17). Let $n$ have a primitive root and $a$ and $n$ be relatively prime. The congruence $x^m \equiv a \pmod n$ has a solution if and only if $a^{\phi(n)/g} \equiv 1 \pmod n$ where $g = \gcd (m, \phi (n))$. Additionally, there are exactly $g$ incongruent solutions.
(a) We have $\gcd(89,197)=1$ so we can use Proposition (6.17), and also Euler's Theorem.
Euler's Theorem tells us $89^{\phi(197)} \equiv 1 \pmod {197}$, and noting $\gcd(3, 196)=1$,
$$ 89^{\frac{\phi(197)}{\gcd(3,196)}}\equiv 89^{\frac{\phi(197)}{1}} \equiv 89^{\phi(197)} \equiv 1 \pmod {197}$$
By Proposition (6.17), the cubic congruence has a solution, and in fact has 1 incongruent solution modulo 197.
(b) We have $\gcd(89,197)=1$ so we can use Proposition (6.17), and also Euler's Theorem.
Euler's Theorem tells us $89^{\phi(197)} \equiv 1 \pmod {197}$, and noting $\gcd(2, 196)=2$,
$$ 89^{\frac{\phi(197)}{\gcd(2,196)}}\equiv 89^{\frac{\phi(197)}{2}} \equiv 89^{98} \pmod {197}$$
Noting that:
- $89^2 \equiv 7921 \equiv 41 \pmod {197}$
- $41^7 \equiv 194754273881 \equiv 6 \pmod {197}$
$$ 89^{98} \equiv (89^2)^49 \equiv (41)^49 \equiv (41^7)^7 \equiv 6^7 \equiv 46656 \equiv -1 \pmod {197}$$
And so $89^{98} \not \equiv 1 \pmod{197}$, which means the given congruence has no solutions.
(c) We have $\gcd(89,197)=1$ so we can use Proposition (6.17), and also Euler's Theorem.
Euler's Theorem tells us $197^{\phi(89)} \equiv 1 \pmod {89}$, and noting $\gcd(2,88)=2$,
$$ 197^{\frac{\phi(89)}{\gcd(2,88)}} \equiv 197^{\frac{88}{2}} \equiv 197^{44} \pmod {89} $$
Noting that:
- $ 197^2 \equiv 38809 \equiv 5 \pmod {89} $
- $ 5^{11} \equiv 48828125 \equiv 55 \pmod {89} $
$$ 197^{44} \equiv (197^2)^{22} \equiv 5^{22} \equiv (5^{11})^2 \equiv 55^2 \equiv -1 \pmod {89} $$
And so $197^{44} \not \equiv 1 \pmod {89}$, which means the given congruence has no solutions.
(d) We can simplify the congruence by noting that $218 \equiv -4 \pmod {111}$, and so
$$ x^2 \equiv 218 \equiv -4 \pmod {111} $$
We have $\gcd(111, 218)=1$ so we can use Proposition (6.17), and also Euler's Theorem.
Euler's Theorem tells us that $(-4)^{\phi(111)} \equiv 1 \pmod {111}$, and noting $\gcd(2,72)=2$,
$$ (-4)^{\frac{72}{2}} \equiv (-4)^{36} \pmod {111} $$
Noting that $ (-4)^9 \equiv -262144 \equiv 38 \pmod {111} $,
$$ (-4)^{36} \equiv ((-4)^9)^4 \equiv 38^4 \equiv 2085136 \equiv 1 \pmod {111} $$
This means $(-4)^{72} \equiv 218^{72} \equiv 1$ and so the congruence has 2 solutions.
Note: Proposition (6.17) requires $n$ to have a primitive root. Primes have primitive roots but this isn't covered until later in the book. The author's solutions don't show that $n$ has a primitive root.