# Thread: Proofs a bout primes

1. ## Proofs a bout primes

Here are some proofs re primes I need help with

1. Prove that any prime of the form 3n+1 is also of the form 6m+1

2. Show that any integer of the form 3n+2 must have a prime factor of the same form.

3. Show that 7 is the only prime of the form n^3-1

4. Show that p=5 is the only prime for which 3p+1 is a perfect square.

5. If p is prime and p divides a^n, show that p^n divides a^n

6. Show that every integer of the form n^4+4 is composite

Any help gratefully accepted.
Cheers
Cabouli

2. Originally Posted by Cabouli
1. Prove that any prime of the form 3n+1 is also of the form 6m+1
A prime number (excluding 2 and 3) must have form 6k+1 or 6k+5. Let p have form 3k+1. If p had form 6k+5 then 6k+5=3(2k+1)+2 so p would have form 3k+2, a contradiction. Thus, p must have form 3k+1.

2. Show that any integer of the form 3n+2 must have a prime factor of the same form.
Let x be a positive integer of the form 3k+2. Since it is odd we know x is a product of odd prime numbers. Thus, each prime factor has form 3k+1 or 3k+2. If each prime factor had form 3k+1 then the product of all of them still will have form 3k+1, which is a contradiction.
3. Show that 7 is the only prime of the form n^3-1
Hint: $n^3 - 1 = (n-1)(n^2+n+1)$
4. Show that p=5 is the only prime for which 3p+1 is a perfect square.
We will asume that $p\geq 3$. If $3p+1=n^2 \implies 3p = (n-1)(n+1)$ by unique factorization it forces $n-1 =3\text{ and }n+1=p$. Thus, $p=5$ is the solution.
5. If p is prime and p divides a^n, show that p^n divides a^n
If $p|a^n$ then $p|a$ then $p^n|a^n$.
6. Show that every integer of the form n^4+4 is composite
See this.

3. Originally Posted by Cabouli
1. Prove that any prime of the form 3n+1 is also of the form 6m+1
2 is the only even prime and its not of the form 3n+1

hence all primes of the form 3n+1 must be odd

this means that n must be even so n = 2m

,
,

,

,

,

,

,

,

,

,

,

,

# any prime o the form 3n 1 is also of the form 6m 1. Prove

Click on a term to search for related topics.