Is there a nice proof that $123456789098765432111$ is prime?

Solution 1:

Not sure if this is humanly illuminating, but I believe it is humanly checkable. The following is a Pratt certificate, assuming primality for primes $\leq 100$:

123456789098765432111, 7, 123456789098765432111-1 = 2*5*63493*322997*601991891
  63493, 2, 63493-1 = 2*2*3*11*13*37
  322997, 2, 322997-1 = 2*2*80749
    80749, 2, 80749-1 = 2*2*3*3*2243
      2243, 2, 2243-1 = 2*19*59
  601991891, 2, 601991891-1 = 2*5*191*315179
    191, 19, 191-1 = 2*5*19
      315179, 2, 315179-1 = 2*59*2671
        2671, 7, 2671-1 = 2*3*5*89

Solution 2:

More Fun with Numbers

The number 12345678987654321=111111111x111111111 is mentioned in the OP. And, believe it or not, $1234567898765432111$ is a prime number too!!!

You have to believe it! The following $maxima$ output shall demonstrate this using Pratt's primality certificat.

(%i1) m:1234567898765432111;a:29;power_mod(a,m-1,m);factor(m-1); makelist(power_mod(a,(m-1)/p,m),p,map(first,ifactors(m-1)));
(%o1) 1234567898765432111
(%o2) 29
(%o3) 1
(%o4) 2*5*11*11223344534231201
(%o5) [1234567898765432110, 972745681039223016, 1223153431857342200, 1089307852892054661]


• %i1 is the input line.
• %o1is the output showing the modul $m$, the number that we check if it is prime.
• %o2 is an outputline showing the number $a$ we exponate.
• %o3 is the output of $a^{m-1} \pmod{m}$. It should be $1$ if $m$ is a prime. But it could be $1$ even if $M$ is composite.
• %o4 is the factorisation of $m-1$ and
• %o5 are the numbers $a^{\frac{m-1}{p}}$ for all prime factors of $m-1$

The factors $2$,$5$ and $11$ are primes but it is not obvious that $11223344534231201$ is a prime number. so we add a proof that $11223344534231201$ is a prime too:

(%i1) m:11223344534231201;a:3;power_mod(a,m-1,m);factor(m-1); makelist(power_mod(a,(m-1)/p,m),p,map(first,ifactors(m-1)));
(%o1) 11223344534231201
(%o2) 3
(%o3) 1
(%o4) 2^5*5^2*7*73*101*109^2*137*167
(%o5) [11223344534231200, 7251767246727978,1687389182360412, 5679768249246961, 2181793601204580, 9078160829860754, 8735272021960592, 1320423471360269]


Because it is easy to check that $2,5,7,73,109,137,167$ are primes we are finished.

( both $a=29$ and $a=3$ can be replaced by the larger but funnier number $1111111$ int the certificates)

But how does this primality certificate work?

The following is well known:

• all residue classes $a$ that are relatively prime to the module $m$ constitute a multiplicative group $\pmod{m}$
• If $a^{m-1} \pmod{m}$ is not equal to $1$ then $m$ could not be a prime because this contradicts Fermat's little theorem.
• $\text{ord}_{m-1}(a)$ is the smallest power $e$ such that $a^{e} \equiv 1 \pmod{m}$, it is a divisor of every such $e$. Especially of $\phi(m)$.
• if $a^{m-1} \equiv 1 \pmod{m}$ then $\text{ord}_{m-1}(a)$ is a divisor of $m-1$. If it is a proper divisor of $m-1$ it must be a divisor of $\frac{m-1}{p}$ for a prime $p$ dividing $m$. Then $a^\frac{m-1}{p} \equiv 1 \pmod{m}$ for such a $p$
• all the residue classes $a,a^2,...,a^{\text{ord}(a)}$ are pairwise different

So if $\text{ord}(a)=m-1$ and $\phi(m)=m-1$ and therefore $m$ is a prime.

@ronno would note this certificate as

1234567898765432111,29,1234567898765432111-1=2*5*11*11223344534231201
  11223344534231201,3,11223344534231201-1=2^5*5^2*7*73*101*109^2*137*167
    167,...
    137,...
    109,...
    101,...