## 18374Proth-like thinking

Expand Messages
• Sep 21 5:38 PM
Hello, Group.

modifying the theorem...

choose a odd 'n' such that 2^k +1 < n < 2*(2^k +1) for some k --
notice that this is different from Proth's notion that 'n' must be <
2^k +1.

if Z = n*(2^k) +1, then any number relatively prime to, less than,
and up to the lower limit for 'n' would rather quickly expose 'Z' as
composite using q^(Z-1) != 1 (mod Z) test.

choose n = 15, k = 3 and 9 < 15 < 18 and q = 7 since gcd(3 or 5, 15) !
= 1; Z = 121. compute 7^120 == 109^24 == 45^6 == 23 (mod 121). I
could have also chosen q = 2, 4, or 8 to prove not prime.

Conversely, however, a single test might also confirm primality when
the value for 'q' is chosen relatively prime to, less than, and up to
the lower limit for 'n' as opposed to performing several classical 'p-
1' tests.

The two notable counter examples for Z < 1000 (that are shown prime
via 2^(p-1) == 1 mod p but are actually composite) are 341 & 561 and
both of them can't be produced using the above criteria since 341 =
2^2 * 85 +1 (85 is much larger than n < 2*(2^2 +1)) and 561 = 2^4 *
35 +1 (35 is just larger than n < 2*(2^4 +1) = 34.

Can someone find a counter-example of Z > 1000 using the construct?

i.e. After 'Z' is produced and 'q' is so carefully chosen... Can Z be
composite and still return a value of '1' from a classical 'p-1' test?

I can't show it... or prove it, but it would seem so... I think the
classical counter-examples would not fall into this class of primes.

Bill
• Show all 4 messages in this topic