Every prime > 3 is congruent to \pm 1 mod 6

**dwsmith** · July 8th 2010, 03:32 AM

Every prime > 3 is congruent to $\pm 1 \ \mbox{mod 6}$

Induction maybe?

$5\equiv\pm 1\ \mbox{(mod 6)}$ This isn't true though

**aman_cc** · July 8th 2010, 04:41 AM

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

**Ackbeet** · July 8th 2010, 04:42 AM

$5\equiv -1\ \mbox{(mod 6)},$ since $5-(-1)=6\times 1$ .

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.

**melese** · July 10th 2010, 01:31 AM

Originally Posted by dwsmith

Every prime > 3 is congruent to $\pm 1 \ \mbox{mod 6}$

Induction maybe?

$5\equiv\pm 1\ \mbox{(mod 6)}$ This isn't true though

You can generalize and consider integers $a$ that are relatively prime to $6$ and the result will follow, in particular, to any prime $p>3$ .

Let $a=6q+r$ , with $0\leq r<6$ . Then $gcd(a,6)=gcd(6,r)$ , so we need only to look at values $r$ such that $gcd(6,r)=1$ . These are $r=1,5$ .

Now, $a\equiv 1(mod\ 6)$ ,or $a\equiv 5\equiv -1(mod\ 6)$ .

**Bacterius** · July 10th 2010, 05:32 AM

Keep it simple ... I assume that $p > 3$ in the whole post by the way ... since the fact $3 | 3$ does not contradict the primality of $p$ ... just adjust what is below as you wish ...

Let $p \equiv x \pmod{n} \Rightarrow p = kn + x$ , $k \in \mathbb{Z}$ , $x \in \mathbb{Z}/n\mathbb{Z}$
Then it follows that $\gcd{(n, x)} | p$
But if $p$ is prime we must have $\gcd{(n, x)} = 1$ (otherwise there is a contradiction with respect to the definition of a prime number)

Applying this to the current problem with $n = 6$ , the only $x$ that are coprime to $6$ (in the congruence ring $\mathbb{Z}/6\mathbb{Z}$ of course) are, surprisingly enough, $1$ and $5$ (which turns out to be congruent to $-1 \pmod{6}$ ).

It follows that if $p$ is indeed prime then it must be congruent to $\pm 1 \pmod{6}$

...

Interestingly, it is also possible to prove that this implies that $\gcd{(k, n)} = 1$ for any prime $p$ ... This gives me an idea, I'll be right back !

**Bingk** · July 12th 2010, 04:30 PM

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

**Bacterius** · July 12th 2010, 07:25 PM

I don't understand what you mean, can you develop ?

**Bingk** · July 16th 2010, 06:50 AM

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

Thread: Every prime > 3 is congruent to \pm 1 mod 6

LinkBack

Thread Tools

Display

Every prime > 3 is congruent to \pm 1 mod 6

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Is S_3 congruent to D_3?

Prove that if n>=2 and not prime, then n has a prime divisor p<=(sq.root)n

x^6 congruent to 1 (mod 19)

Prove: For ever prime p and integer a, a^p is congruent to a (mod p)