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

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.

some more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search