1

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$

The answer is 55.

Any ideas how to proceed?

MathWA wenti
  • 13
H.E
  • 2,056
  • 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. – Jyrki Lahtonen Aug 20 '13 at 18:37

2 Answers2

3

$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}$

lab bhattacharjee
  • 274,582
  • 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 :-) – Jyrki Lahtonen Aug 20 '13 at 18:43
  • @JyrkiLahtonen, Does the other answer use CRT? To me, the methods are different enough to be read independently. – lab bhattacharjee Aug 20 '13 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. – Jyrki Lahtonen Aug 20 '13 at 19:04
  • @JyrkiLahtonen, I have deleted the other answer as I've added a small answer as method $1$ in this answer. – lab bhattacharjee Aug 21 '13 at 04:56
  • @labbhattacharjee For method 2, how are you using CRT. How do you obtain 55 exactly? – Ruochan Liu Feb 18 '21 at 04:19
  • @Larry, If $x\equiv3\pmod{13}, x\equiv0\pmod{11},$ $$x\equiv3b_1\cdot\dfrac{143}{13}+0\cdots\pmod{143}$$ where $$b_1\cdot\dfrac{143}{13}\equiv1\pmod{13}\implies b_1\equiv6\pmod{13}$$ – lab bhattacharjee Feb 18 '21 at 05:19
0

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}$

CopyPasteIt
  • 11,366