--- In

primenumbers@yahoogroups.com, "Paul Underwood"

<paulunderwood@...> wrote:

>

>

> Bill,

>

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

>

> ? N=1657700353

> 1657700353

> ? factor(N-1)

>

> [2 15]

>

> [3 2]

>

> [7 1]

>

> [11 1]

>

> [73 1]

No. The idea for testing any Proth-like number would be to subtract 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

>