Misplaced Pages

#500499

107-402: The problem was first described by Gauss in his Disquisitiones Arithmeticae in 1801. This problem is believed to be computationally difficult . Several cryptographic methods rely on its hardness , see § Applications . An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether

214-623: A {\displaystyle a} is a quadratic residue modulo N {\displaystyle N} if and only if a {\displaystyle a} is a quadratic residue modulo both p 1 {\displaystyle p_{1}} and p 2 {\displaystyle p_{2}} and gcd ( a , N ) = 1 {\displaystyle \gcd(a,N)=1} . Since we don't know p 1 {\displaystyle p_{1}} or p 2 {\displaystyle p_{2}} , we cannot compute (

321-400: A {\displaystyle a} is necessarily a quadratic non-residue modulo either p 1 {\displaystyle p_{1}} or p 2 {\displaystyle p_{2}} , in which case we are done. But if ( a N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} then it is either

428-573: A mod p {\displaystyle x^{2}\equiv a{\bmod {p}}} for an odd prime p {\displaystyle p} ; that is, to determine the "perfect squares" modulo p {\displaystyle p} . However, this is a 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 ≡ 3 mod 4 {\displaystyle p\equiv 3{\bmod {4}}} using Euler's criterion one can give an explicit formula for

535-513: A p 1 ) {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}} and ( a p 2 ) {\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}} . However, it is easy to compute their product. This is known as the Jacobi symbol : This also can be efficiently computed using the law of quadratic reciprocity for Jacobi symbols. However, (

642-881: A p 1 ) = 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=1} , and for the rest we have ( a p 1 ) = − 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1} . By extension, this also holds for half the choices of a ∈ { 1 , … , N − 1 } ∖ p 1 Z {\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} } . Similarly for p 2 {\displaystyle p_{2}} . From basic algebra, it follows that this partitions ( Z / N Z ) × {\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }} into 4 parts of equal size, depending on

749-605: A ≠ 0 {\displaystyle a\neq 0} (leaving out the two solutions ( 1 , ± 1 ) {\displaystyle (1,\pm 1)} ), then the original equation transforms into Here t {\displaystyle t} can have any value that does not make the denominator zero – for which there are 1 + ( − 1 p ) {\displaystyle 1+\left({\frac {-1}{p}}\right)} possibilities (i.e. 2 {\displaystyle 2} if − 1 {\displaystyle -1}

856-423: A N ) {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}} cannot in all cases tell us whether a {\displaystyle a} is a quadratic residue modulo N {\displaystyle N} or not! More precisely, if ( a N ) = − 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1} then

