Primes Greater Than/Less Than Multiples of SixDate: 01/18/2002 at 16:31:54 From: Riley Subject: Primes greater than/less than multiples of six. I seem to remember my math teacher a couple years ago telling me about a postulate stating that every prime number was either one more or one less than a multiple of six, excluding 2 and 3. I believe she said it was unproven (that's why I call it a postulate), and I was wondering if you knew whether or not it was indeed proven. Thanks. Date: 01/18/2002 at 19:44:43 From: Doctor Paul Subject: Re: Primes greater than/less than multiples of six. It has been proven and a proof is really not that hard if you think about it the right way: All integers can be divided into six classes: those that are multiples of six those that are 1 more than a multiple of six those that are 2 more than a multiple of six those that are 3 more than a multiple of six those that are 4 more than a multiple of six those that are 5 more than a multiple of six All primes except two are odd and any number that is either: (1) a multiple of six, (2) two more than a multiple of six, or (3) four more than a multiple of six will be even and hence cannot be prime. Thus the only kinds of numbers that can possibly be prime (i.e., the odd numbers) can be thought of as either: one more than a multiple of six three more than a multiple of six five more than a multiple of six It's pretty easy to see that any number that is three more than a multiple of six must be divisible by three and hence won't be prime unless that number is actually three itself. To see that any number that is three more than a multiple of six must be divisible by three, let x be three more than a multiple of six. Then x = 6*k + 3 for some integer k. But then x = 6*k + 3 = 3*(2k + 1), so x is divisible by three. Thus the only possible candidates for prime numbers are: 2, 3, and numbers that are either 1 more than a multiple of six or five more than a multiple of six. Notice that a number that is five more than a multiple of six will be one less than a multiple of six. This completes the proof. I hope this helps. Please write back if you'd like to talk about this more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/