# Simplifying Large Bases with large Exponents

I'm told to find:

$105 308^{7125} \pmod {11}$

I'm not exactly sure how to go about calculating this. I know that I could split the exponent into multiples of it, for instance.

$7125 = 7 * 10 * 10 * 10 * \cdots$ whatever else

As such: $105308^{7(10)(etc..)}$

But even then the base number is too big to be multiplied to get an actual answer on a calculator, any ideas?

• Hint: Note that $105308\equiv 5\pmod{11}$ and since $11$ is a prime, you can reduce the exponent using Fermat's Little Theorem. We'll get, $$105308^{7125}\equiv 5^5\equiv 25^2\times 5\equiv 3^2\times 5\equiv 45\equiv 1\pmod{11}$$ – learner Apr 4 '16 at 17:27

First, notice that $105308 \equiv 5 \pmod {11}$.

So, $$105308^{7125} \equiv 5^{7125} \pmod {11}$$ By Fermat's Little Theorem, $5^{10} \equiv 1 \pmod {11}$.

We have that $$5^{7125} \equiv 5^{5} \equiv 125 \times 25 \equiv 4 \times 3 \equiv 1 \pmod {11}$$

• How would one know that 105308 is congruent to 5(mod 11) – TTEd Apr 4 '16 at 17:26
• @TTEd $105308=105 \times 10^3+105+203=105 \times (10^3+1) +203$. But it is easy to see $203=18 \times 11+5$. And $10^3+1=(10+1)(10^2-10+1) \equiv 0 \pmod {11}$. Thus we have $105308 \equiv 5 \pmod {11}$. – S.C.B. Apr 4 '16 at 17:28
• @TTEd Do you understand? – S.C.B. Apr 4 '16 at 17:34
• So the final answer is 5^5 mod 11 which = 1? i'm just not sure how to write out/ understand the final answer – TTEd Apr 4 '16 at 17:34
• Yes, the final answer is $5^5 \equiv 1 \pmod {11}$. – S.C.B. Apr 4 '16 at 17:34