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:
:
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.
Not at all.
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!
QED, indeed!
That was very cheeky!
Trained the sprog well, in the intricacies of dorkdom, you have.
What, Quantum ElectroDynamics?
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.
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.
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.
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?
Indeed, djlactin. Worse still, there are problems which provably cannot be proven to be provable or disprovable.
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.)
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)
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!
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.
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.
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 :-).
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.
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…