5
$\begingroup$

I have to find the remainder of the division of $7^{1203}$ by $143$. I thought that I could use the Euler Theorem: Let $a \in \mathbb{Z}$ and $n \in \mathbb{N}$.We also know that $(a,n)=1$.Then $a^{\varphi(n)} \equiv 1 \mod n$ So,we set $a=7$ and $n=143$ and see that $(a,n)=1$.So,from the above theorem,we get that $7^{120} \equiv 1 \mod 143$. $$7^{1203} \mod 143=7^{10 \cdot 120+3} \mod 143=(7^{120})^{10} \cdot 7^{3} \mod 143=7^{3} \mod 143=57$$ So the remainder of the division of $7^{1203}$ by $143$ is $57$.Is that what I have done right or have I done something wrong??

$\endgroup$
  • 5
    $\begingroup$ $143=11 \times 13$, find the remainder mod $11$ and $13$ first .. then I think you will get your answer :) $\endgroup$ – r9m Mar 8 '14 at 1:03
  • 1
    $\begingroup$ Could you explain it further to me?Also,is the way that I did it wrong?? $\endgroup$ – evinda Mar 8 '14 at 1:05
  • 1
    $\begingroup$ What you have done is correct ... I was just pointing out another alternative :) $\endgroup$ – r9m Mar 8 '14 at 1:09
  • 1
    $\begingroup$ evinda, you have applied Euler's theorem correctly and obtained the correct answer 57. There is no need to work with the factors of $n$ directly (indirectly they have been used to find $\varphi(n)$). $\endgroup$ – P Vanchinathan Mar 8 '14 at 1:11
  • 1
    $\begingroup$ The first sentence of the last paragraph is incomplete - there is no verb or result. $\endgroup$ – Thomas Andrews Mar 8 '14 at 1:30
4
$\begingroup$

Everything was done correctly. The following is an "improvement" that is not needed in this case.

Imagine working separately modulo $11$ and $13$. We have $7^{10}\equiv 1\pmod{11}$ and $7^{12}\equiv 1\pmod{13}$. Note that $60$ is the lcm of $10$ and $12$. It follows that $7^{60}\equiv 1$ modulo $11$ and $13$, and hence modulo $143$.

If your exponent has been $1263$ instead of $1203$, this observation would have saved a significant amount of time.

Note that the more distinct prime divisors the modulus $n$ has, the more we tend to save by using this type of trick.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.