963-476: A N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} , determine whether a {\displaystyle a} is a quadratic residue modulo N {\displaystyle N} or not. If a {\displaystyle a} is drawn uniformly at random from integers 0 , … , N − 1 {\displaystyle 0,\ldots ,N-1} such that (

1070-502: A N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} , is a {\displaystyle a} more often a quadratic residue or a quadratic non-residue modulo N {\displaystyle N} ? As mentioned earlier, for exactly half of the choices of a ∈ { 1 , … , p 1 − 1 } {\displaystyle a\in \{1,\ldots ,p_{1}-1\}} , then (

1177-544: A N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} . This leads to the precise formulation of the quadratic residue problem: Problem: Given integers a {\displaystyle a} and N = p 1 p 2 {\displaystyle N=p_{1}p_{2}} , where p 1 {\displaystyle p_{1}} and p 2 {\displaystyle p_{2}} are distinct unknown primes, and where (

SECTION 10

#1732797630501

1284-471: A composite N {\displaystyle N} of unknown factorization is the product of 2 or 3 primes. Given integers a {\displaystyle a} and T {\displaystyle T} , a {\displaystyle a} is said to be a quadratic residue modulo T {\displaystyle T} if there exists an integer b {\displaystyle b} such that Otherwise we say it

1391-492: A heliometer from Fraunhofer . The scientific activity of Gauss, besides pure mathematics, can be roughly divided into three periods: astronomy was the main focus in the first two decades of the 19th century, geodesy in the third decade, and physics, mainly magnetism, in the fourth decade. Gauss made no secret of his aversion to giving academic lectures. But from the start of his academic career at Göttingen, he continuously gave lectures until 1854. He often complained about

1498-423: A magnetometer in 1833 and – alongside Wilhelm Eduard Weber – the first electromagnetic telegraph in 1833. Gauss was the first to discover and study non-Euclidean geometry , coining the term as well. He further developed a fast Fourier transform some 160 years before John Tukey and James Cooley . Gauss refused to publish incomplete work and left several works to be edited posthumously . He believed that

1605-446: A ≡ m (mod p ) and 0 ≤ a < p . If a is in row p , then m is a residue (mod p ); if a is not in row p of the table, then m is a nonresidue (mod p ). The quadratic reciprocity law is the statement that certain patterns found in the table are true in general. Another way to organize the data is to see which primes are residues mod which other primes, as illustrated in the following table. The entry in row p column q

1712-406: A butcher, bricklayer, gardener, and treasurer of a death-benefit fund. Gauss characterized his father as honourable and respected, but rough and dominating at home. He was experienced in writing and calculating, whereas his second wife Dorothea, Carl Friedrich's mother, was nearly illiterate. He had one elder brother from his father's first marriage. Gauss was a child prodigy in mathematics. When

1819-569: A collection of short remarks about his results from the years 1796 until 1814, shows that many ideas for his mathematical magnum opus Disquisitiones Arithmeticae (1801) date from this time. Gauss graduated as a Doctor of Philosophy in 1799, not in Göttingen, as is sometimes stated, but at the Duke of Brunswick's special request from the University of Helmstedt, the only state university of

1926-491: A considerable literary estate, too. Gauss referred to mathematics as "the queen of sciences" and arithmetics as "the queen of mathematics", and supposedly once espoused a belief in the necessity of immediately understanding Euler's identity as a benchmark pursuant to becoming a first-class mathematician. On certain occasions, Gauss claimed that the ideas of another scholar had already been in his possession previously. Thus his concept of priority as "the first to discover, not

2033-672: A critique of d'Alembert's work. He subsequently produced three other proofs, the last one in 1849 being generally rigorous. His attempts clarified the concept of complex numbers considerably along the way. In the preface to the Disquisitiones , Gauss dates the beginning of his work on number theory to 1795. By studying the works of previous mathematicians like Fermat, Euler, Lagrange, and Legendre, he realized that these scholars had already found much of what he had discovered by himself. The Disquisitiones Arithmeticae , written since 1798 and published in 1801, consolidated number theory as

2140-431: A curious feature of his working style that he carried out calculations with a high degree of precision much more than required, and prepared tables with more decimal places than ever requested for practical purposes. Very likely, this method gave him a lot of material which he used in finding theorems in number theory. Gauss refused to publish work that he did not consider complete and above criticism. This perfectionism

2247-474: A decade. Therese then took over the household and cared for Gauss for the rest of his life; after her father's death, she married actor Constantin Staufenau. Her sister Wilhelmina married the orientalist Heinrich Ewald . Gauss's mother Dorothea lived in his house from 1817 until she died in 1839. The eldest son Joseph, while still a schoolboy, helped his father as an assistant during the survey campaign in

SECTION 20

#1732797630501

2354-483: A discipline and covered both elementary and algebraic number theory . Therein he introduces the triple bar symbol ( ≡ ) for congruence and uses it for a clean presentation of modular arithmetic . It deals with the unique factorization theorem and primitive roots modulo n . In the main sections, Gauss presents the first two proofs of the law of quadratic reciprocity and develops the theories of binary and ternary quadratic forms . The Disquisitiones include

2461-682: A habit in his later years, for example, the number of paths from his home to certain places in Göttingen, or the number of living days of persons; he congratulated Humboldt in December 1851 for having reached the same age as Isaac Newton at his death, calculated in days. Similar to his excellent knowledge of Latin he was also acquainted with modern languages. At the age of 62, he began to teach himself Russian , very likely to understand scientific writings from Russia, among them those of Lobachevsky on non-Euclidean geometry. Gauss read both classical and modern literature, and English and French works in

2568-555: A heart attack in Göttingen; and was interred in the Albani Cemetery there. Heinrich Ewald , Gauss's son-in-law, and Wolfgang Sartorius von Waltershausen , Gauss's close friend and biographer, gave eulogies at his funeral. Gauss was a successful investor and accumulated considerable wealth with stocks and securities, finally a value of more than 150 thousand Thaler; after his death, about 18 thousand Thaler were found hidden in his rooms. The day after Gauss's death his brain

2675-474: A private scholar. He gave the second and third complete proofs of the fundamental theorem of algebra , made contributions to number theory , and developed the theories of binary and ternary quadratic forms. Gauss was instrumental in the identification of Ceres as a dwarf planet. His work on the motion of planetoids disturbed by large planets led to the introduction of the Gaussian gravitational constant and

2782-702: A scandal in public, Eugen suddenly left Göttingen under dramatic circumstances in September 1830 and emigrated via Bremen to the United States. He wasted the little money he had taken to start, after which his father refused further financial support. The youngest son Wilhelm wanted to qualify for agricultural administration, but had difficulties getting an appropriate education, and eventually emigrated as well. Only Gauss's youngest daughter Therese accompanied him in his last years of life. Collecting numerical data on very different things, useful or useless, became

2889-409: A similar characterization of prime divisors of f ( n ) = n 2 − q {\displaystyle f(n)=n^{2}-q} for any prime q , which leads to a characterization for any integer q {\displaystyle q} . Let p be an odd prime. A number modulo p is a quadratic residue whenever it is congruent to a square (mod p ); otherwise it

2996-415: A strong calculus as the sole tasks of astronomy. At university, he was accompanied by a staff of other lecturers in his disciplines, who completed the educational program; these included the mathematician Thibaut with his lectures, the physicist Mayer , known for his textbooks, his successor Weber since 1831, and in the observatory Harding , who took the main part of lectures in practical astronomy. When

3103-445: A university chair in Göttingen, "because he was always involved in some polemic." Gauss's life was overshadowed by severe problems in his family. When his first wife Johanna suddenly died shortly after the birth of their third child, he revealed the grief in a last letter to his dead wife in the style of an ancient threnody , the most personal surviving document of Gauss. The situation worsened when tuberculosis ultimately destroyed

3210-692: Is 1 {\displaystyle 1} or 9 {\displaystyle 9} ; no primes ending in 3 {\displaystyle 3} or 7 {\displaystyle 7} ever appear. Now, p {\displaystyle p} is a prime factor of some n 2 − 5 {\displaystyle n^{2}-5} whenever n 2 − 5 ≡ 0 mod p {\displaystyle n^{2}-5\equiv 0{\bmod {p}}} , i.e. whenever n 2 ≡ 5 mod p , {\displaystyle n^{2}\equiv 5{\bmod {p}},} i.e. whenever 5

3317-450: Is R if q is a quadratic residue (mod p ); if it is a nonresidue the entry is N . If the row, or the column, or both, are ≡ 1 (mod 4) the entry is blue or green; if both row and column are ≡ 3 (mod 4), it is yellow or orange. The blue and green entries are symmetric around the diagonal: The entry for row p , column q is R (resp N ) if and only if the entry at row q , column p , is R (resp N ). The yellow and orange ones, on

Quadratic residuosity problem - Misplaced Pages Continue

3424-439: Is a quadratic non-residue. ("Quadratic" can be dropped if it is clear from the context.) Here we exclude zero as a special case. Then as a consequence of the fact that the multiplicative group of a finite field of order p is cyclic of order p-1 , the following statements hold: For the avoidance of doubt, these statements do not hold if the modulus is not prime. For example, there are only 3 quadratic residues (1, 4 and 9) in

3531-494: Is a quadratic non-residue. When T = p {\displaystyle T=p} is a prime, it is customary to use the Legendre symbol : This is a multiplicative character which means ( a p ) = 1 {\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1} for exactly ( p − 1 ) / 2 {\displaystyle (p-1)/2} of

3638-555: Is a quadratic residue modulo p {\displaystyle p} . This happens for p = 2 , 5 {\displaystyle p=2,5} and those primes with p ≡ 1 , 4 mod 5 , {\displaystyle p\equiv 1,4{\bmod {5}},} and the latter numbers 1 = ( ± 1 ) 2 {\displaystyle 1=(\pm 1)^{2}} and 4 = ( ± 2 ) 2 {\displaystyle 4=(\pm 2)^{2}} are precisely

3745-451: Is a quadratic residue. That is, 2 {\displaystyle 2} is a quadratic residue precisely if the number of solutions of this equation is divisible by 8 {\displaystyle 8} . And this equation can be solved in just the same way here as over the rational numbers: substitute x = a + 1 , y = a t + 1 {\displaystyle x=a+1,y=at+1} , where we demand that

3852-487: Is a residue modulo 13, etc. The more complicated-looking rules for the quadratic characters of 3 and −5, which depend upon congruences modulo 12 and 20 respectively, are simply the ones for −3 and 5 working with the first supplement. The generalization of the rules for −3 and 5 is Gauss's statement of quadratic reciprocity. Quadratic Reciprocity (Gauss's statement). If q ≡ 1 mod 4 {\displaystyle q\equiv 1{\bmod {4}}} , then

