- If P = x y where x and y are primes, and b is relatively prime to P,

then b^(P+1) = b^(x+y).

How might this theorem be used to prove that a number was not prime?

Suppose y is presumed to be prime, but is not really prime.

Then since y is prime, and 3 is prime,

it would be true that

2^(3y+1) =2^(y+3) mod (3y).

If this equation is not true, it would prove that y is not prime.

However, if the equation is true, it would not prove that y is prime.

It will be a matter of empirical research to determine lower bounds

on composite y such that

2^(3y+1) = 2^(y+3) mod (3y)

2^(5y+1) = 2^(y+5) mod (5y)

2^(7y+1) = 2^(y+7) mod (7y)

etc

Kermit > It will be a matter of empirical research to determine lower bounds

Four shalt be the number thou shalt count, and the number of the counting

> on composite y such that

>

> 2^(3y+1) = 2^(y+3) mod (3y)

> 2^(5y+1) = 2^(y+5) mod (5y)

> 2^(7y+1) = 2^(y+7) mod (7y)

shalt be four.

For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so

2^(4x+1) = 0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder

Theorem, we get 2^(4x+1) = 2^5 (mod 4x)

We also have 2^(x+4) = 2^(5 + (x-1)), which gets us

2^(x+4) = 0 (mod 4) and 2^(x+4) = 2^5 (mod x). Combining them by CNT

gives 2^(x+4) = 2^5 (mod 4x)

Ergo, 2^(4x+1) = 2^(4+x) mod (4x), and 4 is the smallest counterexample

for any odd prime x.

Peter- On 6/23/2012 5:44 PM, Peter Kosinar wrote:
>> It will be a matter of empirical research to determine lower bounds

counting shalt be four.

>> on composite y such that

>>

>> 2^(3y+1) = 2^(y+3) mod (3y)

>> 2^(5y+1) = 2^(y+5) mod (5y)

>> 2^(7y+1) = 2^(y+7) mod (7y)

>

> Four shalt be the number thou shalt count, and the number of the

>

0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder Theorem,

> For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so 2^(4x+1) =

we get 2^(4x+1) = 2^5 (mod 4x)>

counterexample for any odd prime x.

> We also have 2^(x+4) = 2^(5 + (x-1)), which gets us

> 2^(x+4) = 0 (mod 4) and 2^(x+4) = 2^5 (mod x). Combining them by CNT

> gives 2^(x+4) = 2^5 (mod 4x)

>

> Ergo, 2^(4x+1) = 2^(4+x) mod (4x), and 4 is the smallest

>

Hello Peter.

> Peter

Thanks.

My test is even worse than you have discovered.

For any composite y such that 2^y = 2 mod y, (Original Fermat test

which fails too many times)

and for any odd prime x,

Calculate 2^(xy-x-y+1) mod x and 2^(xy-x-y+1) mod y

2^(xy-x-y+1) = (2^x)^y * 2^(-x-y+1) = 2^y * 2^(-x-y+1) = 2^(y-x-y+1) =

2^(-x+1) = 2^(1-1) mod x

2^(xy-x-y+1) = (2^x)^y * 2^(-x-y+1) = 2^x * 2^(-x-y+1) = 2^(x-x-y+1) =

2^(-y+1) = 2^(1-1) mod y

Thus by chinese remainder theorem, 2(xy-x-y+1) = 1 mod (xy).

This proves that my proposed "new" test is only a disguised Fermat test.

Kermit Rose