TIL...... [modified]
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics... Where does 24 come from? Since p is prime and greater than 5, p cannot be an even number. So: p2-1=(p-1)*(p+1). Like p is odd, both (p-1) and (p+1) are even, so we can say: p2-1=2a*2b=4ab. Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like: p2-1=4a*2c=8ac or p2-1=4b*2d=8bd I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so: p2-1=8a*3d=24ad or p2-1=8c*3e=24ce And there it is.
-
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics... Where does 24 come from? Since p is prime and greater than 5, p cannot be an even number. So: p2-1=(p-1)*(p+1). Like p is odd, both (p-1) and (p+1) are even, so we can say: p2-1=2a*2b=4ab. Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like: p2-1=4a*2c=8ac or p2-1=4b*2d=8bd I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so: p2-1=8a*3d=24ad or p2-1=8c*3e=24ce And there it is.
You haven't explained the last step correctly, and the statement
_Erik_ wrote:
Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3
is wrong.
-
You haven't explained the last step correctly, and the statement
_Erik_ wrote:
Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3
is wrong.
It is not wrong, becouse p is a prime number, what means: if p mod 3 = 1 then (p-1) mod 3=0, so (p-1) is multiple of 3. if p mod 3 = 2 then (p+1) mod 3=0, so (p+1) is multiple of 3. if p mod 3 = 0 then p would not be prime and we would not be following our premise
-
It is not wrong, becouse p is a prime number, what means: if p mod 3 = 1 then (p-1) mod 3=0, so (p-1) is multiple of 3. if p mod 3 = 2 then (p+1) mod 3=0, so (p+1) is multiple of 3. if p mod 3 = 0 then p would not be prime and we would not be following our premise
Yes, sorry - I was forgetting that p is prime! Time to knock off for the day I think...
-
Well, I know you are not asking for a mathematical proof, but like I am much better at maths than metaphisics... Where does 24 come from? Since p is prime and greater than 5, p cannot be an even number. So: p2-1=(p-1)*(p+1). Like p is odd, both (p-1) and (p+1) are even, so we can say: p2-1=2a*2b=4ab. Like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 4, so 2a is multiple of 4 or 2b is multiple of 4, so we can express this like: p2-1=4a*2c=8ac or p2-1=4b*2d=8bd I will examine just one of these two cases becouse they are symmetrical. Now, like (p-1) and (p+1) are two consecutive even numbers, one of them must be multiple of 3, so: p2-1=8a*3d=24ad or p2-1=8c*3e=24ce And there it is.
-
Try
p ^ 2 = 1 + 24 * (p - 6)
Just say 'NO' to evaluated arguments for diadic functions! Ash
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
For p = 5, p^2 = 24 * 1 + 1 All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes. p^2 = 900*k^2 + 60*k*l + l^2 Rewrite the first 2 terms as 60*( 15*k^2 + k*l ). The sum in the parentheses is always even, so the entire expression is divisible by 24. We are left with l^2. By inspection: 1^2 = 24 * 0 + 1 7^2 = 24 * 2 + 1 11^2 = 24 * 5 + 1 13^2 = 24 * 7 + 1 17^2 = 24 * 12 + 1 19^2 = 24 * 15 + 1 23^2 = 24 * 22 + 1 29^2 = 24 * 35 + 1 QED
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
So to put it another way, to test the primality of any number, first square it, then mod it by 24. If the answer is 1, it's possibly prime. Nifty. Perhaps impractical for cryptological purposes, but nifty nonetheless. Reminds me of p = 6*n + 1 OR p = 6*n - 1 for all p given some n.
-
For p = 5, p^2 = 24 * 1 + 1 All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes. p^2 = 900*k^2 + 60*k*l + l^2 Rewrite the first 2 terms as 60*( 15*k^2 + k*l ). The sum in the parentheses is always even, so the entire expression is divisible by 24. We are left with l^2. By inspection: 1^2 = 24 * 0 + 1 7^2 = 24 * 2 + 1 11^2 = 24 * 5 + 1 13^2 = 24 * 7 + 1 17^2 = 24 * 12 + 1 19^2 = 24 * 15 + 1 23^2 = 24 * 22 + 1 29^2 = 24 * 35 + 1 QED
Daniel Pfeffer wrote:
All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes.
That's quite an assertion... not saying it's wrong, but it can't be s starting point for a proof of anything; it has to be proved first. Surely.
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
NeverHeardOfMe wrote:
If p is prime, then p ^ 2 = 1 + 24 * n, for some n Don't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!)
It only needs a small modification to use 42: If p is prime and p > 7 then
p^6 = 1 + 42n for some n
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
modified on Wednesday, November 10, 2010 11:37 PM
-
...an extraordinary fact - probably known to half of you, but nevertheless I thought I'd share it. It's not an alogorithm, but never mind! The square of any prime number >= 5 can be expressed as 1 + a multiple of 24 or
If p is prime, then p ^ 2 = 1 + 24 * n, for some nDon't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!) [edit] When I ask "where does 24 come from?" I am not asking for a mathermatical proof - I can look that up myself. It's more just a metaphysical musing...)modified on Thursday, November 4, 2010 6:37 AM
Your algorithm finds the nth prime with reasonable speed. If you eliminate the (1 + (24 * N))^.5 that are not integers the calculation is almost trivial. This could be very useful in cryptographic and password gen. apps.
"Coding for fun and profit ... mostly fun"
-
Daniel Pfeffer wrote:
All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes.
That's quite an assertion... not saying it's wrong, but it can't be s starting point for a proof of anything; it has to be proved first. Surely.
NeverHeardOfMe wrote:
Daniel Pfeffer wrote: All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes. That's quite an assertion... not saying it's wrong, but it can't be s starting point for a proof of anything; it has to be proved first. Surely.
I have simply performed the first three steps of the Sieve of Erathostenes, eliminating all numbers divisible by 2, 3 or 5, as follows: 30 is the product of the first three primes (2 * 3 * 5). All integers may be represented as n = 30*k + l where k is any integer, and l is any integer in the range { 0..29 }. Of these integers: Any integers of the form 30*k + {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28} are divisible by 2. Any integers of the form 30*k + {0, 3, 6, 9, 12, 15, 18, 21, 24, 27} are divisible by 3. Any integers of the form 30*k + {0, 5, 10, 15, 20, 25} are divisible by 5. When all integers known to be divisible by 2, 3, or 5 are removed, we are left with 30*k + {1, 7, 11, 13, 17, 19, 23, 29} that MAY be prime.
-
Daniel Pfeffer wrote:
All primes > 5 have the form p = 30*k + l, where l is 1, 7, 11, 13, 17, 19, 23 or 29. All other values of l have a common factor > 1 with 30, and therefore cannot produce primes.
That's quite an assertion... not saying it's wrong, but it can't be s starting point for a proof of anything; it has to be proved first. Surely.
Now that I think of it, there is no need to carry the Sieve of Erathostenes beyond the second step. All numbers may be written in the form n = 6*k +l where k is any integer and l = { 0.. 5 }. Numbers of the form 6*k + {0, 2, 4} are divisible by 2. Numbers of the form 6*k + {0, 3} are divisible by 3 Numbers of the form 6*k + {1, 5} MAY be prime. With the exception of {2,3} {which are divisible by 2 and by 3, respectively), all primes fit this template. p^2 = {6*k + l)^2 p^2 = 36*k^2 + 12*k*l + l^2 p^2 = 12*(3*k^2 + k*l} + l^2 The value in the parentheses is always even, and therefore the first term is divisible by 24. We are left with l^2. By inspection: 1^2 = 1 = 24*0 + 1 5^2 = 25 = 24*1 + 1 QED
-
NeverHeardOfMe wrote:
If p is prime, then p ^ 2 = 1 + 24 * n, for some n Don't know about you, but I think that's quite amazing. Why is it true at all, and given that it is, where does 24 come from?! (Pity it's not 42 really!)
It only needs a small modification to use 42: If p is prime and p > 7 then
p^6 = 1 + 42n for some n
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
modified on Wednesday, November 10, 2010 11:37 PM
Hello cp9876, the correct formula is actually
p^6 = 1 + 84n for some n, and p being a prime >7
With
84 = 2 * 42, your version is not wrong either, but only half of the truth. At a first glance, it looked like a big step forward to proving the universal truth and meaning of everything (which is said to be 42), but as soon as I started to find the proof, doubts were shed on this old belief. Let me now prove my version of the formula, following the steps outlined by _Erik_ previously in this thread. We have to show thatp^6 - 1can be divided by 84, and I will do that by showing that it can be divided by 4, 3, and 7 (because4*3*7=84) at the same time. The first two factors are quite trivial: I)(p^6 - 1) = (p^3 - 1) * (p^3 + 1), since p is prime and > 2, it is an odd number, thusp^3
is an odd number, and consequently both
(p^3 - 1)and(p^3 + 1)are even numbers, hence:(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 2*a * 2*b = 4*a*b
II) With p being a prime and p > 3,
p^3
is an odd number which cannot be divided by 3. Consequently, either
(p^3 - 1)(x)or(p^3 + 1)can be divided by 3 (for a more detailed proof of this, see a post from _Erik_ above). Hence:(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 3*c * d
III) I did not find a smart proof for that "7", but the number of cases can be simply enumerated: With p being prime and > 7,
p = (7*o + e) with o being an odd integer and e an even integer in {2; 4; 6; 8; 10; 12}
Now we have to prove that either
(p^3 - 1)(x)or(p^3 + 1)can be divided by 7.p^3 = (7*o + e)^3 = (7*o)^3 + 3*e*(7*o)^2 + 3*(7*o)*e^2 + e^3
It is easy to see that each of the summands
(7*o)^3,3*e*(7*o)^2,3*(7*o)*e^2can be divided by 7. We need to concentrate only one^3: eithere^3+1(x)ore^3-1must be dividable by 7. I enumerate all the 6 possible cases and then dicide for+1or-1:- e=2: e^3= 8 => -1
- e=4: e^3= 64 => -1
- e=6: e^3= 216 => +1
- e=8: e^3= 512 => +1
- e=10: e^3=1000 => +1
- e=12: e^3=1728 => +1
Now we can write:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 7*e * f
And consequently here it is:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 4*3*7*n
Now we must recognize the full proven truth of 84. Previously, we were told half of the truth
-
Hello cp9876, the correct formula is actually
p^6 = 1 + 84n for some n, and p being a prime >7
With
84 = 2 * 42, your version is not wrong either, but only half of the truth. At a first glance, it looked like a big step forward to proving the universal truth and meaning of everything (which is said to be 42), but as soon as I started to find the proof, doubts were shed on this old belief. Let me now prove my version of the formula, following the steps outlined by _Erik_ previously in this thread. We have to show thatp^6 - 1can be divided by 84, and I will do that by showing that it can be divided by 4, 3, and 7 (because4*3*7=84) at the same time. The first two factors are quite trivial: I)(p^6 - 1) = (p^3 - 1) * (p^3 + 1), since p is prime and > 2, it is an odd number, thusp^3
is an odd number, and consequently both
(p^3 - 1)and(p^3 + 1)are even numbers, hence:(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 2*a * 2*b = 4*a*b
II) With p being a prime and p > 3,
p^3
is an odd number which cannot be divided by 3. Consequently, either
(p^3 - 1)(x)or(p^3 + 1)can be divided by 3 (for a more detailed proof of this, see a post from _Erik_ above). Hence:(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 3*c * d
III) I did not find a smart proof for that "7", but the number of cases can be simply enumerated: With p being prime and > 7,
p = (7*o + e) with o being an odd integer and e an even integer in {2; 4; 6; 8; 10; 12}
Now we have to prove that either
(p^3 - 1)(x)or(p^3 + 1)can be divided by 7.p^3 = (7*o + e)^3 = (7*o)^3 + 3*e*(7*o)^2 + 3*(7*o)*e^2 + e^3
It is easy to see that each of the summands
(7*o)^3,3*e*(7*o)^2,3*(7*o)*e^2can be divided by 7. We need to concentrate only one^3: eithere^3+1(x)ore^3-1must be dividable by 7. I enumerate all the 6 possible cases and then dicide for+1or-1:- e=2: e^3= 8 => -1
- e=4: e^3= 64 => -1
- e=6: e^3= 216 => +1
- e=8: e^3= 512 => +1
- e=10: e^3=1000 => +1
- e=12: e^3=1728 => +1
Now we can write:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 7*e * f
And consequently here it is:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 4*3*7*n
Now we must recognize the full proven truth of 84. Previously, we were told half of the truth
for Bernard proveth that if p > 7 then
p^6 = 1 + 84n
and thus 84 is the full proven truth, twice the truth of 42. However 84 is but an imposter of the full proven truth. As Bernard showeth, for p an odd prime, p^3 is an odd number, and consequently both (p^3 - 1) and (p^3 + 1) are even, but as they are consecutive even numbers then one must be divisible by 4, hence:
(p^6 - 1) = (p^3 - 1) * (p^3 + 1) = 2*a * 4*b = 8*a*b
Thus we have the next full proven truth that
p^6 = 1 + 168n
But there is more... As p is prime, then the residue modulo 9 shall be one of {+/- 1, +/- 2, +/- 4} which using the fact that 2^3 = 8 = -1(mod 9), and 4 = 2^2 so 4^3 = 2^6 = 1(mod 9), then p^3 = +/- 1 (mod 9), then p^6 = 1 (mod 9) and hence:
(p^6 - 1) = 9*c
And so we have the next proven truth that if p is prime and p is not 2,3 or 7 then:
p^6 = 1 + 504n
and the full truth is that there is no number higher than 504 to satisfy this.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."