Register to reply

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

by jhson114
Tags: congruent, greater, number, prime, proof
Share this thread:
jhson114
#1
Oct23-05, 02:12 AM
P: 82
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
Phys.Org News Partner Science news on Phys.org
Security CTO to detail Android Fake ID flaw at Black Hat
Huge waves measured for first time in Arctic Ocean
Mysterious molecules in space
Tide
#2
Oct23-05, 03:11 AM
Sci Advisor
HW Helper
P: 3,147
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?
jhson114
#3
Oct23-05, 03:45 AM
P: 82
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 im 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.

Benny
#4
Oct23-05, 03:51 AM
P: 585
Proof: any prime number greater than 3 is congruent to 1 or 5 mod 6

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.
ivybond
#5
Oct23-05, 03:52 AM
P: 37
Which integers can't be prime?
jhson114
#6
Oct23-05, 04:04 AM
P: 82
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?
Tide
#7
Oct23-05, 04:10 AM
Sci Advisor
HW Helper
P: 3,147
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)?
ivybond
#8
Oct23-05, 04:31 AM
P: 37
Quote Quote by jhson114
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
jhson114
#9
Oct23-05, 04:43 AM
P: 82
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 dont 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.
HallsofIvy
#10
Oct23-05, 06:53 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,345
Quote Quote by jhson114
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.


Register to reply

Related Discussions
Prime number proof Calculus & Beyond Homework 2
Infineti number of prime numbers proof General Math 13
Prime Number Proof Precalculus Mathematics Homework 5
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number. Linear & Abstract Algebra 0