def jacobi(a, n):
    if n <= 0:
        raise ValueError()
    if n% 2 == 0:
        raise ValueError()
    a%= n
    result = 1
    while a != 0:
        while a% 2 == 0:
            a /= 2
            n_mod_8 = n% 8
            if n_mod_8 in (3, 5):
                result = -result
        a, n = n, a
        if a% 4 == 3 and n% 4 == 3:
            result = -result
        a%= n
    if n == 1:
        return result
    else:
        return 0