## Legendre’s Symbol

### May 1, 2012

The Legendre Symbol and its cousin the Jacobi Symbol are used in modular arithmetic to determine if a number *a* is a quadratic residue to the modulus *m*. A number *a* is a quadratic residue if there exists a number *x* such that *x*^{2} ≡ *a* (mod *m*) and is defined only when *a* and *m* are co-prime. For instance, *a*^{2} (mod 7) for *a* from 0 to 6 is the list 0^{2} (mod 7) = 0, 1^{2} (mod 7) = 1, 2^{2} (mod 7) = 4, 3^{2} (mod 7) = 2, 4^{2} (mod 7) = 2, 5^{2} (mod 7) = 4, and 6^{2} (mod 7) = 1, so the quadratic residues of 7 are 1, 2 and 4 (0 is excluded because it isn’t co-prime to 7). The jacobi symbol considers any odd modulus; the legendre symbol is limited to odd prime moduli. The symbols are usually written in parentheses with *a* over *m*, like this: . Sometimes the symbol is written with a horizontal rule between the *a* and *m*, and sometimes it is written on a single line as (*a* / *m*).

The legendre/jacobi symbol can be calculated according to the following three termination rules:

1. (0 /

m) = 02. (1 /

m) = 13. (2 /

m) = −1 ifmmod 8 ∈ {3, 5} or 1 ifmmod 8 ∈ {1, 7}

and the following three reduction rules:

4. [reducing factors of 2] (2

a/m) = (2 /m) × (a/m)5. [reducing modulo

m] (a/m) = (a(modm) /m) ifa≥mora< 06. [reducing odd co-primes

aandm] (a/m) = −(m/a) ifa≡m≡ 3 (mod 4), or (m/a) otherwise

Thus, the legendre/jacobi symbol is 1 if *a* is a quadratic residue, -1 if *a* is not a quadratic residue, and 0 if *a* and *m* are not co-prime.

Our various prime-number programs have used a definition of the legendre/jacobi symbol that doesn’t work; for some values of *a* and *m* it returned wrong results, and for other values of *a* and *m* it entered an infinite loop. This exercise fixes the problem.

Your task is to write a function that calculates the legendre/jacobi symbol using the rules given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.