Prime numbers test primality - with proof written in invisible ink - Page 2

CRGreathouse · 2018-04-05, 18:23

Quote:

Originally Posted by Godzilla

maybe I expressed myself badly, but even if I made wrong statements in my work, I can always say that wrong for even pseudoprime and multiples of 5 and very few odd pseudoprime numbers (five numbers excluded number 1 up to 1000), I know you mean that it is not a universal formula, but I wanted to know if it was already known as 2 ^ 2p-1 = 2 (mod p) or was it unknown as a consequence of Fermat's little Theorem?

It's wrong for all 2-pseudoprimes, odd and even. This follows pretty much directly from their definitions and Fermat's little theorem, yes.

Godzilla · 2018-04-05, 19:30

Quote:

Originally Posted by CRGreathouse

It's wrong for all 2-pseudoprimes, odd and even. This follows pretty much directly from their definitions and Fermat's little theorem, yes.

EDIT EDIT NOT $(p+1)*2^{p-1}\bmod p = 1$ BUT $(p+1)*(2^{p}-1)\bmod p = 1$
Is it possible to control this work up to 1000? fails only for the semi-prime number 341.

Is a Prime Numer if :

$(p+1)*(2^{p}-1)\bmod p = 1$ Than $p$ Is a Prime Number

$(p+1)*(2^{p}-1)\bmod (p+1) = 0$ Than $p$ Is a Prime Number

Isn't a Prime Number if

$(p+1)*(2^{p}-1)\bmod p \ne 1$ Than $p$ Is not a Prime Number

$(p+1)*(2^{p}-1)\bmod (p+1) = 0$ Than $p$ Is not a Prime Number

Example :

$(3+1)*(2^{3}-1)=28 \bmod 3 = 1$
$(3+1)*(2^{3}-1)=28 \bmod 4 = 0$

Batalov · 2018-04-05, 20:47

Quote:

Originally Posted by Godzilla

...
$(p+1)*(2^{p}-1)\bmod p = 1$ Than $p$ Is a Prime Number

/sigh/ That's "not even wrong!"

If a == b (mod p), then (p+1)*a == b (mod p).

The "(p+1)*" part is blatantly useless.

...Because /gasp/ p+1 == 1 (mod p). Multiplying by it is like multiplying by 1.
"Who knew?!" (c) D.Trump

Quote:

Originally Posted by Godzilla

...
$(p+1)*(2^{p}-1)\bmod (p+1) = 0$ Than $p$ Is not a Prime Number

This is even more genius! You are multiplying by zero!
"Who knew that you can get anything other that zero after multiplying by zero?!" It's an amazing discovery, no doubt!

Godzilla · 2018-04-05, 21:16

Quote:

Originally Posted by Batalov

/sigh/ That's "not even wrong!"

If a == b (mod p), then (p+1)*a == b (mod p).

The "(p+1)*" part is blatantly useless.

...Because /gasp/ p+1 == 1 (mod p). Multiplying by it is like multiplying by 1.
"Who knew?!" (c) D.Trump

This is even more genius! You are multiplying by zero!
"Who knew that you can get anything other that zero after multiplying by zero?!" It's an amazing discovery, no doubt!

in fact when it is equal to zero it does not make sense, I would like to test from 1 up to 1000 when it is equal to 1 (it's prime) and different from 1 (it's not prime), I did not understand what you said about this, you already know the solution ?

CRGreathouse · 2018-04-05, 21:52

Batalov's criticism is correct, the second equation is trivially true for all p and the first simplifies to
$2^p \equiv 2 \pmod p$
which shows that it's just (a slightly weaker form of) the Fermat/2-pseudoprime test.

retina · 2018-04-06, 01:19

Quote:

Originally Posted by Godzilla

This is right, but up to 1000 there is a relatively small error. if we then exclude the even numbers and the multiple numbers of 5, the error is even less

And if you exclude all multiples of 3 then the error is even less. And if you exclude all multiples of 7 then the error is even less. And if you exclude all multiples of 11 then the error is even less. And if you exclude all multiples of 13 then the error is even less. And if you exclude all multiples of 17 then the error is even less. etc. etc. etc.

So all you need to do is feed in a list of prime numbers, and exclude all the multiples of them, and then your method will find all prime numbers. Oh wait ...

Dr Sardonicus · 2018-04-06, 13:10

Quote:

Originally Posted by Godzilla

EDIT EDIT [snip]
$(p+1)*(2^{p}-1)\bmod (p+1) = 0$ Than $p$ Is a Prime Number
[snip]
$(p+1)*(2^{p}-1)\bmod (p+1) = 0$ Than $p$ Is not a Prime Number

Uh-oh, trouble! I would suggest another EDIT:

