# find remainder using modulo arithmetic

what is the remainder when $55^{142}$ is divided by 143?

Initially I wanted to use Fermat's little theorem but 143 is not prime. Euler's theorem does not seem to work here either as $(55,143)\neq 1$

Any ideas how to proceed?

• Have you heard of Chinese remainder theorem? If you can figure out the remained modulo $11$ (easy) and modulo $13$ (here's where you can use Little Fermat), then you "know" the remainder modulo $11\cdot13$, because $\gcd(11,13)=1$. That "knowing" part can be done by brute force, but there is also an algorithm for doing it, if the numbers are too big for brute force. Aug 20, 2013 at 18:37

$55\equiv3\pmod {13}\implies 55^3\equiv 3^3=27\equiv1\pmod{13}$

Method $1:$ As the highest power of $11$ in $55$ is $1,$ let us find $55^{141}\pmod{13}$

$55^{141}=(55^3)^{47}\equiv1^{47}\equiv1\pmod{13}=13c+1$ where $c$ is an integer

$\implies 55^{142}=55\cdot55^{141}=55(1+13c)\equiv55\pmod{13\cdot55}\equiv55\pmod{13\cdot11}$

Method $2:$ We have $55^{142}=55\cdot(55^3)^{47}\equiv3\cdot1^{47}\equiv3\pmod{13}$

and $55^{142}\equiv0\pmod {11}$

Now, using CRT, we can find $55^{142}\equiv 55\pmod {13\cdot11}$

• Why another answer? I think that editing your first one would be more appropriate, as the approach is more or less the same. At least that's what I think is normally done. Don't know for sure obviously :-) Aug 20, 2013 at 18:43
• @JyrkiLahtonen, Does the other answer use CRT? To me, the methods are different enough to be read independently. Aug 20, 2013 at 18:45
• This metathread does suggest that people here usually prefer to combine two short answers to a single post. Your call, of course. Aug 20, 2013 at 19:04
• @JyrkiLahtonen, I have deleted the other answer as I've added a small answer as method $1$ in this answer. Aug 21, 2013 at 4:56
• @labbhattacharjee For method 2, how are you using CRT. How do you obtain 55 exactly? Feb 18, 2021 at 4:19

The OP should verify the following fact:

If $$n \equiv 0 \text{ mod 11}$$ and $$n \equiv r \text{ mod 13}$$ then $$n^2 \equiv n \cdot r \text{ mod 143}$$ and $$n^2 \equiv r^2 \text{ mod 13}$$.

We plan on employing an algorithm and it makes sense to make a couple of preliminary calculations:

$$\; 55^2 \equiv 55 \cdot 3 \equiv 22 \text{ mod 143}$$
$$\; 22^2 \equiv 22 \cdot 9 \equiv 55 \text{ mod 143}$$

Now that is a stroke of luck!

$$55^{142} \equiv 22^{71} \equiv 22 \cdot 22^{70} \equiv 22 \cdot 55^{35} \equiv 22 \cdot 55 \cdot 55^{34} \equiv 22 \cdot 55 \cdot 22^{17} \equiv$$
$$\quad 22 \cdot 55 \cdot 22 \cdot 22^{16} \equiv 22 \cdot 55 \cdot 22 \cdot 55^{8} \equiv$$
$$\quad 22 \cdot 55 \cdot 22 \cdot 22^{4} \equiv 22 \cdot 55 \cdot 22 \cdot 55^{2} \equiv$$
$$\quad 22 \cdot 55 \cdot 22 \cdot 22 \equiv^\text{algorithm complete / now applying discretionary techniques}$$
$$\quad 55 \text{ mod 143}$$