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

  • $\begingroup$ The the general logic flows in the proof, but it's a bit "messy". That cleans it up nicely. I don't want include the mod in my proof as the book works linearly and there is no mention of mods until next chapter. However, as I understand modular arithmetic, I grasp the simplicity of the argument better, so thank you. $\endgroup$ – Lalaloopsy Jun 6 '14 at 2:04
  • 2
    $\begingroup$ Can't you use the concept of congruences without the congruence notation? e.g., $(3j + 1)(3k + 1) = 9jk + 3j + 3k + 1$. $\endgroup$ – Robert Soupe Jun 6 '14 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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