The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.