Results 1 to 5 of 5

Math Help - Help with primes

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    17

    Help with primes

    Prove that if a is a positive integer of the form 4n+3, then at least one prime divisor of a is of the form 4n+3.

    I'm suck D: The book gave a hint to prove the contrapositive, but I'm still not sure what to do. I thought of a proof and at first I thought it was right, but then on re-examination I see I made a mistake. I'll type it up because maybe there is some way to scavange my wrong proof and make it right.

    Let S={a in N|a=4t+3 and a is not divisible by a prime of the form 4n+3}[/tex]

    Suppose S =/= empty set, then by the Well Ordering Principle there exists a smallest element. Call it n. n can't be a prime because it would then be divisible by a prime of the form 4t+3. Hence n is composite and there exists integers x and y s.t. n=xy where 1<x<n and 1<y<n. Since x<n then x is not in S (this is where I made my mistake), then x is divisible by a prime of the form 4t+3 (I can't make this conclusion, right? Because x may not even be of the form 4t+3... I'll finish what I wrote out). Call this prime p. But since p|x and x|n, then p|n - a contradiction. Thus S= empty set.

    Help would be appreciated. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    think mod 4

    Every integer has a unique prime decomposition. Suppose for a moment that every prime factor was in fact not of the form 4k+3 (3 mod 4). There are only two kinds of primes, 2 and odd ones. Clearly an integer of the form 4n +3 is odd and thus does not have 2 as a factor. Thus every factor must be odd which leaves integers of the form 4k + 3 and 4l + 1 to make up its prime factorization (3 or 1 mod 4 respectively) . If one is of the form 4k + 3, you are done. So all must be of the form 4l + 1 (1 mod 4). Think about what happens when you multiply two numbers of this form together to see why this could never be the prime factorization.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Sorry, I know it's been a while since this thread has be replied, but in response to Gamma, the resulting product of 4l+1 primes is 16l^2 + 8l + 1. Is it because it is still of the form 4l+1 that it cannot be a prime factorization?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    Bingo

    We have ruled out the only other possible prime factor (2). And your observation shows exactly why there is no way a number that is 3 mod 4 could possible consist of all prime numbers that are 1 mod 4. So there must be at least 1 prime factor of the form 3 mod 4 (in particular there would have to be an odd number of these types of primes too as 3^2 \equiv 1 \mod 4).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member star_tenshi's Avatar
    Joined
    Jan 2009
    Posts
    32
    Awesome, thanks lots Gamma!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 2nd 2010, 11:18 AM
  2. n^2 + n + 41 and primes
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 26th 2010, 09:13 AM
  3. Primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 8th 2009, 02:26 PM
  4. Primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 12th 2009, 10:59 PM
  5. primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2008, 01:21 AM

Search Tags


/mathhelpforum @mathhelpforum