Is every prime number other than 2 and 3 of the form (6k±1)? Alon Amit, PhD in Mathematics answers Yes, of course. If a number leaves a remainder of 0, 2 or 4 when divided by 6, then it is even and therefore non-prime (unless it is 2). If it leaves a remainder of 3 when divided by 6 then it is divisible by 3 and therefore non-prime (unless it is 3). That leaves just the remainders 1 and 5, or in other words, numbers of the form 6k \pm 1. — EDIT: People seem to go back to this answer quite often so I thought I’d add a few more details, specifically because “what are other resources about it?” was part of the question. So… there isn’t a whole lot more to be said about the fact and the proof, nor about the generalization: for every positive integer m, every prime number (other than the first few) must be of the form am+b for some b which is relatively prime to m (that is, band m have no prime factors in common). This a straightforward observation. When m=6 the only relatively-prime b‘s are 1 and 5, leading to the statement that every prime (except the first few) must be of the form 6a+1 or 6a+5. This gets a lot more interesting though when you ask about the converse: so every prime has one of these two forms, and we know that there are infinitely many primes; do both forms appear infinitely often? How frequently? Perhaps it is the case that eventually primes of the form 6a+1 run out and we’re left only with 6a+5s? Answers to these questions are known as well but they are far less obvious. It turns out that there are infinitely many primes of both shapes, and more generally, there are infinitely many primes of the form am+b for any fixed values of m,b that are relatively prime. This is the celebrated Dirichlet’s theorem on arithmetic progressions. The general proof is ingenious and requires, amazingly, some complex analysis; special cases can be proved in elementary ways. Moreover, going back to the case m=6, the frequency of both types of primes is the same. If you count the primes of each type up to a million, and then a billion, and then a trillion, the ratio between the counts get closer and closer to 1. The same is true in general: for any m there are \varphi(m) possible values for b, and the primes that leave a remainder of b upon division by m occur at relative proportion 1/\varphi(m). However this isn’t the end of the story… the fact that 6a+1 primes appear 50% of the time doesn’t rule out the possibility that they always, or often, come first, namely that there are always more of them up to a billion or a trillion than the other kind. It’s still possible for this to happen even if the relative frequency of both types is 50%. For example, odd and even numbers are split evenly between the natural numbers, but up to every specific limit there are always either the same number of each or more odd numbers. The even ones never take the lead. It seems that, similarly, the lead is not shared evenly between primes of various types. For example, it is observed (and conjectured to be true, and proven to be true under some strong versions of RH) that primes of the form 4a+3 are winning the race against primes of the form 4a+1. This is known as Chebyshev’s bias. Primes are an endless source of wonder and beauty.
Posted on: Mon, 07 Jul 2014 04:43:57 +0000
Trending Topics
Recently Viewed Topics
© 2015