In mathematics, the Fibonacci numbers denoted Fn form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F 0 = 0, F 1 = 1, F n = F n − 1 + F n − 2, for n > 1. One has F2 = 1. In some books, in old ones, F0, the "0" is omitted, the Fibonacci sequence starts with F1 = F2 = 1; the beginning of the sequence is thus: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … Fibonacci numbers are related to the golden ratio: Binet's formula expresses the nth Fibonacci number in terms of n and the golden ratio, implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases. Fibonacci numbers are named after Italian mathematician Leonardo of Pisa known as Fibonacci, they appear to have first arisen as early as 200 BC in work by Pingala on enumerating possible patterns of poetry formed from syllables of two lengths. In his 1202 book Liber Abaci, Fibonacci introduced the sequence to Western European mathematics, although the sequence had been described earlier in Indian mathematics.
Fibonacci numbers appear unexpectedly in mathematics, so much so that there is an entire journal dedicated to their study, the Fibonacci Quarterly. Applications of Fibonacci numbers include computer algorithms such as the Fibonacci search technique and the Fibonacci heap data structure, graphs called Fibonacci cubes used for interconnecting parallel and distributed systems, they appear in biological settings, such as branching in trees, the arrangement of leaves on a stem, the fruit sprouts of a pineapple, the flowering of an artichoke, an uncurling fern and the arrangement of a pine cone's bracts. Fibonacci numbers are closely related to Lucas numbers L n in that they form a complementary pair of Lucas sequences U n = F n and V n = L n. Lucas numbers are intimately connected with the golden ratio; the Fibonacci sequence appears in Indian mathematics in connection with Sanskrit prosody, as pointed out by Parmanand Singh in 1985. In the Sanskrit poetic tradition, there was interest in enumerating all patterns of long syllables of 2 units duration, juxtaposed with short syllables of 1 unit duration.
Counting the different patterns of successive L and S with a given total duration results in the Fibonacci numbers: the number of patterns of duration m units is Fm + 1. Knowledge of the Fibonacci sequence was expressed as early as Pingala. Singh cites Pingala's cryptic formula misrau cha and scholars who interpret it in context as saying that the number of patterns for m beats is obtained by adding one to the Fm cases and one to the Fm−1 cases. Bharata Muni expresses knowledge of the sequence in the Natya Shastra. However, the clearest exposition of the sequence arises in the work of Virahanka, whose own work is lost, but is available in a quotation by Gopala: Variations of two earlier meters... For example, for four, variations of meters of two three being mixed, five happens.... In this way, the process should be followed in all mātrā-vṛttas. Hemachandra is credited with knowledge of the sequence as well, writing that "the sum of the last and the one before the last is the number... of the next mātrā-vṛtta."
Outside India, the Fibonacci sequence first appears in the book Liber Abaci by Fibonacci. Using it to calculate the growth of rabbit populations. Fibonacci considers the growth of a hypothetical, idealized rabbit population, assuming that: a newly born pair of rabbits, one male, one female, are put in a field. Fibonacci posed the puzzle: how many pairs will there be in one year? At the end of the first month, they mate. At the end of the second month the female produces a new pair, so now there are 2 pairs of rabbits in the field. At the end of the third month, the original female produces a second pair, making 3 pairs in all in the field. At the end of the fourth month, the original female has produced yet another new pair, the female born two months ago produces her first pair, making 5 pairs. At the end of the nth month, the number of pairs of rabbits is equal to the number of new pairs plus the number of pairs alive last month; this is the nth Fibonacci number. The name "Fibonacci sequence" was first used by the 19th
Number theory is a branch of pure mathematics devoted to the study of the integers. German mathematician Carl Friedrich Gauss said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of objects made out of integers or defined as generalizations of the integers. Integers can be considered either as solutions to equations. Questions in number theory are best understood through the study of analytical objects that encode properties of the integers, primes or other number-theoretic objects in some fashion. One may study real numbers in relation to rational numbers, for example, as approximated by the latter; the older term for number theory is arithmetic. By the early twentieth century, it had been superseded by "number theory"; the use of the term arithmetic for number theory regained some ground in the second half of the 20th century, arguably in part due to French influence. In particular, arithmetical is preferred as an adjective to number-theoretic.
The first historical find of an arithmetical nature is a fragment of a table: the broken clay tablet Plimpton 322 contains a list of "Pythagorean triples", that is, integers such that a 2 + b 2 = c 2. The triples are too large to have been obtained by brute force; the heading over the first column reads: "The takiltum of the diagonal, subtracted such that the width..." The table's layout suggests that it was constructed by means of what amounts, in modern language, to the identity 2 + 1 = 2, implicit in routine Old Babylonian exercises. If some other method was used, the triples were first constructed and reordered by c / a for actual use as a "table", for example, with a view to applications, it is not known whether there could have been any. It has been suggested instead. While Babylonian number theory—or what survives of Babylonian mathematics that can be called thus—consists of this single, striking fragment, Babylonian algebra was exceptionally well developed. Late Neoplatonic sources state.
Much earlier sources state that Pythagoras traveled and studied in Egypt. Euclid IX 21–34 is probably Pythagorean. Pythagorean mystics gave great importance to the even; the discovery that 2 is irrational is credited to the early Pythagoreans. By revealing that numbers could be irrational, this discovery seems to have provoked the first foundational crisis in mathematical history; this forced a distinction between numbers, on the one hand, lengths and proportions, on the other hand. The Pythagorean tradition spoke of so-called polygonal or figurate numbers. While square numbers, cubic numbers, etc. are seen now as more natural than triangular numbers, pentagonal numbers, etc. the study of the sums of triangular and pentagonal numbers would prove fruitful in the early modern period. We know of no arithmetical material in ancient Egyptian or Vedic sources, though there is some algebra in both; the Chinese remainder theorem appears as an exercise in Sunzi Suanjing There is some numerical mysticism in Chinese mathematics, unlike that of the Pythagoreans, it seems to have led nowhere.
Like the Pythagoreans' perfect numbers, magic squares have passed from superstition into recreation. Aside from a few fragments, the mathematics of Classical Greece is known to us either through the reports of contemporary non-m
Adrien-Marie Legendre was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are named after him. Adrien-Marie Legendre was born in Paris on 18 September 1752 to a wealthy family, he received his education at the Collège Mazarin in Paris, defended his thesis in physics and mathematics in 1770. He taught at the École Militaire in Paris from 1775 to 1780 and at the École Normale from 1795. At the same time, he was associated with the Bureau des Longitudes. In 1782, the Berlin Academy awarded Legendre a prize for his treatise on projectiles in resistant media; this treatise brought him to the attention of Lagrange. The Académie des sciences made Legendre an adjoint member in 1783 and an associate in 1785. In 1789, he was elected a Fellow of the Royal Society, he assisted with the Anglo-French Survey to calculate the precise distance between the Paris Observatory and the Royal Greenwich Observatory by means of trigonometry.
To this end in 1787 he visited Dover and London together with Dominique, comte de Cassini and Pierre Méchain. The three visited William Herschel, the discoverer of the planet Uranus. Legendre lost his private fortune in 1793 during the French Revolution; that year, he married Marguerite-Claudine Couhin, who helped him put his affairs in order. In 1795, Legendre became one of six members of the mathematics section of the reconstituted Académie des Sciences, renamed the Institut National des Sciences et des Arts. In 1803, Napoleon reorganized the Institut National, Legendre became a member of the Geometry section. From 1799 to 1812, Legendre served as mathematics examiner for graduating artillery students at the École Militaire and from 1799 to 1815 he served as permanent mathematics examiner for the École Polytechnique. In 1824, Legendre's pension from the École Militaire was stopped because he refused to vote for the government candidate at the Institut National, his pension was reinstated with the change in government in 1828.
In 1831, he was made an officer of the Légion d'Honneur. Legendre died in Paris on 10 January 1833, after a long and painful illness, Legendre's widow preserved his belongings to memorialize him. Upon her death in 1856, she was buried next to her husband in the village of Auteuil, where the couple had lived, left their last country house to the village. Legendre's name is one of the 72 names inscribed on the Eiffel Tower. Abel's work on elliptic functions was built on Legendre's and some of Gauss' work in statistics and number theory completed that of Legendre, he developed the least squares method and firstly communicated it to his contemporaries before Gauss, which has broad application in linear regression, signal processing and curve fitting. Today, the term "least squares method" is used as a direct translation from the French "méthode des moindres carrés", his major work is Exercices de Calcul Intégral, published in three volumes in 1811, 1817 and 1819. In the first volume he introduced the basic properties of elliptic integrals, beta functions and gamma functions, introducing the symbol Γ normalizing it to Γ = n!.
Further results on the beta and gamma functions along with their applications to mechanics - such as the rotation of the earth, the attraction of ellipsoids, appeared in the second volume. In 1830, he gave a proof of Fermat's last theorem for exponent n = 5, proven by Lejeune Dirichlet in 1828. In number theory, he conjectured the quadratic reciprocity law, subsequently proved by Gauss, he did pioneering work on the distribution of primes, on the application of analysis to number theory. His 1798 conjecture of the prime number theorem was rigorously proved by Hadamard and de la Vallée-Poussin in 1896. Legendre did an impressive amount of work on elliptic functions, including the classification of elliptic integrals, but it took Abel's stroke of genius to study the inverses of Jacobi's functions and solve the problem completely, he is known for the Legendre transformation, used to go from the Lagrangian to the Hamiltonian formulation of classical mechanics. In thermodynamics it is used to obtain the enthalpy and the Helmholtz and Gibbs energies from the internal energy.
He is the namesake of the Legendre polynomials, solutions to Legendre's differential equation, which occur in physics and engineering applications, e.g. electrostatics. Legendre is best known as the author of Éléments de géométrie, published in 1794 and was the leading elementary text on the topic for around 100 years; this text rearranged and simplified many of the propositions from Euclid's Elements to create a more effective textbook. Foreign Honorary Member of the American Academy of Arts and Sciences The Moon crater Legendre is named after him. Main-belt asteroid. Legendre is one of the 72 prominent French scientists who were commemorated on plaques at the first stage of the Eiffel Tower when it first opened. Essays1782 Recherches sur la trajectoire des projectiles dans les milieux résistants BooksEléments de géométrie, textbook 1794 Essai sur la Théorie des Nombres 1797-8, 2nd ed. 1808, 3rd ed. in 2 vol. 1830 Nouvelles Méthodes pour la Détermination des Orbites des Comètes, 1805 Exercices de Calcul Intégral, book in three volumes 1811, 1817, 1819 Traité des Fonctions Elliptiques, book in three volumes 1825, 1826, 1830Memoires in Histoire de l'Académie Royale des Scien
Oxford University Press
Oxford University Press is the largest university press in the world, the second oldest after Cambridge University Press. It is a department of the University of Oxford and is governed by a group of 15 academics appointed by the vice-chancellor known as the delegates of the press, they are headed by the secretary to the delegates, who serves as OUP's chief executive and as its major representative on other university bodies. Oxford University has used a similar system to oversee OUP since the 17th century; the Press is located on opposite Somerville College, in the suburb Jericho. The Oxford University Press Museum is located on Oxford. Visits are led by a member of the archive staff. Displays include a 19th-century printing press, the OUP buildings, the printing and history of the Oxford Almanack, Alice in Wonderland and the Oxford English Dictionary; the university became involved in the print trade around 1480, grew into a major printer of Bibles, prayer books, scholarly works. OUP took on the project that became the Oxford English Dictionary in the late 19th century, expanded to meet the ever-rising costs of the work.
As a result, the last hundred years has seen Oxford publish children's books, school text books, journals, the World's Classics series, a range of English language teaching texts. Moves into international markets led to OUP opening its own offices outside the United Kingdom, beginning with New York City in 1896. With the advent of computer technology and harsh trading conditions, the Press's printing house at Oxford was closed in 1989, its former paper mill at Wolvercote was demolished in 2004. By contracting out its printing and binding operations, the modern OUP publishes some 6,000 new titles around the world each year; the first printer associated with Oxford University was Theoderic Rood. A business associate of William Caxton, Rood seems to have brought his own wooden printing press to Oxford from Cologne as a speculative venture, to have worked in the city between around 1480 and 1483; the first book printed in Oxford, in 1478, an edition of Rufinus's Expositio in symbolum apostolorum, was printed by another, printer.
Famously, this was mis-dated in Roman numerals as "1468", thus pre-dating Caxton. Rood's printing included John Ankywyll's Compendium totius grammaticae, which set new standards for teaching of Latin grammar. After Rood, printing connected with the university remained sporadic for over half a century. Records or surviving work are few, Oxford did not put its printing on a firm footing until the 1580s. In response to constraints on printing outside London imposed by the Crown and the Stationers' Company, Oxford petitioned Elizabeth I of England for the formal right to operate a press at the university; the chancellor, Robert Dudley, 1st Earl of Leicester, pleaded Oxford's case. Some royal assent was obtained, since the printer Joseph Barnes began work, a decree of Star Chamber noted the legal existence of a press at "the universitie of Oxforde" in 1586. Oxford's chancellor, Archbishop William Laud, consolidated the legal status of the university's printing in the 1630s. Laud envisaged a unified press of world repute.
Oxford would establish it on university property, govern its operations, employ its staff, determine its printed work, benefit from its proceeds. To that end, he petitioned Charles I for rights that would enable Oxford to compete with the Stationers' Company and the King's Printer, obtained a succession of royal grants to aid it; these were brought together in Oxford's "Great Charter" in 1636, which gave the university the right to print "all manner of books". Laud obtained the "privilege" from the Crown of printing the King James or Authorized Version of Scripture at Oxford; this "privilege" created substantial returns in the next 250 years, although it was held in abeyance. The Stationers' Company was alarmed by the threat to its trade and lost little time in establishing a "Covenant of Forbearance" with Oxford. Under this, the Stationers paid an annual rent for the university not to exercise its full printing rights – money Oxford used to purchase new printing equipment for smaller purposes.
Laud made progress with internal organization of the Press. Besides establishing the system of Delegates, he created the wide-ranging supervisory post of "Architypographus": an academic who would have responsibility for every function of the business, from print shop management to proofreading; the post was more an ideal than a workable reality, but it survived in the loosely structured Press until the 18th century. In practice, Oxford's Warehouse-Keeper dealt with sales and the hiring and firing of print shop staff. Laud's plans, hit terrible obstacles, both personal and political. Falling foul of political intrigue, he was executed in 1645, by which time the English Civil War had broken out. Oxford became a Royalist stronghold during the conflict, many printers in the city concentrated on producing political pamphlets or sermons; some outstanding mathematical and Orientalist works emerged at this time—notably, texts edited by Edward Pococke, the Regius Professor of Hebrew—but no university press on Laud's model was possible before the Restoration of the Monarchy in 1660.
It was established by the vice-chancellor, John Fell, Dean of Christ Church, Bishop of Oxford, Secretary to the Delegates. Fell regarded Laud as a martyr, was determined to honour his vision of the Press. Using the provisions of the Great Charter, Fell persuaded Oxford to refuse any further payments from the Stationers and drew
Leopold Kronecker was a German mathematician who worked on number theory and logic. He criticized Georg Cantor's work on set theory, was quoted by Weber as having said, "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk". Kronecker was a student and lifelong friend of Ernst Kummer. Leopold Kronecker was born on 7 December 1823 in Prussia in a wealthy Jewish family, his parents and Johanna, took care of their children's education and provided them with private tutoring at home – Leopold's younger brother Hugo Kronecker would follow a scientific path becoming a notable physiologist. Kronecker went to the Liegnitz Gymnasium where he was interested in a wide range of topics including science and philosophy, while practicing gymnastics and swimming. At the gymnasium he was taught by Ernst Kummer, who noticed and encouraged the boy's interest in mathematics. In 1841 Kronecker became a student at the University of Berlin where his interest did not focus on mathematics, but rather spread over several subjects including astronomy and philosophy.
He spent the summer of 1843 at the University of Bonn studying astronomy and 1843–44 at the University of Breslau following his former teacher Kummer. Back in Berlin, Kronecker studied mathematics with Peter Gustav Lejeune Dirichlet and in 1845 defended his dissertation in algebraic number theory written under Dirichlet's supervision. After obtaining his degree, Kronecker did not follow his interest in research on an academic career path, he went back to his hometown to manage a large farming estate built up by his mother's uncle, a former banker. In 1848 he married his cousin Fanny Prausnitzer, the couple had six children. For several years Kronecker focused on business, although he continued to study mathematics as a hobby and corresponded with Kummer, he published no mathematical results. In 1853 he wrote a memoir on the algebraic solvability of equations extending the work of Évariste Galois on the theory of equations. Due to his business activity, Kronecker was financially comfortable, thus he could return to Berlin in 1855 to pursue mathematics as a private scholar.
Dirichlet, whose wife Rebecka came from the wealthy Mendelssohn family, had introduced Kronecker to the Berlin elite. He became a close friend of Karl Weierstrass, who had joined the university, his former teacher Kummer who had just taken over Dirichlet's mathematics chair. Over the following years Kronecker published numerous papers resulting from his previous years' independent research; as a result of this published research, he was elected a member of the Berlin Academy in 1861. Although he held no official university position, Kronecker had the right as a member of the Academy to hold classes at the University of Berlin and he decided to do so, starting in 1862. In 1866, when Riemann died, Kronecker was offered the mathematics chair at the University of Göttingen, but he refused, preferring to keep his position at the Academy. Only in 1883, when Kummer retired from the University, was Kronecker invited to succeed him and became an ordinary professor. Kronecker was the supervisor of Kurt Hensel, Adolf Kneser, Mathias Lerch, Franz Mertens, amongst others.
His philosophical view of mathematics put him in conflict with several mathematicians over the years, notably straining his relationship with Weierstrass, who decided to leave the University in 1888. Kronecker died on 29 December 1891 in several months after the death of his wife. In the last year of his life, he converted to Christianity, he is buried in the Alter St Matthäus Kirchhof cemetery in Berlin-Schöneberg, close to Gustav Kirchhoff. An important part of Kronecker's research focused on number algebra. In an 1853 paper on the theory of equations and Galois theory he formulated the Kronecker–Weber theorem, without however offering a definitive proof, he introduced the structure theorem for finitely-generated abelian groups. Kronecker studied elliptic functions and conjectured his "liebster Jugendtraum", a generalization, put forward by Hilbert in a modified form as his twelfth problem. In an 1850 paper, On the Solution of the General Equation of the Fifth Degree, Kronecker solved the quintic equation by applying group theory.
In algebraic number theory Kronecker introduced the theory of divisors as an alternative to Dedekind's theory of ideals, which he did not find acceptable for philosophical reasons. Although the general adoption of Dedekind's approach led Kronecker's theory to be ignored for a long time, his divisors were found useful and were revived by several mathematicians in the 20th century. Kronecker contributed to the concept of continuity, reconstructing the form of irrational numbers in real numbers. In analysis, Kronecker rejected the formulation of a continuous, nowhere differentiable function by his colleague, Karl Weierstrass. Named for Kronecker are the Kronecker limit formula, Kronecker's congruence, Kronecker delta, Kronecker comb, Kronecker symbol, Kronecker product, Kronecker's method for factorizing polynomials, Kronecker substitution, Kronecker's theorem in number theory, Kronecker's lemma, Eisenstein–Kronecker numbers. Kronecker's finitism made him a forerunner of intuitionism in foundations of mathematics.
Kronecker was elected as a member of several academies: Prussian Academy of Sciences French Academy of Sciences Roy
A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1, not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 6 is composite because it is the product of two numbers that are both smaller than 6. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes, unique up to their order; the property of being prime is called primality. A simple but slow method of checking the primality of a given number n, called trial division, tests whether n is a multiple of any integer between 2 and n. Faster algorithms include the Miller–Rabin primality test, fast but has a small chance of error, the AKS primality test, which always produces the correct answer in polynomial time but is too slow to be practical.
Fast methods are available for numbers of special forms, such as Mersenne numbers. As of December 2018 the largest known prime number has 24,862,048 decimal digits. There are infinitely many primes, as demonstrated by Euclid around 300 BC. No known simple formula separates prime numbers from composite numbers. However, the distribution of primes within the natural numbers in the large can be statistically modelled; the first result in that direction is the prime number theorem, proven at the end of the 19th century, which says that the probability of a randomly chosen number being prime is inversely proportional to its number of digits, that is, to its logarithm. Several historical questions regarding prime numbers are still unsolved; these include Goldbach's conjecture, that every integer greater than 2 can be expressed as the sum of two primes, the twin prime conjecture, that there are infinitely many pairs of primes having just one number between them. Such questions spurred the development of various branches of number theory, focusing on analytic or algebraic aspects of numbers.
Primes are used in several routines in information technology, such as public-key cryptography, which relies on the difficulty of factoring large numbers into their prime factors. In abstract algebra, objects that behave in a generalized way like prime numbers include prime elements and prime ideals. A natural number is called a prime number if it is greater than 1 and cannot be written as a product of two natural numbers that are both smaller than it; the numbers greater than 1 that are not prime are called composite numbers. In other words, n is prime if n items cannot be divided up into smaller equal-size groups of more than one item, or if it is not possible to arrange n dots into a rectangular grid, more than one dot wide and more than one dot high. For example, among the numbers 1 through 6, the numbers 2, 3, 5 are the prime numbers, as there are no other numbers that divide them evenly. 1 is not prime, as it is excluded in the definition. 4 = 2 × 2 and 6 = 2 × 3 are both composite. The divisors of a natural number n are the numbers.
Every natural number has both itself as a divisor. If it has any other divisor, it cannot be prime; this idea leads to a different but equivalent definition of the primes: they are the numbers with two positive divisors, 1 and the number itself. Yet another way to express the same thing is that a number n is prime if it is greater than one and if none of the numbers 2, 3, …, n − 1 divides n evenly; the first 25 prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. No number n greater than 2 is prime because any such number can be expressed as the product 2 × n / 2. Therefore, every prime number other than 2 is an odd number, is called an odd prime; when written in the usual decimal system, all prime numbers larger than 5 end in 1, 3, 7, or 9. The numbers that end with other digits are all composite: decimal numbers that end in 0, 2, 4, 6, or 8 are and decimal numbers that end in 0 or 5 are divisible by 5; the set of all primes is sometimes denoted by P or by P.
The Rhind Mathematical Papyrus, from around 1550 BC, has Egyptian fraction expansions of different forms for prime and composite numbers. However, the earliest surviving records of the explicit study of prime numbers come from Ancient Greek mathematics. Euclid's Elements proves the infinitude of primes and the fundamental theorem of arithmetic, shows how to construct a perfect number from a Mersenne prime. Another Greek invention, the Sieve of Eratosthenes, is still used to construct lists of primes. Around 1000 AD, the Islamic mathematician Alhazen found Wilson's theorem, characterizing the prime numbers as the numbers n that evenly divide
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 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 ≡ a for p an odd prime; the theorem was first proved by Gauss. He refers to it as the "fundamental theorem" in the Disquisitiones Arithmeticae and his papers, writing The fundamental theorem must be regarded as one of the most elegant of its type, he referred to it as the "golden theorem." He published six proofs, two more were found in his posthumous papers. There are now over 240 published proofs. Since Gauss, generalizing the reciprocity law has been a leading problem in mathematics, has been crucial to the development of much of the machinery of modern algebra, number theory, algebraic geometry, culminating in Artin reciprocity, class field theory, the Langlands program.
Quadratic reciprocity arises from certain subtle factorization patterns involving perfect square numbers. In this section, we give examples. Consider the polynomial f = n 2 − 5 and its values for n ∈ N; the prime factorizations of these values are given as follows: The prime factors p dividing f are p = 2, 5, every prime whose final digit is 1 or 9. Now, p is a prime factor of some n 2 − 5 whenever n 2 − 5 ≡ 0, i.e. whenever n 2 ≡ 5, i.e. whenever 5 is a quadratic residue modulo p. This happens for p = 2, 5 and those primes with p ≡ 1, 4, note that the latter numbers 1 = 2 and 4 = 2 are the quadratic residues modulo 5. Therefore, except for p = 2, 5, we have that 5 is a quadratic residue modulo p iff p is a quadratic residue modulo 5; the law of quadratic reciprocity gives a similar characterization of prime divisors of f = n 2 − q for any prime q, which leads to a characterization for any integer q. Let p be an odd prime. A number modulo p is a quadratic residue. Here we exclude zero as a special case.
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: There are an equal number of quadratic residues and non-residues. For the avoidance of doubt, these statements do not hold. For example, there are only 2 quadratic residues in the multiplicative group modulo 15. Moreover although 7 and 8 are quadratic non-residues, their product 7x8 = 11 is a quadratic non-residue, in contrast to the prime case. Quadratic residues are entries in the following table: 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 a ≡ m and 0 ≤ a < p. If a is in row p m is a residue; the quadratic reciprocity law is the statement that certain patterns found in the table are true in general. 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, 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, the latter are