# prime divisor of $3n+2$ proof

I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof

I tried saying by the division algorithm the prime factor is either the form 3m,3m+1,3m+2.

Case 1: $3m$ suppose $3m$ does divide $3n+2$. That means $3mr=3n+2$ where $r$ is some integer. But we get $mr-n= 2/3$ and since $mr-n$ is an integer that's a contradiction. Thus $3m$ does not work.

Case 2: $3m+1$ Same argument here

Case 3: $3m+2$ By the fundamental theorem of arithmetic every integer is divisible by a prime. But not sure what to do from here.

-
Your case 2 is very well possible. – azimut Mar 4 '13 at 18:24
I've corrected the title and the problem statement: please check to make sure I've conveyed what you intended, given your proof. – amWhy Mar 4 '13 at 18:26
Alternatively, say all the primes $p_i$ such that $p_i \mid N$ were $p_i \equiv \{0,1\}\ (3)$, then $N \equiv \{0, 1\} \not\equiv 2\ (3)$. – J.H. Mar 4 '13 at 18:27
$14=3\cdot 4 +2$ does have a prime factor $p\equiv 1\pmod 3$, namely, $7$. So, as @azimut says, you can't conclude that $n$ does not have such a prime factor. You can only prove that such prime factors are not the only prime factors. – Thomas Andrews Mar 4 '13 at 18:30

## 6 Answers

Hint $\$ If $\rm\:N = 3n+2\:$ has no prime factors of form $\rm\:3k+2,\:$ then all prime factors must have form $\rm\:3k+1,\:$ hence their product $\rm\:N\:$ has form $\rm\:3k+1,\:$ contra $\rm\:N = 3n+2.$

Generally any factorization of an integer $\rm\not\equiv 1\,\ (mod\ m),\:$ must include a factor $\rm\not\equiv 1\,\ (mod\ m), \:$ simply because integers $\rm \equiv 1\,\ (mod\ m)\:$ are closed under multiplication (form a monoid). Similarly for other sets of integers closed under multiplication. Consider the set T of integers divisible by $10,\:$ i.e. those with unit digit $= 0.\:$ Any factorization of an integer $\rm\:n\not\in T\,$ must include a factor $\rm\not\in T,\,$ else all factors have unit digit $= 0\,$ thus so too does their product $\rm\,n,\,$ i.e. $\rm\,n\in T,\,$ contra hypothesis. Similarly, one could let $\rm\,T\,$ be all powers of $\,10,\,$ etc. The property on factors of elements in the complement of T is just an equivalent complementary restatement of the closure of T under multiplication. See also this post on the complementary view of subgroups, which generalizes: integer $*$ noninteger = noninteger; $\$ rational $*$ irrational = irrational, etc.

-

Hint: Denote the prime factorization of $3n + 2$ by $$3n + 2 = p_1^{e_1}\cdot\ldots\cdot p_r^{e_r}$$ and consider this equation modulo $3$.

EDIT: Since other people have posted a full solution in the meanwhile, I'll do the same:

Modulo $3$ you get $$2 \equiv p_1^{e_1} \cdot\ldots\cdot p_r^{e_r}\pmod{3}.$$ Now assume that all prime factors $p_i$ are equivalent $0$ or $1$ modulo $3$. Then also $p_1^{e_1}\cdot\ldots\cdot p_r^{e_r}$ is equivalent to $0$ or $1$ modulo $3$. Contradiction.

-
No case 2 doesn't work I think. If it did then the statement I'm proving be wrong. – user60887 Mar 4 '13 at 18:33
No and no. Look at the example of @ThomasAndrews: 14 = 2\cdot 7. The prime factor $7$ is of the form $3m + 1$. The claimed statement is still true, since the other prime factor $2$ is of the form $3m + 2$. – azimut Mar 4 '13 at 18:35
I figured out case three I think. – user60887 Mar 5 '13 at 16:01

We will assume that by number we mean positive integer.

