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.

Thank you for your interest!

  • 1
    $\begingroup$ 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...$ $\endgroup$ Sep 3, 2022 at 0:26
  • 1
    $\begingroup$ It's probably using a pseudoprimality test. $\endgroup$
    – K.defaoite
    Sep 3, 2022 at 0:30
  • 2
    $\begingroup$ it is under $10^{400},$ you could use Primo for an actual proof certificate $\endgroup$
    – Will Jagy
    Sep 3, 2022 at 0:38
  • 1
    $\begingroup$ @WillJagy Yes, but ECPP is overkill here because $p-1$ is easy to factor. OpenPFGW can do it in an instant. $\endgroup$ Sep 3, 2022 at 2:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – orangeskid
    Sep 3, 2022 at 6:20

2 Answers 2


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$.)

  • $\begingroup$ Nice! I just learned that this is called the Lucas primality test: en.wikipedia.org/wiki/Lucas_primality_test $\endgroup$ Sep 3, 2022 at 0:49
  • $\begingroup$ 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 :-) $\endgroup$
    – orangeskid
    Sep 3, 2022 at 1:34
  • $\begingroup$ @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$. $\endgroup$ 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.

  • $\begingroup$ Thank you, this is very useful! $\endgroup$
    – orangeskid
    Sep 3, 2022 at 1:38
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Sep 3, 2022 at 8:36
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Sep 3, 2022 at 8:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .