Are There Prime Factors of the Same Form for Integers of Form 3n+2?

[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

 

[shmoe]

Try a proof by contradiction.

 

[mathwonk]

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

 

[ComputerGeek]

Try a proof by contradiction.

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

 

[shmoe]

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

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.

 

[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.

 

[shmoe]

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

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.

 

[ComputerGeek]

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

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