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

• May 28th 2006, 03: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, 04: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 $\displaystyle p>3$ be a prime. Consider the possible values of the remainder
when $\displaystyle p$ is divided by $\displaystyle 6$. As $\displaystyle p>3$ is prime the remainder cannot
be divisible by any factor of $\displaystyle 6$.

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

And that,
$\displaystyle 6k+3$ is divisble by 3 and $\displaystyle p>3$ thus not a prime.
Hence the only possibilites are,
$\displaystyle 6k+1$
or,
$\displaystyle 6k+5=6k+6-1=6(k+1)-1$
Thus,
$\displaystyle 6k\pm 1$ for some integer $\displaystyle k$.
• May 29th 2006, 12: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, 10: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, 09:28 AM
srulikbd
cool
coincidence :)
• May 31st 2006, 02:58 PM
ThePerfectHacker
I can present a proof to why are there infinitely many primes of form $\displaystyle 4k+1 \mbox{ and }4k+3$ if you really wish to know.
• May 31st 2006, 11:45 PM
srulikbd
ok
i'll be happy!
• Jun 1st 2006, 09:02 AM
ThePerfectHacker
Quote:

Originally Posted by srulikbd
i'll be happy!

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

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

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

Proof: Assume there are finitely many primes of form $\displaystyle 4k+3$ call them $\displaystyle \{ p_1,...,p_s} \}$. Then form an integer,
$\displaystyle n=4p_1p_2\cdot ...\cdot p_s-1$
Prime factorize $\displaystyle n$ as,
$\displaystyle n=q_1q_2\cdot ...\cdot q_r$
Note that $\displaystyle 2\not | n$ because it is odd. Thus, $\displaystyle q_i\not =2$ for any $\displaystyle 1\leq i\leq r$.
We cannot have that all the primes factors of $\displaystyle n$ are of the form $\displaystyle 4k+1$ for that would imply that $\displaystyle n$ has form $\displaystyle 4k+1$, which is does not because $\displaystyle 4k-1=4(k-1)+3$ by the lemma. Thus one of its factors $\displaystyle r_i$ has form $\displaystyle 4k+3$. Because an odd prime has one of two forms $\displaystyle 4k+1,4k+3$. But then $\displaystyle r_i|n$ thus, $\displaystyle r_i|(4p_1p_2\cdot ...\cdot p_s-1)$ thus, $\displaystyle r_i|1$, because $\displaystyle r_i$ is found among $\displaystyle p_1,...,p_s$ thus an impossibility. Q.E.D.
• Jun 2nd 2006, 12: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, 04: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 :)

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

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

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