How to solve the congruence $y^{31}\equiv 3 \mod{100}$ $\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.
 A: 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$.
A: $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.
A: 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).   
A: 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}$.
