Writing a recursive function to compute the Jacobi symbol

[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 }$$

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.

 

[rcgldr]

also called coprime, wiki article:

http://en.wikipedia.org/wiki/Coprime