|
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 a paper, . Statement Kummer's theorem states that for given integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...s ''n'' ≥ ''m'' ≥ 0 and a prime number ''p'', the ''p''-adic valuation \nu_p\left( \tbinom n m \right) 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of t ... [...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 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 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 method of checking the primality of a given number n, called trial division, tests whether n is a multiple of any integer between 2 and \sqrt. Faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which alway ... [...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 -adic valuation is a valuation and gives rise to an analogue of the usual absolute value. Whereas the 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 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 denotes the set of natural numbers and m \mid n denotes divisibility of n by m. In particular, \nu_p is a function \nu_p \colon \mathbb \to \mathbb \cup\ . For example, \nu_2(-12) = 2, \nu_3(-12) = 1, and ... [...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 n=0,1,2,\ldots gives a triangular array called Pascal's triangle, satisfying the recurrence relation :\binom = \binom + \binom. The binomial coefficients occur in many areas of mathematics, a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ernst Kummer
Ernst Eduard Kummer (29 January 1810 – 14 May 1893) was a German mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On .... Skilled in applied mathematics, Kummer trained German army officers in ballistics; afterwards, he taught for 10 years in a ''Gymnasium (school), gymnasium'', the German equivalent of high school, where he inspired the mathematical career of Leopold Kronecker. Life Kummer was born in Sorau, Province of Brandenburg, 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 eventually published a year later. In 1840, Kummer married Ottilie Mendelssohn, daughter of N ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of mathematics, the set of integers is often denoted by the boldface or blackboard bold \mathbb. 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 natural numbers, \mathbb is countably infinite. An integer may be regarded as a real number that can be written without a fractional component. For example, 21, 4, 0, and −2048 are integers, while 9.75, , and are not. The integers form the smallest group and the smallest ring containing the natural numbers. In algebraic number theory, the integers are sometimes qualified as rational integers to distinguish them from the more general algebraic in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Carry (arithmetic)
In elementary arithmetic, a carry is a digit that is transferred from one column of digits to another column of more significant digits. It is part of the standard algorithm to 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 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 is the carry. The opposite is a borrow, as in −1 47 − 19 ---- 28 Here, , so try , and the 10 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Radix
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) 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, although for base ten the subscript is usually assumed (and omitted, together with the pair of 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 In the system with radix 13, for example, a string of digits such as ... [...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 = 2 ... [...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 formula describes how a sum with terms expands when raised to an arbitrary power : :(x_1 + x_2 + \cdots + x_m)^n = \sum_ \prod_^m x_t^\,, 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 . Also, as with the binomial theorem, quantities of the form that appear are taken to equal 1 ( even when equals zero). 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 ... [...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 base ''p'' digits of ''n'' is greater than the corresponding digit of ''m''. * In particular, is |
