1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
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

  1. Apr 13, 2012 #1
    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
    [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]

    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);
              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. jcsd
  3. Apr 13, 2012 #2


    User Avatar
    Homework Helper

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook