Modular Arithmetic

Source: Wikipedia. Pages: 73. Chapters: Euler's totient function, Fermat's little theorem, Chinese remainder theorem, Euler's theorem, Carmichael number, Linear congruence theorem, Congruence relation, Proofs of Fermat's little theorem, Linear congruential generator, Quadratic reciprocity, Legendre symbol, Fermat primality test, Euler's criterion, Jacobi symbol, Quadratic residue, Quartic reciprocity, Cubic reciprocity, Primitive root modulo n, Gauss's lemma, Multiplicative group of integers modulo n, Verhoeff algorithm, Cipolla's algorithm, Montgomery reduction, Modular exponentiation, Root of unity modulo n, Tonelli¿Shanks algorithm, Wilson's theorem, Solovay¿Strassen primality test, Zeller's congruence, Luhn algorithm, Luhn mod N algorithm, Hensel's lemma, Carmichael function, Discrete logarithm, Kochanski multiplication, Pocklington's algorithm, Discrete logarithm records, Residue number system, Lehmer random number generator, Modular multiplicative inverse, Additive polynomial, Beaver bit-vector decision procedure, Mod n cryptanalysis, Multiplicative order, Vedic square, Congruence of squares, Method of successive substitution, Kronecker symbol, Reduced residue system, Jordan's totient function, Barrett reduction, Vantieghems theorem. Excerpt: In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers. There are a number of equivalent statements of the theorem, which consists of two "supplements" and the reciprocity law: Let p, q > 2 be two distinct (positive odd) prime numbers. Then (Supplement 1) x = -1 (mod p) is solvable if and only if p = 1 (mod 4).(Supplement 2) x = 2 (mod p) is solvable if and only if p = ±1 (mod 8).(Quadratic reciprocity)Let q = ±q where the sign is plus if q = 1 (mod 4) and minus if q = -1 (mod 4). (I.e. |q | = q and q = 1 (mod 4).) Then x = p (mod q) is solvable if and only if x = q (mod p) is solvable.Although the law can be used to tell whether any quadratic equation modulo a prime number has a solution, it does not provide any help at all for actually finding the solution. (The article on quadratic residues discusses algorithms for this.) The theorem was conjectured by Euler and Legendre and first proven by Gauss. He refers to it as the "fundamental theorem" in the Disquisitiones Arithmeticae and his papers; privately he referred to it as the "golden theorem." He published six proofs, and two more were found in his posthumous papers. There are now over 200 published proofs. The first section of this article does not use the Legendre symbol and gives the formulations of quadratic reciprocity found by Legendre and Gauss. The Legendre-Jacobi symbol is introduced in the second section. A quadratic residue (mod n) is any number congruent to a square (mod n). A quadratic nonresidue (mod n) is any number which is not congruent to a square (mod n). The adjective "quadratic" can be dropped if the context makes it clear that it is implied. When working modulo primes (as in this article), it is usual to treat zero as a special case. By doing so, the following statements become true: Modulo a prime, there are an equal number of quadratic residues and nonresidues. Modulo