How would you show that not every number of the form N =(p1*p2*p3*...*pn)+1 is prime?
====================================================================
This theorem says to multiply all of the prime numbers up to a certain level, then add 1. See if the result is also prime. If we can find even one exception, we have disproven the theorem.
Prime: A number is prime if it has exactly two factors -- 1 and itself.
All composite numbers (non-prime numbers) have pairs of factors, where one of the factors is less than the square root of the number, and the second is greater than the square root of the number. The exception is a perfect square, which has a "singular" factor.
For example, 6 has factors of 1 * 6 and 2 * 3; 16 has factors of 1 * 16, 2 * 8, and 4 * 4.
To find if the result from our theorem is prime, multiply the numbers, add 1, then check the square root of the number. Are there any possible primes that we have to look at? We don't need to look at any of the primes that we used to get there, since these numbers can't be factors (if we divided by any of these numbers, we would always get a remainder of 1).
Possible numbers:
2 * 3 + 1 = 7.
2 * 3 * 5 + 1 = 31
2 * 3 * 5 * 7 + 1 = 211
2 * 3 * 5 * 7 * 11 + 1 = 2311
2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031
Are any of these known primes? Here is a list: http://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_500_prime_numbers
The first four results are on this list. How about the last number? The
square root of 30031 is 173.29. We need to check every prime less than 173 to
find out if it is a factor of 30031. We also know that the primes up to 13 are
not factors.
After a little experimentation, you find that 59 * 509 = 30031, so this
number is not a prime number.
Nice!
ReplyDeleteI'm learning that this is how these things should be done. I've always been reluctant to do all of this, thinking that there is probably some more concise way that I'm not seeing. That may be the case sometimes, but getting there starts with longer explanations like this.
I just always assumed that "math people" could see the concise, elegant answer straight off (and maybe some of them can), and thought I was slow because I couldn't.
(Max)
Mathematicians generally do the hard work "behind the scenes" but only show the elegant solution they found at the end. I took problem-solving math class years ago. I turned in 7 pages of work for one problem, and never did solve it. I spent weeks in the discovery phase -- try this, try that, try another way...
ReplyDeleteMy son was in first grade at the time and go into trouble. When he couldn't do something like he wanted to, he would crumple up his paper and toss it in the garbage can. He never understood why this was an acceptable behavior at home but not in the classroom!
So, my only question with this is that you've shown an example, but not a proof. I'm not sure if that's a relevant distinction at this stage. That said, given that you don't necessarily know that 2 is one of the primes in the set every result for N = (p1 * p2 * p3 *...pn)+1 is not prime since the result will always be an even number. But, if 2 is one of the numbers I can't, at this point, think of a better solution. Kudos.
ReplyDeleteA proof is much more difficult than a disproof. To prove a theorem is wrong you simply need a single exception to the rule.
DeleteThis theorem says to use ALL primes less than a certain number; this means that you have to include 2.