3959-429: Is a residue modulo 5. −5 is in rows 3, 7, 23, 29, 41, 43, and 47 but not in rows 11, 13, 17, 19, 31, or 37. The former are ≡ 1, 3, 7, 9 (mod 20) and the latter are ≡ 11, 13, 17, 19 (mod 20). The observations about −3 and 5 continue to hold: −7 is a residue modulo p if and only if p is a residue modulo 7, −11 is a residue modulo p if and only if p is a residue modulo 11, 13 is a residue (mod p ) if and only if p

4066-547: Is a residue, 0 {\displaystyle 0} if not) – and also does not make a {\displaystyle a} zero, which excludes one more option, t = − 1 {\displaystyle t=-1} . Thus there are possibilities for t {\displaystyle t} , and so together with the two excluded solutions there are overall p − ( − 1 p ) {\displaystyle p-\left({\frac {-1}{p}}\right)} solutions of

4173-509: Is not solvable. The last is immediately equivalent to the modern form stated in the introduction above. It is a simple exercise to prove that Legendre's and Gauss's statements are equivalent – it requires no more than the first supplement and the facts about multiplying residues and nonresidues. Apparently, the shortest known proof yet was published by B. Veklych in the American Mathematical Monthly . The value of

4280-468: Is solvable if and only if x 2 ≡ p mod q {\displaystyle x^{2}\equiv p{\bmod {q}}} is solvable. If p and q are congruent to 3 modulo 4, then: x 2 ≡ q mod p {\displaystyle x^{2}\equiv q{\bmod {p}}} is solvable if and only if x 2 ≡ p mod q {\displaystyle x^{2}\equiv p{\bmod {q}}}

4387-592: The Celestial police . One of their aims was the discovery of further planets. They assembled data on asteroids and comets as a basis for Gauss's research on their orbits, which he later published in his astronomical magnum opus Theoria motus corporum coelestium (1809). In November 1807, Gauss followed a call to the University of Göttingen , then an institution of the newly founded Kingdom of Westphalia under Jérôme Bonaparte , as full professor and director of

Quadratic residuosity problem - Misplaced Pages Continue

4494-502: The Gauss composition law for binary quadratic forms, as well as the enumeration of the number of representations of an integer as the sum of three squares. As an almost immediate corollary of his theorem on three squares , he proves the triangular case of the Fermat polygonal number theorem for n = 3. From several analytic results on class numbers that Gauss gives without proof towards

