# Proof that $123456789098765432111$ is prime?

The mathematician Charles Weibel asks on his home page the following "fun question": How can you prove that 123456789098765432111 is a prime number? (He notes the fact

$$12345678987654321 = 111111111 \times 111111111$$

which is of course well-known.)

By "proof", I assume he means something more humanly illuminating than asking a computer program. I haven't a clue what he has in mind. Does someone have an idea?

-
Thanks; let me know if you flesh out a more precise argument. –  user43208 Sep 13 '13 at 4:51
my attempt: $\frac{123456789098765432111 - 11}{100} = 1234567890987654321$ don't know where to go from there... hopefully it helps, somehow –  bestversionofme Sep 13 '13 at 6:14
Relevant: primality certificate. –  dtldarek Sep 13 '13 at 7:12
Note that $123456789009876543211$ is prime as well, and $1111111111\cdot 1111111111=1234567900987654321$ –  Dietrich Burde Sep 13 '13 at 8:14
@abiessu: As I tried to indicate, I'd like something conceptual and not horribly brute force (because knowing Charles Weibel, I'll bet he has something more conceptual in mind). Although I am not a number theorist, I am a mathematician and I'd be willing to tolerate a fair dose of number-theoretic sophistication in an answer. I'd be interested if the little observation he made were not just a red herring he threw in there just for kicks. –  user43208 Sep 13 '13 at 14:38

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,...

-
Yeah, I understood that. Thanks for answering though. –  user43208 Sep 30 '13 at 22:13

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
63496, 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

-
Thanks for this answer. I'll give you an upvote for it, but I'd like to see if there are some other ideas on this... Chuck Weibel called it a "fun question", meaning I'd guess it also has a "fun solution". But in principle I accept this type of answer as perfectly reasonable, from a methodological point of view. –  user43208 Sep 30 '13 at 18:24