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

Dr Sardonicus · 2018-04-06, 15:18

It is perhaps not-uninteresting to see how changing the usual Fermat base-2 pseudoprime condition

2^n-1 == 1 (mod n) to

2^2n-1 == 2 (mod n)

actually weakens it. The latter condition can be rewritten as

2*2^2n-2 == 2 (mod n), or

2*(2^n-1)² == 2 (mod n).

If p is an odd prime divisor of n, we can cancel a factor of 2 (mod p), giving

(2^n-1)² == 1 (mod p), or

2^n-1 == 1 or -1 (mod p),

whereas in the original congruence we would have

2^n-1 == 1 (mod p).

This is why 15 "passes" the "new and improved" test, whereas it fails to be a Fermat base-2 pseudoprime;

2¹⁴ == 1 (mod 3), but 2¹⁴ == -1 (mod 5).

We can say a little more if n is odd, an odd prime p divides n, and 2^n-1 == -1 (mod p). For then, n - 1 is even, so that -1 is a quadratic residue (mod p), so that p is congruent to 1 (mod 4). Further, n-1 must be divisible by 2 fewer times than p-1 is.

LaurV · 2018-04-07, 08:22

https://oeis.org/A001567

Edit @Dr.S: you are right with the concept, this is weakening the condition, but you are making a mess of "n" and "p" in the post. You can always simplify by 2 if n is not even, as 2 is never a factor of n. No need any p. If n is odd, $(2^{n-1})^2=1$ (mod n) and the test is passed also by the n's which have 2^(n-1)=-1 (mod n), at least.

Dr Sardonicus · 2018-04-07, 13:22

(my emphasis added)

Quote:

Originally Posted by LaurV

https://oeis.org/A001567

Edit @Dr.S: you are right with the concept, this is weakening the condition, but you are making a mess of "n" and "p" in the post. You can always simplify by 2 if n is not even, as 2 is never a factor of n. No need any p. If n is odd, $(2^{n-1})^2=1$ (mod n) and the test is passed also by the n's which have 2^(n-1)=-1 (mod n), at least.

By my "messy" argument, it follows that n-1 would have to be divisible by 2 fewer times than p-1, for every prime factor p of n. Finding such an n > 1 might be difficult...

LaurV · 2018-04-09, 05:34

You are totally right, they are more common than the "-1" version, I may not have understood why you need to split n. Such example include (beside 15 mentioned by you) also 85, 91, 435, etc that pass the ^2 test but do not pass the Sarus test.

Dr Sardonicus · 2018-04-09, 13:34

Quote:

Originally Posted by LaurV

You are totally right, they are more common than the "-1" version, I may not have understood why you need to split n. Such example include (beside 15 mentioned by you) also 85, 91, 435, etc that pass the ^2 test but do not pass the Sarus test.

Just to be clear: there are no n > 1 for which 2^n-1 == -1 (mod n).

(There is nothing special about the base 2 in this regard).

I looked at the prime factors of n as a way to make a statement that was true regardless of whether n was even or odd. The implication

2*(2^n-1)^2 == 2 (mod n) implies (2^n-1)^2 == 1 (mod n)

holds only for odd n. (For even n, you have to reduce the modulus to n/2 when you cancel a factor of 2.)

The consequence

2^n-1 == +/- 1 (mod p) for every odd prime factor p of n

cannot be reversed; that it, 2^n-1 need not be congruent to 1 or -1 (mod n). In fact, as I point out, if

2^n-1 == -1 (mod p) for an odd prime divisor p of n,

then n-1 must be divisible by 2 at least one time fewer than is p-1 (in fact, exactly one time fewer than the multiplicative order of Mod(2,p)). Obviously this condition cannot hold for every odd prime divisor of n if n is odd. It can hold if n is even but in that case, obviously

2^n-1 =/= -1 (mod n),

although for even n

2^n-1 == -1 (mod n/2)

is possible, e.g. n = 6, 66, 946. For such n, the multiplicative order of Mod(2,p) must be divisible by 2, but not by 4, for every odd prime factor p of n.

For odd n, n-1 is even, and 2^n-1 == -1 (mod n) is impossible; but 2^n-1 == -1 for some prime divisors of n, (and +1 for the rest, of which there must be at least one) is possible. For example

n = 85, 2⁸⁴ == +1 (mod 5), 2⁸⁴ == -1 (mod 17)

n = 91; 2⁹⁰ == +1 (mod 7), 2⁹⁰ == -1 (mod 13)

n = 435; 2⁴³⁴ == +1 (mod 3), 2⁴³⁴ == -1 (mod 5), and 2⁴³⁴ == -1 (mod 29).

It is the n's for which 2^n-1 == -1 (mod p) for some odd prime factors p of n (and +1 for the rest) which fool the "new and improved" test, but are not base-2 pseudoprimes.

BTW, I had to really look hard to find "Sarus numbers" as a synonym for "Poulet numbers," i.e composite numbers n for which 2^n == 2 (mod n), so thanks for adding to my vocabulary!

Godzilla · 2018-04-10, 03:56

Quote:

Originally Posted by CRGreathouse

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

Adding 0.5 is curious

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

Example If $(2)*(2^{1}-1)\bmod (1.5) >0$ then $p$ is not a prime number

CRGreathouse · 2018-04-10, 15:30

Quote:

Originally Posted by Godzilla

Adding 0.5 is curious

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

