Difference between revisions of "Twin primes"
(Created page with "==Definition== Let {{M|p,q\in}}\mathbb{P} }} be given; here {{M|\mathbb{P} }} denotes the set of all primes. We say {{M|p}} and {{M|q}} are ''twin primes...") |
m |
||
Line 8: | Line 8: | ||
***# {{M|p+2\eq q\ \iff\ p\eq q-2}}, or | ***# {{M|p+2\eq q\ \iff\ p\eq q-2}}, or | ||
***# {{M|p-2\eq q\ \iff\ p\eq q+2}} | ***# {{M|p-2\eq q\ \iff\ p\eq q+2}} | ||
+ | ==Terminology== | ||
+ | Typically for twin primes {{M|u,v\in\mathbb{P} }} (which to be twins means they differ by 2) we call the smaller one {{M|p}} and the larger one {{M|q}} or just {{M|p+2}} (as if {{M|p}} is the smallest one, to be the smallest and differ by 2 from the other, the other must equal {{M|p+2}}, that is to say if {{M|q}} is the larger one, then {{M|q\eq p+2}}) | ||
+ | |||
+ | And we write these as: | ||
+ | * "{{M|(p,q)}} (or {{M|(p,p+2)}} instead) are twin primes" | ||
+ | Which uses the [[ordered pair]] notation where the first is the smaller prime and the 2nd the largest. | ||
+ | ==Examples== | ||
+ | The first few primes are: | ||
+ | * {{M|2,3,5,7,11,13,17,19,23,29}} and {{M|31}} | ||
+ | A prime {{M|p}} is twinned with another if {{M|p+2}} is also a prime, so going through this list, adding 2 to the number and searching for this new number in the list to find its twin shows us the first few twins are (using the smallest first convention, so {{M|(3,5)}} is considered as 1 set of twins, where the first prime is {{M|3}} and second {{M|5}} is not considered distinct from {{M|5}} as the first prime and {{M|3}} as its twin): | ||
+ | * {{M|(3,5)}}, {{M|(5,7}}}, {{M|(11,13)}}, {{M|(17,19)}}, and {{M|(29,31)}} | ||
+ | We can also rule out {{M|(31,33)}} as being twins as {{M|33}} isn't even prime, it can be divided by {{M|1}} and itself ({{M|33}}) yes, but also 11 and 3 (11 x 3 = 33) - which are 4 distinct divisors (there may be even more<ref group="Note">There isn't. As {{M|33\eq 3\times 11}} and {{M|3}} and {{M|11} are both prime, so we cannot divide further</ref>, I only have to show there is only 1 or at least 3 distinct divisors to prove something as not prime remember) | ||
==Motivation== | ==Motivation== | ||
The idea is to be able to talk about primes that come as close together as possible, and any such primes are called twin primes. The number {{M|2}} is prime on a technicality, as it has exactly 2 divisors, {{M|1}} and {{M|2}} itself all the other primes are odd numbers. | The idea is to be able to talk about primes that come as close together as possible, and any such primes are called twin primes. The number {{M|2}} is prime on a technicality, as it has exactly 2 divisors, {{M|1}} and {{M|2}} itself all the other primes are odd numbers. |
Revision as of 08:14, 25 September 2018
Contents
Definition
Let [ilmath]p,q\in[/ilmath][ilmath]\mathbb{P} [/ilmath] be given; here [ilmath]\mathbb{P} [/ilmath] denotes the set of all primes.
We say [ilmath]p[/ilmath] and [ilmath]q[/ilmath] are twin primes if(f)^{[Note 1]}:
- [ilmath]\vert p-q\vert\eq 2[/ilmath] where [ilmath]\vert\cdot\vert[/ilmath] refers to the absolute value
- This is to say that {{M|p}] and [ilmath]q[/ilmath] differ by [ilmath]2[/ilmath] or:
- either we have:
- [ilmath]p+2\eq q\ \iff\ p\eq q-2[/ilmath], or
- [ilmath]p-2\eq q\ \iff\ p\eq q+2[/ilmath]
- either we have:
- This is to say that {{M|p}] and [ilmath]q[/ilmath] differ by [ilmath]2[/ilmath] or:
Terminology
Typically for twin primes [ilmath]u,v\in\mathbb{P} [/ilmath] (which to be twins means they differ by 2) we call the smaller one [ilmath]p[/ilmath] and the larger one [ilmath]q[/ilmath] or just [ilmath]p+2[/ilmath] (as if [ilmath]p[/ilmath] is the smallest one, to be the smallest and differ by 2 from the other, the other must equal [ilmath]p+2[/ilmath], that is to say if [ilmath]q[/ilmath] is the larger one, then [ilmath]q\eq p+2[/ilmath])
And we write these as:
- "[ilmath](p,q)[/ilmath] (or [ilmath](p,p+2)[/ilmath] instead) are twin primes"
Which uses the ordered pair notation where the first is the smaller prime and the 2nd the largest.
Examples
The first few primes are:
- [ilmath]2,3,5,7,11,13,17,19,23,29[/ilmath] and [ilmath]31[/ilmath]
A prime [ilmath]p[/ilmath] is twinned with another if [ilmath]p+2[/ilmath] is also a prime, so going through this list, adding 2 to the number and searching for this new number in the list to find its twin shows us the first few twins are (using the smallest first convention, so [ilmath](3,5)[/ilmath] is considered as 1 set of twins, where the first prime is [ilmath]3[/ilmath] and second [ilmath]5[/ilmath] is not considered distinct from [ilmath]5[/ilmath] as the first prime and [ilmath]3[/ilmath] as its twin):
- [ilmath](3,5)[/ilmath], [ilmath](5,7[/ilmath]}, [ilmath](11,13)[/ilmath], [ilmath](17,19)[/ilmath], and [ilmath](29,31)[/ilmath]
We can also rule out [ilmath](31,33)[/ilmath] as being twins as [ilmath]33[/ilmath] isn't even prime, it can be divided by [ilmath]1[/ilmath] and itself ([ilmath]33[/ilmath]) yes, but also 11 and 3 (11 x 3 = 33) - which are 4 distinct divisors (there may be even more^{[Note 2]}, I only have to show there is only 1 or at least 3 distinct divisors to prove something as not prime remember)
Motivation
The idea is to be able to talk about primes that come as close together as possible, and any such primes are called twin primes. The number [ilmath]2[/ilmath] is prime on a technicality, as it has exactly 2 divisors, [ilmath]1[/ilmath] and [ilmath]2[/ilmath] itself all the other primes are odd numbers.
For any prime, [ilmath]p[/ilmath], that isn't 2, we have that [ilmath]p[/ilmath] is odd, then [ilmath]p+1[/ilmath] would be even, but even numbers are divisible by 2, thus [ilmath]p+1[/ilmath] is divisible by 1, itself ([ilmath]p+1[/ilmath]) and 2 - that's 3 divisors! So [ilmath]p+1[/ilmath] cannot be prime (if we ignore [ilmath]p\eq 2[/ilmath])
As such given any prime [ilmath]p[/ilmath] that isn't 2, we can be sure that [ilmath]p+1[/ilmath] is not prime.
However:
If [ilmath]p[/ilmath] is a prime that isn't 2, then as stated, [ilmath]p+1[/ilmath] is even, so [ilmath]p+2[/ilmath] is odd - and all primes except 2 are odd. Thus [ilmath]p+2[/ilmath] might be prime. We can't rule it out (without more information)
Note that if we consider [ilmath]p[/ilmath] to be any prime (so allowing 2) and using [ilmath]p+1[/ilmath] as the maybe next prime, the only "twins" we could have are [ilmath]2[/ilmath] and [ilmath]3[/ilmath] - these are the only primes to come [ilmath]1[/ilmath] apart for the reasons above.
- That is to say if we have [ilmath]p,q\in\mathbb{P} [/ilmath] and called them twins if [ilmath]\vert p-q\vert\eq 1[/ilmath] (that they differ by 1) - then the only twins that exist are [ilmath]2[/ilmath] and [ilmath]3[/ilmath].
- This isn't very interesting, so we don't waste "twins" on these only 2 exhibits.
See the proof ruling out [ilmath]p+1[/ilmath] as the next prime below for a rigorous proof of the above.
Proofs
Ruling out (any prime)+1 as the next prime
Recall that:
- All primes greater than or equal to 3 are odd (note this is the same as: all primes except 2 are odd)
Then let [ilmath]p\in\mathbb{P}_{\ge 3} [/ilmath] be given. That is to say "let [ilmath]p[/ilmath] be an arbitrary prime number greater than or equal to [ilmath]3[/ilmath]"
- From the above theorem, we have that [ilmath]\forall p\in\mathbb{P}[p\ge 3\implies (p\text{ is odd})][/ilmath]^{[Note 3]}
- As [ilmath]p\in\mathbb{P}_{\ge 3} [/ilmath] by definition of [ilmath]p[/ilmath], we see [ilmath]p[/ilmath] must be odd.
By this point the reader should understand that we have deduced our [ilmath]p[/ilmath] is an odd number (and by definition is a prime greater than or equal to [ilmath]3[/ilmath])
If we wish to consider the immediate next prime number, we could try [ilmath]p+1[/ilmath], however note that:
- adding 1 to an odd number yields an even number
- Explicitly we now know that [ilmath]p+1[/ilmath] is an even number
Now:
- [ilmath]p\ge 3[/ilmath], this means [ilmath]p+1\ge 4[/ilmath]
- For a number, say [ilmath]n[/ilmath], to be a prime number, [ilmath]n[/ilmath] must have exactly two distinct numbers that divide it, as we are only considering the numbers [ilmath]1,2,3,\ldots[/ilmath] we can state that "for any n we can always divide it by 1" and "we can always divide [ilmath]n[/ilmath] by [ilmath]n[/ilmath] itself" - note that if [ilmath]n\eq 1[/ilmath] then dividing it by [ilmath]n[/ilmath] is the same as dividing it by [ilmath]1[/ilmath] - so only one thing divides [ilmath]1[/ilmath], not two. This is why 1 is not prime. Prime numbers always have two distinct divisors, for example [ilmath]n[/ilmath]-n\eq 2 has 1 and 2 as divisors (hence 2 is a prime number), 3 has 1 and 3 for divisors so is also prime, 4 has 1,2 and 4 as divisors (which is 3 not 2 divisors) so 4 is not prime, so on.
- However we know that [ilmath]p+1[/ilmath] is an even number - which means we can divide it by [ilmath]2[/ilmath]
- The only way [ilmath]p+1[/ilmath] could be a prime number is if [ilmath]1[/ilmath] (which we can divide everything by) and [ilmath]2[/ilmath] (which we just showed we can divide [ilmath]p+1[/ilmath] by) are its only divisors
- We also know that [ilmath]p+1\ge 4[/ilmath], that is [ilmath]p+1[/ilmath] is greater than or equal to [ilmath]4[/ilmath], it is at least [ilmath]4[/ilmath].
- This means that there is no way [ilmath]p+1\eq 2[/ilmath], because if this were so then:
- [ilmath]2\eq p+1\ge 4[/ilmath] which would give [ilmath]2\ge 4[/ilmath] - and 2 is greater than or equal to 4 is absurd, so we can't have [ilmath]p+1\eq 2[/ilmath] (as if we did, we get the nonsense: [ilmath]2\ge 4[/ilmath])
- Thus we know [ilmath]p+1\neq 2[/ilmath] (the symbol: [ilmath]\neq[/ilmath] means "not equal")
- This means that there is no way [ilmath]p+1\eq 2[/ilmath], because if this were so then:
- We also know that [ilmath]p+1\ge 4[/ilmath], that is [ilmath]p+1[/ilmath] is greater than or equal to [ilmath]4[/ilmath], it is at least [ilmath]4[/ilmath].
- Now we have shown that [ilmath]1[/ilmath] divides [ilmath]p+1[/ilmath], along with [ilmath]2[/ilmath] divides [ilmath]p+1[/ilmath] (as [ilmath]p+1[/ilmath] is even) and also that [ilmath]p+1\ge 4[/ilmath] (which let us show that [ilmath]p+1\neq 2[/ilmath])
- As [ilmath]p+1\neq 2[/ilmath], when we say "we can divide it by 2" we know this is not dividing it by itself.
- We can always divide a number (we are working with [ilmath]1,2,3,\ldots[/ilmath] - so 0 can't play any role here) by itself: [ilmath]p+1[/ilmath] divided by [ilmath]p+1[/ilmath] is of course 1.
- Thus we claim [ilmath]1,2,p+1[/ilmath] are all divisors of [ilmath]p+1[/ilmath]
- We have shown [ilmath]p+1\neq 2[/ilmath] - so 2 and [ilmath]p+1[/ilmath] are different, it is obvious that [ilmath]1\neq 2[/ilmath], and if we have [ilmath]p+1\neq 1[/ilmath] then we have shown all 3 of these are different numbers
- But a prime only has exactly 2 divisors (this is why 1 isn't prime, it can only be divided by 1, we need to be able to divide it by exactly two things for it to be prime)
- So if we have 3 divisors, it can't be prime
- But a prime only has exactly 2 divisors (this is why 1 isn't prime, it can only be divided by 1, we need to be able to divide it by exactly two things for it to be prime)
- We have shown [ilmath]p+1\neq 2[/ilmath] - so 2 and [ilmath]p+1[/ilmath] are different, it is obvious that [ilmath]1\neq 2[/ilmath], and if we have [ilmath]p+1\neq 1[/ilmath] then we have shown all 3 of these are different numbers
- Thus we claim [ilmath]1,2,p+1[/ilmath] are all divisors of [ilmath]p+1[/ilmath]
- We can always divide a number (we are working with [ilmath]1,2,3,\ldots[/ilmath] - so 0 can't play any role here) by itself: [ilmath]p+1[/ilmath] divided by [ilmath]p+1[/ilmath] is of course 1.
- As [ilmath]p+1\neq 2[/ilmath], when we say "we can divide it by 2" we know this is not dividing it by itself.
- Let us now show that dividing by [ilmath]p+1[/ilmath] is not the same as dividing by [ilmath]1[/ilmath] (this is almost identical to the proof that dividing by 2 is not the same as dividing by [ilmath]p+1[/ilmath])
- Suppose that [ilmath]p+1\eq 1[/ilmath], then we'd have [ilmath]1\eq p+1\ge 4[/ilmath] which would give [ilmath]1\ge 4[/ilmath] - which is absurd
- Thus we can't have [ilmath]p+1\eq 1[/ilmath], as that would lead to absurd conclusions, so we must have [ilmath]p+1\neq 1[/ilmath]
- Suppose that [ilmath]p+1\eq 1[/ilmath], then we'd have [ilmath]1\eq p+1\ge 4[/ilmath] which would give [ilmath]1\ge 4[/ilmath] - which is absurd
- The only way [ilmath]p+1[/ilmath] could be a prime number is if [ilmath]1[/ilmath] (which we can divide everything by) and [ilmath]2[/ilmath] (which we just showed we can divide [ilmath]p+1[/ilmath] by) are its only divisors
- We have now shown that [ilmath]1[/ilmath], [ilmath]2[/ilmath] and [ilmath]p+1[/ilmath] are 3 distinct divisors of [ilmath]p+1[/ilmath] - thus [ilmath]p+1[/ilmath] cannot possibly be prime.
- However we know that [ilmath]p+1[/ilmath] is an even number - which means we can divide it by [ilmath]2[/ilmath]
- For a number, say [ilmath]n[/ilmath], to be a prime number, [ilmath]n[/ilmath] must have exactly two distinct numbers that divide it, as we are only considering the numbers [ilmath]1,2,3,\ldots[/ilmath] we can state that "for any n we can always divide it by 1" and "we can always divide [ilmath]n[/ilmath] by [ilmath]n[/ilmath] itself" - note that if [ilmath]n\eq 1[/ilmath] then dividing it by [ilmath]n[/ilmath] is the same as dividing it by [ilmath]1[/ilmath] - so only one thing divides [ilmath]1[/ilmath], not two. This is why 1 is not prime. Prime numbers always have two distinct divisors, for example [ilmath]n[/ilmath]-n\eq 2 has 1 and 2 as divisors (hence 2 is a prime number), 3 has 1 and 3 for divisors so is also prime, 4 has 1,2 and 4 as divisors (which is 3 not 2 divisors) so 4 is not prime, so on.
Notes
- ↑ See: Definitions and iff
- ↑ There isn't. As [ilmath]33\eq 3\times 11[/ilmath] and [ilmath]3[/ilmath] and {{M|11} are both prime, so we cannot divide further
- ↑ Read [ilmath]\forall p\in\mathbb{P}[p\ge 3\implies (p\text{ is odd})][/ilmath] as:
- forall [ilmath]p[/ilmath] in the set of primes we have [ if we have [ilmath]p\ge 3[/ilmath] then we have ([ilmath]p[/ilmath] is an odd number) ]