# 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) $\displaystyle n$ has to be greater than 1 !

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

Now repeat this process. We can ensure it will end since after $\displaystyle m$ steps we get $\displaystyle 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 $\displaystyle m$.

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

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

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

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

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

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

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

Now repeat this process. We can ensure it will end since after $\displaystyle m$ steps we get $\displaystyle 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 $\displaystyle m$.

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

2). Simple note that $\displaystyle 6k+2$ is even, ( so if k>0 then it is a number greater than 2 and divisible by it, hence not prime). $\displaystyle 6k+3=3(2k+1)$ is multiple of 3, so it only can be prime if it is 3 itself. $\displaystyle 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.

Thanks again for your time

5. $\displaystyle 6k+7 = 6k+6+1 = 6(k+1)+1$. Letting $\displaystyle k+1=j$, we have $\displaystyle 6j+1$, which is exactly what we've already stated is true.

The statement is really: Any prime can be expressed as $\displaystyle 6k+a$, where $\displaystyle a\,mod\,6\equiv1$ or $\displaystyle a\,mod\,6\equiv5$.

6. Originally Posted by Th3sandm4n
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?)
The idea is that $\displaystyle 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.

Also read the second proof ( my second post)