If $(p+1)*(2^{p}-1)\bmod (p+1) \ne 0$ then $p$ is a prime number
[snip]
If $(p+1)*(2^{p}-1)\bmod (p+1) \ne 0$ then $p$ is not a prime number

on the grounds that any implication with a a false premise is (logically) "true."

Godzilla · 2018-04-06, 13:13

If $(p+1)*(2^{p}-1)\bmod (p) = 1$ then $p$ is a prime number

Up to 1000 fails only for three numbers 5 , 341 , 561.
Edit citation.I did not notice.

Dr Sardonicus · 2018-04-06, 13:28

Er, ah, that last post is misquoting me. And the poster is misquoting himself. MODERATOR!

Godzilla · 2018-04-06, 13:34

Quote:

Originally Posted by Dr Sardonicus

Er, ah, that last post is misquoting me. And the poster is misquoting himself. MODERATOR!

Sorry

CRGreathouse · 2018-04-06, 14:03

Quote:

Originally Posted by Godzilla

If $(p+1)*(2^{p}-1)\bmod (p) = 1$ then $p$ is a prime number

Up to 1000 fails only for three numbers 5 , 341 , 561.

It's actually ok for 5, but it also fails for 1 and 645.

The next batch:

Code:

1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341, 30121, 30889, 31417, 31609, 31621, 33153, 34945, 35333, 39865, 41041, 41665, 42799, 46657, 49141, 49981, 52633, 55245, 57421, 60701, 60787, 62745, 63973, 65077, 65281, 68101, 72885, 74665, 75361, 80581, 83333, 83665, 85489, 87249, 88357, 88561, 90751, 91001, 93961, 101101, 104653, 107185, 113201, 115921, 121465, 123251, 126217, 129889, 129921, 130561, 137149, 149281, 150851, 154101, 157641, 158369, 161038, 162193, 162401, 164737, 172081, 176149, 181901, 188057, 188461, 194221, 196021, 196093, 204001, 206601, 208465, 212421, 215265, 215326, 215749, 219781, 220729, 223345, 226801, 228241, 233017, 241001, 249841, 252601, 253241, 256999, 258511, 264773, 266305, 271951, 272251, 275887, 276013, 278545, 280601, 282133, 284581, 285541, 289941, 294271, 294409, 314821, 318361, 323713, 332949, 334153, 340561, 341497, 348161, 357761, 367081, 387731, 390937, 396271, 399001, 401401, 410041, 422659, 423793, 427233, 435671, 443719, 448921, 449065, 451905, 452051, 458989, 464185, 476971, 481573, 486737, 488881, 489997, 493697, 493885, 512461, 513629, 514447, 526593, 530881, 534061, 552721, 556169, 563473, 574561, 574861, 580337, 582289, 587861, 588745, 604117, 611701, 617093, 622909, 625921, 635401, 642001, 647089, 653333, 656601, 657901, 658801, 665281, 665333, 665401, 670033, 672487, 679729, 680627, 683761, 688213, 710533, 711361, 721801, 722201, 722261, 729061, 738541, 741751, 742813, 743665, 745889, 748657, 757945, 769567, 769757, 786961, 800605, 818201, 825265, 831405, 838201, 838861, 841681, 847261, 852481, 852841, 873181, 875161, 877099, 898705, 915981, 916327, 934021, 950797, 976873, 983401, 997633

2018-04-06, 13:13	#19
Godzilla May 2016 2×3⁴ Posts	If $(p+1)(2^{p}-1)\bmod (p) = 1$ then $p$ is a prime number Up to 1000 fails only for three numbers 5 , 341 , 561. Edit citation.I did not notice. Last fiddled with by Godzilla on 2018-04-06 at 13:33*

2018-04-06, 13:28	#20
Dr Sardonicus Feb 2017 Nowhere 1001000100011₂ Posts	Er, ah, that last post is misquoting me. And the poster is misquoting himself. *MODERATOR!* Last fiddled with by Dr Sardonicus on 2018-04-06 at 13:30

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
500€ Reward for a proof for the Wagstaff primality test conjecture	Tony Reix	Wagstaff PRP Search	7	2013-10-10 01:23
Proof of Primality Test for Fermat Numbers	princeps	Math	15	2012-04-02 21:49
The fastest primality test for Fermat numbers.	Arkadiusz	Math	6	2011-04-05 19:39
PRIMALITY PROOF for Wagstaff numbers!	AntonVrba	Math	96	2009-02-25 10:37
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2018-04-05, 21:52	#16
CRGreathouse Aug 2006 175B₁₆ Posts	Batalov's criticism is correct, the second equation is trivially true for all p and the first simplifies to $2^p \equiv 2 \pmod p$ which shows that it's just (a slightly weaker form of) the Fermat/2-pseudoprime test.