1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 20, 2013 at 18:37

2 Answers 2

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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 :-) $\endgroup$ Aug 20, 2013 at 18:43
  • $\begingroup$ @JyrkiLahtonen, Does the other answer use CRT? To me, the methods are different enough to be read independently. $\endgroup$ Aug 20, 2013 at 18:45
  • $\begingroup$ This metathread does suggest that people here usually prefer to combine two short answers to a single post. Your call, of course. $\endgroup$ Aug 20, 2013 at 19:04
  • $\begingroup$ @JyrkiLahtonen, I have deleted the other answer as I've added a small answer as method $1$ in this answer. $\endgroup$ Aug 21, 2013 at 4:56
  • $\begingroup$ @labbhattacharjee For method 2, how are you using CRT. How do you obtain 55 exactly? $\endgroup$ Feb 18, 2021 at 4:19
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .