0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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}$$ $\endgroup$ – learner Apr 4 '16 at 17:27
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How would one know that 105308 is congruent to 5(mod 11) $\endgroup$ – TTEd Apr 4 '16 at 17:26
  • $\begingroup$ @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}$. $\endgroup$ – S.C.B. Apr 4 '16 at 17:28
  • $\begingroup$ @TTEd Do you understand? $\endgroup$ – S.C.B. Apr 4 '16 at 17:34
  • $\begingroup$ So the final answer is 5^5 mod 11 which = 1? i'm just not sure how to write out/ understand the final answer $\endgroup$ – TTEd Apr 4 '16 at 17:34
  • $\begingroup$ Yes, the final answer is $5^5 \equiv 1 \pmod {11}$. $\endgroup$ – S.C.B. Apr 4 '16 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.