Adventures in Ethics and Science

It’s a proud day for any parent when offspring start getting interested in formal proofs. So I felt a little thrill when the elder Free-Ride offspring sat down with Dr. Free-Ride’s better half to consider whether it was possible for there to be a largest prime number:

i-cb46ac9218043057600a3bb7841853d6-PrimeProofSmall.jpg

:

Not just a proof, people. A proof by reductio!

It makes a mother a little emotional.

Lest I get totally verklempt, let us note the levity my child has inserted into the proof.

In the line of the proof that notes the contradiction (that n, which is prime and also greater than p presents a problem for the claim that p is the greatest prime), after the “But! But!” … that’s not an omega.

i-f9d94c8058348d39021cf5570a5747af-ButButBut.jpg

Not at all.

Comments

  1. #1 Dr. Free-Ride's Better Half
    March 20, 2009

    Another note of levity (leavening?) is the cryptic diagram at the bottom. It is the “proof”-ing of a doughnut.

    And yet another: if you look closely, you’ll see that EO added a dot to the “therefore” symbol. Now there are four!

  2. #2 Isis the Scientist
    March 20, 2009

    QED, indeed!

  3. #3 arvind
    March 20, 2009

    That was very cheeky! :-)

    Trained the sprog well, in the intricacies of dorkdom, you have.

  4. #4 Alex Besogonov
    March 20, 2009

    What, Quantum ElectroDynamics? :)

  5. #5 Neil
    March 20, 2009

    You’re right to be proud, but you can now show F-R offspring that proofs can have subtle problems and need to be checked. I’m afraid n is not necessarily prime.

    $ bc
    bc 1.06
    Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
    This is free software with ABSOLUTELY NO WARRANTY.
    For details type `warranty’.
    2*3*5*7*11*13+1
    30031
    $ factor 30031
    30031: 59 509

    It is, though, not divisible by any of the original primes and therefore divisible only by a larger one. So there is no largest prime.
    It’s still an impressive achievement.

  6. #6 Joshua Zelinsky
    March 20, 2009

    I’d be very curious as to how much input/hints from adults there were to develop this. This isn’t at all an easy proof to come up with if one hasn’t seen it before (also how old is the offspring to have already seen modular arithmetic?).

    Incidentally, a marginally related anecdote about my youngest sibling when he was about four years old. He was playing with legos all about the same size and he was putting them in different size rectangles. I asked him what he was doing and he explained that certain numbers of pieces could be made into multiple different rectangles, but some could only be made into a single rectangle, the one that had a width of 1 piece. He was trying to find a pattern in which could be put into only one rectangle size. So he had more or less discovered the idea of a prime number for himself. Having smart siblings is nice.

  7. #7 Jonathan Vos Post
    March 20, 2009

    Excellent!

    My son, at 13, was trying to explain to some other teenagers how it could be that there were unsolved Math problems. He led them through what your sprog did (Euclid’s proof) and then defined Twin Primes for them, which they all got.

    So, are there an infinite number of twin primes? he let them argue for a while. Then said: “We don’t know. After centuries of effort, we just don’t know.”

    The other teenagers now GOT it.

  8. #8 djlactin
    March 21, 2009

    y’have to wonder… are there some postulates that we can prove true, some that we can prove false, whereas some we can prove to be unanswerable?

  9. #9 Matt Springer
    March 21, 2009

    Indeed, djlactin. Worse still, there are problems which provably cannot be proven to be provable or disprovable.

  10. #10 Janet D. Stemwedel
    March 22, 2009

    Neil, I’m pretty sure the reductio still works, because you show that the assumptions (p is the greatest prime) leads to a contradiction — in your example, it would fail because there is a prime greater than p *and* greater than n (in the case that n is not prime).

    It’s worth pointing out here that the elder Free-Ride offspring, who knows mods like nobody’s business and was right on board with each step of the proof, did not devise the strategy for the proof. (At age 9, a sprog can benefit from some parental guidance.)

  11. #11 Simon
    March 23, 2009

    Neil is right. for a prime p, n=p!+1 need not be prime. the proof proceeds by noting that either n is prime or if it is composite, then its prime factors must be bigger that p (and there is your desired contradiction)

  12. #12 Stephen Miller
    March 23, 2009

    Yes, but an integer is prime iff it cannot be divided by any prime smaller than it, and since we have checked ALL the primes…

    I don’t have a problem with the proof!

  13. #13 Tony Jeremiah
    March 23, 2009

    It seems that one could make the argument that the largest prime number is one containing an infinite number of 1s (i.e., 111…).

  14. #14 Paul
    March 26, 2009

    It seems that one could make the argument that the largest prime number is one containing an infinite number of 1s (i.e., 111…).

    Care to explain the argument? Many of the lower sequences of 1s (e.g. 111, 1111, 11111) are composite.

  15. #15 Tony Jeremiah
    March 27, 2009

    Care to explain the argument? Many of the lower sequences of 1s (e.g. 111, 1111, 11111) are composite.

    My first thought was that if n = 1 through 9, n(infinite)/n = 1(infinite). My 2nd thought was that digits 2 (infinite) through 9 (infinite) could never be prime numbers because if one arbitrarily defined infinity to be a certain cutoff point, it doesn’t matter where the cutoff point is, that number would still be capable of being divided by itself and n.

    1(infinite) on the other hand, seems capable of only being divided by 1(infinite), which would make it the largest prime number.

  16. #16 Paul
    March 27, 2009

    Actually, without going into a formal proof you can detect a pattern in factoring a sequence of 1′s (longer than 11).

    With an even number (n) of 1′s, it can be factored into:
    n/2 1s * (1 followed by ((n-2)/2) zeros followed by a 1)
    e.g. n = 4, 6, 8 as follows:

    1111 = 11 * 101
    111111 = 111 * 1001
    11111111 = 1111 * 10001

    It’s pretty easy to see with a basic understanding of multiplication why this pattern produces the even lengths of 1s. I have not been able to discern a mathematical pattern with regards to factors of odd sequences of 1s, but at least every one where n mod 3 = 0 will be composite. So let’s hope infinity doesn’t end on an even number or with a string whose length is a multiple of 3 :-).

  17. #17 Tony Jeremiah
    March 27, 2009

    Yeah,

    I did notice that from 111 to 1(infinite), 1-repeats containing n-digits that are a multiple of 3 are non-prime (e.g., 111, 111.111, 111.111.111, 111.111.111.111 etc).

    I just tracked down a website discussing something similar ( prime numbers with equal digits , which indicates that 1.111.111.111.111.111.111 is a prime number. I don’t have software that can verify that.

    What would be an interesting test of the (relative) validity of the hypothesis of 1(infinite) as the largest prime, is to determine whether there’s a 1-repeat prime greater than the current largest known primes .

    Apparently there’s some contest involving considerable monetary compensation for finding a prime number with 1 billion digits. If there is something to this 1(infinite) idea, it takes on a whole new level of practical significance.

  18. #18 Joshua Zelinsky
    April 11, 2009

    In general, you can show that if you have a number k that is a sequence of n 1s and n is composite then k is composite. You essentially use a generalization of the factorization mentioned above. You can write k= (10^n-1)/9 and then factor the numerator as a difference of mth powers where m is a non-trivial divisor of n.

    This generalizes to any base b instead of just 10. The case b=2 leads naturally to the Mersenne primes (primes of the form 2^n-1) which are connected to perfect numbers and have been studied since ancient times. It is unknown whether for any b there are infinitely many n such that a string of 1s in base b is prime, however it is suspected to be true for any base.

    For base 10 the largest known example is n=109297 (I think). It is easier to remember the very large n=1031 which if you remember this fact you can tell people you have an 1031 digit prime memorized. People get annoyed fast if you start reciting the digits. I can’t imagine why…