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?

  • 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 ) 
  • 0
    @Bill Dubuque: Wow! Many thanks for the program ;)! Love it.2011-04-06