# remainder of the division of $7^{1203}$ by $143$

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??

• $143=11 \times 13$, find the remainder mod $11$ and $13$ first .. then I think you will get your answer :) – r9m Mar 8 '14 at 1:03
• Could you explain it further to me?Also,is the way that I did it wrong?? – evinda Mar 8 '14 at 1:05
• What you have done is correct ... I was just pointing out another alternative :) – r9m Mar 8 '14 at 1:09
• 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)$). – P Vanchinathan Mar 8 '14 at 1:11
• The first sentence of the last paragraph is incomplete - there is no verb or result. – Thomas Andrews Mar 8 '14 at 1:30

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.