Please review/verify this proof of assertion (Number Theory)

[Math100]

Homework Statement

Prove the assertion below:
Each integer of the form 3n+2 has a prime factor of this form.

Relevant Equations

None.

Proof: Suppose that all primes except for 3 must have
remainder of 1 or 2 when divided by 3.
Then we have the form 3p+1 or 3p+2.
Note that the product of integers of the form 3p+1
also have the form 3p+1.
Let m be an integer whose prime divisors have the form 3p+1,
now we know that m also has the form 3p+1.
Since the given integer has the form 3n+2,
it follows that not all of the prime divisors have the form 3p+1.
Thus, one of them will have the form 3p+2.
Therefore, each integer of the form 3n+2 has a prime factor of this form.

Above is my proof for this assertion. Can anyone please review/verify this and see if it's correct?

 

[FactChecker]

I don't follow it at all. You should make your proofs follow a logical order from the initial conditions to the desired conclusion. Start with an integer, k = 3n+2. What is the series of logical steps to conclude that k has a prime factor, p, of the form p=3m+2? If you need to prove some facts before you get into the main line of the proof, you should state and prove them as lemmas.

 

[Office_Shredder]

I think the proof idea is actually correct but I agree it's not worded well. You have p standing in for a lot of different things that aren't the same number.

You also haven't ruled out 3p being a factor.

 

[FactChecker]

Homework Statement:: Prove the assertion below:
Each integer of the form 3n+2 has a prime factor of this form.
Relevant Equations:: None.

Proof: Suppose that all primes except for 3 must have
remainder of 1 or 2 when divided by 3.

Do you mean to say "suppose"? It is a fact.

Then we have the form 3p+1 or 3p+2.
Note that the product of integers of the form 3p+1
also have the form 3p+1.

You could explain this:
$(3n_1+1)(3n_2+1)=9n_1n_2+3n_1+3n_2+1=3(3n_1n_2+n_1+n_2)+1=3n_3+1$, where $n_3=3n_1n_2+n_1+n_2$
(Note: I would recommend that you do not use 'p' as a natural number because many readers will assume that it means a prime number.)

Let m be an integer whose prime divisors have the form 3p+1,
now we know that m also has the form 3p+1.
Since the given integer has the form 3n+2,
it follows that not all of the prime divisors have the form 3p+1.
Thus, one of them will have the form 3p+2.

Ok. Looks good to me except that, as @Office_Shredder said, you haven't ruled out having 3p as a factor.

 

[Math100]

Here is my revised proof for this assertion:

Suppose a=3n+2 for some a$\in\mathbb{Z}$.
Since each integer of the form 3n+2 is not divisible by 3,
it follows that a=3n+2 cannot have prime factor of the form 3n,
so all prime factors are either of the form 3n+1 or 3n+2.
Then we have (3n1+1)(3n2+1)=9n1n2+3n1+3n2+1
=3(3n1n2+n1+n2)+1
=3n3+1,
where n3=3n1n2+n1+n2.
Thus, a=3n+2 must have a prime factor of the form 3n+2.
Therefore, each integer of the form 3n+2 has a prime factor of this form.

Can anyone please review/verify this revised proof, to see if it's correct?

 

[nuuskur]

Correct. You can optimise as follows. Let $a\equiv 2\pmod{3}$. Then $3$ is not a prime factor of $a$. If all prime factors of $a$ are of the form $3k+1$, then also $a\equiv 1\pmod{3}$.

1. If at all possible, use some basic TeX. It will help a lot in the readability department.
2. You make some strange jumps in your arguments. For example

Then we have (3n1+1)(3n2+1)=9n1n2+3n1+3n2+1
=3(3n1n2+n1+n2)+1
=3n3+1,
where n3=3n1n2+n1+n2.

You are so detail-oriented in this part of the argument. But what did you show, exactly? And then you skipped right to

Thus, a=3n+2 must have a prime factor of the form 3n+2.

Why did the details become so vague all of a sudden?

In short, your presentation is not convincing. Sure, anybody that knows what to look for understands your arguments. More importantly, however, I am not entirely convinced you understand your arguments.

 

[Math100]

How about this one?

Suppose a=3n+2 for some a$\in\mathbb{Z}$.
Since each integer of the form 3n+2 is not divisible by 3,
it follows that a=3n+2 cannot have prime factor of the form 3n,
so all prime factors of a=3n+2 are either of the form 3n+1 or 3n+2.
Now we consider two cases.
Case#1) Suppose the integer a=3n+2 have prime factors of 3m+1 and 3q+1.
Then we have (3m+1)(3q+1)=9mq+3m+3q+1
=3(3mq+m+q)+1
=3k+1,
where k=3mq+m+q is an integer.
Note that the product of prime factors 3m+1 and 3q+1 takes the form 3n+1.
Case#2) Suppose the integer a=3n+2 have prime factors of 3m+1 and 3q+2.
Then we have (3m+1)(3q+2)=9mq+6m+3q+2
=3(mq+2m+q)+2
=3k+2,
where k=mq+2m+q is an integer.
Note that the product of prime factors 3m+1 and 3q+2 takes the form 3n+2.
Therefore, each integer of the form 3n+2 has a prime factor of this form.

Above is my revised proof for this assertion. Can anyone please review/verify to see if this is correct?

 

[nuuskur]

Yes, now it's clear you understand why you made the computations. What you focus on most of the time can be briefly expressed as follows.
Proposition. If $a\equiv k\pmod{n}$ and $b\equiv \ell \pmod{n}$, then $a+b\equiv k+\ell \pmod{n}$ and $ab \equiv k\ell\pmod{n}$.
Proof is very straight-forward, apply what you know about the divisibility relation. Were all the prime factors congruent to $1$, then $a$ itself would also be by the Proposition.