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

4 Answers 4

up vote 5 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

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.