My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree2Thanks
  • 2 Post By romsek
Reply
 
LinkBack Thread Tools Display Modes
January 2nd, 2019, 08:07 PM   #1
Senior Member
 
romsek's Avatar
 
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)
romsek is offline  
 
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.
Maschke is offline  
January 2nd, 2019, 08:55 PM   #3
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,430
Thanks: 1315

Quote:
Originally Posted by Maschke View Post
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}$
Thanks from Maschke and topsquark
romsek is offline  
January 2nd, 2019, 08:57 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,312
Thanks: 707

Quote:
Originally Posted by romsek View Post
mod $10$ would be easy... this is mod $10^{10}$
Oh sorry nevermind.
Maschke is offline  
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.
Micrm@ss is offline  
January 3rd, 2019, 10:18 AM   #6
Senior Member
 
romsek's Avatar
 
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.
Attached Images
File Type: jpg Clipboard01.jpg (49.2 KB, 13 views)

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

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.