1
$\begingroup$

Is $\left(\dfrac{3299}{2663}\right) = 1$?

The solution from the book was $-1$ :(.
My attempt was:

$$\left(\dfrac{3299}{2663}\right) = \left(\dfrac{636}{2663}\right) = \left(\dfrac{2^2}{2663}\right) \cdot \left(\dfrac{159}{2663}\right)$$ $$ = 1 \cdot \left(\dfrac{2663}{159}\right) = \left(\dfrac{119}{159}\right) = \left(\dfrac{159}{119}\right) = \left(\dfrac{40}{119}\right) = \left(\dfrac{2^3}{119}\right) \cdot \left(\dfrac{5}{119}\right)$$

And $\dfrac{119^2 - 1}{8} = 1770$. Hence, $$ = \left(\dfrac{5}{119}\right) = \left(\dfrac{119}{5}\right) = \left(\dfrac{2^2}{5}\right) = 1$$.

Any idea?

  • 1
    [Wolfram Alpha](http://www.wolframalpha.com/input/?i=JacobiSymbol%5B3299%2C2663%5D) says that the answer is 1.2011-04-06
  • 0
    @Tsuyoshi Ito: Many thanks for your answer and the link ;)2011-04-06
  • 0
    Can someone explain the notation? I would like to know what the question is about.2011-04-06
  • 0
    @picakhu See [Jacobi symbol](http://en.wikipedia.org/wiki/Jacobi_symbol).2011-04-06

1 Answers 1

4

In fact $1$ is correct. Indeed $\rm\ 173^2\ \equiv\ 636\ \equiv\ 3299\ \ (mod\ 2663)\:.\ $ But your proof is wrong since you incorrectly flipped with no sign change in two spots (but the errors cancelled out). $\:$ Namely $\rm\ (159|2663)\ $ and $\rm\ (119|159)\:.$

For testing your program, you might find it helpful to compare to the following unified GCD and Jacobi symbol algorithm. I devised this program not for efficiency but, rather, in response to a challenge problem to show that such a unified program schema exists.

Assumptions: m,n > 0, n odd  (Jacobi (m|n) is defined only for n odd)  BOUNDARY CONDITIONS  (m|n) where 0 ≤ m ≤ 2   GCD:     (0|n) = n,  (1|n) = 1,  (2|n) = 1 Jacobi:  (0|n) = 0,  (1|n) = 1,  (2|n) = 1 if n=1,7 (mod 8) else -1  RECURSION  (m|n) =  m odd:        m=n=3 (mod 4):   ( m-(n mod m) | m ) except (0|m) if n = m        else:            (    n mod m  | m )  m even:        n = 5 (mod 8):   ( n-m   | n )        n = 3 (mod 8):   ( n-m/2 | n ) except (0|n-m) if n-m/2 = m        else:            (   m/2 | n ) 
  • 3
    Sometimes two wrongs do make a right.2011-04-06
  • 2
    Sometimes I call such erroneous proofs *involuted* (vs. convoluted).2011-04-06
  • 0
    @Bill Dubuque: So when I flip, I need to change the sign? Thank you.2011-04-06
  • 0
    @Chan: The sign changes iff both odd arguments are $\rm\: \equiv\ 3\ \ (mod\ 4)\:.$2011-04-06
  • 0
    @Bill Dubuque: I see it now. I'm writing a program to calculate Jacobi Symbol. I read the book example and thought I got it, but it turned out to be "big" NO. I really need to read the theorem again. Thanks a lot.2011-04-06
  • 0
    @Bill Dubuque: Wow! Many thanks for the program ;)! Love it.2011-04-06