# Thread: 2 Prime Number questions

1. ## 2 Prime Number questions

1.
Let n be an integer greater than 0. Show that there is a prime p such that p | n (p divides n). Don't use the theorem that every integer greater than 1 can be expressed as a product of prime numbers.
I really don't know how to go about solving this one without using the theorem I can't use

2.
Let p be prime, p >= 5. Show that p is of the form 6k+1 or 6k+5 for some integer k.
I was trying to use induction here but get stuck trying to prove for n+1 (I was inducting over k)

Thanks for any help

2. 1) $n$ has to be greater than 1 !

If $n$ is prime we are done, so let's assume that $n$ is not prime. Then $n=a_1\cdot{b_1}$ for some $a_1,b_1\geq{2}$. If $a_1$ is prime, we are done. If this is not so, then $a_1=a_2\cdot b_2$ for some $a_2,b_2\geq{2}$ that is $n=a_2\cdot b_2 \cdot b_1 \geq{2^3}$

Now repeat this process. We can ensure it will end since after $m$ steps we get $n=a_m\cdot b_m\cdot b_{m-1}\cdot ..\cdot b_1\geq{2^{m+1}}$ and this doesn't hold for large enough $m$.

This proves that at some point $a_{m}$ is going to be prime. (since this ends if and only if $a_m$ is prime) .And we are done.

2). Simple note that $6k+2$ is even, ( so if k>0 then it is a number greater than 2 and divisible by it, hence not prime). $6k+3=3(2k+1)$ is multiple of 3, so it only can be prime if it is 3 itself. $6k+4=2(3k+2)$ (again even) ...

3. Maybe you'll find this proof of 1) clearer than the other one.

If $n>1$ then the set $
A = \left\{ {d \in \mathbb{Z}^ + ,d > 1/\left. d \right|n} \right\}
$
is non-empty ( since $n\in A$ ) further $
A \subset \mathbb{N}
$
thus $
k = \min \left( A \right)
$
exists.

If $k$ was not prime then $
k = a \cdot b
$
with $a,b>1$, but then $a|n$ ( $n=k\cdot u = a\cdot (b\cdot u)$) and so $
a \in A \wedge a < \min \left( A \right) = k
$
contradiction ! Thus $k$ is prime and we are done.

4. Originally Posted by PaulRS
1) $n$ has to be greater than 1 !

If $n$ is prime we are done, so let's assume that $n$ is not prime. Then $n=a_1\cdot{b_1}$ for some $a_1,b_1\geq{2}$. If $a_1$ is prime, we are done. If this is not so, then $a_1=a_2\cdot b_2$ for some $a_2,b_2\geq{2}$ that is $n=a_2\cdot b_2 \cdot b_1 \geq{2^3}$

Now repeat this process. We can ensure it will end since after $m$ steps we get $n=a_m\cdot b_m\cdot b_{m-1}\cdot ..\cdot b_1\geq{2^{m+1}}$ and this doesn't hold for large enough $m$.

This proves that at some point $a_{m}$ is going to be prime. (since this ends if and only if $a_m$ is prime) .And we are done.

2). Simple note that $6k+2$ is even, ( so if k>0 then it is a number greater than 2 and divisible by it, hence not prime). $6k+3=3(2k+1)$ is multiple of 3, so it only can be prime if it is 3 itself. $6k+4=2(3k+2)$ (again even) ...
First of all thanks,
I do have some questions though, just better insight for me

1)
Do we have to worry about what that first b1 is? Or is it okay to just leave it an integer (which I'm guessing after it all happens is just 1?)

2)
Are you just showing that since it holds for 6k+1
Doesn't hold for 6k+2, since 2(3k+1) is a multiple of 2
Doesn't hold for 6k+3, since 3(2k+1) so multiple of 3 unless k = 0
Doesn't hold for 6k+4, since 2(3k+2), multple of 2
Hold's for 6k+5

Do you just have to cover the interval of 1-5? I just can't see how this proves that p is of the forms for any p >= 5.

It seems like it can hold for 6k+7 too? or 6k + any prime.

5. $6k+7 = 6k+6+1 = 6(k+1)+1$. Letting $k+1=j$, we have $6j+1$, which is exactly what we've already stated is true.
The statement is really: Any prime can be expressed as $6k+a$, where $a\,mod\,6\equiv1$ or $a\,mod\,6\equiv5$.
The idea is that $b_1$ and the rest of the b's ( if they appear) are integers greater than 1, read the proof again. We do not care what they are because it is enough to just work with the a's in order to get a prime number, we could also decompose each of the b's in the same way, and we'd get that n can be written as a product of prime numbers.