calculating Modulus on Massive numbers

Question

In the case I have two numbers large enough to justify using scientific notation twice $A \times 10^{B \times 10^C}$ or $Ae+Be+C$ How would I calculate Modulo without taking the numbers or any part of them out of scientific notation?

Answer 1

Thing is, powers are cycle under modular arithmetic.

Find out what power it takes for $10$ to cyclic through and take $B\times 10^C$ modulo that. ANd to do that you might need know what power modulo that is cycle modulo that.

For example to figure $58\times 10^{97\times 10^{43}}\pmod {63}$ ... (something I made up out of the top of my head). $10$ and $63$ are relatively prime. $\phi(63)=\phi 7\phi 9=6*6=36$ so $10^{36} \equiv 1\pmod{63}$ and

$58\times 10^{97\times 10^{43}} \equiv (-5)\times 10^{97 \times 10^{43}\pmod {36}}\pmod {63}\equiv (-5)\times 10^{25 \times 10^{43}\pmod {36}}\pmod {63}$

Now to figure out $10^{43}\pmod {36}$ $10$ and $36$ are relatively prime so I'll have to use chinese remainder theorem.

$10^{43}=2^{43}5^{43} \equiv 0 \pmod 4$

And $10^{43} \equiv 1^{43}\equiv 1 \pmod 9$ so $10^{43} \equiv 28\pmod {36}$ and

$58\times 10^{97\times 10^{43}}\equiv (-5)\times 10^{25 \times 28\pmod {36}}\pmod {63}\equiv$

$(-5)\times 10^{-11\cdot -8\pmod{36}} \equiv $

$(-5)\times 10^{88 \pmod{36}} \equiv $

$(-5)\times 10^{16}\pmod{63}$.

Okay $10^{16}$ is still pretty large. We can use CRT again.

$10^{16} \equiv 1 \pmod 9$ and $10^{16}\equiv 3^{16} \equiv (3^6)^2*3^4 \equiv 3^4 \equiv 9^2\equiv 2^2 \equiv 4 \pmod 7$ so $10^{16}\equiv 46 \pmod {63}$

So $(-5)\times 10^{16}\equiv -5*46\equiv -5\cdot (-17)\equiv 83\equiv 21 \pmod {63}$.