2.7. Non-linear congruences

The exercise presented here connects the most important results seen so far. It is a summary.

Exercise.

Find all integers $x$ such that

$$717x^2\equiv 23^{95}(\mathrm{mod}970).$$

Hint.

$97$ is a prime.

Warning:

As always, if you read the solution before trying to solve the exercise yourself, you are likely wasting your time.

Solution.

Step 1: Linearize

I use the Euclidean algorithm to find the inverse of $717$ mod $970$. First, I iterate the Q-R formula:

Step	Equation
1	$970=717\times 1+253$
2	$717=253\times 2+211$
3	$253=211\times 1+42$
4	$211=42\times 5+\boxed{1}$
5	$42=1\times 42+0$ (optional)

Second, I plug the remainders back in reverse order:

Step	Equation
4	$1=211+(–5)42$
3	$=211+(–5)[253+(–1)211]=6\times 211+(–5)253$
2	$=6[717+(–2)253]+(–5)253=(6)717+(–17)253$
1	$=(6)717+(–17)[970+(–1)253]=(23)717+(–17)970$

Reducing mod $970$, I have $1\equiv 23\cdot 717$, hence the inverse is $23$. Substituting $y=x^2$, the congruence to solve becomes

$$y\equiv 23^{96}(\mathrm{mod}970).$$

Step 2: Divide

Factoring $970=2\cdot 5\cdot 97$. By the Chinese remainder theorem, solving the above is equivalent to solving the system

$$y\equiv 23^{96}(\mathrm{mod}2)y\equiv 23^{96}(\mathrm{mod}5)y\equiv 23^{96}(\mathrm{mod}97)$$

The middle congruence easily reduces to $y{\equiv }_{2}23^{96}{\equiv }_2{1}^{96}=1$. And the only integer whose square is 1 mod 2 is 1, thus $x{\equiv }_{2}1$.

The right congruence simplifies to $y{\equiv }_{5}23^{96}{\equiv }_5(-2{)}^{96}=2^{96}$.

Hint.

The latter can easily be solved by cases since $5$ is small. However, if the prime factor were large, such as the case of $97$, guessing and checking is unfeasible.

By Fermat’s little theorem, $2^4{\equiv }_{5}1$, and since $4\mid 96$,

$$2^{96}=2^{4\cdot (96/4)}=(2^4{)}^{96/4}{\equiv }_5{1}^{96/4}=1.$$

In the lectures I prove that the only square roots of 1 mod a prime are $\pm 1$. Then, $x{\equiv }_{5}1,4$.

Now, again by Fermat’s little theorem, $23^{96}\equiv 1(\mathrm{mod}97)$. Therefore, the system reduces to

$$x\equiv 1(\mathrm{mod}2)x\equiv 1,4(\mathrm{mod}5)x\equiv 1,96(\mathrm{mod}97)$$

Hint.

What do the commas in the last two congruences mean precisely? I am no longer trying to solve one system, but four. Here is the precise logical statement:

$$\left(x{\equiv }_{2}1\wedge x{\equiv }_{5}1\wedge x{\equiv }_{96}1\right)$$ $$\vee$$ $$\left(x{\equiv }_{2}1\wedge x{\equiv }_{5}1\wedge x{\equiv }_{96}95\right)$$ $$\vee$$ $$\left(x{\equiv }_{2}1\wedge x{\equiv }_{5}4\wedge x{\equiv }_{97}1\right)$$ $$\vee$$ $$\left(x{\equiv }_{2}1\wedge x{\equiv }_{5}4\wedge x{\equiv }_{97}96\right)$$

Step 3: Conquer

Clearly $x=1$ solves one of the systems, so by the Chinese remainder theorem, $x=1$ is the only solution mod $970$ to the first system. $x=-1$ is a solution to another one of the systems.

Since the first congruence only says $x$ is odd, I omit it to reduce clutter. The remaining two systems are

$$x\equiv 1(\mathrm{mod}5)x\equiv 96(\mathrm{mod}97)$$ $$x\equiv 4(\mathrm{mod}5)x\equiv 1(\mathrm{mod}97)$$

The top one is solved by taking the second congruence as $x=97k-1$ for some $k$, and plugging it into the second one: $1\equiv x=97k-1\equiv 2k-1(\mathrm{mod}5)$, from where $k=5\ell +1$ for some $\ell$. Hence, $x=97(5\ell +1)-1$; but I want $x$ to be odd, so I can pick $\ell =1$ and get $x=581$.

Reflect.

Any value of $\ell$ that makes $97(5\ell +1)-1$ odd produces a valid solution $x$. You have understood how to solve systems of congruences when you can explain why. Also, why did I plug the second congruence into the first one and not the other way around?

The bottom one is solved exactly the same way to get $x=389$.

Step 4: Multiply

By the Chinese remainder theorem, the final answer is

$$x\equiv 1,389,581,969(\mathrm{mod}970),$$

so the set of all integer solutions is

$$\boxed{\{970n+m:n\in \mathbb{Z},m\in \{1,389,581,969\}\}}.$$

---

Exercise.

What is the shortest computer program you can write that solves this problem? What about the fastest?

Solution.

# This is Python3.
*[x for x in range(970) if (717*x**2)%970 == 23**95%970]
>>>1, 389, 581, 969

Exercise.

Try solving the same initial congruence but with $x^3$ instead of $x^2$. Do you expect to find more solutions or fewer mod $970$?