47
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ Thanks; let me know if you flesh out a more precise argument. $\endgroup$
    – user43208
    Sep 13, 2013 at 4:51
  • $\begingroup$ my attempt: $\frac{123456789098765432111 - 11}{100} = 1234567890987654321$ don't know where to go from there... hopefully it helps, somehow $\endgroup$ Sep 13, 2013 at 6:14
  • $\begingroup$ Relevant: primality certificate. $\endgroup$
    – dtldarek
    Sep 13, 2013 at 7:12
  • $\begingroup$ Note that $123456789009876543211$ is prime as well, and $1111111111\cdot 1111111111=1234567900987654321$ $\endgroup$ Sep 13, 2013 at 8:14
  • 2
    $\begingroup$ @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. $\endgroup$
    – user43208
    Sep 13, 2013 at 14:38

2 Answers 2

9
$\begingroup$

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
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user43208
    Sep 30, 2013 at 18:24
3
$\begingroup$

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,... 
$\endgroup$
1
  • 1
    $\begingroup$ Yeah, I understood that. Thanks for answering though. $\endgroup$
    – user43208
    Sep 30, 2013 at 22:13

You must log in to answer this question.

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