I'm assuming you intend p to be an integer, so a number is 0 mod p + 0.5 if it is either 0 mod 2p + 1 or p + 0.5 mod 2p + 1. Since (p+1)*(2^p-1) is an integer only the former is possible so your claim is:

If $(p+1)(2^p-1)\equiv0\pmod{2p+1}$ then p is prime.

The first failures are 8, 15, 20, 35, 36, 39, 44, 48, 51, 56, 63, 68, 75, 95, 96, 99, 111, 116, 119, 120, 128, 135, 140, 155, 156, 168, 170, 176, 183, 200, 204, 215, 216, 219, 224, 228, 231, 243, 260, 280, 284, 288, 296, 299, 300, 303, 308, 315, 320, 323, 336, 363, 371, 375, 380, 384, 404, 411, 428, 440, 455, 459, 464, 468, 476, 483, 488, 495, 504, 515, 516, 519, 524, 531, 543, 548, 551, 552, 564, 575, 576, 596, 600, 608, 611, 615, 624, 639, 644, 648, 651, 660, 663, 680, 699, 704, 711, 716, 723, 735, 740, 744, 755, 771, 776, 779, 783, 791, 800, 803, 804, 828, 831, 848, 860, 864, 876, 879, 888, 891, 900, 915, 923, 935, 936, 939, 944, 952, 956, 975, 996, 999, ....

Godzilla · 2018-04-15, 13:29

@CRGreathouse could you take a test up to 1000? . I would be very grateful. Thanks.

If $(0.5)*((1-2^{-p})*(2^p-1))\pmod{p}=0$ then p is prime.

P.S.
It fails only for numer 2 at the moment.

VBCurtis · 2018-04-15, 17:05

Quote:

Originally Posted by Godzilla

P.S.
It fails only for number 2 at the moment.

"at the moment" tells us nothing. You tested it up to what number, exactly? Your statement could be interpreted as "I tested 2 through 5, and it worked for three of them."

science_man_88 · 2018-04-15, 18:06

Quote:

Originally Posted by Godzilla

@CRGreathouse could you take a test up to 1000? . I would be very grateful. Thanks.

If $(0.5)*((1-2^{-p})*(2^p-1))\pmod{p}=0$ then p is prime.

P.S.
It fails only for numer 2 at the moment.

1 mod 3/ 2 mod 3=2 mod 3; so you get 2 mod 3 * 2 mod 3 * 1 mod 3= 1 mod 3= 0 mod 3 and the test fails for p=3. For p=5, you get 4 mod 5= 0 mod 5. Emphasis added to the typo made in stating the hypothesis.

Batalov · 2018-04-15, 18:50

Quote:

Originally Posted by Godzilla

If $(0.5)*((1-2^{-p})*(2^p-1))\pmod{p}=0$ then p is prime.

The "if 0.5 * ... == 0" part is especially priceless.
It is very important to multiply by 0.5 before comparing to 0. "ORLY? Really, really."

Another excellent solution is to square something before comparing to 0. Really, really. And indeed, that's what is done here.

And finally, looks like there is a couple typos, too. (should be raising to power of p-1, not p.)

2018-04-06, 15:18	#23
Dr Sardonicus Feb 2017 Nowhere 11043₈ Posts	It is perhaps not-uninteresting to see how changing the usual Fermat base-2 pseudoprime condition 2^n-1 == 1 (mod n) to 2^2n-1 == 2 (mod n) actually weakens it. The latter condition can be rewritten as 22^2n-2 == 2 (mod n), or 2(2^n-1)² == 2 (mod n). If p is an odd prime divisor of n, we can cancel a factor of 2 (mod p), giving (2^n-1)² == 1 (mod p), or 2^n-1 == 1 or -1 (mod p), whereas in the original congruence we would have 2^n-1 == 1 (mod p). This is why 15 "passes" the "new and improved" test, whereas it fails to be a Fermat base-2 pseudoprime; 2¹⁴ == 1 (mod 3), but 2¹⁴ == -1 (mod 5). We can say a little more if n is odd, an odd prime p divides n, and 2^n-1 == -1 (mod p). For then, n - 1 is even, so that -1 is a quadratic residue (mod p), so that p is congruent to 1 (mod 4). Further, n-1 must be divisible by 2 fewer times than p-1 is. Last fiddled with by Dr Sardonicus on 2018-04-06 at 15:19

2018-04-07, 08:22	#24
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 Posts	https://oeis.org/A001567 Edit @Dr.S: you are right with the concept, this is weakening the condition, but you are making a mess of "n" and "p" in the post. You can always simplify by 2 if n is not even, as 2 is never a factor of n. No need any p. If n is odd, \((2^{n-1})^2=1\) (mod n) and the test is passed also by the n's which have 2^(n-1)=-1 (mod n), at least. Last fiddled with by LaurV on 2018-04-07 at 08:29

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-09, 05:34	#26
LaurV Romulan Interpreter Jun 2011 Thailand 258B₁₆ Posts	You are totally right, they are more common than the "-1" version, I may not have understood why you need to split n. Such example include (beside 15 mentioned by you) also 85, 91, 435, etc that pass the ^2 test but do not pass the Sarus test.

2018-04-15, 13:29	#30
Godzilla May 2016 2×3⁴ Posts	@CRGreathouse could you take a test up to 1000? . I would be very grateful. Thanks. If $(0.5)((1-2^{-p})(2^p-1))\pmod{p}=0$ then p is prime. P.S. It fails only for numer 2 at the moment.