# Find the remainder of a number with a large exponent [duplicate]

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.

• Bar basically means the remainder that you get when divided by the divisor. In this case, the divisor is $7$. Sep 27, 2015 at 22:51

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$.

• Why is $10 \equiv 3 \mod 7$? Sep 28, 2015 at 21:48
• Because $a \equiv b \mod c$ means that $a-b$ is divisible by $c$. And $10-3=7$ is divisible by $7$. Sep 29, 2015 at 19:50
• I wonder why the $3^3 \equiv -1 (mod 7)$ and not $6 (mod 7)$ Oct 16, 2019 at 10:38
• @DimitrisDimitriadis, $-1$ and $6$ are equivalent mod $7$. We choose $-1$ here as $(-1)^{38}$ is easier to calculate then $6^{38}$. Oct 16, 2019 at 11:19

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

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.)

$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$.

• Welcome on the MathSE! Note, the site supports Latex, type $10^{115}$ and you get $10^{115}$. Aug 6, 2018 at 5:27