# Number of the form $3k+2$ has a prime factor of the same form

I was thinking of using a proof by contradiction. I will also note that following the book I am using has not covered congruences in case that is the methodology.

Let $n=3k+2=ab$. Assume that $n$ has no prime factors of the form $3m+2$. Then its prime factors can only be of the form $3m$ or $3m+1$ Since factors of the form $3m$ cannot be prime, it suffices to show that the prime factors are of the form $3k+1$. But $$3m_1(3m_2+1)=9m_1m_2+3m_1=3(3m_1m_2+m_1)$$ $$(3m_1+1)(3m_2+1)=9m_1m_2+3m_1+3m_2+1=3(3m_1m_2+m_1+m_2)+1$$ Neither of these product yield a number of the form $3k+2$, therefore our assumption must be wrong. Thus, a number of the form $3k+2$ has a prime factor of the same form.

Is this a logical proof? I understand that there is an underlying assumption that my composite number $n$ has only two factors, $a,$ and $b$ but one could show that any combination of products of the form $3m$ and $3m+1$ will ultimately yield the same results...

EDIT: Should I instead have $$n=\prod_{p}p$$ Then this would be the prime factorization and the same argument holds?

Just do this. Obviously $3 \nmid 3k+2$. Now if all prime factors $q_i$ of $3k+2$ are $\equiv 1 \pmod 3$, then $3k+2 = \prod q_i^{a_i} \equiv (1)^{a_i} \equiv 1 \pmod 3$ which is a contradiction since $3k+2 \equiv -1 \pmod 3$.
• Can't you use the concept of congruences without the congruence notation? e.g., $(3j + 1)(3k + 1) = 9jk + 3j + 3k + 1$. – Robert Soupe Jun 6 '14 at 3:45