4601-493: The astronomical observatory , and kept the chair until his death in 1855. He was soon confronted with the demand for two thousand francs from the Westphalian government as a war contribution, which he could not afford to pay. Both Olbers and Laplace wanted to help him with the payment, but Gauss refused their assistance. Finally, an anonymous person from Frankfurt , later discovered to be Prince-primate Dalberg , paid

4708-472: The method of least squares , which he had discovered before Adrien-Marie Legendre published it. Gauss was in charge of the extensive geodetic survey of the Kingdom of Hanover together with an arc measurement project from 1820 to 1844; he was one of the founders of geophysics and formulated the fundamental principles of magnetism . Fruits of his practical work were the inventions of the heliotrope in 1821,

4815-550: The popularization of scientific matters. His only attempts at popularization were his works on the date of Easter (1800/1802) and the essay Erdmagnetismus und Magnetometer of 1836. Gauss published his papers and books exclusively in Latin or German . He wrote Latin in a classical style but used some customary modifications set by contemporary mathematicians. In his inaugural lecture at Göttingen University from 1808, Gauss claimed reliable observations and results attained only by

4922-558: The reciprocity law to higher powers has been a leading problem in mathematics, and has been crucial to the development of much of the machinery of modern algebra , number theory, and algebraic geometry , culminating in Artin reciprocity , class field theory , and the Langlands program . Quadratic reciprocity arises from certain subtle factorization patterns involving perfect square numbers. In this section, we give examples which lead to

5029-479: The "fundamental theorem" in his Disquisitiones Arithmeticae and his papers, writing Privately, Gauss referred to it as the "golden theorem". He published six proofs for it, and two more were found in his posthumous papers. There are now over 240 published proofs. The shortest known proof is included below , together with short proofs of the law's supplements (the Legendre symbols of −1 and 2). Generalizing

5136-479: The "square roots" modulo p {\displaystyle p} of a quadratic residue a {\displaystyle a} , namely, indeed, This formula only works if it is known in advance that a {\displaystyle a} is a quadratic residue , which can be checked using the law of quadratic reciprocity. The quadratic reciprocity theorem was conjectured by Euler and Legendre and first proved by Gauss , who referred to it as

5243-441: The Duke was killed in the battle of Jena in 1806. The duchy was abolished in the following year, and Gauss's financial support stopped. When Gauss was calculating asteroid orbits in the first years of the century, he established contact with the astronomical community of Bremen and Lilienthal , especially Wilhelm Olbers , Karl Ludwig Harding , and Friedrich Wilhelm Bessel , as part of the informal group of astronomers known as

5350-494: The French language. Gauss was "in front of the new development" with documented research since 1799, his wealth of new ideas, and his rigour of demonstration. Whereas previous mathematicians like Leonhard Euler let the readers take part in their reasoning for new ideas, including certain erroneous deviations from the correct path, Gauss however introduced a new style of direct and complete explanation that did not attempt to show

5457-427: The Legendre symbol of − 1 {\displaystyle -1} (used in the proof above) follows directly from Euler's criterion : by Euler's criterion, but both sides of this congruence are numbers of the form ± 1 {\displaystyle \pm 1} , so they must be equal. Whether 2 {\displaystyle 2} is a quadratic residue can be concluded if we know

SECTION 50

#1732797630501

5564-475: The act of getting there, which grants the greatest enjoyment. When I have clarified and exhausted a subject, then I turn away from it, in order to go into darkness again. The posthumous papers, his scientific diary , and short glosses in his own textbooks show that he worked to a great extent in an empirical way. He was a lifelong busy and enthusiastic calculator, who made his calculations with extraordinary rapidity, mostly without precise controlling, but checked

5671-642: The act of learning, not possession of knowledge, provided the greatest enjoyment. Gauss confessed to disliking teaching, but some of his students became influential mathematicians, such as Richard Dedekind and Bernhard Riemann . Gauss was born on 30 April 1777 in Brunswick in the Duchy of Brunswick-Wolfenbüttel (now in the German state of Lower Saxony ). His family was of relatively low social status. His father Gebhard Dietrich Gauss (1744–1808) worked variously as

5778-637: The best-paid professors of the university. When Gauss was asked for help by his colleague and friend Friedrich Wilhelm Bessel in 1810, who was in trouble at Königsberg University because of his lack of an academic title, Gauss provided a doctorate honoris causa for Bessel from the Philosophy Faculty of Göttingen in March 1811. Gauss gave another recommendation for an honorary degree for Sophie Germain but only shortly before her death, so she never received it. He also gave successful support to

5885-517: The birth of Louis, who himself died a few months later. Gauss chose the first names of his children in honour of Giuseppe Piazzi , Wilhelm Olbers, and Karl Ludwig Harding, the discoverers of the first asteroids. On 4 August 1810, Gauss married Wilhelmine (Minna) Waldeck, a friend of his first wife, with whom he had three more children: Eugen (later Eugene) (1811–1896), Wilhelm (later William) (1813–1879), and Therese (1816–1864). Minna Gauss died on 12 September 1831 after being seriously ill for more than

