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


by jhson114
Tags: congruent, greater, number, prime, proof
jhson114
jhson114 is offline
#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
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Tide
Tide is offline
#2
Oct23-05, 03:11 AM
Sci Advisor
HW Helper
P: 3,149
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
jhson114 is offline
#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
Benny is offline
#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
ivybond is offline
#5
Oct23-05, 03:52 AM
P: 37
Which integers can't be prime?
jhson114
jhson114 is offline
#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
Tide is offline
#7
Oct23-05, 04:10 AM
Sci Advisor
HW Helper
P: 3,149
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
ivybond is offline
#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
jhson114 is offline
#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
HallsofIvy is online now
#10
Oct23-05, 06:53 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,899
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