Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prime factor of the same form

  1. Nov 15, 2005 #1
    Any help would be appreciated. I need to show that for all integers of the form [tex]3n+2[/tex] 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 [tex]2n[/tex] and [tex]2n+1[/tex]

    that did not work out so well because 2n gave me factors of 2 and [tex] 3n + 1[/tex]

    I then tried it with the [tex]4n+X[/tex] class of numbers and achieved similar results.

    what am I missing here?

  2. jcsd
  3. Nov 15, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    Try a proof by contradiction.
  4. Nov 15, 2005 #3


    User Avatar
    Science Advisor
    Homework Helper

    when you get that, try showing there is an infinite number of primes of form 3n+2.
  5. Nov 15, 2005 #4
    would that just prove the existence of an integer of the form 3n+2 with a prime factor 3n+2?
  6. Nov 15, 2005 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Nov 15, 2005 #6
    I think I figured out a way:

    let [tex] 3n+2[/tex] be prime

    then just multiply it with [tex] 3n, 3n+1, 3n+2[/tex]

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

    it is an exhaustion proof, but with such few considerations it is not to much work.
  8. Nov 15, 2005 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Nov 15, 2005 #8
    so, say mod 3 when talking about numbers in the form 3n+x
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook