Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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.

share|cite|improve this answer

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 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.

share|cite|improve this answer

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?

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.