Write a recursive function to compute the Jacobi symbol J(a, n), is defined for relatively prime integers a and n, [tex] a> o, \mbox{ and } n > 0[/tex] by the formula(adsbygoogle = window.adsbygoogle || []).push({});

[tex] J(a, n) = 1 \mbox{ if a = 1, } = J(a/2, n)*(-1)^\frac{n^2-1}{8} \mbox{ if a is even, }[/tex]

[tex]=J(n \% a, a)*(-1)^\frac{(a-1)*(n-1)}{4} \mbox{ otherwise } [/tex]

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.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;

}

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**