# Why is $120^{128}+1$ a prime number

Wolfram Alpha says that the number $$120^{128}+1$$ is prime. I wonder if that is in fact true, and if so, what is an argument for it.

• The prime factors of $120^{128}$ are $2,3,5$, and $1$ more than that number would result in the number not being divisible by $2,3,5$. I cannot find a simple way to prove that $120^{128}+1$ is not a multiple of $7,11,13...$ Sep 3, 2022 at 0:26
• It's probably using a pseudoprimality test. Sep 3, 2022 at 0:30
• it is under $10^{400},$ you could use Primo for an actual proof certificate Sep 3, 2022 at 0:38
• @WillJagy Yes, but ECPP is overkill here because $p-1$ is easy to factor. OpenPFGW can do it in an instant. Sep 3, 2022 at 2:01
• @InanimateBeing: In this case I would trust WA. But in principle software can have glitches. I remember some fairly simple definite integral was not given the right result by WA. This is perhaps due to their sophisticated algorithms that failed in some "extreme cases". I would say in this case we do have a prime number. Hey, maybe you can discover another one in a similar way, for me it was a lucky strike. Sep 3, 2022 at 6:20

If given the correct command, WolframAlpha can tell us that $$22$$ is a primitive root modulo $$120^{128}+1$$.

• PowerMod[22, 120^128/{1, 2, 3, 5}, 120^128 + 1] computes the list $$\{ 22^{120^{128}}, 22^{120^{128}/2}, 22^{120^{128}/3}, 22^{120^{128}/5} \}$$ modulo $$120^{128}+1$$.
• The fact that $$22^{120^{128}} \equiv 1 \pmod {120^{128}+1}$$ tells us that the order of $$22$$ modulo $$120^{128}+1$$ is a divisor of $$120^{128}$$.
• The fact that $$22^{120^{128}/2} \not\equiv 1 \pmod {120^{128}+1}$$ tells us that the order of $$22$$ modulo $$120^{128}+1$$ is not a divisor of $$120^{128}/2$$. Similarly, the order of $$22$$ modulo $$120^{128}+1$$ is not a divisor of $$120^{128}/3$$ nor a divisor of $$120^{128}/5$$.
• Since $$2$$, $$3$$, and $$5$$ are the only primes dividing $$120^{128}$$, we conclude that the only divisor of $$120^{128}$$ that is not a divisor of any of $$120^{128}/2$$, $$120^{128}/3$$, or $$120^{128}/5$$ is $$120^{128}$$ itself.
• Therefore the order of $$22$$ modulo $$120^{128}+1$$ is exactly $$120^{128}$$, which implies that $$120^{128}+1$$ is prime.

($$22$$ is simply the first primitive root I found; the smallest three primitive roots are $$19$$, $$22$$, and $$29$$.)

• Nice! I just learned that this is called the Lucas primality test: en.wikipedia.org/wiki/Lucas_primality_test Sep 3, 2022 at 0:49
• Very nice, thank you! The order of $a$ is $p-1$, so $(\mathbb{Z}/p)^{\times}$ has at least $p-1$ elements. Now I understand :-) Sep 3, 2022 at 1:34
• @orangeskid This is an instance of the Lucas Primality Test (an order test) - which has been discussed here many times in the past, e.g. proved here in $2011$. Sep 3, 2022 at 19:44

I can't find any public documentation of how WolframAlpha does primality testing. The simplest generally applicable option for numbers this large is the Fermat primality test, which for a positive integer $$p$$ means randomly choosing integers $$a \in [2, p-2]$$ and testing whether or not $$a^{p-1} \equiv 1 \bmod p$$. With $$p = 120^{168}$$ this computation can be done using binary exponentiation without too much hassle; the only prime factors of $$120$$ are $$2, 3, 5$$ we could do it by repeatedly taking second, third, and fifth powers, and for fifth powers we could use $$5 = 2^2 + 1$$ to speed the calculation up a bit too.

Unfortunately the Fermat primality test is really a compositeness test; if it finds $$a$$ such that $$a^{p-1} \not \equiv 1 \bmod p$$ then $$p$$ is composite, but if it doesn't then $$p$$ is only a probable prime. By finding more and more values of $$a$$ that probability can be driven arbitrarily low but it's still not a proof. There are variants here like the Solovay-Strassen primality test, the Miller-Rabin primality test, or the Baillie-PSW primality test.

For $$p$$ such that the prime factorization of $$p - 1$$ is known we can also apply the test Greg Martin describes which is called the Lucas primality test, which I just learned about right now. This one really is a primality test: if a number passes then it is provably prime.

Mathematica has a function ProvablePrimeQ which generates certificates proving that numbers are prime based on elliptic curve primality tests; I don't know if this is what WolframAlpha is doing. It might be some heuristic combination of tests depending on what seems like it would be easiest to apply?

Edit: Documentation linked to on Wikipedia says that Mathematica's PrimeQ function uses a variation of the Baillie-PSW test:

PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test. There are no known composite numbers that pass this procedure.

• Thank you, this is very useful! Sep 3, 2022 at 1:38
• Miller-Rabin is stronger than Fermat, the implementation is almost the same, and actually runs a tiny bit faster at each step. Importantly there are no known composites that systematically escape it, unlike Fermat. Sep 3, 2022 at 8:36
• I thought the Lucas test requires complete factorisation of p-1 - which is trivial for 120^128+1 and even more trivial for Fermat numbers, but very very hard in general. Sep 3, 2022 at 8:46