Every prime > 3 is congruent to

Induction maybe?

This isn't true though

Printable View

- Jul 8th 2010, 03:32 AMdwsmithEvery prime > 3 is congruent to \pm 1 mod 6
Every prime > 3 is congruent to

Induction maybe?

This isn't true though - Jul 8th 2010, 04:41 AMaman_cc
any number can be

0,1,2,3,4,5 mod 6

because the number is prime - 0,2,3,4 can be ruled out - Jul 8th 2010, 04:42 AMAckbeet
since .

You could try arguing along these lines: all primes greater than 3 are odd. Therefore, they must be congruent to either -1, 1, or 3 mod 6. (5 and -1 are equivalent). However, any number greater than 3 that is congruent to 3 mod 6 would be divisible by 3, and hence not prime. Therefore, all primes greater than 3 are congruent to 1 or -1 mod 6.

[EDIT]: This is essentially the same as what aman_cc said. - Jul 10th 2010, 01:31 AMmelese
- Jul 10th 2010, 05:32 AMBacterius
Keep it simple ... I assume that in the whole post by the way ... since the fact does not contradict the primality of ... just adjust what is below as you wish ...

Let , ,

Then it follows that

But if is prime we must have (otherwise there is a contradiction with respect to the definition of a prime number)

Applying this to the current problem with , the only that are coprime to (in the congruence ring of course) are, surprisingly enough, and (which turns out to be congruent to ).

It follows that if is indeed prime then it must be congruent to

...

Interestingly, it is also possible to prove that this implies that for any prime ... This gives me an idea, I'll be right back ! - Jul 12th 2010, 04:30 PMBingk
To Bacterius

gcd(n,x) = 1 or p

i.e. p = p mod p^2, so gcd(p^2,p) = p, and p|p

But since n is 6, then we can say that gcd(n,x) should be 1 :) - Jul 12th 2010, 07:25 PMBacterius
I don't understand what you mean, can you develop ? (Worried)

- Jul 16th 2010, 06:50 AMBingk
I was just pointing out that gcd(n,x) isn't necessarily 1, it could be p also, at least in general ... for this particular case, since n is 6, then gcd(n,x) would be 1 ...