How to solve the congruence $y^{31}\equiv 3 \mod{100}$

Question

$\phi (100) = 40$

Hence:

$y^{31}\equiv y^{-9} \equiv 3\mod{100}$

$y^{9}\equiv 67 \mod{100}$

However I do not know where to go from here.

Answer 1

$y^9 = (y^3)^3$ so you need something that is a perfect cube. we then look at the numbers 1 - 9 and cube them. And only $3^3$ give 7 as a last digit.

$(10n+3)^3 = 1000+900n+270n+27 \equiv 70n + 27(\mod 100)\\ 70n \equiv 40(\mod 100)\\ n = 2\\ y^3 \equiv 23 (\mod100)$

and now we go trough the same exercise again.

$y=(10n+7) \equiv 70n + 43(\mod100)\\ y = 47$

In hindsight $k^9 \equiv k (\mod10)$ may have saved some steps.

Answer 2

Solve the easier equations $$x^{31}\equiv 3\ (\ mod\ 4\ )$$ and $$x^{31}\equiv 3\ (\ mod\ 25\ )$$

(Solutions $3$ and $22$) and use the chinese remainder theorem to solve the system

$x\equiv 3\ (\ mod \ 4\ )$

$x\equiv 22\ (\ mod\ 25\ )$

The final solution is $x\equiv 47\ (\ mod\ 100\ )$.

To find the solution modulo $25$ more quickly, note that $x^{31}\equiv 3\ (\ mod\ 5\ )$ gives $x\equiv 2\ (\ mod\ 5\ )$ , so you only have to check $2,7,12,17$ and $22$.

Answer 3

Here is a very simple method. The congruence:

(1) $y^{31}\equiv 3 \mod{100}$

implies that:

(2) $(y^{31})^{31} = y^{31.31} = y^{961} \equiv 3^{31} \equiv 47 \mod{100}$

But $961$ gives remainder $1$ when divided by $\phi(100)=40$.

So:

(3) $y^{961} \equiv y^{960} . y \equiv 1 . y \equiv y \mod{100}$

(since $40$ divides $960$)

Now from (2) and (3) we get:

(4) $y^{961} \equiv y \equiv 47 \mod{100}$

which is the solution you were looking for.

How did I know to raise $y^{31}$ to the power of $31$ as I did in (2)?
Well, I first looked for a natural number $k$ such that: $31.k = 40.t+1$ for some natural $t$. The smallest such $k$ happens to be $k=31$ (but it's just a coincidence that this $k$ is also $31$ just like the power in the original congruence).

Answer 4

This is a kind of tedious solution:

$$x^{31}\equiv 3\pmod{100}\iff \begin{cases}x^{31}\equiv 3\pmod{25}\\ x^{31}\equiv 3\pmod{4}\end{cases}$$

$$\iff \begin{cases}x^{31}\equiv 3\pmod{25}\\ x\equiv 3\pmod{4}\end{cases}$$

Clearly $\gcd(x,25)=1$, so by Euler's theorem:

$$\iff \begin{cases}x^{11}\equiv 3\pmod{25}\\ x\equiv 3\pmod{4}\end{cases}$$

$2$ is a primitive root mod $5^2$, because $\gcd(2,25)=1$ and $\phi(25)=20=2^2\cdot 5$ and

$2^{\frac{20}{2}}\equiv 2^{10}\equiv 1024\equiv -1\not\equiv 1\pmod{25}$

and $2^{\frac{20}{5}}\equiv 2^{4}\equiv 16\not\equiv 1\pmod{25}$.

Let $x\equiv 2^k\pmod{25}$ for some $k\in\mathbb Z^+$.

$$2^{11k}\equiv 3\equiv 2^7\pmod{25}\iff 11k\equiv 7\equiv -33\pmod{20}$$

$$\stackrel{:11}\iff k\equiv -3\equiv 17\pmod{20}$$

Therefore $x\equiv 2^{17}\equiv 2^{10}2^{7}\equiv (1024)(128)\equiv (-1)(3)\equiv -3\equiv 22\pmod{25}$,

so by Chinese Remainder Theorem $x\equiv 47\pmod{100}$.