-- http://en.wikipedia.org/wiki/Euler%27s_totient_function

totient :: (Integral a) => a -> Int
totient x = length $ filter ((==1).(gcd x)) [1..x]