module SummePhi
where

summePhi :: Int -> Int
summePhi n = sum $ map phi [1..n]

phi :: Int -> Int
phi n = length (filter (relprime n) [1..(n-1)])

--alternativ gcd im Prelude
hcf     :: Int -> Int -> Int
hcf x 0 = x
hcf x y = hcf y (rem x y)

relprime     :: Int -> Int -> Bool
relprime x y = hcf x y == 1