Prime Factor

Date: 02/18/2002 at 15:21:46
From: D. Bates
Subject: Prime number

I need to prove that each integer of the form 3n + 2 has a prime 
factor of this form. Can you help? 

Thank you.

Date: 04/16/2002 at 08:59:17
From: Doctor Paul
Subject: Re: Prime number

Proof by contradiction:

Suppose k is an integer of the form 3*n + 2 with no prime factor of 
that form.  

Notice that k = 2 mod 3. In particular, k is not divisible by three 
(k would have to be congruent to zero mod three if k were to be 
divisible by three) so three does not appear in the prime 
factorization of k. Moreover, since k does not contain a prime factor 
of the form 3*x + 2, none of its prime factors can be congruent to 
2 mod 3 either.  Thus all of the prime factors must be congruent to 
1 mod 3.

So we can write k as a product of numbers, all of which are congruent 
to 1 mod 3.  But such a product will always be congruent to 1 mod 3 
since 1 * 1 * ... * 1 = 1 mod 3.  Thus k = 1 mod 3, a contradiction.

Does this help?  Please write back if you'd like to talk about this 
some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/