- 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 - --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...>

wrote:>

as

> 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'

> composite using the q^(Z-1) != 1 (mod Z) test.

15) !

>

> choose n = 15, k = 3 and 9 < 15 < 18 and q = 7 since gcd(3 or 5,

> = 1; Z = 121. compute 7^120 == 109^24 == 45^6 == 23 (mod 121). I

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

> could have also chosen q = 2, 4, or 8 to prove it not prime.

>

when

> Conversely, however, a single test might also confirm primality

> 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.

561 and

>

> 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 &

> both of them can't be produced using the above criteria since 341 =

theorem?

> 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

>

be

> i.e. After 'Z' is produced and 'q' is so carefully chosen... Can Z

> composite and still return a value of '1' from a classical 'p-1'

test?

>

I would name this class of primes... "2nd kind Proth primes"

> 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

>

- --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...> wrote:
>

Bill,

> --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@>

> 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"

>

is the 771st (?) Carmichael number a counterexample?:

? N=1657700353

1657700353

? factor(N-1)

[2 15]

[3 2]

[7 1]

[11 1]

[73 1]

? n=(N-1)/(2^15)

50589

? 2^15+1<n&&n<2*(2^15+1)

1

Paul - --- In primenumbers@yahoogroups.com, "Paul Underwood"

<paulunderwood@...> wrote:>

No. The idea for testing any Proth-like number would be to subtract 1

>

> Bill,

>

> is the 771st (?) Carmichael number a counterexample?:

>

> ? N=1657700353

> 1657700353

> ? factor(N-1)

>

> [2 15]

>

> [3 2]

>

> [7 1]

>

> [11 1]

>

> [73 1]

and divide out 2 until only other prime factors existed, and then to

compute the classical 'p-1' test with 'any' of those numbers relative-

ly prime to 50589. Hence, 2, 5, 13 up to 2^15 +1 would work but gcd

(50589,3)!= 1 and 2 exposes that 1657700353 isn't prime.

Bill

The same is true for Proth primes except the test changes to a^((p-

1)/2) == 1 mod p instead of the 'p-1'.

>

> ? n=(N-1)/(2^15)

> 50589

> ? 2^15+1<n&&n<2*(2^15+1)

> 1

>

> Paul

>