Prime factor of the same form

1. Nov 15, 2005

ComputerGeek

Any help would be appreciated. I need to show that for all integers of the form $$3n+2$$ there is a prime factor of the same form.

I know that integers of this form can be either even or odd depending on what class n falls into, so I thought a logical starting point would be to plug in $$2n$$ and $$2n+1$$

that did not work out so well because 2n gave me factors of 2 and $$3n + 1$$

I then tried it with the $$4n+X$$ class of numbers and achieved similar results.

what am I missing here?

thanks

2. Nov 15, 2005

shmoe

3. Nov 15, 2005

mathwonk

when you get that, try showing there is an infinite number of primes of form 3n+2.

4. Nov 15, 2005

ComputerGeek

would that just prove the existence of an integer of the form 3n+2 with a prime factor 3n+2?

5. Nov 15, 2005

shmoe

No, start with any integer of the form 3n+2. Assume it has no prime factors of the form 3m+2. Come to a contradiction.

6. Nov 15, 2005

ComputerGeek

I think I figured out a way:

let $$3n+2$$ be prime

then just multiply it with $$3n, 3n+1, 3n+2$$

this shows that only numbers with a second factor(not necessarily a prime factor) of the form $$3n+1$$ or $$3n+2$$ has a prime factor of $$3n+2$$

it is an exhaustion proof, but with such few considerations it is not to much work.

7. Nov 15, 2005

shmoe

This isn't true. A number with a prime factor of the form 3n+2 doesn't have to have another factor of the form 3m+2 or one of 3m+1 either (15 is a counter example).

Did you try assuming that 3n+2 has no prime divisors of the form 3m+2? For another hint in this direction, what do you get when you multiply primes of the form 3k+1 together?

As an aside, I don't suppose you've learned modular arithmetic yet? Not necessary but it makes the language much nicer.

8. Nov 15, 2005

ComputerGeek

so, say mod 3 when talking about numbers in the form 3n+x