Euleri's Totient using DFT

Question

I am trying to implement the computation of Euler's Totient function using Discreet Fourier Transform (https://en.wikipedia.org/wiki/Euler%27s_totient_function#Fourier_transform)

$\phi$(n)= $\sum_{k=1}^ngcd(k,n)cos2\pi\frac{k}{n}$

Here is my python snippet for this:

import math
import sys
def gcd(x, y):
    # print x, y;
    if x > y:
        small = y
    else:
        small = x
    for i in range(1, small + 1):
        if (x % i == 0) and (y % i == 0):
            m = i
    print "GCD of ", x, y, " is ", m
    return m

if 2 != len(sys.argv):
    print ("Usage: euler.py <int>")
    exit(-1)
n = int(sys.argv[1])  # type: int
phi = math.pi
sumvalue = 0
for k in range(1, n):
    j = (2 * phi * k) / n;
    print j;
    elementval = gcd(k, n) * math.cos(j)
    print "Cosine val is ", math.cos(j), " Element val is ", elementval, " (for ", k, " )"
    sumvalue = sumvalue + elementval

print "Euler's Totient for ", n, " is ", sumvalue

Looks simple enough but I get the Totient value incorrectly. For example,

$\phi$(9) returns 3 instead of 6: Euler's Totient for 9 is -3.0