1.
Phi
–
Phi is the 21st letter of the Greek alphabet. In Ancient Greek, it represented a voiceless bilabial plosive. In modern Greek, it represents a voiceless fricative and is correspondingly romanized as f. Its origin is uncertain but it may be that phi originated as the letter qoppa, in traditional Greek numerals, phi has a value of 500 or 500 000. The Cyrillic letter Ef descends from phi, phi is also used as a symbol for the golden ratio and on other occasions in math and science. This use is separately encoded as the Unicode glyph ϕ, the modern Greek pronunciation of the letter is sometimes encountered in English when the letter is being used in this sense. The lower-case letter φ is often used to represent the following, Magnetic flux in physics The golden ratio 1 +52 ≈1.618033988749894848204586834. in mathematics, art, Eulers totient function φ in number theory, also called Eulers phi function. The cyclotomic polynomial functions Φn of algebra, in algebra, group or ring homomorphisms In probability theory, ϕ = −½e−x2/2 is the probability density function of the normal distribution. In probability theory, φX = E is the function of a random variable X. An angle, typically the second angle mentioned, after θ, especially, The argument of a complex number. The phase of a wave in signal processing, in spherical coordinates, mathematicians usually refer to phi as the polar angle. The convention in physics is to use phi as the azimuthal angle, one of the dihedral angles in the backbones of proteins in a Ramachandran plot Internal or effective angle of friction. The work function of a surface, in solid-state physics, a shorthand representation for an aromatic functional group in organic chemistry. The ratio of free energy destabilizations of protein mutants in phi value analysis, in cartography, geodesy and navigation, latitude. In aircraft flight mechanics as the symbol for bank angle, in combustion engineering, fuel–air equivalence ratio. The ratio between the fuel air ratio to the stoichiometric fuel air ratio. The Veblen function in set theory Porosity in geology and hydrology, strength reduction factor in structural engineering, used to account for statistical variabilities in materials and construction methods. The symbol for a voiceless fricative in the International Phonetic Alphabet In economics
2.
Number theory
–
Number theory or, in older usage, arithmetic is a branch of pure mathematics devoted primarily to the study of the integers. It is sometimes called The Queen of Mathematics because of its place in the discipline. Number theorists study prime numbers as well as the properties of objects out of integers or defined as generalizations of the integers. Integers can be considered either in themselves or as solutions to equations, questions in number theory are often 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 also study real numbers in relation to rational numbers, the older term for number theory is arithmetic. By the early century, it had been superseded by number theory. The use of the arithmetic for number theory regained some ground in the second half of the 20th century. In particular, arithmetical is preferred as an adjective to number-theoretic. The first historical find of a nature is a fragment of a table. The triples are too many and too large to have been obtained by brute force, the heading over the first column reads, The takiltum of the diagonal which has been subtracted such that the width. The tables layout suggests that it was constructed by means of what amounts, in language, to the identity 2 +1 =2. If some other method was used, the triples were first constructed and then reordered by c / a, presumably for use as a table. It is not known what these applications may have been, or whether there could have any, Babylonian astronomy, for example. It has been suggested instead that the table was a source of examples for school problems. While Babylonian number theory—or what survives of Babylonian mathematics that can be called thus—consists of this single, striking fragment, late Neoplatonic sources state that Pythagoras learned mathematics from the Babylonians. Much earlier sources state that Thales and Pythagoras traveled and studied in Egypt, Euclid IX 21—34 is very probably Pythagorean, it is very simple material, but it is all that is needed to prove that 2 is irrational. Pythagorean mystics gave great importance to the odd and the even, the discovery that 2 is irrational is credited to the early Pythagoreans. This forced a distinction between numbers, on the one hand, and lengths and proportions, on the other hand, the Pythagorean tradition spoke also of so-called polygonal or figurate numbers
3.
Coprime integers
–
In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime if the only positive integer that divides both of them is 1. That is, the common positive factor of the two numbers is 1. This is equivalent to their greatest common divisor being 1, the numerator and denominator of a reduced fraction are coprime. In addition to gcd =1 and =1, the notation a ⊥ b is used to indicate that a and b are relatively prime. For example,14 and 15 are coprime, being divisible by only 1. The numbers 1 and −1 are the only integers coprime to every integer, a fast way to determine whether two numbers are coprime is given by the Euclidean algorithm. The number of integers coprime to an integer n, between 1 and n, is given by Eulers totient function φ. A set of integers can also be called if its elements share no common positive factor except 1. A set of integers is said to be pairwise coprime if a and b are coprime for every pair of different integers in it, a number of conditions are individually equivalent to a and b being coprime, No prime number divides both a and b. There exist integers x and y such that ax + by =1, the integer b has a multiplicative inverse modulo a, there exists an integer y such that by ≡1. In other words, b is a unit in the ring Z/aZ of integers modulo a, the least common multiple of a and b is equal to their product ab, i. e. LCM = ab. As a consequence of the point, if a and b are coprime and br ≡ bs. That is, we may divide by b when working modulo a, as a consequence of the first point, if a and b are coprime, then so are any powers ak and bl. If a and b are coprime and a divides the product bc and this can be viewed as a generalization of Euclids lemma. In a sense that can be made precise, the probability that two randomly chosen integers are coprime is 6/π2, which is about 61%, two natural numbers a and b are coprime if and only if the numbers 2a −1 and 2b −1 are coprime. As a generalization of this, following easily from the Euclidean algorithm in base n >1, a set of integers S = can also be called coprime or setwise coprime if the greatest common divisor of all the elements of the set is 1. For example, the integers 6,10,15 are coprime because 1 is the positive integer that divides all of them. If every pair in a set of integers is coprime, then the set is said to be pairwise coprime, pairwise coprimality is a stronger condition than setwise coprimality, every pairwise coprime finite set is also setwise coprime, but the reverse is not true
4.
Greatest common divisor
–
In mathematics, the greatest common divisor of two or more integers, when at least one of them is not zero, is the largest positive integer that is a divisor of both numbers. For example, the GCD of 8 and 12 is 4, the greatest common divisor is also known as the greatest common factor, highest common factor, greatest common measure, or highest common divisor. This notion can be extended to polynomials and other commutative rings, in this article we will denote the greatest common divisor of two integers a and b as gcd. What is the greatest common divisor of 54 and 24, the number 54 can be expressed as a product of two integers in several different ways,54 ×1 =27 ×2 =18 ×3 =9 ×6. Thus the divisors of 54 are,1,2,3,6,9,18,27,54, similarly, the divisors of 24 are,1,2,3,4,6,8,12,24. The numbers that these two share in common are the common divisors of 54 and 24,1,2,3,6. The greatest of these is 6 and that is, the greatest common divisor of 54 and 24. The greatest common divisor is useful for reducing fractions to be in lowest terms, for example, gcd =14, therefore,4256 =3 ⋅144 ⋅14 =34. Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1, for example,9 and 28 are relatively prime. For example, a 24-by-60 rectangular area can be divided into a grid of, 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, therefore,12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can be divided into a grid of 12-by-12 squares, in practice, this method is only feasible for small numbers, computing prime factorizations in general takes far too long. Here is another example, illustrated by a Venn diagram. Suppose it is desired to find the greatest common divisor of 48 and 180, first, find the prime factorizations of the two numbers,48 =2 ×2 ×2 ×2 ×3,180 =2 ×2 ×3 ×3 ×5. What they share in common is two 2s and a 3, Least common multiple =2 ×2 × ×3 ×5 =720 Greatest common divisor =2 ×2 ×3 =12. To compute gcd, divide 48 by 18 to get a quotient of 2, then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, note that we ignored the quotient in each step except to notice when the remainder reached 0, signalling that we had arrived at the answer. Formally the algorithm can be described as, gcd = a gcd = gcd, in this sense the GCD problem is analogous to e. g. the integer factorization problem, which has no known polynomial-time algorithm, but is not known to be NP-complete. Shallcross et al. showed that a problem is NC-equivalent to the problem of integer linear programming with two variables, if either problem is in NC or is P-complete, the other is as well
5.
Order (group theory)
–
In group theory, a branch of mathematics, the term order is used in two unrelated senses, The order of a group is its cardinality, i. e. the number of elements in its set. Also, the order, sometimes period, of an element a of a group is the smallest positive integer m such that am = e, if no such m exists, a is said to have infinite order. The ordering relation of a partially or totally ordered group and this article is about the first sense of order. The order of a group G is denoted by ord or | G |, the symmetric group S3 has the following multiplication table. This group has six elements, so ord =6, by definition, the order of the identity, e, is 1. Each of s, t, and w squares to e, completing the enumeration, both u and v have order 3, for u2 = v and u3 = vu = e, and v2 = u and v3 = uv = e. The order of a group and that of an element tend to speak about the structure of the group, roughly speaking, the more complicated the factorization of the order the more complicated the group. If the order of group G is 1, then the group is called a trivial group, given an element a, ord =1 if and only if a is the identity. If every element in G is the same as its inverse, then ord =2 and consequently G is abelian since a b = −1 = b −1 a −1 = b a by Elementary group theory. The converse of this statement is not true, for example, the cyclic group Z6 of integers modulo 6 is abelian, but the number 2 has order 3,2 +2 +2 =6 ≡0. The relationship between the two concepts of order is the following, if we write ⟨ a ⟩ = for the subgroup generated by a, for any integer k, we have ak = e if and only if ord divides k. In general, the order of any subgroup of G divides the order of G, more precisely, if H is a subgroup of G, then ord / ord =, where is called the index of H in G, an integer. As an immediate consequence of the above, we see that the order of every element of a group divides the order of the group. For example, in the symmetric group shown above, where ord =6, the following partial converse is true for finite groups, if d divides the order of a group G and d is a prime number, then there exists an element of order d in G. The statement does not hold for composite orders, e. g. the Klein four-group does not have an element of order four) and this can be shown by inductive proof. The consequences of the include, the order of a group G is a power of a prime p if. If a has order, then all powers of a have infinite order as well. If a has order, we have the following formula for the order of the powers of a
6.
Ring (mathematics)
–
In mathematics, a ring is one of the fundamental algebraic structures used in abstract algebra. It consists of a set equipped with two operations that generalize the arithmetic operations of addition and multiplication. Through this generalization, theorems from arithmetic are extended to non-numerical objects such as polynomials, series, matrices, the conceptualization of rings started in the 1870s and completed in the 1920s. Key contributors include Dedekind, Hilbert, Fraenkel, and Noether, rings were first formalized as a generalization of Dedekind domains that occur in number theory, and of polynomial rings and rings of invariants that occur in algebraic geometry and invariant theory. Afterward, they proved to be useful in other branches of mathematics such as geometry. A ring is a group with a second binary operation that is associative, is distributive over the abelian group operation. By extension from the integers, the group operation is called addition. Whether a ring is commutative or not has profound implications on its behavior as an abstract object, as a result, commutative ring theory, commonly known as commutative algebra, is a key topic in ring theory. Its development has greatly influenced by problems and ideas occurring naturally in algebraic number theory. The most familiar example of a ring is the set of all integers, Z, −5, −4, −3, −2, −1,0,1,2,3,4,5. The familiar properties for addition and multiplication of integers serve as a model for the axioms for rings, a ring is a set R equipped with two binary operations + and · satisfying the following three sets of axioms, called the ring axioms 1. R is a group under addition, meaning that, + c = a + for all a, b, c in R. a + b = b + a for all a, b in R. There is an element 0 in R such that a +0 = a for all a in R, for each a in R there exists −a in R such that a + =0. R is a monoid under multiplication, meaning that, · c = a · for all a, b, c in R. There is an element 1 in R such that a ·1 = a and 1 · a = a for all a in R.3. Multiplication is distributive with respect to addition, a ⋅ = + for all a, b, c in R. · a = + for all a, b, c in R. As explained in § History below, many follow a alternative convention in which a ring is not defined to have a multiplicative identity. This article adopts the convention that, unless stated, a ring is assumed to have such an identity
7.
RSA (cryptosystem)
–
RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman. Clifford Cocks, an English mathematician working for the UK intelligence agency GCHQ, had developed an equivalent system in 1973, a user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret, breaking RSA encryption is known as the RSA problem, whether it is as hard as the factoring problem remains an open question. RSA is a relatively slow algorithm, and because of this it is commonly used to directly encrypt user data. More often, RSA passes encrypted shared keys for symmetric key cryptography which in turn can perform bulk encryption-decryption operations at higher speed. The idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman and they also introduced digital signatures and attempted to apply number theory, their formulation used a shared secret key created from exponentiation of some number, modulo a prime numbers. However, they open the problem of realizing a one-way function. Ron Rivest, Adi Shamir, and Leonard Adleman at MIT made several attempts over the course of a year to create a function that is hard to invert. Rivest and Shamir, as scientists, proposed many potential functions while Adleman. They tried many approaches including knapsack-based and permutation polynomials, for a time they thought it was impossible for what they wanted to achieve due to contradictory requirements. In April 1977, they spent Passover at the house of a student, Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one-way function. He spent the rest of the night formalizing his idea and had much of the paper ready by daybreak, the algorithm is now known as RSA – the initials of their surnames in same order as their paper. Clifford Cocks, an English mathematician working for the UK intelligence agency GCHQ, however, given the relatively expensive computers needed to implement it at the time, it was mostly considered a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its secret classification, Kid-RSA is a simplified public-key cipher published in 1997, designed for educational purposes. Some people feel that learning Kid-RSA gives insight into RSA and other public-key ciphers, Patent 4,405,829 for a Cryptographic communications system and method that used the algorithm, on September 20,1983
8.
Leonhard Euler
–
He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion of a mathematical function. He is also known for his work in mechanics, fluid dynamics, optics, astronomy, Euler was one of the most eminent mathematicians of the 18th century, and is held to be one of the greatest in history. He is also considered to be the most prolific mathematician of all time. His collected works fill 60 to 80 quarto volumes, more than anybody in the field and he spent most of his adult life in Saint Petersburg, Russia, and in Berlin, then the capital of Prussia. A statement attributed to Pierre-Simon Laplace expresses Eulers influence on mathematics, Read Euler, read Euler, Leonhard Euler was born on 15 April 1707, in Basel, Switzerland to Paul III Euler, a pastor of the Reformed Church, and Marguerite née Brucker, a pastors daughter. He had two sisters, Anna Maria and Maria Magdalena, and a younger brother Johann Heinrich. Soon after the birth of Leonhard, the Eulers moved from Basel to the town of Riehen, Paul Euler was a friend of the Bernoulli family, Johann Bernoulli was then regarded as Europes foremost mathematician, and would eventually be the most important influence on young Leonhard. Eulers formal education started in Basel, where he was sent to live with his maternal grandmother. In 1720, aged thirteen, he enrolled at the University of Basel, during that time, he was receiving Saturday afternoon lessons from Johann Bernoulli, who quickly discovered his new pupils incredible talent for mathematics. In 1726, Euler completed a dissertation on the propagation of sound with the title De Sono, at that time, he was unsuccessfully attempting to obtain a position at the University of Basel. In 1727, he first entered the Paris Academy Prize Problem competition, Pierre Bouguer, who became known as the father of naval architecture, won and Euler took second place. Euler later won this annual prize twelve times, around this time Johann Bernoullis two sons, Daniel and Nicolaus, were working at the Imperial Russian Academy of Sciences in Saint Petersburg. In November 1726 Euler eagerly accepted the offer, but delayed making the trip to Saint Petersburg while he applied for a physics professorship at the University of Basel. Euler arrived in Saint Petersburg on 17 May 1727 and he was promoted from his junior post in the medical department of the academy to a position in the mathematics department. He lodged with Daniel Bernoulli with whom he worked in close collaboration. Euler mastered Russian and settled life in Saint Petersburg. He also took on a job as a medic in the Russian Navy. The Academy at Saint Petersburg, established by Peter the Great, was intended to improve education in Russia, as a result, it was made especially attractive to foreign scholars like Euler
9.
Carl Friedrich Gauss
–
Johann Carl Friedrich Gauss was born on 30 April 1777 in Brunswick, in the Duchy of Brunswick-Wolfenbüttel, as the son of poor working-class parents. Gauss later solved this puzzle about his birthdate in the context of finding the date of Easter and he was christened and confirmed in a church near the school he attended as a child. A contested story relates that, when he was eight, he figured out how to add up all the numbers from 1 to 100, there are many other anecdotes about his precocity while a toddler, and he made his first ground-breaking mathematical discoveries while still a teenager. He completed Disquisitiones Arithmeticae, his opus, in 1798 at the age of 21. This work was fundamental in consolidating number theory as a discipline and has shaped the field to the present day, while at university, Gauss independently rediscovered several important theorems. Gauss was so pleased by this result that he requested that a regular heptadecagon be inscribed on his tombstone, the stonemason declined, stating that the difficult construction would essentially look like a circle. The year 1796 was most productive for both Gauss and number theory and he discovered a construction of the heptadecagon on 30 March. He further advanced modular arithmetic, greatly simplifying manipulations in number theory, on 8 April he became the first to prove the quadratic reciprocity law. This remarkably general law allows mathematicians to determine the solvability of any quadratic equation in modular arithmetic, the prime number theorem, conjectured on 31 May, gives a good understanding of how the prime numbers are distributed among the integers. Gauss also discovered that every integer is representable as a sum of at most three triangular numbers on 10 July and then jotted down in his diary the note, ΕΥΡΗΚΑ. On October 1 he published a result on the number of solutions of polynomials with coefficients in finite fields, in 1831 Gauss developed a fruitful collaboration with the physics professor Wilhelm Weber, leading to new knowledge in magnetism and the discovery of Kirchhoffs circuit laws in electricity. It was during this time that he formulated his namesake law and they constructed the first electromechanical telegraph in 1833, which connected the observatory with the institute for physics in Göttingen. In 1840, Gauss published his influential Dioptrische Untersuchungen, in which he gave the first systematic analysis on the formation of images under a paraxial approximation. Among his results, Gauss showed that under a paraxial approximation an optical system can be characterized by its cardinal points and he derived the Gaussian lens formula. In 1845, he became associated member of the Royal Institute of the Netherlands, in 1854, Gauss selected the topic for Bernhard Riemanns Habilitationvortrag, Über die Hypothesen, welche der Geometrie zu Grunde liegen. On the way home from Riemanns lecture, Weber reported that Gauss was full of praise, Gauss died in Göttingen, on 23 February 1855 and is interred in the Albani Cemetery there. Two individuals gave eulogies at his funeral, Gausss son-in-law Heinrich Ewald and Wolfgang Sartorius von Waltershausen and his brain was preserved and was studied by Rudolf Wagner who found its mass to be 1,492 grams and the cerebral area equal to 219,588 square millimeters. Highly developed convolutions were also found, which in the early 20th century were suggested as the explanation of his genius, Gauss was a Lutheran Protestant, a member of the St. Albans Evangelical Lutheran church in Göttingen
10.
Disquisitiones Arithmeticae
–
The Disquisitiones Arithmeticae is a textbook of number theory written in Latin by Carl Friedrich Gauss in 1798 when Gauss was 21 and first published in 1801 when he was 24. In this book, Gauss brings together results in number theory obtained by such as Fermat, Euler, Lagrange and Legendre. The Disquisitiones covers both elementary number theory and parts of the area of mathematics now called number theory. However, Gauss did not explicitly recognize the concept of a group and his own title for his subject was Higher Arithmetic. Gauss also states When confronting many difficult problems, derivations have been suppressed for the sake of brevity when readers refer to this work. Although few of the results in these first sections are original, Gauss was the first mathematician to bring this material together and he also realized the importance of the property of unique factorization, which he restates and proves using modern tools. From Section IV onwards, much of the work is original, Section IV itself develops a proof of quadratic reciprocity, Section V, which takes up over half of the book, is a comprehensive analysis of binary and ternary quadratic forms. Section VI includes two different primality tests, Gauss started to write an eighth section on higher order congruences, but he did not complete this, and it was published separately after his death. The eighth section was published as a treatise entitled general investigations on congruences. Its worth notice since Gauss attacked the problem of general congruences from a standpoint closely related to that taken later by Dedekind, Galois, the treatise paved the way for the theory of function fields over a finite field of constants. Ideas unique to that treatise are clear recognition of the importance of the Frobenius morphism, the Disquisitiones was one of the last mathematical works to be written in scholarly Latin. Before the Disquisitiones was published, number theory consisted of a collection of isolated theorems, Gauss brought the work of his predecessors together with his own original work into a systematic framework, filled in gaps, corrected unsound proofs, and extended the subject in numerous ways. The logical structure of the Disquisitiones set a standard for later texts, while recognising the primary importance of logical proof, Gauss also illustrates many theorems with numerical examples. The Disquisitiones was the point for the work of other nineteenth century European mathematicians including Ernst Kummer, Peter Gustav Lejeune Dirichlet. Many of the annotations given by Gauss are in effect announcements of further research of his own and they must have appeared particularly cryptic to his contemporaries, they can now be read as containing the germs of the theories of L-functions and complex multiplication, in particular. Gauss Disquisitiones continued to influence in the 20th century. This was later interpreted as the determination of imaginary quadratic fields with even discriminant and class number 1,2 and 3. Sometimes referred to as the number problem, this more general question was eventually confirmed in 1986
11.
James Joseph Sylvester
–
James Joseph Sylvester FRS was an English mathematician. He made fundamental contributions to theory, invariant theory, number theory, partition theory. He played a role in American mathematics in the later half of the 19th century as a professor at the Johns Hopkins University. At his death, he was professor at Oxford, Sylvester was born James Joseph in London, England. His father, Abraham Joseph, was a merchant, at the age of 14, Sylvester was a student of Augustus De Morgan at the University of London. His family withdrew him from the University after he was accused of stabbing a fellow student with a knife, subsequently, he attended the Liverpool Royal Institution. Sylvester began his study of mathematics at St Johns College, Cambridge in 1831, for the same reason, he was unable to compete for a Fellowship or obtain a Smiths prize. In 1838 Sylvester became professor of philosophy at University College London. In 1841, he was awarded a BA and an MA by Trinity College, following his early retirement, Sylvester published a book entitled The Laws of Verse in which he attempted to codify a set of laws for prosody in poetry. In 1872, he received his B. A. and M. A. from Cambridge. In 1876 Sylvester again crossed the Atlantic Ocean to become the professor of mathematics at the new Johns Hopkins University in Baltimore. His salary was $5,000, which he demanded be paid in gold, after negotiation, agreement was reached on a salary that was not paid in gold. In 1878 he founded the American Journal of Mathematics, the only other mathematical journal in the US at that time was the Analyst, which eventually became the Annals of Mathematics. In 1883, he returned to England to take up the Savilian Professor of Geometry at Oxford University and he held this chair until his death, although in 1892 the University appointed a deputy professor to the same chair. Sylvester invented a number of mathematical terms such as matrix, graph. He coined the term totient for Eulers totient function φ and his collected scientific work fills four volumes. In Discrete geometry he is remembered for Sylvesters Problem and a result on the orchard problem, Sylvester House, a portion of an undergraduate dormitory at Johns Hopkins University, is named in his honor. Several professorships there are named in his honor also, the collected mathematical papers of James Joseph Sylvester, I, New York, AMS Chelsea Publishing, ISBN 978-0-8218-3654-5 Sylvester, James Joseph, Baker, Henry Frederick, ed
12.
Prime number
–
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a number is called a composite number. For example,5 is prime because 1 and 5 are its only positive integer factors, the property of being prime is called primality. A simple but slow method of verifying the primality of a number n is known as trial division. It consists of testing whether n is a multiple of any integer between 2 and n, algorithms much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for numbers of forms, such as Mersenne numbers. As of January 2016, the largest known prime number has 22,338,618 decimal digits, there are infinitely many primes, as demonstrated by Euclid around 300 BC. There is no simple formula that separates prime numbers from composite numbers. However, the distribution of primes, that is to say, many questions regarding prime numbers remain open, such as Goldbachs conjecture, and the twin prime conjecture. Such questions spurred the development of branches of number theory. Prime numbers give rise to various generalizations in other domains, mainly algebra, such as prime elements. A natural number is called a number if it has exactly two positive divisors,1 and the number itself. Natural numbers greater than 1 that are not prime are called composite, among the numbers 1 to 6, the numbers 2,3, and 5 are the prime numbers, while 1,4, and 6 are not prime. 1 is excluded as a number, for reasons explained below. 2 is a number, since the only natural numbers dividing it are 1 and 2. Next,3 is prime, too,1 and 3 do divide 3 without remainder, however,4 is composite, since 2 is another number dividing 4 without remainder,4 =2 ·2. 5 is again prime, none of the numbers 2,3, next,6 is divisible by 2 or 3, since 6 =2 ·3. The image at the right illustrates that 12 is not prime,12 =3 ·4, no even number greater than 2 is prime because by definition, any such number n has at least three distinct divisors, namely 1,2, and n
13.
Arithmetical function
–
In number theory, an arithmetic, arithmetical, or number-theoretic function is a real or complex valued function f defined on the set of natural numbers that expresses some arithmetical property of n. An example of a function is the divisor function whose value at a positive integer n is equal to the number of divisors of n. There is a class of number-theoretic functions that do not fit the above definition. This article provides links to functions of both classes, ∑ p f and ∏ p f mean that the sum or product is over all prime numbers, ∑ p f = f + f + f + ⋯ ∏ p f = f f f ⋯. E. g. if n =12, ∏ d ∣12 f = f f f f f f. The notations can be combined, ∑ p ∣ n f and ∏ p ∣ n f mean that the sum or product is over all prime divisors of n. E. g. if n =24, ∏ p k ∣24 f = f f f f. e. if there is no number that divides both of them. Then an arithmetic function a is additive if a = a + a for all natural numbers m and n. The fundamental theorem of arithmetic states that any integer n can be represented uniquely as a product of powers of primes. < pk are primes and the aj are positive integers and it is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define νp as the exponent of the highest power of the prime p that divides n, I. e. if p is one of the pi then νp = ai, otherwise it is zero. In terms of the above the functions ω and Ω are defined by ω = k, Ω = a1 + a2 +. To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding pi, ai, ω, and Ω. σk is the sum of the kth powers of the divisors of n, including 1 and n. σ1, the sum of the divisors of n, is denoted by σ. Since a positive number to the power is one, σ0 is therefore the number of divisors of n. σ k = ∏ i =1 ω p i k −1 p i k −1 = ∏ i =1 ω, setting k =0 in the second product gives τ = d = ⋯. φ, the Euler totient function, is the number of integers not greater than n that are coprime to n
14.
Bijection
–
In mathematical terms, a bijective function f, X → Y is a one-to-one and onto mapping of a set X to a set Y. A bijection from the set X to the set Y has a function from Y to X. If X and Y are finite sets, then the existence of a means they have the same number of elements. For infinite sets the picture is complicated, leading to the concept of cardinal number. A bijective function from a set to itself is called a permutation. Bijective functions are essential to many areas of including the definitions of isomorphism, homeomorphism, diffeomorphism, permutation group. Satisfying properties and means that a bijection is a function with domain X and it is more common to see properties and written as a single statement, Every element of X is paired with exactly one element of Y. Functions which satisfy property are said to be onto Y and are called surjections, Functions which satisfy property are said to be one-to-one functions and are called injections. With this terminology, a bijection is a function which is both a surjection and an injection, or using words, a bijection is a function which is both one-to-one and onto. Consider the batting line-up of a baseball or cricket team, the set X will be the players on the team and the set Y will be the positions in the batting order The pairing is given by which player is in what position in this order. Property is satisfied since each player is somewhere in the list, property is satisfied since no player bats in two positions in the order. Property says that for each position in the order, there is some player batting in that position, in a classroom there are a certain number of seats. A bunch of students enter the room and the instructor asks them all to be seated. After a quick look around the room, the instructor declares that there is a bijection between the set of students and the set of seats, where each student is paired with the seat they are sitting in. The instructor was able to conclude there were just as many seats as there were students. For any set X, the identity function 1X, X → X, the function f, R → R, f = 2x +1 is bijective, since for each y there is a unique x = /2 such that f = y. In more generality, any linear function over the reals, f, R → R, f = ax + b is a bijection, each real number y is obtained from the real number x = /a. The function f, R →, given by f = arctan is bijective since each real x is paired with exactly one angle y in the interval so that tan = x
15.
Chinese remainder theorem
–
This theorem has this name because it is a theorem about remainders and was first discovered in the 3rd century AD by the Chinese mathematician Sunzi in Sunzi Suanjing. The Chinese remainder theorem is true over every principal ideal domain and it has been generalized to any commutative ring, with a formulation involving ideals. What amounts to an algorithm for solving this problem was described by Aryabhata, special cases of the Chinese remainder theorem were also known to Brahmagupta, and appear in Fibonaccis Liber Abaci. The result was later generalized with a solution called Dayanshu in Qin Jiushaos 1247 Mathematical Treatise in Nine Sections. The notion of congruences was first introduced and used by Gauss in his Disquisitiones Arithmeticae of 1801, Gauss introduces a procedure for solving the problem that had already been used by Euler but was in fact an ancient method that had appeared several times. Nk be integers greater than 1, which are often called moduli or divisors, Let us denote by N the product of the ni. The Chinese remainder theorem asserts that if the ni are pairwise coprime and this may be restated as follows in term of congruences, If the ni are pairwise coprime, and if a1. Ak are any integers, then there exists an x such that x ≡ a 1 ⋮ x ≡ a k. This means that for doing a sequence of operations in Z / N Z, one may do the same computation independently in each Z / n i Z. This may be faster than the direct computation if N. This is widely used, under the name multi-modular computation, for linear algebra over the integers or the rational numbers, the theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family. The existence and the uniqueness of the solution may be proven independently, however, the first proof of existence, given below, uses this uniqueness. Suppose that x and y are both solutions to all the congruences, as x and y give the same remainder, when divided by ni, their difference x − y is a multiple of each ni. As the ni are pairwise coprime, their product N divides also x − y, If x and y are supposed to be non negative and less than N, then their difference may be a multiple of N only if x = y. The map x ↦ maps congruence classes modulo N to sequences of congruence classes modulo ni, the proof of uniqueness shows that this map is injective. As the domain and the codomain of this map have the number of elements, the map is also surjective. This proof is simple but does not provide any direct way for computing a solution. Moreover, it cannot be generalized to situations where the following proof can
16.
Fundamental theorem of arithmetic
–
For example,1200 =24 ×31 ×52 =3 ×2 ×2 ×2 ×2 ×5 ×5 =5 ×2 ×3 ×2 ×5 ×2 ×2 = etc. The requirement that the factors be prime is necessary, factorizations containing composite numbers may not be unique. This theorem is one of the reasons why 1 is not considered a prime number, if 1 were prime. Book VII, propositions 30,31 and 32, and Book IX, proposition 14 of Euclids Elements are essentially the statement, proposition 30 is referred to as Euclids lemma. And it is the key in the proof of the theorem of arithmetic. Proposition 31 is proved directly by infinite descent, proposition 32 is derived from proposition 31, and prove that the decomposition is possible. Book IX, proposition 14 is derived from Book VII, proposition 30, indeed, in this proposition the exponents are all equal to one, so nothing is said for the general case. Article 16 of Gauss Disquisitiones Arithmeticae is a modern statement. < pk are primes and the αi are positive integers and this representation is commonly extended to all positive integers, including one, by the convention that the empty product is equal to 1. This representation is called the representation of n, or the standard form of n. For example 999 = 33×37,1000 = 23×53,1001 = 7×11×13 Note that factors p0 =1 may be inserted without changing the value of n, allowing negative exponents provides a canonical form for positive rational numbers. However, as Integer factorization of large integers is much harder than computing their product, gcd or lcm, these formulas have, in practice, many arithmetical functions are defined using the canonical representation. In particular, the values of additive and multiplicative functions are determined by their values on the powers of prime numbers, the proof uses Euclids lemma, if a prime p divides the product of two natural numbers a and b, then p divides a or p divides b. We need to show that every integer greater than 1 is either prime or a product of primes, for the base case, note that 2 is prime. By induction, assume true for all numbers between 1 and n, if n is prime, there is nothing more to prove. Otherwise, there are integers a and b, where n = ab and 1 < a ≤ b < n, by the induction hypothesis, a = p1p2. pj and b = q1q2. qk are products of primes. But then n = ab = p1p2. pjq1q2. qk is a product of primes, assume that s >1 is the product of prime numbers in two different ways, s = p 1 p 2 ⋯ p m = q 1 q 2 ⋯ q n. We must show m = n and that the qj are a rearrangement of the pi, by Euclids lemma, p1 must divide one of the qj, relabeling the qj if necessary, say that p1 divides q1
17.
Cyclic group
–
In algebra, a cyclic group or monogenous group is a group that is generated by a single element. Each element can be written as a power of g in multiplicative notation and this element g is called a generator of the group. Every infinite cyclic group is isomorphic to the group of Z. Every finite cyclic group of n is isomorphic to the additive group of Z/nZ. Every cyclic group is a group, and every finitely generated abelian group is a direct product of cyclic groups. A group G is called if there exists an element g in G such that G = ⟨g⟩ =. Since any group generated by an element in a group is a subgroup of that group, for example, if G = is a group of order 6, then g6 = g0, and G is cyclic. In fact, G is essentially the same as the set with addition modulo 6, for example,1 +2 ≡3 corresponds to g1 · g2 = g3, and 2 +5 ≡1 corresponds to g2 · g5 = g7 = g1, and so on. One can use the isomorphism χ defined by χ = i, the name cyclic may be misleading, it is possible to generate infinitely many elements and not form any literal cycles, that is, every gn is distinct. A group generated in this way is called a cyclic group. The French mathematicians known as Nicolas Bourbaki referred to a group as a monogenous group. The set of integers, with the operation of addition, forms a group and it is an infinite cyclic group, because all integers can be written as a finite sum or difference of copies of the number 1. In this group,1 and −1 are the only generators, every infinite cyclic group is isomorphic to this group. For every positive n, the set of integers modulo n, again with the operation of addition, forms a finite cyclic group. An element g is a generator of this group if g is relatively prime to n, thus, the number of different generators is φ, where φ is the Euler totient function, the function that counts the number of numbers modulo n that are relatively prime to n. Every finite cyclic group is isomorphic to a group Z/n, where n is the order of the group, the integer and modular addition operations, used to define the cyclic groups, are both the addition operations of commutative rings, also denoted Z and Z/n. If p is a prime, then Z/p is a finite field, every field with p elements is isomorphic to this one. For every positive n, the subset of the integers modulo n that are relatively prime to n, with the operation of multiplication
18.
Subgroup
–
In group theory, a branch of mathematics, given a group G under a binary operation ∗, a subset H of G is called a subgroup of G if H also forms a group under the operation ∗. More precisely, H is a subgroup of G if the restriction of ∗ to H × H is an operation on H. This is usually denoted H ≤ G, read as H is a subgroup of G, the trivial subgroup of any group is the subgroup consisting of just the identity element. A proper subgroup of a group G is a subgroup H which is a subset of G. This is usually represented notationally by H < G, read as H is a subgroup of G. Some authors also exclude the group from being proper. If H is a subgroup of G, then G is sometimes called an overgroup of H, the same definitions apply more generally when G is an arbitrary semigroup, but this article will only deal with subgroups of groups. The group G is sometimes denoted by the pair, usually to emphasize the operation ∗ when G carries multiple algebraic or other structures. This article will write ab for a ∗ b, as is usual, a subset H of the group G is a subgroup of G if and only if it is nonempty and closed under products and inverses. In the case that H is finite, then H is a subgroup if and only if H is closed under products. The above condition can be stated in terms of a homomorphism, the identity of a subgroup is the identity of the group, if G is a group with identity eG, and H is a subgroup of G with identity eH, then eH = eG. The intersection of subgroups A and B is again a subgroup. The union of subgroups A and B is a if and only if either A or B contains the other, since for example 2 and 3 are in the union of 2Z and 3Z. Another example is the union of the x-axis and the y-axis in the plane, each of these objects is a subgroup and this also serves as an example of two subgroups, whose intersection is precisely the identity. An element of G is in <S> if and only if it is a product of elements of S. Every element a of a group G generates the cyclic subgroup <a>, if <a> is isomorphic to Z/nZ for some positive integer n, then n is the smallest positive integer for which an = e, and n is called the order of a. If <a> is isomorphic to Z, then a is said to have infinite order, the subgroups of any given group form a complete lattice under inclusion, called the lattice of subgroups. If e is the identity of G, then the group is the minimum subgroup of G
19.
Root of unity
–
In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that gives 1 when raised to some positive integer power n. Roots of unity are used in branches of mathematics, and are especially important in number theory, the theory of group characters. In field theory and ring theory the notion of root of unity also applies to any ring with an identity element. Any algebraically closed field has exactly n nth roots of unity if n is not divisible by the characteristic of the field, an nth root of unity, where n is a positive integer, is a number z satisfying the equation z n =1. Without further specification, the roots of unity are complex numbers, however the defining equation of roots of unity is meaningful over any field F, and this allows considering roots of unity in F. Whichever is the field F, the roots of unity in F are either numbers, if the characteristic of F is 0, or, otherwise. Conversely, every element in a finite field is a root of unity in that field. See Root of unity modulo n and Finite field for further details, an nth root of unity is primitive if it is not a kth root of unity for some smaller k, z k ≠1. Every nth root of unity z is a primitive ath root of unity for some a where 1 ≤ a ≤ n. In fact, if z1 =1 then z is a primitive first root of unity, otherwise if z2 =1 then z is a second root of unity. And, as z is a root of unity, one finds a first a such that za =1. If z is an nth root of unity and a ≡ b then za = zb, Therefore, given a power za of z, it can be assumed that 1 ≤ a ≤ n. Any integer power of an nth root of unity is also an nth root of unity, n = z k n = k =1 k =1. In particular, the reciprocal of an nth root of unity is its complex conjugate, let z be a primitive nth root of unity. Zn−1, zn = z0 =1 are all distinct, assume the contrary, that za = zb where 1 ≤ a < b ≤ n. But 0 < b − a < n, which contradicts z being primitive. Since an nth-degree polynomial equation can only have n distinct roots, from the preceding, it follows that if z is a primitive nth root of unity, z a = z b ⟺ a ≡ b. If z is not primitive there is only one implication, a ≡ b ⟹ z a = z b
20.
Riemann zeta function
–
More general representations of ζ for all s are given below. The Riemann zeta function plays a role in analytic number theory and has applications in physics, probability theory. As a function of a variable, Leonhard Euler first introduced and studied it in the first half of the eighteenth century without using complex analysis. The values of the Riemann zeta function at even positive integers were computed by Euler, the first of them, ζ, provides a solution to the Basel problem. In 1979 Apéry proved the irrationality of ζ, the values at negative integer points, also found by Euler, are rational numbers and play an important role in the theory of modular forms. Many generalizations of the Riemann zeta function, such as Dirichlet series, the Riemann zeta function ζ is a function of a complex variable s = σ + it. It can also be defined by the integral ζ =1 Γ ∫0 ∞ x s −1 e x −1 d x where Γ is the gamma function. The Riemann zeta function is defined as the continuation of the function defined for σ >1 by the sum of the preceding series. Leonhard Euler considered the series in 1740 for positive integer values of s. The above series is a prototypical Dirichlet series that converges absolutely to a function for s such that σ >1. Riemann showed that the function defined by the series on the half-plane of convergence can be continued analytically to all complex values s ≠1, for s =1 the series is the harmonic series which diverges to +∞, and lim s →1 ζ =1. Thus the Riemann zeta function is a function on the whole complex s-plane. For any positive even integer 2n, ζ = n +1 B2 n 2 n 2, where B2n is the 2nth Bernoulli number. For odd positive integers, no simple expression is known, although these values are thought to be related to the algebraic K-theory of the integers. For nonpositive integers, one has ζ = B n +1 n +1 for n ≥0 In particular, ζ = −12, Similarly to the above, this assigns a finite result to the series 1 +1 +1 +1 + ⋯. ζ ≈ −1.4603545 This is employed in calculating of kinetic boundary layer problems of linear kinetic equations, ζ =1 +12 +13 + ⋯ = ∞, if we approach from numbers larger than 1. Then this is the harmonic series, but its Cauchy principal value lim ε →0 ζ + ζ2 exists which is the Euler–Mascheroni constant γ =0. 5772…. ζ ≈2.612, This is employed in calculating the critical temperature for a Bose–Einstein condensate in a box with periodic boundary conditions, and for spin wave physics in magnetic systems
21.
On-Line Encyclopedia of Integer Sequences
–
The On-Line Encyclopedia of Integer Sequences, also cited simply as Sloanes, is an online database of integer sequences. It was created and maintained by Neil Sloane while a researcher at AT&T Labs, Sloane continues to be involved in the OEIS in his role as President of the OEIS Foundation. OEIS records information on integer sequences of interest to professional mathematicians and amateurs, and is widely cited. As of 30 December 2016 it contains nearly 280,000 sequences, the database is searchable by keyword and by subsequence. Neil Sloane started collecting integer sequences as a student in 1965 to support his work in combinatorics. The database was at first stored on punched cards and he published selections from the database in book form twice, A Handbook of Integer Sequences, containing 2,372 sequences in lexicographic order and assigned numbers from 1 to 2372. The Encyclopedia of Integer Sequences with Simon Plouffe, containing 5,488 sequences and these books were well received and, especially after the second publication, mathematicians supplied Sloane with a steady flow of new sequences. The collection became unmanageable in book form, and when the database had reached 16,000 entries Sloane decided to go online—first as an e-mail service, as a spin-off from the database work, Sloane founded the Journal of Integer Sequences in 1998. The database continues to grow at a rate of some 10,000 entries a year, Sloane has personally managed his sequences for almost 40 years, but starting in 2002, a board of associate editors and volunteers has helped maintain the database. In 2004, Sloane celebrated the addition of the 100, 000th sequence to the database, A100000, in 2006, the user interface was overhauled and more advanced search capabilities were added. In 2010 an OEIS wiki at OEIS. org was created to simplify the collaboration of the OEIS editors and contributors, besides integer sequences, the OEIS also catalogs sequences of fractions, the digits of transcendental numbers, complex numbers and so on by transforming them into integer sequences. Sequences of rationals are represented by two sequences, the sequence of numerators and the sequence of denominators, important irrational numbers such as π =3.1415926535897. are catalogued under representative integer sequences such as decimal expansions, binary expansions, or continued fraction expansions. The OEIS was limited to plain ASCII text until 2011, yet it still uses a form of conventional mathematical notation. Greek letters are represented by their full names, e. g. mu for μ. Every sequence is identified by the letter A followed by six digits, sometimes referred to without the leading zeros, individual terms of sequences are separated by commas. Digit groups are not separated by commas, periods, or spaces, a represents the nth term of the sequence. Zero is often used to represent non-existent sequence elements, for example, A104157 enumerates the smallest prime of n² consecutive primes to form an n×n magic square of least magic constant, or 0 if no such magic square exists. The value of a is 2, a is 1480028129, but there is no such 2×2 magic square, so a is 0
22.
Upper and lower bounds
–
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of K which is greater than or equal to every element of S. The term lower bound is defined dually as an element of K which is less than or equal to every element of S. A set with an upper bound is said to be bounded from above by that bound, the terms bounded above are also used in the mathematical literature for sets that have upper bounds. For example,5 is a bound for the set, so is 4. Another example, for the set, the number 42 is both an upper bound and a bound, all other real numbers are either an upper bound or a lower bound for that set. Every subset of the numbers has a lower bound, since the natural numbers have a least element. An infinite subset of the numbers cannot be bounded from above. An infinite subset of the integers may be bounded from below or bounded from above, an infinite subset of the rational numbers may or may not be bounded from below and may or may not be bounded from above. Every finite subset of a non-empty totally ordered set has both upper and lower bounds, the definitions can be generalized to functions and even sets of functions. Given a function f with domain D and an ordered set as codomain. The upper bound is called sharp if equality holds for at least one value of x, function g defined on domain D and having the same codomain is an upper bound of f if g ≥ f for each x in D. Function g is said to be an upper bound of a set of functions if it is an upper bound of each function in that set. The notion of lower bound for functions is defined analogously, with ≤ replacing ≥, an upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly a lower bound is said to be a lower bound
23.
Fermat's little theorem
–
Fermats little theorem states that if p is a prime number, then for any integer a, the number a p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as a p ≡ a, for example, if a =2 and p =7,27 =128, and 128 −2 =7 ×18 is an integer multiple of 7. If a is not divisible by p, Fermats little theorem is equivalent to the statement that a p −1 −1 is a multiple of p. For example, if a =2 and p =7 then 26 =64 and 64 −1 =63 is thus a multiple of 7, Fermats little theorem is the basis for the Fermat primality test and is one of the fundamental results of elementary number theory. The theorem is named after Pierre de Fermat, who stated it in 1640 and it is called the little theorem to distinguish it from Fermats last theorem. Pierre de Fermat first stated the theorem in a letter dated October 18,1640, to his friend, an early use in English occurs in A. A. Albert, Modern Higher Algebra, which refers to the so-called little Fermat theorem on page 206, some mathematicians independently made the related hypothesis that 2p ≡2 if and only if p is a prime. Indeed, the if part is true, and is a case of Fermats little theorem. However, the if part of this hypothesis is false, for example,2341 ≡2. Several proofs of Fermats little theorem are known and it is frequently proved as a corollary of Eulers theorem. Fermats little theorem is a case of Eulers theorem, for any modulus n and any integer a coprime to n, we have a φ ≡1. Eulers theorem is indeed a generalization, because if n = p is a prime number, then φ = p −1. A slight generalization of Eulers theorem, which follows from it, is, if a, n, x, y are integers with n positive. This follows as x is of the form y + φk, in this form, the theorem finds many uses in cryptography and, in particular, underlies the computations used in the RSA public key encryption method. The special case with n a prime may be considered a consequence of Fermats little theorem, Fermats little theorem is also related to the Carmichael function and Carmichaels theorem, as well as to Lagranges theorem in group theory. The algebraic setting of Fermats little theorem can be generalized to finite fields, the converse of Fermats little theorem is not generally true, as it fails for Carmichael numbers. However, a stronger form of the theorem is true. The theorem is as follows, If there exists an a such that a p −1 ≡1 and this theorem forms the basis for the Lucas–Lehmer test, an important primality test
24.
Lagrange's theorem (group theory)
–
Lagranges theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph-Louis Lagrange and this can be shown using the concept of left cosets of H in G. If we can show that all cosets of H have the number of elements. This map is bijective because its inverse is given by f −1 = a b −1 y and this proof also shows that the quotient of the orders |G| / |H| is equal to the index. If we allow G and H to be infinite, and write this statement as | G | = ⋅ | H |, then, seen as a statement about cardinal numbers, it is equivalent to the axiom of choice. A consequence of the theorem is that the order of any element a of a group divides the order of that group. If the group has n elements, it follows a n = e and this can be used to prove Fermats little theorem and its generalization, Eulers theorem. These special cases were known long before the general theorem was proved, the theorem also shows that any group of prime order is cyclic and simple. This in turn can be used to prove Wilsons theorem, that if p is prime p is a factor of. Hence p < q, contradicting the assumption that p is the largest prime, Lagranges theorem raises the converse question as to whether every divisor of the order of a group is the order of some subgroup. This does not hold in general, given a finite group G, the smallest example is the alternating group G = A4, which has 12 elements but no subgroup of order 6. A CLT group is a group with the property that for every divisor of the order of the group. It is known that a CLT group must be solvable and that every group is a CLT group. There are partial converses to Lagranges theorem, for solvable groups, Halls theorems assert the existence of a subgroup of order equal to any unitary divisor of the group order. Lagrange did not prove Lagranges theorem in its general form, the number of such polynomials is the index in the symmetric group Sn of the subgroup H of permutations that preserve the polynomial. So the size of H divides n, with the later development of abstract groups, this result of Lagrange on polynomials was recognized to extend to the general theorem about finite groups which now bears his name. In his Disquisitiones Arithmeticae in 1801, Carl Friedrich Gauss proved Lagranges theorem for the case of Z*, the multiplicative group of nonzero integers modulo p. In 1844, Augustin-Louis Cauchy proved Lagranges theorem for the symmetric group Sn, camille Jordan finally proved Lagranges theorem for the case of any permutation group in 1861
25.
Inverse function
–
I. e. f = y if and only if g = x. As a simple example, consider the function of a real variable given by f = 5x −7. Thinking of this as a procedure, to reverse this and get x back from some output value, say y. In this case means that we should add 7 to y. In functional notation this inverse function would be given by, g = y +75, with y = 5x −7 we have that f = y and g = x. Not all functions have inverse functions, in order for a function f, X → Y to have an inverse, it must have the property that for every y in Y there must be one, and only one x in X so that f = y. This property ensures that a function g, Y → X will exist having the necessary relationship with f, let f be a function whose domain is the set X, and whose image is the set Y. Then f is invertible if there exists a g with domain Y and image X, with the property. If f is invertible, the g is unique, which means that there is exactly one function g satisfying this property. That function g is called the inverse of f, and is usually denoted as f −1. Stated otherwise, a function is invertible if and only if its inverse relation is a function on the range Y, not all functions have an inverse. For a function to have an inverse, each element y ∈ Y must correspond to no more than one x ∈ X, a function f with this property is called one-to-one or an injection. If f −1 is to be a function on Y, then each element y ∈ Y must correspond to some x ∈ X. Functions with this property are called surjections. This property is satisfied by definition if Y is the image of f, to be invertible a function must be both an injection and a surjection. If a function f is invertible, then both it and its inverse function f−1 are bijections, there is another convention used in the definition of functions. This can be referred to as the set-theoretic or graph definition using ordered pairs in which a codomain is never referred to, under this convention all functions are surjections, and so, being a bijection simply means being an injection. Authors using this convention may use the phrasing that a function is invertible if, the two conventions need not cause confusion as long as it is remembered that in this alternate convention the codomain of a function is always taken to be the range of the function. With this type of function it is impossible to deduce an input from its output, such a function is called non-injective or, in some applications, information-losing
26.
Multiplicative inverse
–
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity,1. The multiplicative inverse of a fraction a/b is b/a, for the multiplicative inverse of a real number, divide 1 by the number. For example, the reciprocal of 5 is one fifth, the reciprocal function, the function f that maps x to 1/x, is one of the simplest examples of a function which is its own inverse. In the phrase multiplicative inverse, the qualifier multiplicative is often omitted, multiplicative inverses can be defined over many mathematical domains as well as numbers. In these cases it can happen that ab ≠ ba, then inverse typically implies that an element is both a left and right inverse. The notation f −1 is sometimes used for the inverse function of the function f. For example, the multiplicative inverse 1/ = −1 is the cosecant of x, only for linear maps are they strongly related. The terminology difference reciprocal versus inverse is not sufficient to make this distinction, since many authors prefer the opposite naming convention, in the real numbers, zero does not have a reciprocal because no real number multiplied by 0 produces 1. With the exception of zero, reciprocals of every real number are real, reciprocals of every rational number are rational, the property that every element other than zero has a multiplicative inverse is part of the definition of a field, of which these are all examples. On the other hand, no other than 1 and −1 has an integer reciprocal. In modular arithmetic, the multiplicative inverse of a is also defined. This multiplicative inverse exists if and only if a and n are coprime, for example, the inverse of 3 modulo 11 is 4 because 4 ·3 ≡1. The extended Euclidean algorithm may be used to compute it, the sedenions are an algebra in which every nonzero element has a multiplicative inverse, but which nonetheless has divisors of zero, i. e. nonzero elements x, y such that xy =0. A square matrix has an inverse if and only if its determinant has an inverse in the coefficient ring, the linear map that has the matrix A−1 with respect to some base is then the reciprocal function of the map having A as matrix in the same base. Thus, the two notions of the inverse of a function are strongly related in this case, while they must be carefully distinguished in the general case. A ring in which every element has a multiplicative inverse is a division ring. As mentioned above, the reciprocal of every complex number z = a + bi is complex. In particular, if ||z||=1, then 1 / z = z ¯, consequently, the imaginary units, ±i, have additive inverse equal to multiplicative inverse, and are the only complex numbers with this property
27.
Integer factorization
–
In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these integers are further restricted to numbers, the process is called prime factorization. When the numbers are large, no efficient, non-quantum integer factorization algorithm is known. However, it has not been proven that no efficient algorithm exists, the presumed difficulty of this problem is at the heart of widely used algorithms in cryptography such as RSA. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, not all numbers of a given length are equally hard to factor. The hardest instances of these problems are semiprimes, the product of two prime numbers, many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure, by the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. If the integer is then it can be recognized as such in polynomial time. If composite however, the theorem gives no insight into how to obtain the factors, given a general algorithm for integer factorization, any integer can be factored down to its constituent prime factors simply by repeated application of this algorithm. The situation is complicated with special-purpose factorization algorithms, whose benefits may not be realized as well or even at all with the factors produced during decomposition. For example, if N =10 × p × q where p < q are very large primes, trial division will quickly produce the factors 2 and 5 but will take p divisions to find the next factor. Among the b-bit numbers, the most difficult to factor in practice using existing algorithms are those that are products of two primes of similar size, for this reason, these are the integers used in cryptographic applications. The largest such semiprime yet factored was RSA-768, a 768-bit number with 232 decimal digits and this factorization was a collaboration of several research institutions, spanning two years and taking the equivalent of almost 2000 years of computing on a single-core 2.2 GHz AMD Opteron. Like all recent factorization records, this factorization was completed with an optimized implementation of the general number field sieve run on hundreds of machines. No algorithm has been published that can factor all integers in polynomial time, neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P. The problem is clearly in class NP but has not been proved to be in, or not in and it is generally suspected not to be in NP-complete. There are published algorithms that are faster than O for all positive ε, i. e. sub-exponential, the best published asymptotic running time is for the general number field sieve algorithm, which, for a b-bit number n, is, O. For current computers, GNFS is the best published algorithm for large n, for a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time
28.
Least common multiple
–
Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm as 0 for all a, the LCM is the lowest common denominator that must be determined before fractions can be added, subtracted or compared. The LCM of more than two integers is also well-defined, it is the smallest positive integer that is divisible by each of them, a multiple of a number is the product of that number and an integer. For example,10 is a multiple of 5 because 5 ×2 =10, because 10 is the smallest positive integer that is divisible by both 5 and 2, it is the least common multiple of 5 and 2. By the same principle,10 is the least common multiple of −5, in this article we will denote the least common multiple of two integers a and b as lcm. The programming language J uses a*. b What is the LCM of 4 and 6. Multiples of 4 are,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76. and the multiples of 6 are,6,12,18,24,30,36,42,48,54,60,66,72. Common multiples of 4 and 6 are simply the numbers that are in both lists,12,24,36,48,60,72. So, from this list of the first few common multiples of the numbers 4 and 6, their least common multiple is 12. For instance,221 +16 =442 +742 =1142 where the denominator 42 was used because it is the least common multiple of 21 and 6. This formula is valid when exactly one of a and b is 0. However, if both a and b are 0, this formula would cause division by zero, lcm =0 is a special case, there are fast algorithms for computing the GCD that do not require the numbers to be factored, such as the Euclidean algorithm. To return to the example above, lcm =21 ⋅6 gcd =21 ⋅6 gcd =21 ⋅63 =1263 =42. Because gcd is a divisor of both a and b, it is efficient to compute the LCM by dividing before multiplying. This reduces the size of one input for both the division and the multiplication, and reduces the required storage needed for intermediate results. Because gcd is a divisor of both a and b, the division is guaranteed to yield an integer, so the result can be stored in an integer. Done this way, the previous becomes, lcm =21 gcd ⋅6 =21 gcd ⋅6 =213 ⋅6 =7 ⋅6 =42. The unique factorization theorem says that every integer greater than 1 can be written in only one way as a product of prime numbers
29.
Arithmetic function
–
In number theory, an arithmetic, arithmetical, or number-theoretic function is a real or complex valued function f defined on the set of natural numbers that expresses some arithmetical property of n. An example of a function is the divisor function whose value at a positive integer n is equal to the number of divisors of n. There is a class of number-theoretic functions that do not fit the above definition. This article provides links to functions of both classes, ∑ p f and ∏ p f mean that the sum or product is over all prime numbers, ∑ p f = f + f + f + ⋯ ∏ p f = f f f ⋯. E. g. if n =12, ∏ d ∣12 f = f f f f f f. The notations can be combined, ∑ p ∣ n f and ∏ p ∣ n f mean that the sum or product is over all prime divisors of n. E. g. if n =24, ∏ p k ∣24 f = f f f f. e. if there is no number that divides both of them. Then an arithmetic function a is additive if a = a + a for all natural numbers m and n. The fundamental theorem of arithmetic states that any integer n can be represented uniquely as a product of powers of primes. < pk are primes and the aj are positive integers and it is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define νp as the exponent of the highest power of the prime p that divides n, I. e. if p is one of the pi then νp = ai, otherwise it is zero. In terms of the above the functions ω and Ω are defined by ω = k, Ω = a1 + a2 +. To avoid repetition, whenever possible formulas for the functions listed in this article are given in terms of n and the corresponding pi, ai, ω, and Ω. σk is the sum of the kth powers of the divisors of n, including 1 and n. σ1, the sum of the divisors of n, is denoted by σ. Since a positive number to the power is one, σ0 is therefore the number of divisors of n. σ k = ∏ i =1 ω p i k −1 p i k −1 = ∏ i =1 ω, setting k =0 in the second product gives τ = d = ⋯. φ, the Euler totient function, is the number of integers not greater than n that are coprime to n
30.
Divisor function
–
In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as the function, it counts the number of divisors of an integer. It appears in a number of identities, including relationships on the Riemann zeta function. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities, a related function is the divisor summatory function, which, as the name implies, is a sum over the divisor function. The sum of divisors function σx, for a real or complex number x, is defined as the sum of the xth powers of the positive divisors of n. It can be expressed in sigma notation as σ x = ∑ d ∣ n d x, the notations d, ν and τ are also used to denote σ0, or the number-of-divisors function. When x is 1, the function is called the function or sum-of-divisors function. The aliquot sum s of n is the sum of the proper divisors, and equals σ1 − n, the cases x =2 to 5 are listed in A001157 − A001160, x =6 to 24 are listed in A013954 − A013972. For a non-square integer, n, every divisor, d, of n is paired with divisor n/d of n and σ0 is even, for an integer, one divisor is not paired with a distinct divisor. Similarly, the number σ1 is odd if and only if n is a square or twice a square. For a prime p, σ0 =2 σ0 = n +1 σ1 = p +1 because by definition. Also, where pn# denotes the primorial, σ0 =2 n since n prime factors allow a sequence of binary selection from n terms for each proper divisor formed, clearly,1 < σ0 < n and σ > n for all n >2. The divisor function is multiplicative, but not completely multiplicative and it follows that d is, σ0 = ∏ i =1 r. For example, if n is 24, there are two factors, noting that 24 is the product of 23×31, a1 is 3. Thus we can calculate σ0 as so, σ0 = ∏ i =12 = =4 ⋅2 =8, the eight divisors counted by this formula are 1,2,4,8,3,6,12, and 24. Here s denotes the sum of the divisors of n, that is. This function is the one used to perfect numbers which are the n for which s = n. If s > n then n is an abundant number and if s < n then n is a deficient number
31.
Golden ratio
–
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. The figure on the right illustrates the geometric relationship, expressed algebraically, for quantities a and b with a > b >0, a + b a = a b = def φ, where the Greek letter phi represents the golden ratio. Its value is, φ =1 +52 =1.6180339887 …, A001622 The golden ratio is also called the golden mean or golden section. Other names include extreme and mean ratio, medial section, divine proportion, divine section, golden proportion, golden cut, the golden ratio appears in some patterns in nature, including the spiral arrangement of leaves and other plant parts. The golden ratio has also used to analyze the proportions of natural objects as well as man-made systems such as financial markets. Two quantities a and b are said to be in the golden ratio φ if a + b a = a b = φ, one method for finding the value of φ is to start with the left fraction. Through simplifying the fraction and substituting in b/a = 1/φ, a + b a =1 + b a =1 +1 φ, multiplying by φ gives φ +1 = φ2 which can be rearranged to φ2 − φ −1 =0. First, the line segment A B ¯ is about doubled and then the semicircle with the radius A S ¯ around the point S is drawn, now the semicircle is drawn with the radius A B ¯ around the point B. The arising intersection point E corresponds 2 φ, next up, the perpendicular on the line segment A E ¯ from the point D will be establish. The subsequent parallel F S ¯ to the line segment C M ¯, produces, as it were and it is well recognizable, this triangle and the triangle M S C are similar to each other. The hypotenuse F S ¯ has due to the cathetuses S D ¯ =1 and D F ¯ =2 according the Pythagorean theorem, finally, the circle arc is drawn with the radius 5 around the point F. The golden ratio has been claimed to have held a fascination for at least 2,400 years. But the fascination with the Golden Ratio is not confined just to mathematicians, biologists, artists, musicians, historians, architects, psychologists, and even mystics have pondered and debated the basis of its ubiquity and appeal. In fact, it is fair to say that the Golden Ratio has inspired thinkers of all disciplines like no other number in the history of mathematics. Ancient Greek mathematicians first studied what we now call the golden ratio because of its frequent appearance in geometry, the division of a line into extreme and mean ratio is important in the geometry of regular pentagrams and pentagons. Euclid explains a construction for cutting a line in extreme and mean ratio, throughout the Elements, several propositions and their proofs employ the golden ratio. The golden ratio is explored in Luca Paciolis book De divina proportione, since the 20th century, the golden ratio has been represented by the Greek letter φ or less commonly by τ. Timeline according to Priya Hemenway, Phidias made the Parthenon statues that seem to embody the golden ratio, plato, in his Timaeus, describes five possible regular solids, some of which are related to the golden ratio
32.
Prime number theorem
–
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée-Poussin in 1896 using ideas introduced by Bernhard Riemann, the first such distribution found is π ~ N/log, where π is the prime-counting function and log is the natural logarithm of N. This means that for large enough N, the probability that an integer not greater than N is prime is very close to 1 / log. Consequently, an integer with at most 2n digits is about half as likely to be prime as a random integer with at most n digits. For example, among the integers of at most 1000 digits, about one in 2300 is prime, whereas among positive integers of at most 2000 digits. In other words, the gap between consecutive prime numbers among the first N integers is roughly log. Let π be the function that gives the number of primes less than or equal to x. For example, π =4 because there are four prime numbers less than or equal to 10, using asymptotic notation this result can be restated as π ∼ x log x. This notation does not say anything about the limit of the difference of the two functions as x increases without bound, instead, the theorem states that x / log x approximates π in the sense that the relative error of this approximation approaches 0 as x increases without bound. For example, the 7017200000000000000♠2×1017th prime number is 7018851267738604819♠8512677386048191063, and log rounds to 7018796741875229174♠7967418752291744388, a relative error of about 6. 4%. The prime number theorem is equivalent to lim x → ∞ ϑ x = lim x → ∞ ψ x =1, where ϑ and ψ are the first. Based on the tables by Anton Felkel and Jurij Vega, Adrien-Marie Legendre conjectured in 1797 or 1798 that π is approximated by the function a /, where A and B are unspecified constants. In the second edition of his book on number theory he made a more precise conjecture. Carl Friedrich Gauss considered the question at age 15 or 16 in the year 1792 or 1793. In 1838 Peter Gustav Lejeune Dirichlet came up with his own approximating function, in two papers from 1848 and 1850, the Russian mathematician Pafnuty Chebyshev attempted to prove the asymptotic law of distribution of prime numbers. He was able to prove unconditionally that this ratio is bounded above, an important paper concerning the distribution of prime numbers was Riemanns 1859 memoir On the Number of Primes Less Than a Given Magnitude, the only paper he ever wrote on the subject. In particular, it is in paper of Riemann that the idea to apply methods of complex analysis to the study of the real function π originates
33.
Riemann hypothesis
–
In mathematics, the Riemann hypothesis is a conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 1/2. It was proposed by Bernhard Riemann, after whom it is named, the name is also used for some closely related analogues, such as the Riemann hypothesis for curves over finite fields. The Riemann hypothesis implies results about the distribution of prime numbers, along with suitable generalizations, some mathematicians consider it the most important unresolved problem in pure mathematics. The Riemann zeta function ζ is a function whose argument s may be any complex number other than 1 and it has zeros at the negative even integers, that is, ζ =0 when s is one of −2, −4, −6. These are called its trivial zeros, However, the negative even integers are not the only values for which the zeta function is zero. The other ones are called non-trivial zeros, the Riemann hypothesis is concerned with the locations of these non-trivial zeros, and states that, The real part of every non-trivial zero of the Riemann zeta function is 1/2. Thus, if the hypothesis is correct, all the non-trivial zeros lie on the line consisting of the complex numbers 1/2 + i t. There are several books on the Riemann hypothesis, such as Derbyshire, Rockmore. The books Edwards, Patterson, Borwein et al. and Mazur & Stein give mathematical introductions, while Titchmarsh, Ivić, furthermore, the book Open Problems in Mathematics, edited by John Forbes Nash Jr. and Michael Th. Rassias, features an essay on the Riemann hypothesis by Alain Connes. The convergence of the Euler product shows that ζ has no zeros in this region, the Riemann hypothesis discusses zeros outside the region of convergence of this series and Euler product. To make sense of the hypothesis, it is necessary to continue the function to give it a definition that is valid for all complex s. This can be done by expressing it in terms of the Dirichlet eta function as follows. If the real part of s is greater than one, then the function satisfies ζ = ∑ n =1 ∞ n +1 n s =11 s −12 s +13 s − ⋯. However, the series on the right converges not just when the part of s is greater than one. Thus, this alternative series extends the function from Re >1 to the larger domain Re >0. The zeta function can be extended to these values, as well, by taking limits, in the strip 0 < Re <1 the zeta function satisfies the functional equation ζ =2 s π s −1 sin Γ ζ. If s is an even integer then ζ =0 because the factor sin vanishes
34.
Arnold Walfisz
–
Arnold Walfisz was a Polish mathematician working in analytic number theory. After the Abitur in Warsaw, Arnold Walfisz studied in Germany at Munich, Berlin, Heidelberg, edmund Landau was his doctoral-thesis supervisor at the University of Göttingen. Walfisz lived in Wiesbaden from 1922 through 1927, then he returned to Warsaw, worked at an insurance company, in 1935, together with Salomon Lubelski, he founded the mathematical journal Acta Arithmetica. In 1936 Walfisz became professor at the University of Tbilisi in the nation of Georgia and he wrote approximately 100 mathematical articles and three books. Pells equation, Tbilisi,1952 Gitterpunkte in mehrdimensionalen Kugeln, Panstwowe Wydawnictwo Naukowe, Monografi Matematyczne, warszawa,1957, online Weylsche Exponentialsummen in der neueren Zahlentheorie, VEB Deutscher Verlag der Wissenschaften, Berlin,1963