Legendre Symbol
   HOME
*





Legendre Symbol
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic residue (''non-residue'') is −1. Its value at zero is 0. The Legendre symbol was introduced by Adrien-Marie Legendre in 1798 in the course of his attempts at proving the law of quadratic reciprocity. Generalizations of the symbol include the Jacobi symbol and Dirichlet characters of higher order. The notational convenience of the Legendre symbol inspired introduction of several other "symbols" used in algebraic number theory, such as the Hilbert symbol and the Artin symbol. Definition Let p be an odd prime number. An integer a is a quadratic residue modulo p if it is congruent to a perfect square modulo p and is a quadratic nonresidue modulo p otherwise. The Legendre symbol is a function of a and p defined as :\left(\frac\right) = \begi ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Quadratic Residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic nonresidue modulo ''n''. Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers. History, conventions, and elementary facts Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries established theorems and formed conjectures about quadratic residues, but the first systematic treatment is § IV of Gauss's ''Disquisitiones Arithmeticae'' (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that if the context makes it clear, the adjective "quadratic" may be dropped. For ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Quadratic Reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is: This law, together with its #q_=_±1_and_the_first_supplement, supplements, allows the easy calculation of any Legendre symbol, making it possible to determine whether there is an integer solution for any quadratic equation of the form x^2\equiv a \bmod p for an odd prime p; that is, to determine the "perfect squares" modulo p. However, this is a constructivism (mathematics), non-constructive result: it gives no help at all for finding a ''specific'' solution; for this, other methods are required. For example, in the case p\equiv 3 \bmod 4 using Euler's criterion one can give an explicit formula for the "square roots" modulo p of a quadratic residue a, namely, :\pm a^ indeed, :\left (\pm a^ \right )^2=a^=a\cdot a^\equiv a\ ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Quartic Reciprocity
Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence ''x''4 ≡ ''p'' (mod ''q'') is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence ''x''4 ≡ ''p'' (mod ''q'') to that of ''x''4 ≡ ''q'' (mod ''p''). History Euler made the first conjectures about biquadratic reciprocity. Gauss published two monographs on biquadratic reciprocity. In the first one (1828) he proved Euler's conjecture about the biquadratic character of 2. In the second one (1832) he stated the biquadratic reciprocity law for the Gaussian integers and proved the supplementary formulas. He saidGauss, BQ, § 67 that a third monograph would be forthcoming with the proof of the general theorem, but it never appeared. Jacobi presented proofs in his Königsberg lectures of 1836–37. The first published proofs were by Eise ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Cubic Reciprocity
Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence ''x''3 ≡ ''p'' (mod ''q'') is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if ''p'' and ''q'' are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence ''x''3 ≡ ''p'' (mod ''q'') is solvable if and only if ''x''3 ≡ ''q'' (mod ''p'') is solvable. History Sometime before 1748 Euler made the first conjectures about the cubic residuacity of small integers, but they were not published until 1849, after his death. Gauss's published works mention cubic residues and reciprocity three times: there is one result pertaining to cubic residues in the Disquisitiones Arithmeticae (1801). In the introduction to the fifth and sixth proofs of quadratic reciprocity (1818) he said that he was publishing these proofs because their techniques ( Gauss's lemma ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Sine Function
In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side that is opposite that angle to the length of the longest side of the triangle (the hypotenuse), and the cosine is the ratio of the length of the adjacent leg to that of the hypotenuse. For an angle \theta, the sine and cosine functions are denoted simply as \sin \theta and \cos \theta. More generally, the definitions of sine and cosine can be extended to any real value in terms of the lengths of certain line segments in a unit circle. More modern definitions express the sine and cosine as infinite series, or as the solutions of certain differential equations, allowing their extension to arbitrary positive and negative values and even to complex numbers. The sine and cosine functions are commonly used to model periodic phenomena such as sound and li ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Elliptic Function
In the mathematical field of complex analysis, elliptic functions are a special kind of meromorphic functions, that satisfy two periodicity conditions. They are named elliptic functions because they come from elliptic integrals. Originally those integrals occurred at the calculation of the arc length of an ellipse. Important elliptic functions are Jacobi elliptic functions and the Weierstrass \wp-function. Further development of this theory led to hyperelliptic functions and modular forms. Definition A meromorphic function is called an elliptic function, if there are two \mathbb- linear independent complex numbers \omega_1,\omega_2\in\mathbb such that : f(z + \omega_1) = f(z) and f(z + \omega_2) = f(z), \quad \forall z\in\mathbb. So elliptic functions have two periods and are therefore also called ''doubly periodic''. Period lattice and fundamental domain Iff is an elliptic function with periods \omega_1,\omega_2 it also holds that : f(z+\gamma)=f(z) for every linear ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Gotthold Eisenstein
Ferdinand Gotthold Max Eisenstein (16 April 1823 – 11 October 1852) was a German mathematician. He specialized in number theory and mathematical analysis, analysis, and proved several results that eluded even Carl Friedrich Gauss, Gauss. Like Évariste Galois, Galois and Niels Henrik Abel, Abel before him, Eisenstein died before the age of 30. He was born and died in Berlin, Kingdom of Prussia, Prussia. Early life His parents, Johann Konstantin Eisenstein and Helene Pollack, were of Jewish descent and converted to Protestantism prior to his birth. From an early age, he demonstrated talent in mathematics and music. As a young child he learned to play piano, and he continued to play and compose for piano throughout his life. He suffered various health problems throughout his life, including meningitis as an infant, a disease that took the lives of all five of his brothers and sisters. In 1837, at the age of 14, he enrolled at Friedrich Wilhelm Gymnasium (school), Gymnasium, and ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Leopold Kronecker
Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, all else is the work of man").The English translation is from Gray. In a footnote, Gray attributes the German quote to "Weber 1891/92, 19, quoting from a lecture of Kronecker's of 1886". Weber, Heinrich L. 1891–1892Kronecker''Jahresbericht der Deutschen Mathematiker-Vereinigung''
2:5-23. (The quote is on p. 19.) Kronecker was a student and lifelong friend of .


