Jacobi symbol
Videos
Jacobi symbol for various k and n. Only 0 ≤ k < n are shown, since due to rule below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacob
Carl Gustav Jacob Jacobi who introduced the symbol.
Euclidean algorithm
Videos
In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor of two integers, the largest number that divides them both without a re
Jacobi symbol
…Dirichlet character to the modulus n. The above formulas lead to an efficient O(log a log b) algorithm for calculating the Jacobi symbol, analogous to the Euclidean algorithm for finding the gcd of two numbers. (This should not be surprising in light of rule 2.) Reduce the "numerator" modulo the "denominator" using rule 2…
The Euclidean algorithm was probably invented before Euclid, depicted here holding a compass in a painting of about 1474.