Call a number of the form $3n+2$ which has no prime divisor of the form $3m+2$ bad. We will show that there are no bad numbers.

Suppose to the contrary that there is at least one bad number. Then there is a smallest bad number $b$.

It is clear that $b\ne 1$. It is also clear that $b$ is not prime. For if $b$ is prime, then it has a prime divisor of the form $3m+2$, namely itself. So there are integers $k$ and $l$, both bigger than $1$, such that $b=kl$.

If one of $k$ or $l$ is divisible by $3$, then so is their product. But $b$ cannot be divisible by $3$. For if $3$ divides $3n+2$, then $3$ must divide $2$, which is not the case.

If both $k$ and $l$ are congruent to $1$ modulo $3$, then so is their product. But $b$ is congruent to $2$ modulo $3$.

Thus at least one of $k$ and $l$ (in fact exactly one) is congruent to $2$ modulo $3$. Let it be $k$.

Because $k\lt b$, by the definition of $b$ as the smallest bad number, $k$ cannot be bad. It follows that $k$ is divisible by a prime $p$ of the form $3m+2$. But then so is $b$, contradicting the fact that $b$ is bad.

Remark: A proof that uses the fact that every integer $\gt 1$ is a product of primes is more efficient. Note that we do not need the Fundamental Theorem of Arithmetic, aka the Unique Factorization Theorem. It is enough to have a factorization.

-
How is b not prime? For n=1, 3n+2 = 5 which is prime. Similarly, there are other values of n for which 3n+2 is prime so your argument is lacking proof there as n=3,5, and 7 would also have the characteristic of being prime. – JB King Mar 4 '13 at 19:13
If $b$ is prime, then it has a prime divisor of the form $3m+2$, namely itself, so it is not bad. – André Nicolas Mar 4 '13 at 19:20

I would try a proof by induction. The case $n=1$ yields $3n+2 = 5$, which is a prime so all is well. Now assume $n > 1$. If $3n+2$ is prime, we are again done. If not you can write it as $3n+2 = rs$ with $r,s < 3n + 2$. It is easy to show that either $r$ or $s$ also has to be of the form $3m + 2$. Applying the induction hypothesis gives the result.

-

If (3n+2) is prime ,then it has a prime factor (3n+2). If (3n+2)is composite ,then there exist integers h,k where 1< h,k <(3n+2). case 1: if at least one of h,k be of the form 3m+2 then there is nothing to prove. case 2:if at least one of h,k be of the form 3m then,3|(3n+2) I.e 3|2 a contradiction.so any integer of the form (3n+2) has no prime factor of the form 3m. case 3:if at least one of h,k be of the form 3m+1( say h). then 3 cases arises for k subcase 1: k= 3p which is impossible by case 2. subcase 2:k=3j+1 ,then 3n+2 = 3(3mj+m+j)+1.which is again a contradiction. subcase 3: so we must have k of the form 3m+2. combining all the cases we have the required result.

-

OK, starting from the case 2:

$$3n+2=r(3m+1)$$ $$3(n-mr)=r-2$$ $$k=n-mr=\frac{r-2}{3}$$ $$r = 3k+2$$

Is this correct?

-
Actually looking at it now no its not correct. I need to redo my entire proof. – user60887 Mar 4 '13 at 20:07
This formula shows that if a number of the form 3n+2 is divisible by a number of the form 3m+1, $\frac{3n+2}{3m+1}=3k+2$\$ for some integer k. If this 3k+2 is not a prime factor, you can repeat this for a finite number of times and produce a prime factor that is in the form 3k+2. I'm pretty sure this is accurate. Your statement that case 2 shows that it can't be divisible by 3m+1 is incorrect but I think this one is. – kaine Mar 4 '13 at 22:01
these type of questions that ask things like if these numbers take this form then prove that it its also this form seemingly is confusing me. Does anyone know of a website or another book that explains this concept well? – user60887 Mar 5 '13 at 1:42