Biography

Leopold Kronecker was born ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Quadratic Gauss Sum
In number theory, quadratic Gauss sums are certain finite sums of roots of unity. A quadratic Gauss sum can be interpreted as a linear combination of the values of the complex exponential function with coefficients given by a quadratic character; for a general character, one obtains a more general Gauss sum. These objects are named after Carl Friedrich Gauss, who studied them extensively and applied them to quadratic, cubic, and biquadratic reciprocity laws. Definition For an odd prime number and an integer , the quadratic Gauss sum is defined as : g(a;p) = \sum_^\zeta_p^, where \zeta_p is a primitive th root of unity, for example \zeta_p=\exp(2\pi i/p). Equivalently, : g(a;p) = \sum_^\big(1+\left(\tfrac\right)\big)\,\zeta_p^. For divisible by the expression \zeta_p^ evaluates to 1. Hence, we have : g(a;p) = p. For not divisible by , this expression reduces to : g(a;p) = \sum_^\left(\tfrac\right)\,\zeta_p^ = G(a,\left(\tfrac\right)), where : G(a,\chi)=\sum_^\chi(n)\,\ze ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Proofs Of Quadratic Reciprocity
In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published. Proof synopsis Of the elementary combinatorial proofs, there are two which apply types of double counting. One by Gotthold Eisenstein counts lattice points. Another applies Zolotarev's lemma to (\mathbb/pq\mathbb)^ , expressed by the Chinese remainder theorem as (\mathbb /p \mathbb)^ \times (\mathbb /q \mathbb)^ and calculates the signature of a permutation. The shortest known proof also uses a simplified version of double counting, namely double counting modulo a fixed prime. Eisenstein's proof Eisenstein's proof of quadratic reciprocity is a simplification of Gauss's third proof. It is more geometrically intuitive and requires less technical manipulation. The point of departure is "Eisenstein's lemma", which states that for distinct odd primes ''p'', ''q'', : ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Wall–Sun–Sun Prime
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known. Definition Let p be a prime number. When each term in the sequence of Fibonacci numbers F_n is reduced modulo p, the result is a periodic sequence. The (minimal) period length of this sequence is called the Pisano period and denoted \pi(p). Since F_0 = 0, it follows that ''p'' divides F_. A prime ''p'' such that ''p''2 divides F_ is called a Wall–Sun–Sun prime. Equivalent definitions If \alpha(m) denotes the rank of apparition modulo m (i.e., \alpha(m) is the smallest positive index m such that m divides F_), then a Wall–Sun–Sun prime can be equivalently defined as a prime p such that p^2 divides F_. For a prime ''p'' ≠ 2, 5, the rank of apparition \alpha(p) is known to divide p - \left(\tfrac\right), where the Legendre symbol \textstyle\left(\frac\right) has the values :\left(\frac\right) = \begin ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Primality Testing
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called ''compositeness tests'' instead of primality tests. Simple methods The simplest primality test is ''trial division'': given an input number, ''n'', check whether it is evenly divisible by any prime number between 2 and (i.e. that the division leaves no remainder). If so, then ''n'' is composite. Otherwise, it is prime.Riesel (1994) pp.2-3 For example, ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]