super huge numbers mod a big number

romsek

Math Team
Sep 2015
2,958
1,672
USA
what is the general method for say finding the last 10 digits of the number

$n=2012^{2011^{2010}}$

I'm thinking that you first find

$n_1=2012^{2011}\pmod{10^{10}}$

and then

$n_2 = n_1^{2010} \pmod{10^{10}}$

and if say $10^{10}$ was prime, or relatively prime to $2012$ then Fermat's Little Theorem or Euler's Theorem can be brought into play but that doesn't occur here.

Is there some trick I'm not aware of? (almost certainly)
 
Aug 2012
2,488
780
What are the powers of $2012^n \bmod10$? They're 2, 4, 8, or 6 depending on whether n is 1, 2, 3, or 4 mod 4.

So the problem is reduced to calculating $2011^{2010} \bmod 4$. That's the general idea for how to reduce a level in these types of problems. You just have to keep track of all the cycles and levels.
 
Last edited:

romsek

Math Team
Sep 2015
2,958
1,672
USA
What are the powers of $2012^n \bmod10$? They're 2, 4, 8, or 6 depending on whether n is 1, 2, 3, or 4 mod 4.

So the problem is reduced to calculating $2011^{2010} \bmod 4$. That's the general idea for how to reduce a level. You keep going like that. Hopefully keeping track of all the cycles at each level isn't too intractable for the specific problem at hand.
mod $10$ would be easy... this is mod $10^{10}$
 
  • Like
Reactions: 2 people
Oct 2009
939
364
The idea seems to first split this into two equations, one mod $2^{10}$ and one mod $5^{10}$. This can be done with the chinese remainder theorem.
 

romsek

Math Team
Sep 2015
2,958
1,672
USA
What I have done that works, but requires software, is to

decompose the exponent into it's base 2 digits

by repeatedly squaring and modding starting the with base number
set up a table of the $2^k$ powers of the base mod $10^{10}$

i.e.

$(2012) \pmod{10^{10}} \\
(2012)^2 \pmod{10^{10}}\\
\dots \\
(2012)^{2^k} \pmod{10^{10}}$ etc.

Then for 1's in the binary expansion select the appropriate value from this list.
These are all <=10 digit numbers so while they are big they aren't that big.

Take this selected list and again multiply mod through the entire list.



Then you repeat the entire process using this new base and the second exponent.

The sheet doesn't show that.
 

Attachments

Last edited: