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!

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.

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 . Is it because it is still of the form 4l+1 that it cannot be a prime factorization?

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

Awesome, thanks lots Gamma!