The biggest exponent that can be computed

I am struggling with my crypt assignments and constantly getting overflow errors. Below is a simplified version of the problems I am experiencing

In:= a:= 44^65537

In:= b:= 22^65537

In:= GCD[a,b]

Out= 2265.....312 very big number


However I want to get an exponent with up to 13 digits or 48 bits to be exact.

If I do

In:= a:= 44^6553700000000

In:= b:= 22^6553700000000

In:= GCD[a,b]


General::ovfl: Overflow occurred in computation.

General::ovfl: Overflow occurred in computation.

GCD::exact: Argument Overflow[] in GCD[Overflow[], Overflow[]] is not an exact number.

Out= GCD[Overflow[], Overflow[]]

And now those question pop into my head

• The numbers becomes so big that the RAM can't handle it ?
• There is limit for the exponential power in Mathematica ?
• There is limit in my OS ?
• Numbers so big are impossible to calculate ?

Any input is appreciated !

• OScam - you should learn the difference between := and = in Mathematica - have a look here: mathematica.stackexchange.com/questions/18393/… – dr.blochwave Jan 5 '15 at 22:44
• 2^48 bits is 2^(48) / 8 = 2^45 bytes. That comes to 32 terabytes, at least using the 2^10=1K convention. So yeah, you may be up against limitations imposed by RAM, Mathematica and OS. – Daniel Lichtblau Jan 5 '15 at 23:01
• Thank you for making my question clean and nice, thanks for pointing out difference := and = i didn't knew about difference. – OScam Jan 6 '15 at 0:24

Your first port of call should be to have a look at the documentation for $MaxNumber, which says: $MaxNumber gives the maximum arbitrary‐precision number that can be represented on a particular computer system.

On my machine, $MaxNumber returns$1.605216761933662 \times 10^{1355718576299609}$. With regards to your number,$44^{6553700000000}$, I initially had to use this online calculator to convert it, it's approximately$3.36*10^{10770695805887}$. So, we need to compare the exponents, which initially seems fine. 10770695805887 > 1355718576299609 (* False *)  However, actually calculating this number exactly takes a very long time... as pointed out by Daniel Lichtblau it is likely a memory limitation! Changing to machine-precision works fine though, since that is 53 bits...look at Control the Precision and Accuracy of Numerical Results, but unfortunately that won't work with GCD[a, b] as machine-precision numbers are not exact. 44.^6553700000000 (* 3.3617443923642*10^10770695805887 *)  • Sorry, I messed up the edit :D – Sektor Jan 5 '15 at 22:37 • No long-term harm done :-) – dr.blochwave Jan 5 '15 at 22:38 • 20686623745 Out= 2.174188391646043 10 – OScam Jan 6 '15 at 0:26 • i am using mac book pro windows 8.1 maxnumber shows me: 20686623745 Out= 2.174188391646043 10 Does This power 20686623745 mean my PC can calculate upto this number ? if i use better Machine with more ram , problem can solve ? apologize for asking too much i am total noob :( – OScam Jan 6 '15 at 0:34 • Yes, if that's what it returns then that's the largest number Mathematica can achieve. Using a better machine won't necessarily solve your problem - calculating$44^{6553700000000}$exactly might well be beyond the capability of Mathematica. – dr.blochwave Jan 6 '15 at 8:17 This works fine for me (v.10.0.0 on Mac Pro): Clear[a, b] a = 44^(65537); b = 22^(65537); c = GCD[a, b];  Where all the digits of c are computed and revealed within about 2 seconds. N@c  2.265859854928417*10^87978 • Same here. Finished instantly. $Version == "10.0 for Mac OS X x86 (64-bit) (December 4, 2014)" – evanb Jan 5 '15 at 22:47
• This doesn't answer the question? The problem was with larger exponents... – dr.blochwave Jan 6 '15 at 8:16

Many times you can solve this kind of problems using realtions such as

GCD[a,b]=GCD[b,Mod[a,b]]


and substituting conventional functions for modular ones more specialized.

Mod[x^y,z]


you have to use

PowerMod[x,y,z]


that works if z is not too big, even if x^y is huge.

Coming back to your example and using different formulas

 In:= a:= 44^6553700000000

In:= b:= 22^6553700000000

In:= GCD[a,b]


You want to calculate

 GCD[(2*m)^x,m^x]


I would take this formula (you can find it on the Wikipedia)

gcd(a + m·b, b) = gcd(a, b)

And for you

 GCD[44^6553700000000, 22^6553700000000] =
GCD[(2*22)^6553700000000, 22^6553700000000] =
GCD[(2^6553700000000)*(22^6553700000000), 22^6553700000000] =
GCD[0,22^6553700000000]=22^6553700000000


You can check it with smaller numbers.

Though I know Mathematica should do it by its own means.