Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 –  zerosofthezeta 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
2  
@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

2 Answers 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,... 
share|improve this answer
    
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
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.