Quote:
Originally Posted by wsc812
we know that if $q=4k+3$ ($q$ is a prime), then $(a+bI)^q=a^q+b^q(I)^{4k+3}(mod q) =a bI$ for every gaussian integer $(a+bi)$ ,Now consider a composite $N=4k+3$ satisfies this condistion for $a+bi=3+2i$, I use Mathematica8 and find no solutison$ less than $5\cdot 10^7, can someone find a lager number for the condition . I guess it's impossible for a composite N.So this can be use for Primality test .

This is in fact a particular case of the Frobenius test, explained in Crandall and Pomerance, among others. You are working in F
_{p}[x]/(x^2+1) which is a proper quadratic extension for a prime p ≡ 3 (mod 4). Then the Frobenius automorphism maps (a+bi) to its conjugate (a+bi)
^{p} = (abi). Testing that this condition holds is the basic idea behind Grantham's
Frobenius test, which he also generalized to higherdegree extension fields. The Frobenius test is quite a strong probabilistic primality test, but there is no proof as far as I know that it is deterministic with any polynomial, and the idea is not new, either.