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

    rcgldr

    User Avatar
    Homework Helper

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