1.
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
2.
Parity (mathematics)
–
Parity is a mathematical term that describes the property of an integers inclusion in one of two categories, even or odd. An integer is even if it is divisible by two and odd if it is not even. For example,6 is even there is no remainder when dividing it by 2. By contrast,3,5,7,21 leave a remainder of 1 when divided by 2, examples of even numbers include −4,0,8, and 1738. In particular, zero is an even number, some examples of odd numbers are −5,3,9, and 73. Parity does not apply to non-integer numbers and this classification applies only to integers, i. e. non-integers like 1/2,4.201, or infinity are neither even nor odd. The sets of even and odd numbers can be defined as following and that is, if the last digit is 1,3,5,7, or 9, then it is odd, otherwise it is even. The same idea will work using any even base, in particular, a number expressed in the binary numeral system is odd if its last digit is 1 and even if its last digit is 0. In an odd base, the number is according to the sum of its digits – it is even if. The following laws can be verified using the properties of divisibility and they are a special case of rules in modular arithmetic, and are commonly used to check if an equality is likely to be correct by testing the parity of each side. As with ordinary arithmetic, multiplication and addition are commutative and associative in modulo 2 arithmetic, however, subtraction in modulo 2 is identical to addition, so subtraction also possesses these properties, which is not true for normal integer arithmetic. The structure is in fact a field with just two elements, the division of two whole numbers does not necessarily result in a whole number. For example,1 divided by 4 equals 1/4, which is neither even nor odd, since the concepts even, but when the quotient is an integer, it will be even if and only if the dividend has more factors of two than the divisor. The ancient Greeks considered 1, the monad, to be neither odd nor fully even. It is this, that two relatively different things or ideas there stands always a third, in a sort of balance. Thus, there is here between odd and even numbers one number which is neither of the two, similarly, in form, the right angle stands between the acute and obtuse angles, and in language, the semi-vowels or aspirants between the mutes and vowels. A thoughtful teacher and a pupil taught to think for himself can scarcely help noticing this, integer coordinates of points in Euclidean spaces of two or more dimensions also have a parity, usually defined as the parity of the sum of the coordinates. For instance, the cubic lattice and its higher-dimensional generalizations
3.
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
4.
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
5.
Derrick Henry Lehmer
–
Derrick Henry Dick Lehmer was an American mathematician who refined Édouard Lucas work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes. Lehmer was born in Berkeley, California, to Derrick Norman Lehmer, a professor of mathematics at the University of California, Berkeley and he studied physics and earned a Bachelor degree from UC Berkeley, and continued with graduate studies at the University of Chicago. He and his father worked together on Lehmer sieves. A. in 1928, Lehmer received a Masters degree and a Ph. D. D. Thesis, An Extended Theory of Lucas Functions, which he wrote under Jacob Tamarkin, Lehmer became a National Research Fellow, allowing him to take positions at the California Institute of Technology from 1930 to 1931 and at Stanford University from 1931 to 1932. In the latter year, the couples first child Laura was born, after being awarded a second National Research Fellowship, the Lehmers moved on to Princeton, New Jersey between 1932 and 1934, where Dick spent a short time at the Institute for Advanced Study. He worked at Lehigh University in Pennsylvania from 1934 until 1938 and their son Donald was born in 1934 while Dick and Emma were at Lehigh. The Lehmers returned to America by ship with second child Donald just before the beginning of the Battle of the Atlantic, Lehmer continued at Lehigh University for the 1939-1940 academic year. In 1940, Lehmer accepted a position back at the department of UC Berkeley. At some point in his career there, he developed the Linear congruential generator, the Lehmers also assisted Harry Vandiver with his work on Fermats Last Theorem, computing many Bernoulli numbers required. Lehmer was chairman of the Department of Mathematics at University of California and he continued working at UC Berkeley until 1972, the year he became professor emeritus. When they could arrange child care, the Lehmers spent weekends staying up all night running such problems, the problem run during the 3-day Independence Day weekend of July 4,1946, with John Mauchly serving as computer operator, ran around the clock without interruption or failure. Lehmer would remain active in computing developments for the remainder of his career, upon his return to Berkeley, he made plans for building the California Digital Computer with Paul Morton and Leland Cunningham. Lehmer took a post as Director of the National Bureau of Standards Institute for Numerical Analysis, on October 17,1952, the State Supreme Court proclaimed the oath unconstitutional, and Lehmer returned to Berkeley shortly thereafter. Lehmer continued to be active for years and would certainly qualify as a dotagy. When John Selfridge was at Northern Illinois University he twice invited Lehmer, one year Selfridge arranged that Erdős and Lehmer taught a course together on Research Problems in the Theory of Numbers. Lehmer taught the first eight weeks and then Erdős taught the remainder, Erdős didnt often teach a course, and he said You know it wasnt that difficult. The only problem was being there, someone said they couldnt find a blackboard and Lehmer spotted some curtains in the middle of the wall. Moving the curtains aside revealed a small blackboard, whereupon Lehmer said Well
6.
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
7.
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
8.
Integer
–
An integer is a number that can be written without a fractional component. For example,21,4,0, and −2048 are integers, while 9.75, 5 1⁄2, the set of integers consists of zero, the positive natural numbers, also called whole numbers or counting numbers, and their additive inverses. This is often denoted by a boldface Z or blackboard bold Z standing for the German word Zahlen, ℤ is a subset of the sets of rational and real numbers and, like the natural numbers, is countably infinite. The integers form the smallest group and the smallest ring containing the natural numbers, in algebraic number theory, the integers are sometimes called rational integers to distinguish them from the more general algebraic integers. In fact, the integers are the integers that are also rational numbers. Like the natural numbers, Z is closed under the operations of addition and multiplication, that is, however, with the inclusion of the negative natural numbers, and, importantly,0, Z is also closed under subtraction. The integers form a ring which is the most basic one, in the following sense, for any unital ring. This universal property, namely to be an object in the category of rings. Z is not closed under division, since the quotient of two integers, need not be an integer, although the natural numbers are closed under exponentiation, the integers are not. The following lists some of the properties of addition and multiplication for any integers a, b and c. In the language of algebra, the first five properties listed above for addition say that Z under addition is an abelian group. As a group under addition, Z is a cyclic group, in fact, Z under addition is the only infinite cyclic group, in the sense that any infinite cyclic group is isomorphic to Z. The first four properties listed above for multiplication say that Z under multiplication is a commutative monoid. However, not every integer has an inverse, e. g. there is no integer x such that 2x =1, because the left hand side is even. This means that Z under multiplication is not a group, all the rules from the above property table, except for the last, taken together say that Z together with addition and multiplication is a commutative ring with unity. It is the prototype of all objects of algebraic structure. Only those equalities of expressions are true in Z for all values of variables, note that certain non-zero integers map to zero in certain rings. The lack of zero-divisors in the means that the commutative ring Z is an integral domain
9.
Composite number
–
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers. Equivalently, it is an integer that has at least one divisor other than 1. Every positive integer is composite, prime, or the unit 1, so the numbers are exactly the numbers that are not prime. For example, the integer 14 is a number because it is the product of the two smaller integers 2 ×7. Likewise, the integers 2 and 3 are not composite numbers because each of them can only be divided by one, every composite number can be written as the product of two or more primes. For example, the composite number 299 can be written as 13 ×23, and the composite number 360 can be written as 23 ×32 ×5, furthermore and this fact is called the fundamental theorem of arithmetic. There are several known primality tests that can determine whether a number is prime or composite, one way to classify composite numbers is by counting the number of prime factors. A composite number with two prime factors is a semiprime or 2-almost prime, a composite number with three distinct prime factors is a sphenic number. In some applications, it is necessary to differentiate between composite numbers with an odd number of prime factors and those with an even number of distinct prime factors. For the latter μ =2 x =1, while for the former μ =2 x +1 = −1, however, for prime numbers, the function also returns −1 and μ =1. For a number n with one or more repeated prime factors, if all the prime factors of a number are repeated it is called a powerful number. If none of its factors are repeated, it is called squarefree. For example,72 =23 ×32, all the factors are repeated. 42 =2 ×3 ×7, none of the factors are repeated. Another way to classify composite numbers is by counting the number of divisors, all composite numbers have at least three divisors. In the case of squares of primes, those divisors are, a number n that has more divisors than any x < n is a highly composite number. Composite numbers have also been called rectangular numbers, but that name can refer to the pronic numbers, numbers that are the product of two consecutive integers. Table of prime factors Integer factorization Canonical representation of a positive integer Sieve of Eratosthenes Fraleigh, a First Course In Abstract Algebra, Reading, Addison-Wesley, ISBN 0-201-01984-1 Herstein, I. N
10.
Subset
–
In mathematics, especially in set theory, a set A is a subset of a set B, or equivalently B is a superset of A, if A is contained inside B, that is, all elements of A are also elements of B. The relationship of one set being a subset of another is called inclusion or sometimes containment, the subset relation defines a partial order on sets. The algebra of subsets forms a Boolean algebra in which the relation is called inclusion. For any set S, the inclusion relation ⊆ is an order on the set P of all subsets of S defined by A ≤ B ⟺ A ⊆ B. We may also partially order P by reverse set inclusion by defining A ≤ B ⟺ B ⊆ A, when quantified, A ⊆ B is represented as, ∀x. So for example, for authors, it is true of every set A that A ⊂ A. Other authors prefer to use the symbols ⊂ and ⊃ to indicate proper subset and superset, respectively and this usage makes ⊆ and ⊂ analogous to the inequality symbols ≤ and <. For example, if x ≤ y then x may or may not equal y, but if x < y, then x definitely does not equal y, and is less than y. Similarly, using the convention that ⊂ is proper subset, if A ⊆ B, then A may or may not equal B, the set A = is a proper subset of B =, thus both expressions A ⊆ B and A ⊊ B are true. The set D = is a subset of E =, thus D ⊆ E is true, any set is a subset of itself, but not a proper subset. The empty set, denoted by ∅, is also a subset of any given set X and it is also always a proper subset of any set except itself. These are two examples in both the subset and the whole set are infinite, and the subset has the same cardinality as the whole. The set of numbers is a proper subset of the set of real numbers. In this example, both sets are infinite but the set has a larger cardinality than the former set. Another example in an Euler diagram, Inclusion is the partial order in the sense that every partially ordered set is isomorphic to some collection of sets ordered by inclusion. The ordinal numbers are a simple example—if each ordinal n is identified with the set of all ordinals less than or equal to n, then a ≤ b if and only if ⊆. For the power set P of a set S, the partial order is the Cartesian product of k = |S| copies of the partial order on for which 0 <1. This can be illustrated by enumerating S = and associating with each subset T ⊆ S the k-tuple from k of which the ith coordinate is 1 if and only if si is a member of T
11.
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