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

• Math100

#### 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?

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.

PeroK and Math100
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
Math100 said:
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.
Math100 said:
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.)
Math100 said:
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.

Last edited:
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?

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.

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?

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.

Math100