Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$

share|improve this question
    
My own solution: According to the division algorithm a number can be of the form $6n$, $6n+1$, $6n+2$, $6n+3$, $6n+4$ or $6n+5$. –  laovultai Sep 14 '11 at 8:04
    
alvoutila, is this really your homework? What division algorithm are you referring to? –  Dan Brumleve Sep 14 '11 at 8:08
    
My own solution: According to the division algorithm( There exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b)a number can be of the form $6n$, $6n+1$, $6n+2$, $6n+3$, $6n+4$ or $6n+5$. If $6n=2*3 = 2k $ => number is even. If $6n+1$ => Number is either product of primes or prime. If $6n+2=2(3n+1)=2k$ => number is even. If $6n+3=3(2n+1)$=> number is divisible by three. If $6n+4=2(3n+2)$ => number is even. If $6n+5$ => number is either product of primes or prime. Thus every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$. –  laovultai Sep 14 '11 at 8:15
    
alvoutila, your solution is correct. –  Dan Brumleve Sep 14 '11 at 8:18

5 Answers 5

up vote 6 down vote accepted

Every integer is of the form $6n$ or $6n+1$ or $6n+2$ or $6n+3$ or $6n+4$ or $6n+5$ for some integer $n$. This is because when we divide an integer $m$ by $6$, we get a remainder of $0$, $1$, $2$, $3$, $4$, or $5$.

If an integer $m>2$ is of the form $6n$ or $6n+2$ or $6n+4$, then $m$ is even and greater than $2$, and therefore $m$ is not prime.

If an integer $m>3$ is of the form $6n+3$, then $m$ is divisible by $3$ and greater than $3$, and therefore $m$ is not prime.

We have shown that an integer $m>3$ of the form $6n$ or $6n+2$ or $6n+3$ or $6n+4$ cannot be prime. That leaves as the only candidates for primality greater than $3$ integers of the form $6n+1$ and $6n+5$.

Comment: In fact, it turns out that there are infinitely many primes of the form $6n+1$, and infinitely many primes of the form $6n+5$. Showing that there are infinitely many of the form $6n+5$ is quite easy, it is a small variant of the "Euclid" proof that there are infinitely many primes. Showing that there are infinitely many primes of the form $6n+1$ requires more machinery. But your question did not ask for such a proof.

share|improve this answer
    
en.wikipedia.org/wiki/… –  Dan Brumleve Sep 14 '11 at 8:19
2  
@Dan Brumlewe: The reference to Dirichlet's theorem is nice, but that's fairly heavyweight stuff. For $6n+5$ one needs basically nothing, and for $6n+1$ some information about quadratic residues. –  André Nicolas Sep 14 '11 at 8:32

$6$ divides $6n$, $2$ divides $6n+2$, $3$ divides $6n+3$, $2$ divides $6n+4$, and there are no other cases.

share|improve this answer

This is elementary algebra. For what value(s) of $n$ is $6n$ prime? $6n+2$? $6n+3$? $6n+4$? Are there any other possibilities besides these and the two that you already mentioned?

share|improve this answer

Copied from here.

Considering n = 6q + r

where q is a non-negative integer and the remainder r is one of 0, 1, 2, 3, 4, or 5.

  • If the remainder is 0, 2 or 4, then the number n is divisible by 2, and can not be prime.
  • If the remainder is 3, then the number n is divisible by 3, and can not be prime.

So if n is prime, then the remainder r is either

  • 1 (and n = 6q + 1 is one more than a multiple of six), or
  • 5 (and n = 6q + 5 = 6(q+1) - 1 is one less than a multiple of six).
share|improve this answer

Indeed all primes greater than 3, are in the form of 6n-1 and 6n+1. I've studied on these few years ago.. here's a basic visual proof of that using a sieve and isolation method that I used : First , list down all the numbers in 6 columns :

1-------- 2---------3--------4 ---------5--------6

7-------- 8-------- 9--------10--------11--------12

13-------14--------15------- 16--------17------- 18.....[ the list will be infinite ]

Then, we cross out the column of 2,3, 4, and 6 as they are all composite.. so we are just left out with two columns of 1 and 5. Using Algebraic progression with a difference of 6, Column 1 generates the prime path of 6n+1 [ 7,13,19,..infinite ] and column 5 generates the prime path of 6n-1. [ 5,11,17,23...infinite..] Thus , by isolation and sieve method, we can see that all primes must be in the form of 6n-1/6n+1...

hope this help a little...thanks..yolito, you can email me at [ tjbaptist@yahoo.com ]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.