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??
Answer
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.
No comments:
Post a Comment