5992-701: The burdens of teaching, feeling that it was a waste of his time. On the other hand, he occasionally described some students as talented. Most of his lectures dealt with astronomy, geodesy, and applied mathematics , and only three lectures on subjects of pure mathematics. Some of Gauss's students went on to become renowned mathematicians, physicists, and astronomers: Moritz Cantor , Dedekind , Dirksen , Encke , Gould , Heine , Klinkerfues , Kupffer , Listing , Möbius , Nicolai , Riemann , Ritter , Schering , Scherk , Schumacher , von Staudt , Stern , Ursin ; as geoscientists Sartorius von Waltershausen , and Wappäus . Gauss did not write any textbook and disliked

6099-469: The case that a {\displaystyle a} is a quadratic residue modulo both p 1 {\displaystyle p_{1}} and p 2 {\displaystyle p_{2}} , or a quadratic non-residue modulo both p 1 {\displaystyle p_{1}} and p 2 {\displaystyle p_{2}} . We cannot distinguish these cases from knowing just that (

6206-558: The cases ( a p 1 ) = ( a p 2 ) = 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1} and ( a p 1 ) = ( a p 2 ) = − 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1} . Consequently, exactly half of

6313-497: The complete theorem. Trivially 1 is a quadratic residue for all primes. The question becomes more interesting for −1. Examining the table, we find −1 in rows 5, 13, 17, 29, 37, and 41 but not in rows 3, 7, 11, 19, 23, 31, 43 or 47. The former set of primes are all congruent to 1 modulo 4, and the latter are congruent to 3 modulo 4. Examining the table, we find 2 in rows 7, 17, 23, 31, 41, and 47, but not in rows 3, 5, 11, 13, 19, 29, 37, or 43. The former primes are all ≡ ±1 (mod 8), and

