# Homework Help: Writing a recursive function to compute the Jacobi symbol

1. Apr 13, 2012

### John O' Meara

Write a recursive function to compute the Jacobi symbol J(a, n), is defined for relatively prime integers a and n, $$a> o, \mbox{ and } n > 0$$ by the formula
$$J(a, n) = 1 \mbox{ if a = 1, } = J(a/2, n)*(-1)^\frac{n^2-1}{8} \mbox{ if a is even, }$$
$$=J(n \% a, a)*(-1)^\frac{(a-1)*(n-1)}{4} \mbox{ otherwise }$$

Code (Text):
int jacobi(int a, int n)
{
if (a == 1)
return 1;
else {
if ((a % 2) == 0)
return jacobi(a/2, n)*(pow(-1.0, (n*n-1)/8);
else
return jacobi(n % a, a)*(pow(-1.0, ((a-1)*(n-1))/4));
}
}
int main() {
cout << jacobi(5, 7);
return 0;
}

I seem not to be able to remember what a relative prime number is? And I don't think I understand the Jacobi function anyway. Any help would be welcome. Thanks in advance.

Last edited: Apr 13, 2012
2. Apr 13, 2012