Problem 182

http://projecteuler.net/index.php?section=problems&id=182

p182 p q = sum [e | e <-[2..phi-1], gcd e phi == 1,
gcd (e-1) (p-1) == 2, gcd (e-1) (q-1) == 2]
where phi = (p-1)*(q-1)
main = print $ p182 1009 3643
{--
g(e,p) = x^e=x (mod p) の解の数
       = gcd(e-1,p-1)+1
a : prime of Zp (Zpの生成元) ,0 <= y < p
 (a^y)^e=a^y (mod p) iff ye-y = y(e-1) = 0 (mod p-1)
 gcd(e-1,p-1) = d とすると
 y(e-1) = ykd
 p-1 = ld
 y(e-1) = z(p-1) iff yk=zl
 -> y = l,2l,3l..dl
 x=0は常に解
g(e,pq) = g(e,p)*g(e,q)
中国剰余定理から
x = a (mod p)
x = b (mod p)
の解は mod pq では一意
--}