6420-530: The congruence x 2 ≡ p mod q {\displaystyle x^{2}\equiv p{\bmod {q}}} is solvable if and only if x 2 ≡ q ∗ mod p {\displaystyle x^{2}\equiv q^{*}{\bmod {p}}} is solvable. Quadratic Reciprocity (Legendre's statement). If p or q are congruent to 1 modulo 4, then: x 2 ≡ q mod p {\displaystyle x^{2}\equiv q{\bmod {p}}}

6527-545: The congruence x 2 ≡ p mod q {\displaystyle x^{2}\equiv p{\bmod {q}}} is solvable if and only if x 2 ≡ − q mod p {\displaystyle x^{2}\equiv -q{\bmod {p}}} is solvable. Quadratic Reciprocity (combined statement). Define q ∗ = ( − 1 ) q − 1 2 q {\displaystyle q^{*}=(-1)^{\frac {q-1}{2}}q} . Then

SECTION 60

#1732797630501

6634-513: The congruence x 2 ≡ p mod q {\displaystyle x^{2}\equiv p{\bmod {q}}} is solvable if and only if x 2 ≡ q mod p {\displaystyle x^{2}\equiv q{\bmod {p}}} is solvable. If q ≡ 3 mod 4 {\displaystyle q\equiv 3{\bmod {4}}} and p ≡ 3 mod 4 {\displaystyle p\equiv 3{\bmod {4}}} , then

6741-496: The contemporary school of Naturphilosophie . Gauss had an "aristocratic and through and through conservative nature", with little respect for people's intelligence and morals, following the motto " mundus vult decipi ". He disliked Napoleon and his system, and all kinds of violence and revolution caused horror to him. Thus he condemned the methods of the Revolutions of 1848 , though he agreed with some of their aims, such as

6848-702: The duchy. Johann Friedrich Pfaff assessed his doctoral thesis, and Gauss got the degree in absentia without further oral examination. The Duke then granted him the cost of living as a private scholar in Brunswick. Gauss subsequently refused calls from the Russian Academy of Sciences in St. Peterburg and Landshut University . Later, the Duke promised him the foundation of an observatory in Brunswick in 1804. Architect Peter Joseph Krahe made preliminary designs, but one of Napoleon's wars cancelled those plans:

6955-514: The elementary teachers noticed his intellectual abilities, they brought him to the attention of the Duke of Brunswick who sent him to the local Collegium Carolinum , which he attended from 1792 to 1795 with Eberhard August Wilhelm von Zimmermann as one of his teachers. Thereafter the Duke granted him the resources for studies of mathematics, sciences, and classical languages at the University of Göttingen until 1798. His professor in mathematics

7062-412: The end of the fifth section, it appears that Gauss already knew the class number formula in 1801. In the last section, Gauss gives proof for the constructibility of a regular heptadecagon (17-sided polygon) with straightedge and compass by reducing this geometrical problem to an algebraic one. He shows that a regular polygon is constructible if the number of its sides is either a power of 2 or

7169-669: The first investigations, due to mislabelling, with that of the physician Conrad Heinrich Fuchs , who died in Göttingen a few months after Gauss. A further investigation showed no remarkable anomalies in the brains of both persons. Thus, all investigations on Gauss's brain until 1998, except the first ones of Rudolf and Hermann Wagner, actually refer to the brain of Fuchs. Gauss married Johanna Osthoff on 9 October 1805 in St. Catherine's church in Brunswick. They had two sons and one daughter: Joseph (1806–1873), Wilhelmina (1808–1840), and Louis (1809–1810). Johanna died on 11 October 1809, one month after

7276-440: The first to publish" differed from that of his scientific contemporaries. In contrast to his perfectionism in presenting mathematical ideas, he was criticized for a negligent way of quoting. He justified himself with a very special view of correct quoting: if he gave references, then only in a quite complete way, with respect to the previous authors of importance, which no one should ignore; but quoting in this way needed knowledge of

7383-646: The form ( ± x , ± y ) , ( ± y , ± x ) {\displaystyle (\pm x,\pm y),(\pm y,\pm x)} , and what is left are four solutions of the form ( ± 1 , ± 1 ) {\displaystyle (\pm 1,\pm 1)} and possibly four additional solutions where x 2 = 2 , y = 0 {\displaystyle x^{2}=2,y=0} and x = 0 , y 2 = 2 {\displaystyle x=0,y^{2}=2} , which exist precisely if 2 {\displaystyle 2}

7490-576: The general case. Consider the polynomial f ( n ) = n 2 − 5 {\displaystyle f(n)=n^{2}-5} and its values for n ∈ N . {\displaystyle n\in \mathbb {N} .} The prime factorizations of these values are given as follows: The prime factors p {\displaystyle p} dividing f ( n ) {\displaystyle f(n)} are p = 2 , 5 {\displaystyle p=2,5} , and every prime whose final digit

7597-525: The health of his second wife Minna over 13 years; both his daughters later suffered from the same disease. Gauss himself gave only slight hints of his distress: in a letter to Bessel dated December 1831 he described himself as "the victim of the worst domestic sufferings". By reason of his wife's illness, both younger sons were educated for some years in Celle , far from Göttingen. The military career of his elder son Joseph ended after more than two decades with

7704-460: The history of science and more time than he wished to spend. Soon after Gauss's death, his friend Sartorius published the first biography (1856), written in a rather enthusiastic style. Sartorius saw him as a serene and forward-striving man with childlike modesty, but also of "iron character" with an unshakeable strength of mind. Apart from his closer circle, others regarded him as reserved and unapproachable "like an Olympian sitting enthroned on

7811-467: The idea of a unified Germany. As far as the political system is concerned, he had a low estimation of the constitutional system; he criticized parliamentarians of his time for a lack of knowledge and logical errors. Some Gauss biographers have speculated on his religious beliefs. He sometimes said "God arithmetizes" and "I succeeded – not on account of my hard efforts, but by the grace of the Lord." Gauss

7918-478: The latter are all ≡ ±3 (mod 8). This leads to −2 is in rows 3, 11, 17, 19, 41, 43, but not in rows 5, 7, 13, 23, 29, 31, 37, or 47. The former are ≡ 1 or ≡ 3 (mod 8), and the latter are ≡ 5, 7 (mod 8). 3 is in rows 11, 13, 23, 37, and 47, but not in rows 5, 7, 17, 19, 29, 31, 41, or 43. The former are ≡ ±1 (mod 12) and the latter are all ≡ ±5 (mod 12). −3 is in rows 7, 13, 19, 31, 37, and 43 but not in rows 5, 11, 17, 23, 29, 41, or 47. The former are ≡ 1 (mod 3) and

8025-400: The latter ≡ 2 (mod 3). Since the only residue (mod 3) is 1, we see that −3 is a quadratic residue modulo every prime which is a residue modulo 3. 5 is in rows 11, 19, 29, 31, and 41 but not in rows 3, 7, 13, 17, 23, 37, 43, or 47. The former are ≡ ±1 (mod 5) and the latter are ≡ ±2 (mod 5). Since the only residues (mod 5) are ±1, we see that 5 is a quadratic residue modulo every prime which

8132-598: The mathematician Gotthold Eisenstein in Berlin. Gauss was loyal to the House of Hanover . After King William IV died in 1837, the new Hanoverian King Ernest Augustus annulled the 1833 constitution. Seven professors, later known as the " Göttingen Seven ", protested against this, among them his friend and collaborator Wilhelm Weber and Gauss's son-in-law Heinrich Ewald. All of them were dismissed, and three of them were expelled, but Ewald and Weber could stay in Göttingen. Gauss

8239-424: The most standard statement is: Law of quadratic reciprocity  —  Let p and q be distinct odd prime numbers, and define the Legendre symbol as Then This law, together with its 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 ≡

8346-446: The multiplicative group modulo 15. Moreover, although 7 and 8 are quadratic non-residues, their product 7x8 = 11 is also a quadratic non-residue, in contrast to the prime case. Quadratic residues appear as entries in the following table, indexed by the row number as modulus and column number as root: This table is complete for odd primes less than 50. To check whether a number m is a quadratic residue mod one of these primes p , find

8453-502: The number of solutions of the equation x 2 + y 2 = 2 {\displaystyle x^{2}+y^{2}=2} with x , y ∈ Z p , {\displaystyle x,y\in \mathbb {Z} _{p},} which can be solved by standard methods. Namely, all its solutions where x y ≠ 0 , x ≠ ± y {\displaystyle xy\neq 0,x\neq \pm y} can be grouped into octuplets of

8560-590: The observatory was completed, Gauss took his living accommodation in the western wing of the new observatory and Harding in the eastern one. They had once been on friendly terms, but over time they became alienated, possibly – as some biographers presume – because Gauss had wished the equal-ranked Harding to be no more than his assistant or observer. Gauss used the new meridian circles nearly exclusively, and kept them away from Harding, except for some very seldom joint observations. Brendel subdivides Gauss's astronomic activity chronologically into seven periods, of which

8667-437: The original equation. Therefore, 2 {\displaystyle 2} is a residue modulo p {\displaystyle p} if and only if 8 {\displaystyle 8} divides p − ( − 1 ) p − 1 2 {\displaystyle p-(-1)^{\frac {p-1}{2}}} . This is a reformulation of the condition stated above. The theorem

8774-411: The original languages. His favorite English author was Walter Scott , his favorite German Jean Paul . Gauss liked singing and went to concerts. He was a busy newspaper reader; in his last years, he used to visit an academic press salon of the university every noon. Gauss did not care much for philosophy, and mocked the "splitting hairs of the so-called metaphysicians", by which he meant proponents of

8881-444: The other hand, are antisymmetric: The entry for row p , column q is R (resp N ) if and only if the entry at row q , column p , is N (resp R ). The reciprocity law states that these patterns hold for all p and q . Ordering the rows and columns mod 4 makes the pattern clearer. The supplements provide solutions to specific cases of quadratic reciprocity. They are often quoted as partial results, without having to resort to

8988-679: The possible a {\displaystyle a} are quadratic residues and the remaining are not. The intractability of the quadratic residuosity problem is the basis for the security of the Blum Blum Shub pseudorandom number generator . It also yields the public key Goldwasser–Micali cryptosystem , as well as the identity based Cocks scheme . Gauss This is an accepted version of this page Johann Carl Friedrich Gauss (German: Gauß [kaʁl ˈfʁiːdʁɪç ˈɡaʊs] ; Latin : Carolus Fridericus Gauss ; 30 April 1777 – 23 February 1855)

9095-475: The problem by accepting offers from Berlin in 1810 and 1825 to become a full member of the Prussian Academy without burdening lecturing duties, as well as from Leipzig University in 1810 and from Vienna University in 1842, perhaps because of the family's difficult situation. Gauss's salary was raised from 1000 Reichsthaler in 1810 to 2400 Reichsthaler in 1824, and in his later years he was one of

9202-425: The product of a power of 2 and any number of distinct Fermat primes . In the same section, he gives a result on the number of solutions of certain cubic polynomials with coefficients in finite fields , which amounts to counting integral points on an elliptic curve . An unfinished eighth chapter was found among left papers only after his death, consisting of work done during 1797–1799. One of Gauss's first results

9309-472: The quadratic residues modulo 5 {\displaystyle 5} . Therefore, except for p = 2 , 5 {\displaystyle p=2,5} , we have that 5 {\displaystyle 5} is a quadratic residue modulo p {\displaystyle p} iff p {\displaystyle p} is a quadratic residue modulo 5 {\displaystyle 5} . The law of quadratic reciprocity gives

9416-592: The railroad system in the US for some months. Eugen left Göttingen in September 1830 and emigrated to the United States, where he joined the army for five years. He then worked for the American Fur Company in the Midwest. Later, he moved to Missouri and became a successful businessman. Wilhelm married a niece of the astronomer Bessel ; he then moved to Missouri, started as a farmer and became wealthy in

9523-437: The rank of a poorly paid first lieutenant , although he had acquired a considerable knowledge of geodesy. He needed financial support from his father even after he was married. The second son Eugen shared a good measure of his father's talent in computation and languages, but had a vivacious and sometimes rebellious character. He wanted to study philology, whereas Gauss wanted him to become a lawyer. Having run up debts and caused

9630-435: The reader the author's train of thought. Gauss was the first to restore that rigor of demonstration which we admire in the ancients and which had been forced unduly into the background by the exclusive interest of the preceding period in new developments. But for himself, he propagated a quite different ideal, given in a letter to Farkas Bolyai as follows: It is not knowledge, but the act of learning, not possession but

9737-411: The results by masterly estimation. Nevertheless, his calculations were not always free from mistakes. He coped with the enormous workload by using skillful tools. Gauss used a lot of mathematical tables , examined their exactness, and constructed new tables on various matters for personal use. He developed new tools for effective calculation, for example the Gaussian elimination . It has been taken as

9844-613: The shoe business in St. Louis in later years. Eugene and William have numerous descendants in America, but the Gauss descendants left in Germany all derive from Joseph, as the daughters had no children. In the first two decades of the 19th century, Gauss was the only important mathematician in Germany, comparable to the leading French ones; his Disquisitiones Arithmeticae was the first mathematical book from Germany to be translated into

9951-448: The sign of ( a p 1 ) {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}} and ( a p 2 ) {\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}} . The allowed a {\displaystyle a} in the quadratic residue problem given as above constitute exactly those two parts corresponding to

