Thursday, 6 October 2016

elementary number theory - 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??


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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...