I have to find the remainder of $10^{115}$ divided by 7.
I was following the way my book did it in an example but then I got confused. So far I have,
$\overline{10}^{115}$=$\overline{10}^{7*73+4}$=($\overline{10}^{7})^{73}$*$\overline{10}^4$
and that's where I'm stuck.
Also, I don't fully understand what it means to have a bar over a number.
$\endgroup$ 14 Answers
$\begingroup$Note that $10 \equiv 3 \mod 7$ so $10^{115} \equiv 3^{115} \mod 7$, and that $3^3=27 \equiv -1\mod 7$.
Then $3^{115} = (3^3)^{38}\times 3 \equiv (-1)^{38}\times 3\equiv 3 \mod 7$.
$\endgroup$ 4 $\begingroup$The remainder is $3$.
We have $10^6 \equiv 1 \pmod 7$, Therefore, modulo $7$, we have $10^{115} \equiv (10^6)^{19}\cdot10 \equiv 1^{19}\cdot10 \equiv 10 \equiv 3$
In general , if $p$ is prime and $p\not| n$ , then $n^{p-1} \equiv 1 \pmod p$.(Fermat's Little Theorem.)
$\endgroup$ $\begingroup$$10^{115} \equiv 3^{115}$ (mod $7$)
$3^{115}=3^{114+1}=3^{114}*3 = (3^3)^{38}*3=27^{38}*3$
$27^{38}*3 \equiv (-1)^{38} *3 \equiv 3$ (mod $7$)
The remainder is $3$
$\endgroup$ 0 $\begingroup$$10^{115}รท7$. Here $7$ is a prime and its Euler number is $6$. Moreover $10$ and $7$ are co-primes. So divide $10$ by $7$ and $115$ by $6$. Then it will be $3^1$ which is equal to $3$. The remainder of $10^{115}=3$.
$\endgroup$ 1