10058-567: The sum. Gauss took on the directorate of the 60-year-old observatory, founded in 1748 by Prince-elector George II and built on a converted fortification tower, with usable, but partly out-of-date instruments. The construction of a new observatory had been approved by Prince-elector George III in principle since 1802, and the Westphalian government continued the planning, but Gauss could not move to his new place of work until September 1816. He got new up-to-date instruments, including two meridian circles from Repsold and Reichenbach , and

10165-577: The summer of 1821. After a short time at university, in 1824 Joseph joined the Hanoverian army and assisted in surveying again in 1829. In the 1830s he was responsible for the enlargement of the survey network to the western parts of the kingdom. With his geodetical qualifications, he left the service and engaged in the construction of the railway network as director of the Royal Hanoverian State Railways . In 1836 he studied

10272-421: The summit of science". His close contemporaries agreed that Gauss was a man of difficult character. He often refused to accept compliments. His visitors were occasionally irritated by his grumpy behaviour, but a short time later his mood could change, and he would become a charming, open-minded host. Gauss abominated polemic natures; together with his colleague Hausmann he opposed to a call for Justus Liebig on

10379-697: The values 1 , … , p − 1 {\displaystyle 1,\ldots ,p-1} , and it is − 1 {\displaystyle -1} for the remaining. It is easy to compute using the law of quadratic reciprocity in a manner akin to the Euclidean algorithm ; see Legendre symbol . Consider now some given N = p 1 p 2 {\displaystyle N=p_{1}p_{2}} where p 1 {\displaystyle p_{1}} and p 2 {\displaystyle p_{2}} are two different unknown primes. A given

