|
Kummer's Theorem
In mathematics, Kummer's theorem is a formula for the exponent of the highest power of a prime number ''p'' that divides a given binomial coefficient. In other words, it gives the ''p''-adic valuation of a binomial coefficient. The theorem is named after Ernst Kummer, who proved it in 1852 . Statement Kummer's theorem states that for given integers ''n'' ≥ ''m'' ≥ 0 and a prime number ''p'', the ''p''-adic valuation \nu_p\!\tbinom n m of the binomial coefficient \tbinom is equal to the number of carries when ''m'' is added to ''n'' − ''m'' in base ''p''. An equivalent formation of the theorem is as follows: Write the base-p expansion of the integer n as n=n_0+n_1p+n_2p^2+\cdots+n_rp^r, and define S_p(n):=n_0+n_1+\cdots+n_r to be the sum of the base-p digits. Then : \nu_p\!\binom nm = \dfrac. The theorem can be proved by writing \tbinom as \tfrac and using Legendre's formula. Examples To compute the largest power of 2 dividing ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many areas of mathematics, which include number theory (the study of numbers), algebra (the study of formulas and related structures), geometry (the study of shapes and spaces that contain them), Mathematical analysis, analysis (the study of continuous changes), and set theory (presently used as a foundation for all mathematics). Mathematics involves the description and manipulation of mathematical object, abstract objects that consist of either abstraction (mathematics), abstractions from nature orin modern mathematicspurely abstract entities that are stipulated to have certain properties, called axioms. Mathematics uses pure reason to proof (mathematics), prove properties of objects, a ''proof'' consisting of a succession of applications of in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prime Number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, or , involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorization, factorized as a product of primes that is unique up to their order. The property of being prime is called primality. A simple but slow primality test, method of checking the primality of a given number , called trial division, tests whether is a multiple of any integer between 2 and . Faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
P-adic Valuation
In number theory, the valuation or -adic order of an integer is the exponent of the highest power of the prime number that divides . It is denoted \nu_p(n). Equivalently, \nu_p(n) is the exponent to which p appears in the prime factorization of n. The P-adic number, -adic valuation is a Valuation (algebra), valuation and gives rise to an analogue of the usual absolute value. Whereas the Complete metric space, completion of the rational numbers with respect to the usual absolute value results in the real numbers \mathbb, the completion of the rational numbers with respect to the p-adic absolute value results in the p-adic number, numbers \mathbb_p. Definition and properties Let be a prime number. Integers The -adic valuation of an integer n is defined to be : \nu_p(n)= \begin \mathrm\ & \text n \neq 0\\ \infty & \text n=0, \end where \mathbb_0 denotes the set of natural numbers (including zero) and m \mid n denotes divisor, divisibility of n by m. In particular, \nu_p is a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Binomial Coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the term in the polynomial expansion of the binomial power ; this coefficient can be computed by the multiplicative formula : \binom nk = \frac, which using factorial notation can be compactly expressed as : \binom = \frac. For example, the fourth power of is : \begin (1 + x)^4 &= \tbinom x^0 + \tbinom x^1 + \tbinom x^2 + \tbinom x^3 + \tbinom x^4 \\ &= 1 + 4x + 6 x^2 + 4x^3 + x^4, \end and the binomial coefficient \tbinom =\tfrac = \tfrac = 6 is the coefficient of the term. Arranging the numbers \tbinom, \tbinom, \ldots, \tbinom in successive rows for gives a triangular array called Pascal's triangle, satisfying the recurrence relation : \binom = \binom + \binom . The binomial coefficients occur in many areas of mathematics, and espe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ernst Kummer
Ernst Eduard Kummer (29 January 1810 – 14 May 1893) was a German mathematician. Skilled in applied mathematics, Kummer trained German army officers in ballistics; afterwards, he taught for 10 years in a '' gymnasium'', the German equivalent of high school, where he inspired the mathematical career of Leopold Kronecker. Life Kummer was born in Sorau, Brandenburg (then part of Prussia). He was awarded a PhD from the University of Halle in 1831 for writing a prize-winning mathematical essay (''De cosinuum et sinuum potestatibus secundum cosinus et sinus arcuum multiplicium evolvendis''), which was published a year later. In 1840, Kummer married Ottilie Mendelssohn, daughter of Nathan Mendelssohn and Henriette Itzig. Ottilie was a cousin of Felix Mendelssohn and his sister Rebecca Mendelssohn Bartholdy, the wife of the mathematician Peter Gustav Lejeune Dirichlet. His second wife (whom he married soon after the death of Ottilie in 1848), Bertha Cauer, was a maternal cousin of Ottil ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative integers. The set (mathematics), set of all integers is often denoted by the boldface or blackboard bold The set of natural numbers \mathbb is a subset of \mathbb, which in turn is a subset of the set of all rational numbers \mathbb, itself a subset of the real numbers \mathbb. Like the set of natural numbers, the set of integers \mathbb is Countable set, countably infinite. An integer may be regarded as a real number that can be written without a fraction, fractional component. For example, 21, 4, 0, and −2048 are integers, while 9.75, , 5/4, and Square root of 2, are not. The integers form the smallest Group (mathematics), group and the smallest ring (mathematics), ring containing the natural numbers. In algebraic number theory, the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Carry (arithmetic)
In elementary arithmetic, a carry is a Numerical digit, digit that is transferred from one column of digits to another column of more significant digits. It is part of the standard algorithm to addition, add numbers together by starting with the rightmost digits and working to the left. For example, when 6 and 7 are added to make 13, the "3" is written to the same column and the "1" is carried to the left. When used in subtraction the operation is called a borrow. Carrying is emphasized in traditional mathematics, while curricula based on reform mathematics do not emphasize any specific method to find a correct answer. Carrying makes a few appearances in higher mathematics as well. In computing, carrying is an important function of adder (electronics), adder circuits. Manual arithmetic A typical example of carry is in the following pencil-and-paper addition: 1 27 + 59 ---- 86 7 + 9 = 16, and the digit 1 (number), 1 is the carry. The opposite is a borrow, as in − ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Radix
In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, because it uses the ten digits from 0 through 9. In any standard positional numeral system, a number is conventionally written as with ''x'' as the string of digits and ''y'' as its base. For base ten, the subscript is usually assumed and omitted (together with the enclosing parentheses), as it is the most common way to express value. For example, (the decimal system is implied in the latter) and represents the number one hundred, while (100)2 (in the binary system with base 2) represents the number four. Etymology ''Radix'' is a Latin word for "root". ''Root'' can be considered a synonym for ''base,'' in the arithmetical sense. In numeral systems Generally, in a system with radix ''b'' (), a string of digits denotes the number , ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Legendre's Formula
In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime ''p'' that divides the factorial ''n''!. It is named after Adrien-Marie Legendre. It is also sometimes known as de Polignac's formula, after Alphonse de Polignac. Statement For any prime number ''p'' and any positive integer ''n'', let \nu_p(n) be the exponent of the largest power of ''p'' that divides ''n'' (that is, the ''p''-adic valuation of ''n''). Then :\nu_p(n!) = \sum_^ \left\lfloor \frac \right\rfloor, where \lfloor x \rfloor is the floor function. While the sum on the right side is an infinite sum, for any particular values of ''n'' and ''p'' it has only finitely many nonzero terms: for every ''i'' large enough that p^i > n, one has \textstyle \left\lfloor \frac \right\rfloor = 0. This reduces the infinite sum above to :\nu_p(n!) = \sum_^ \left\lfloor \frac \right\rfloor \, , where L = \lfloor \log_ n \rfloor. Example For ''n'' = 6, one has 6! = 720 = ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Multinomial Coefficient
In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials. Theorem For any positive integer and any non-negative integer , the multinomial theorem describes how a sum with terms expands when raised to the th power: (x_1 + x_2 + \cdots + x_m)^n = \sum_ x_1^ \cdot x_2^ \cdots x_m^ where = \frac is a multinomial coefficient. The sum is taken over all combinations of nonnegative integer indices through such that the sum of all is . That is, for each term in the expansion, the exponents of the must add up to . In the case , this statement reduces to that of the binomial theorem. Example The third power of the trinomial is given by (a+b+c)^3 = a^3 + b^3 + c^3 + 3 a^2 b + 3 a^2 c + 3 b^2 a + 3 b^2 c + 3 c^2 a + 3 c^2 b + 6 a b c. This can be computed by hand using the distributive property of multiplication over additi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lucas's Theorem
In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient \tbinom by a prime number ''p'' in terms of the base ''p'' expansions of the integers ''m'' and ''n''. Lucas's theorem first appeared in 1878 in papers by Édouard Lucas. Statement For non-negative integers ''m'' and ''n'' and a prime ''p'', the following congruence relation holds: :\binom\equiv\prod_^k\binom\pmod p, where :m=m_kp^k+m_p^+\cdots +m_1p+m_0, and :n=n_kp^k+n_p^+\cdots +n_1p+n_0 are the base ''p'' expansions of ''m'' and ''n'' respectively. This uses the convention that \tbinom = 0 if ''m'' < ''n''. Proofs There are several ways to prove Lucas's theorem.Consequences * A binomial coefficient is divisible by a prime ''p'' if and only if at least one of the digits of the base-''p'' representation of ''n'' is greater than the corresponding digit of ''m''. * In particular, |
