Prime FactorDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/