## 18375Re: Proth-like thinking

Expand Messages
• Sep 22, 2006
wrote:
>
> Hello, Group.
>
> modifying Proth's Theorem...
>
> choose an 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 the 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 it not prime.

Oddly enough, 121 is a psuedoprime base 3 according to Sloane's list.

>
> 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 test 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 any counter-example using this modification of Proth's
theorem?
>
> 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
>
I would name this class of primes... "2nd kind Proth primes"
• Show all 4 messages in this topic