1. Not finding help here? Sign up for a free 30min 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!

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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Writing a recursive function to compute the Jacobi symbol
  1. Recursive function (Replies: 16)

Loading...