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.
Thank you for your interest!
 A: 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.

