
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 2nd, 2019, 08:07 PM  #1 
Senior Member Joined: Sep 2015 From: USA Posts: 2,430 Thanks: 1315  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,312 Thanks: 707 
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,430 Thanks: 1315  Quote:
 
January 2nd, 2019, 08:57 PM  #4 
Senior Member Joined: Aug 2012 Posts: 2,312 Thanks: 707  
January 2nd, 2019, 10:42 PM  #5 
Senior Member Joined: Oct 2009 Posts: 784 Thanks: 280 
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,430 Thanks: 1315 
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. Last edited by romsek; January 3rd, 2019 at 10:21 AM. 

Tags 
big, huge, mod, number, numbers, super 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
anyone have "secrets" for finding lowest terms with huge numbers.  GIjoefan1976  Algebra  9  March 9th, 2016 07:59 PM 
Finding out if a huge number is a prime  3972  Number Theory  4  January 12th, 2016 10:20 AM 
Tricky way to generate huge list of prime numbers  mobel  Number Theory  9  September 26th, 2015 05:54 AM 
Number as product of 3 numbers  sankarshan87  Number Theory  8  July 27th, 2013 02:04 PM 
E (euler's number) flunctuates in Excel for huge n numbers!  Axel  Calculus  3  June 4th, 2011 07:14 PM 