Thread: "New" primality test/check View Single Post 2018-01-12, 04:38   #234
gophne

Feb 2017

101001012 Posts Quote:
 Originally Posted by 10metreh I don't think you've taken on board what axn meant by this: The point is that, if n is odd, then gcd(n, n+2N) = gcd(n, N) and so you are just checking if n has any common factors with N. But if N is not prime, then the smallest n that has a common factor with N is the smallest prime factor of N, so in fact when you first find n such that gcd(n, n+2N) > 1, that n is a factor of N. So you're just doing inefficient trial division. I guess that technically counts as a "primality test" in that it does correctly determine primality or otherwise of N. But it's easy to come up with useless primality tests. Here's one: if N>4, then N is prime if and only if N does not divide (N-1)!. Unlike trial division, it's got only one step, so what could possibly go wrong...? As for why gcd(n, n+2N) = gcd(n, N), it's time for another basic number theory lesson: Suppose d divides n and n+2N. Then d must divide their difference, which is 2N. But d divides n, which is odd, so d is odd, and thus d must divide N. Conversely, suppose d divides n and N. Then clearly d divides n+N+N = n+2N. So the sets of common factors of (n, n+2N) and (n, N) are exactly the same, and in particular gcd(n, n+2N) = gcd(n, N).
Love this!

At least I am getting free math lessons, at the higest levels :)  