def jacobi(a, n):
    s = 1
    while True:
        if n < 1:
            print "error"
            return
        if n % 2 == 0:
            print "not odd"
            return
        if n == 1:
            return s

        a = a % n

        if a == 0:
            return 0
        if a == 1:
            return s

        if a % 2 == 0:
            if n % 8 == 3 or n % 8 == 5:
                s = -s
            a /= 2
            continue

        if a % 4 == 3 and n % 4 == 3:
            s = -s

        a, n = n, a
    return

jacobi(1, 3)
jacobi(74, 163)
jacobi(2, 3)
jacobi(1, 3)
jacobi(6, 3)