10486-421: The years since 1820 are taken as a "period of lower astronomical activity". The new, well-equipped observatory did not work as effectively as other ones; Gauss's astronomical research had the character of a one-man enterprise without a long-time observation program, and the university established a place for an assistant only after Harding died in 1834. Nevertheless, Gauss twice refused the opportunity to solve

10593-630: Was Abraham Gotthelf Kästner , whom Gauss called "the leading mathematician among poets, and the leading poet among mathematicians" because of his epigrams . Astronomy was taught by Karl Felix Seyffer , with whom Gauss stayed in correspondence after graduation; Olbers and Gauss mocked him in their correspondence. On the other hand, he thought highly of Georg Christoph Lichtenberg , his teacher of physics, and of Christian Gottlob Heyne , whose lectures in classics Gauss attended with pleasure. Fellow students of this time were Johann Friedrich Benzenberg , Farkas Bolyai , and Heinrich Wilhelm Brandes . He

10700-585: Was a German mathematician , astronomer , geodesist , and physicist who contributed to many fields in mathematics and science. He was director of the Göttingen Observatory and professor of astronomy from 1807 until his death in 1855. He is widely considered one of the greatest mathematicians ever. While studying at the University of Göttingen , he propounded several mathematical theorems . Gauss completed his masterpieces Disquisitiones Arithmeticae and Theoria motus corporum coelestium as

10807-792: Was a member of the Lutheran church , like most of the population in northern Germany. It seems that he did not believe all dogmas or understand the Holy Bible quite literally. Sartorius mentioned Gauss's religious tolerance , and estimated his "insatiable thirst for truth" and his sense of justice as motivated by religious convictions. In his doctoral thesis from 1799, Gauss proved the fundamental theorem of algebra which states that every non-constant single-variable polynomial with complex coefficients has at least one complex root . Mathematicians including Jean le Rond d'Alembert had produced false proofs before him, and Gauss's dissertation contains

10914-701: Was deeply affected by this quarrel but saw no possibility to help them. Gauss took part in academic administration: three times he was elected as dean of the Faculty of Philosophy. Being entrusted with the widow's pension fund of the university, he dealt with actuarial science and wrote a report on the strategy for stabilizing the benefits. He was appointed director of the Royal Academy of Sciences in Göttingen for nine years. Gauss remained mentally active into his old age, even while suffering from gout and general unhappiness. On 23 February 1855, he died of

11021-401: Was formulated in many ways before its modern form: Euler and Legendre did not have Gauss's congruence notation, nor did Gauss have the Legendre symbol. In this article p and q always refer to distinct positive odd primes, and x and y to unspecified integers. Fermat proved (or claimed to have proved) a number of theorems about expressing a prime by a quadratic form: He did not state

11128-517: Was in keeping with the motto of his personal seal Pauca sed Matura ("Few, but Ripe"). Many colleagues encouraged him to publicize new ideas and sometimes rebuked him if he hesitated too long, in their opinion. Gauss defended himself, claiming that the initial discovery of ideas was easy, but preparing a presentable elaboration was a demanding matter for him, for either lack of time or "serenity of mind". Nevertheless, he published many short communications of urgent content in various journals, but left

11235-484: Was likely a self-taught student in mathematics since he independently rediscovered several theorems. He solved a geometrical problem that had occupied mathematicians since the Ancient Greeks , when he determined in 1796 which regular polygons can be constructed by compass and straightedge . This discovery ultimately led Gauss to choose mathematics instead of philology as a career. Gauss's mathematical diary,

11342-512: Was removed, preserved, and studied by Rudolf Wagner , who found its mass to be slightly above average, at 1,492 grams (3.29 lb). Wagner's son Hermann , a geographer, estimated the cerebral area to be 219,588 square millimetres (340.362 sq in) in his doctoral thesis. In 2013, a neurobiologist at the Max Planck Institute for Biophysical Chemistry in Göttingen discovered that Gauss's brain had been mixed up soon after

11449-454: Was the empirically found conjecture of 1792 – the later called prime number theorem – giving an estimation of the number of prime numbers by using the integral logarithm . Law of 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

#500499