# For all primes greater than 3, p = 6k±1?

• May 28th 2006, 04:44 AM
srulikbd
For all primes greater than 3, p = 6k±1?
is it true?
what is the proof?
I prefer a hint if it ain't difficult to prove.
tnx :)
• May 28th 2006, 05:05 AM
CaptainBlack
Quote:

Originally Posted by srulikbd
is it true?
what is the proof?
I prefer a hint if it ain't difficult to prove.
tnx :)

Hint(?):

Let $p>3$ be a prime. Consider the possible values of the remainder
when $p$ is divided by $6$. As $p>3$ is prime the remainder cannot
be divisible by any factor of $6$.

RonL
• May 28th 2006, 06:30 AM
srulikbd
Ok Understood
quite easy :)
• May 28th 2006, 10:55 AM
ThePerfectHacker
Or to say it another way.
Any number must have form,
$\begin{array}{c}6k\\6k+1\\6k+2\\6k+3\\6k+4\\6k+5$
Note that,
$\begin{array}{c}6k\\6k+2\\6k+4$
are all divisible by 2 and $p>2$ thus not a prime.

And that,
$6k+3$ is divisble by 3 and $p>3$ thus not a prime.
Hence the only possibilites are,
$6k+1$
or,
$6k+5=6k+6-1=6(k+1)-1$
Thus,
$6k\pm 1$ for some integer $k$.
• May 29th 2006, 01:30 AM
srulikbd
another question
how do I prove that there are infinite primes that have the form xk+y, y<x, and share no common factors?
• May 29th 2006, 11:19 AM
ThePerfectHacker
Quote:

Originally Posted by srulikbd
how do I prove that there are infinite primes that have the form xk+y, y<x, and share no common factors?

Whoa!!!
That is too complicated I believe the proof use's funtional analysis. It was first proven by Dirichelt (my avatar :)).

In fact in the book "Introduction to Theory of Numbers" by Hardy and Wright. Which contains elementary,algebraic and analytic number theory; proves all theorems in the book (even the prime number theorem) except this theorem! That is how complicated it is.
• May 31st 2006, 10:28 AM
srulikbd
cool
coincidence :)
• May 31st 2006, 03:58 PM
ThePerfectHacker
I can present a proof to why are there infinitely many primes of form $4k+1 \mbox{ and }4k+3$ if you really wish to know.
• Jun 1st 2006, 12:45 AM
srulikbd
ok
i'll be happy!
• Jun 1st 2006, 10:02 AM
ThePerfectHacker
Quote:

Originally Posted by srulikbd
i'll be happy!

Lemma: The product of integers of the form $4k+1$ is again an integer of the form $4k+1$.

Proof:: If $a=4k+1$ and $b=4j+1$ then, $ab=(4k+1)(4j+1)=4(4kj+k+j)+1$. Q.E.D.

Theorem: There are infinitely many primes of form $4k+3$.

Proof: Assume there are finitely many primes of form $4k+3$ call them $\{ p_1,...,p_s} \}$. Then form an integer,
$n=4p_1p_2\cdot ...\cdot p_s-1$
Prime factorize $n$ as,
$n=q_1q_2\cdot ...\cdot q_r$
Note that $2\not | n$ because it is odd. Thus, $q_i\not =2$ for any $1\leq i\leq r$.
We cannot have that all the primes factors of $n$ are of the form $4k+1$ for that would imply that $n$ has form $4k+1$, which is does not because $4k-1=4(k-1)+3$ by the lemma. Thus one of its factors $r_i$ has form $4k+3$. Because an odd prime has one of two forms $4k+1,4k+3$. But then $r_i|n$ thus, $r_i|(4p_1p_2\cdot ...\cdot p_s-1)$ thus, $r_i|1$, because $r_i$ is found among $p_1,...,p_s$ thus an impossibility. Q.E.D.
• Jun 2nd 2006, 01:04 AM
srulikbd
I didn't understand the end-what does | means?
and whaat does X means? (2X...) does it means doesn't divide?
tnx :)
• Jun 2nd 2006, 05:25 AM
CaptainBlack
Quote:

Originally Posted by srulikbd
I didn't understand the end-what does | means?
and whaat does X means? (2X...) does it means doesn't divide?
tnx :)

$a|b$ is to be read as $a$ divides $b$.

$a \not| \ b$ is to be read as $a$ does not divide $b$.

RonL
• Jun 2nd 2006, 07:10 AM
srulikbd
tnx both of u now I understand
:)