On Sunday 05 June 2011 02:19:58 Jason wrote:
[Fermat Half-Prime]: n such that 2|a|=|b|, for a in 1<a<n, a^(n-1)%n == 1, and 0<b<n relatively prime to n.
(Bug: it should be 0<a<n above.)
Actually, this is somewhat interesting. The "Fermat Half-Primes" in 2..100000 are:
4,6,15,91,703,1891,2701,11305,12403,13981,18721,23001,30889,38503,39865,491 41,68101,79003,88561,88831,91001,93961.
OEIS lists has "A129521: Numbers of the form p*q, p and q prime with q=2*p-1", which appears to be a subset of this sequence:
6,15,91,703,1891,2701,12403,18721,38503,49141,79003,88831,104653,...
Yup. When n=pq with p,q=2p-1 prime, a^(n-1) = 1 (mod p) iff a is a quadratic residue mod q: thus, half the time. Incidentally, I think your definition of "Fermat half-prime" would have been clearer if more explicit: "n such that exactly half of the a such that 0<a<n and (a,n)=1 satisfy a^(n-1) = 1 (mod p)". -- g