Number Theory Number Theory Math Forum

 January 2nd, 2019, 09:07 PM #1 Senior Member   Joined: Sep 2015 From: USA Posts: 2,631 Thanks: 1470 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, 09:48 PM #2 Senior Member   Joined: Aug 2012 Posts: 2,424 Thanks: 759 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 09:56 PM. January 2nd, 2019, 09:55 PM   #3
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,631
Thanks: 1470

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, 09:57 PM   #4
Senior Member

Joined: Aug 2012

Posts: 2,424
Thanks: 759

Quote:
 Originally Posted by romsek mod $10$ would be easy... this is mod $10^{10}$
Oh sorry nevermind. January 2nd, 2019, 11:42 PM #5 Senior Member   Joined: Oct 2009 Posts: 905 Thanks: 351 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, 11:18 AM   #6
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,631
Thanks: 1470

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 11:21 AM. Tags big, huge, mod, number, numbers, super Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post GIjoefan1976 Algebra 9 March 9th, 2016 08:59 PM 3972 Number Theory 4 January 12th, 2016 11:20 AM mobel Number Theory 9 September 26th, 2015 06:54 AM sankarshan87 Number Theory 8 July 27th, 2013 03:04 PM Axel Calculus 3 June 4th, 2011 08:14 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top       