Proof: any prime number greater than 3 is congruent to 1 or 5 mod 6

It is called proof by exhaustion, where you basically check all possible cases to make sure they hold true. This formula is also called the division algorithm.
  • #1
jhson114
82
0
I'm trying to prove that any prime number bigger than 3 is congruent to 1 or 5 modulo 6. I started out by saying that that is the same as saying all prime numbers bigger than 3 are in the form 6n +- 1, n is an integer since 1 or 5 mod 6 yields either 1 or -1 and if you divide 6n+-1 by 6, you also get 1 or -1. But not i have no idea how to continue. any help will be appreciated. thank you
 
Physics news on Phys.org
  • #2
I think you are basically assuming what you set out to prove.

You may want to consider that if p > 3 is prime then both p-1 and p+1 are even (equivalent to 0 mod 2) and at least one of them equivalent to 1 or 2 mod 3. Does that lead anywhere?
 
  • #3
Tide, by first assuming what you said (p>3 is prime then both p-1 and p+1 are even),

1. Assume p>3, p+-1 are even
2. P+-1 = 2n , n is an integer
3. p+-1 = 2n congruent to 0 mod 2
4. p+-1 = 2(3n) = 6n congruent to 0 mod 6
5. p = 6n +- 1
6. p = 6n -1 congruent to 5 mod 6
7. p = 6n +1 congruent to 1 mod 6

is this the correct way to do it? it seems like I am not really proving anything here because you first assumed that p>3 P+-1 is even, but didnt prove that it is in fact even. and the part where i went from 2n to 6n seems incorrect. help please.
 
  • #4
Perhaps you could try looking at it the following way. I don't know if it is much help though.

[tex]a \equiv b\left( {\bmod 6} \right),b \in \left\{ {\mathop 0\limits^\_ ,\mathop 1\limits^\_ ,\mathop 2\limits^\_ ,\mathop 3\limits^\_ ,\mathop 4\limits^\_ ,\mathop 5\limits^\_ } \right\},a \in Z[/tex]

You could then using the definition of a congruent to b modulo 6 and see if you can make some conclusions from that.

Edit: You only need to show that if an integer is a prime and it is greater than 3 then it is congruent to 1 or 5 mod 6. So I think it is sufficient to simply knock out the numbers which do not satisfy the divisibility criteria.
 
Last edited:
  • #5
Any given integer is congruent to 0, or 1, ..., or 5 modulo 6

Which integers can't be prime?
 
  • #6
Using this formula:
[tex]a \equiv b\left( {\bmod 6} \right),b \in \left\{ {\mathop 0\limits^\_ ,\mathop 1\limits^\_ ,\mathop 2\limits^\_ ,\mathop 3\limits^\_ ,\mathop 4\limits^\_ ,\mathop 5\limits^\_ } \right\},a \in Z[/tex]
which states that all whole numbers can be represented as either, 6n, 6n+1, 6n+2, 6n+3, 6n+4, or 6n+5, since 6n is a multiple of 6, 6n+2 and 6n+4 are multiples of 2, 6n+3 is a multiple of 3, this leaves 6n+1 and 6n+5 to be prime numbers. is this proof by exhausion or is it even a proof? can someone also tell me the name of the above formula?
 
Last edited:
  • #7
jh,

Every prime number (except 2) is odd, otherwise it would be divisible by 2 and would not be prime! Therefore, p-1 and p+1 are both even.

Now, since p itself is odd and NOT divisible by 3, it must be equivalent to either 1 or 2 mod 3. We already know that p = 1 mod 2.

Here's one way to proceed (I'll let you fill in the gaps!)

From the above deductions, either (a) [itex]p = 2m+1[/itex] and [itex]p = 3n+1[/itex] or (b) [itex]p = 2m+1[/itex] and [itex]p = 3n+2[/itex] where m and n are integers.

In case (a), we have [itex]2m+1 = 3n+1[/itex] from which [itex]2m=3n[/itex]. Therefore, m is a multiple of 3 and n is even! You must conclude that p is a mulitple of 6 PLUS 1!

Can you handle case (b)?
 
  • #8
jhson114 said:
all whole numbers can be represented as either, 6n, 6n+1, 6n+2, 6n+3, 6n+4, or 6n+5, since 6n is a multiple of 6, 6n+2 and 6n+4 are multiples of 2, 6n+3 is a multiple of 3, this leaves 6n+1 and 6n+5 to be prime numbers.
Righty-oh, jhson114!
You don't need to prove that some prime numbers are of 6n+1 and some of 6n+5 kind.
You've just proven that all prime numbers can be 6n+1 or 6n+5 ONLY.
QED
 
Last edited:
  • #9
for b, 2m +1 = 3n +2 => 2m = 3n+1. does this mean n is even and m is a multiple of 6 PLUS 1; therefore P must be... i don't know.. T.T I know what you did with a, but having that extra 1 totally confused me on how to go about after setting the two equations equal to each other.
 
  • #10
jhson114 said:
Using this formula:
[tex]a \equiv b\left( {\bmod 6} \right),b \in \left\{ {\mathop 0\limits^\_ ,\mathop 1\limits^\_ ,\mathop 2\limits^\_ ,\mathop 3\limits^\_ ,\mathop 4\limits^\_ ,\mathop 5\limits^\_ } \right\},a \in Z[/tex]
which states that all whole numbers can be represented as either, 6n, 6n+1, 6n+2, 6n+3, 6n+4, or 6n+5, since 6n is a multiple of 6, 6n+2 and 6n+4 are multiples of 2, 6n+3 is a multiple of 3, this leaves 6n+1 and 6n+5 to be prime numbers. is this proof by exhausion or is it even a proof? can someone also tell me the name of the above formula?
That is a completely valid proof.
 

FAQ: Proof: any prime number greater than 3 is congruent to 1 or 5 mod 6

What is the significance of the statement "any prime number greater than 3 is congruent to 1 or 5 mod 6"?

The statement is a part of the proof for the famous Goldbach's Conjecture, which states that every even number greater than 4 can be written as the sum of two prime numbers. It serves as an important step in proving this conjecture to be true.

How does the proof for this statement work?

The proof is based on the fact that any prime number greater than 3 can be written in the form of 6n+1 or 6n+5, where n is a positive integer. This can be shown by considering the possible remainders when dividing by 6. From this, it can be proven that any prime number greater than 3 must be congruent to either 1 or 5 mod 6.

Can this statement be extended to all prime numbers?

No, this statement only applies to prime numbers greater than 3. For example, 2 and 3 are prime numbers but they are not congruent to 1 or 5 mod 6. This is because they have special properties as the smallest prime numbers.

Why is this statement important in number theory?

This statement is important because it helps us understand the distribution of prime numbers and the patterns that exist within them. It also plays a crucial role in the proof of Goldbach's Conjecture, which has been a long-standing open problem in number theory.

Are there any real-world applications of this statement?

While this statement may not have any direct real-world applications, it has helped mathematicians better understand the properties of prime numbers and their distribution. This can have potential implications in fields such as cryptography, where prime numbers are used in encryption algorithms.

Back
Top