My Math Forum super huge numbers mod a big number

 Number Theory Number Theory Math Forum

 January 2nd, 2019, 08:07 PM #1 Senior Member     Joined: Sep 2015 From: USA Posts: 2,370 Thanks: 1274 super huge numbers mod a big number 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)
 January 2nd, 2019, 08:48 PM #2 Senior Member   Joined: Aug 2012 Posts: 2,201 Thanks: 646 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 by Maschke; January 2nd, 2019 at 08:56 PM.
January 2nd, 2019, 08:55 PM   #3
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,370
Thanks: 1274

Quote:
 Originally Posted by Maschke 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}$

January 2nd, 2019, 08:57 PM   #4
Senior Member

Joined: Aug 2012

Posts: 2,201
Thanks: 646

Quote:
 Originally Posted by romsek mod $10$ would be easy... this is mod $10^{10}$
Oh sorry nevermind.

 January 2nd, 2019, 10:42 PM #5 Senior Member   Joined: Oct 2009 Posts: 755 Thanks: 261 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.
January 3rd, 2019, 10:18 AM   #6
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,370
Thanks: 1274

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.
Attached Images
 Clipboard01.jpg (49.2 KB, 13 views)

Last edited by romsek; January 3rd, 2019 at 10:21 AM.

 Tags big, huge, mod, number, numbers, super

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post GIjoefan1976 Algebra 9 March 9th, 2016 07:59 PM 3972 Number Theory 4 January 12th, 2016 10:20 AM mobel Number Theory 9 September 26th, 2015 05:54 AM sankarshan87 Number Theory 8 July 27th, 2013 02:04 PM Axel Calculus 3 June 4th, 2011 07:14 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top