24290Re: [PrimeNumbers] Another form of probabilistic test for primeness
- Jun 24, 2012On 6/23/2012 5:44 PM, Peter Kosinar wrote:
>> It will be a matter of empirical research to determine lower boundscounting 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
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.
- << Previous post in topic