:: wikimiki.org ::

Divisibility

Divisibility

:For divisors in algebraic geometry, see divisor (algebraic geometry). In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder.

Explanation

For example, 7 is a divisor of 42 because 42/7 = 6. We also say 42 is divisible by 7 or 42 is a multiple of 7 or 7 divides 42 and we usually write 7 | 42. For example, the positive divisors of 42 are 1, 2, 3, 6, 7, 14, 21, 42. In general, we say m|n (read: m divides n) for any integers m and n iff there exists an integer k such that n = km. Thus, divisors can be negative as well as positive. 1 and -1 are divisors of every integer, every integer is a divisor of itself, and every integer is a divisor of 0, while 0 is a divisor only of 0 (see also division by zero). Numbers divisible by 2 are called even and those that are not are called odd. A divisor of n that is not 1, -1, n or -n is known as a non-trivial divisor; numbers with non-trivial divisors are known as composite numbers, while prime numbers have no non-trivial divisors. The name comes from the arithmetic operation of division: if a/b=c then a is the dividend, b the divisor, and c the quotient. There are some rules which allow to recognize small divisors of a number from the number's decimal digits.

Further notions and facts

Some elementary rules:
- If a | b and a | c, then a | (b + c), in fact, a | (mb + nc) for all integers m, n.
- If a | b and b | c, then a | c. (transitive relation)
- If a | b and b | a, then a = b or a = -b. The following property is important:
- If a | bc, and gcd(a,b) = 1, then a | c. (Euclid's lemma) A positive divisor of n which is different from n is called a proper divisor (or aliquot part) of n. (A number which does not evenly divide n, but leaves a remainder, is called an aliquant part of n.) An integer n > 1 whose only proper divisor is 1 is called a prime number. Any positive divisor of n is a product of prime divisors of n raised to some power. This is a consequence of the Fundamental theorem of arithmetic. If a number equals the sum of its proper divisors, it is said to be a perfect number. Numbers less than that sum are said to be deficient, while numbers greater than that sum are said to be abundant. The total number of positive divisors of n is a multiplicative function d(n) (e.g. d(42) = 8 = 2×2×2 = d(2)×d(3)×d(7)). The sum of the positive divisors of n is another multiplicative function σ(n) (e.g. σ(42) = 96 = 3×4×8 = σ(2)×σ(3)×σ(7)). If the prime factorization of n is given by :

n = p_1^ \, p_2^ \, ... \, p_n^

then the number of positive divisors of n is :

d(n) = (\nu_1 + 1) (\nu_2 + 1) ... (\nu_n + 1),

and each of the divisors has the form :

p_1^ \, p_2^ \, ... \, p_n^

where :

\forall i : 0 \le \mu_i \le \nu_i.

Divisibility of numbers

The relation | of divisibility turns the set N of non-negative integers into a partially ordered set, in fact into a complete distributive lattice. The largest element of this lattice is 0 and the smallest one is 1. The meet operation ^ is given by the greatest common divisor and the join operation v by the least common multiple. This lattice is isomorphic to the dual of the lattice of subgroups of the infinite cyclic group Z. If an integer n is written in base b, and d is an integer with b ≡ 1 (mod d), then n is divisible by d if and only if the sum of its digits is divisible by d. The rules for d=3 and d=9 given above are special cases of this result (b=10). We can generalize this method even further to find how to check divisibility of any integer in any base by any other (smaller integer). Let us say that we want to determine if d | a in base b. Then we first find a pair of integers (n, k) that solves the congruence bⁿ ≡ k (mod d). Now rather than summing the digits, we take a (which has m digits) and multiply the first m-n digits by k and add the product to the last (or more precisely, smallest) k digits and repeat if necessary. If the result is a multiple of d then the original number is divisible by d. A few examples will help demonstrate this. Since 10³ ≡ 1 (mod 37) then the number 1523836638 gives 1+523+836+638 = 1998 which gives 999 which we know is divisible by 37 due to the above congruence. Again, 10² ≡ 2 (mod 7) so 43106 gives 431×2 + 06 = 868 which gives 8×2+68 = 84 which is easily noted as being a multiple of 7. Note that there is no unique triple (n, k, d) since for example 10 ≡ 3 (mod 7) so we could also have done 4310×3 + 6 = 12936 and 1293×3 + 6 = 3885 and 388×3 + 5 = 1169 and 116×3 + 9 = 357 and 35×3 + 7 = 112 and 11×3 + 2 = 35 and 3×3 + 5 = 14 and 1×3 + 4 = 7. Clearly this is not always efficient but note that each number in this series, 43106, 12936, 3885, 1169, 357, 112, 35, 14, 7 is a multiple of 7 and many series could contain trivially identifiable multiples. This method is not necessarily useful for some numbers (for example 10⁴ ≡ 4 (mod 17) is the first n where k < 10) but lends itself to fast calculations in other cases where n and k are relatively small.

Generalization

One can talk about the concept of divisibility in any integral domain. Please see that article for the definitions in that setting.

External links

- [http://www.farfarfar.com/math/calculators/factoring/ Factoring Calculator] -- Factoring calculator that displays the prime factors and the prime and non-prime divisors of a given number.
- [http://users.adelphia.net/~j.mccranie/ webpage that has program for factoring up to 18 digit numbers] Category:Elementary number theory Category:Elementary arithmetic ko:약수 ja:約数

Divisor (algebraic geometry)

In algebraic geometry, divisors are a generalization of subvarieties of algebraic varieties; two different generalizations are in common use, Cartier divisors and Weil divisors (named for Pierre Cartier and André Weil). The concepts agree on non-singular varieties over algebraically closed fields. A Weil divisor is a locally finite linear combination of irreducible subvarieties of codimension one. The set of Weil divisors forms an Abelian group under addition. In the classical theory, where locally finite is automatic, the group of Weil divisors on a variety of dimension n is therefore the free abelian group on the (irreducible) subvarieties of dimension (n − 1). For example, a divisor on an algebraic curve is a formal sum of its points. An effective Weil divisor is then one in which all the coefficients of the formal sum are non-negative. A Cartier divisor consists of an open cover

, and a collection of rational functions

f_i

defined on

U_i

. The functions must be "compatible in this sense: on the intersection of two sets in the cover, the quotient of the corresponding rational functions should be regular and invertible. A Cartier divisor is said to be effective if these

f_i

can be chosen to be regular functions, and in this case the Cartier divisor defines an associated subvariety of codimension 1. To every Cartier divisor D there is an associated line bundle (strictly, invertible sheaf) denoted by L[D], and the sum of divisors corresponds to the tensor product of line bundles. Isomorphism of bundles corresponds precisely to linear equivalence of Cartier divisors, and so the divisor classes give rise to the Picard group. Following the general conceptual clue that sheaves reveal the 'correct' geometry, Cartier divisors, introduced in the 1950s where Weil divisors are classical, are more appropriate to deal with singular points. An example of a surface on which the two concepts differ is a cone, i.e. a singular quadric. At the (unique) singular point, the vertex of the cone, a single line drawn on the cone is a Weil divisor — but is not a Cartier divisor. The divisor appellation is part of the history of the subject, going back to the Dedekind-Weber work which in effect showed the relevance of Dedekind domains to the case of algebraic curves. In that case the free abelian group on the points of the curve is closely related to the fractional ideal theory. Category:Geometry of divisors

Integer

The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. They are also known as the whole numbers, although that term is also used to refer only to the positive integers (with or without zero). Like the natural numbers, the integers form a countably infinite set. The set of all integers is usually denoted in mathematics by a boldface Z (or blackboard bold,

\mathbb

), which stands for Zahlen (German for "numbers"). The term rational integer is used, in algebraic number theory, to distinguish these 'ordinary' integers, in the rational numbers, from other concepts such as the Gaussian integers.

Algebraic properties

Like the natural numbers, Z is closed under the operations of addition and multiplication, that is, the sum and product of any two integers is an integer. However, with the inclusion of the negative natural numbers, and, importantly, zero, Z (unlike the natural numbers) is also closed under subtraction. Z is not closed under the operation of division, since the quotient of two integers (e.g., 1 divided by 2), need not be an integer. The following table lists some of the basic properties of addition and multiplication for any integers a, b and c. In the language of abstract 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, since every nonzero integer can be written as a finite sum 1 + 1 + ... 1 or (−1) + (−1) + ... + (−1). 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, note that not every integer has a multiplicative inverse; e.g. there is no integer x such that 2x = 1, because the left hand side is even, while the right hand side is odd. This means that Z under multiplication is not a group. All the properties from the above table taken together say that Z together with addition and multiplication is a commutative ring with unity. In fact, Z provides the motivation for defining such a structure. The lack of multiplicative inverses, which is equivalent to the fact that Z is not closed under division, means that Z is not a field. The smallest field containing the integers is the field of rational numbers. This process can be mimicked to form the quotient field of any integral domain, where an integral domain is a commutative ring with unity such that whenever ab = 0, either a = 0 or b = 0. Although ordinary division is not defined on Z, it does possess an important property called the division algorithm: that is, given two integers a and b with b ≠ 0, there exist unique integers q and r such that a = q × b + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b. The integer q is called the quotient and r is called the remainder, resulting from division of a by b. This is the basis for the Euclidean algorithm for computing greatest common divisors. Again, in the language of abstract algebra, the above says that Z is a Euclidean domain. This implies that Z is a principal ideal domain and any positive integer can be written as the products of primes in an essentially unique way. This is the fundamental theorem of arithmetic.

Order-theoretic properties

Z is a totally ordered set without upper or lower bound. The ordering of Z is given by : ... < −2 < −1 < 0 < 1 < 2 < ... An integer is positive if it is greater than zero and negative if it is less than zero. Zero is defined as neither negative nor positive. The ordering of integers is compatible with the algebraic operations in the following way: # if a < b and c < d, then a + c < b + d # if a < b and 0 < c, then ac < bc. (From this fact, one can show that if c < 0, then ac > bc.)

Integers in computing

An integer (sometimes known as an "int", from the name of a datatype in the C programming language) is often a primitive datatype in computer languages. However, integer datatypes can only represent a subset of all integers, since practical computers are of finite capacity. Variable-length representations of integers, such as bignums, can store any integer that fits in the computers memory. Other integer datatypes are implemented with a fixed size, usually a number of bits which is a power of 2 (4, 8, 16, etc.) or a memorable number of decimal digits (e.g., 9 or 10). In contrast, theoretical models of digital computers, such as Turing machines, typically do have infinite (but only countable) capacity.

Quotations

God invented the integers, all else is the work of man. Kronecker

External links

- [http://www.positiveintegers.org The Positive Integers - divisor tables and numeral representation tools] Category:Elementary mathematics Category:Group theory Category:Integers Category:Elementary number theory Category:Set theory ko:정수 ja:整数 th:จำนวนเต็ม

IFF

IFF, Iff or iff can stand for:
- Interchange File Format - a computer file format introduced by Electronic Arts
- Identification friend or foe - a battlefield identification system
- iff - the mathematics concept if and only if
- International Film Festival
- TIFF - Toronto International Film Festival
- Montreal International Film Festival
- International Floorball Federation - the international federation regulating the sport of floorball
- International Flavors and Fragrances

Negative and non-negative numbers

A negative number is a number that is less than zero, such as −3. A positive number is a number that is greater than zero, such as 3. Zero itself is neither negative nor positive, though in computing zero is sometimes treated as though it were a positive number. The non-negative numbers are the real numbers that are not negative (positive or zero). The non-positive numbers are the real numbers that are not positive (negative or zero). In the context of complex numbers positive implies real, but for clarity one may say "positive real number".

Negative numbers

Negative integers can be regarded as an extension of the natural numbers, such that the equation x − y = z has a meaningful solution for all values of x and y. The other sets of numbers are then derived as progressively more elaborate extensions and generalizations from the integers. Negative numbers are useful to describe values on a scale that goes below zero, such as temperature, and also in bookkeeping where they can be used to represent debts. In bookkeeping, debts are often represented by red numbers, or a number in parentheses.

Non-negative numbers

A number is nonnegative if and only if it is greater than or equal to zero, i.e. positive or zero. Thus the nonnegative integers are all the integers from zero on upwards, and the nonnegative reals are all the real numbers from zero on upwards. A real matrix A is called nonnegative if every entry of A is nonnegative. A real matrix A is called totally nonnegative by matrix theorists or totally positive by computer scientists if the determinant of every square submatrix of A is nonnegative.

Sign function

It is possible to define a function sgn(x) on the real numbers which is 1 for positive numbers, −1 for negative numbers and 0 for zero (sometimes called the signum function): :

\sgn(x)=\left\

Division by zero

In mathematics, a division is called a division by zero if the divisor is zero. Such a division can be formally expressed as

\frac

, where a is the dividend. Whether this expression can be assigned a meaningful (well-defined) value depends upon how the expression is interpreted.

Algebraic interpretation

It is generally regarded among mathematicians that a natural way to interpret division by zero is to first define division in terms of other arithmetic operations. Under the standard rules for arithmetic on integers, rational numbers, real numbers and complex numbers, the value of a division by zero is undefined, as it is in any field. The reason is that division is defined to be the inverse operation of multiplication. This means that the value of :

is the solution x of the equation :

b x = a \quad

whenever such a value exists and is unique. Otherwise the expression

is undefined. For b = 0, the equation bx = a can be rewritten as 0x = a or simply 0 = a. Thus, in this case, the equation bx = a has no solution if a is not equal to 0, and has any x as a solution if a equals 0. In either case,

is undefined. Conversely, for the number systems mentioned above, the expression

is always defined if b is not equal to zero.

Fallacies based on division by zero

It is possible to disguise a special case of division by zero in an algebraic argument, leading to spurious proofs that 2 = 1 such as the following:
- 1) For any real number

x

: ::

x^2 - x^2 = x^2 - x^2 \quad

- 2) Factoring both sides in two different ways: ::

(x - x)(x + x) = x(x - x)\quad

- 3) Dividing both sides by

x - x

, giving

(0/0)

: ::

(0/0)(x + x) = x(0/0) \quad

- 4) Simplified, yields: ::

(1)(x + x) = x(1) \quad

- 5) Which is: ::

2x = x \quad

- 6) Since this is valid for any value of

x

, we can plug in

x = 1

. ::

2 = 1 \quad

The fallacy is the assumption in step 4 that

(x - x)/(x - x)

-- which is

(0/0)

-- simplifies to

1

. This proof is for the special case of dividing by zero when the numerator is zero. The fallacy results from the assumption that

0/0 = 1

-- an assumption that generates the absurdity that

2 = 1

. This special case proof is instructive in that it is commonly held to be a general proof on how division by zero is destructive to math (a virtual Weapon of Math Destruction). In reality it only shows that

0/0 = 1

is bad for algebra. This proof, strictly speaking, is not a general case against division by zero. If one were to rewrite the proof and assume that

0/0 = 0

, the absurdity would be erased. This flexibility on assuming the value of

0/0

gets to the real issue:

0/0

is indeterminate on the Reals. In the above proof it was determined to be

1

-- possibly because of the rule that

a/a = 1

. But when

a = 0

we have an indeterminate meaning, and we are also free to work as if

0/0 = 0

. Still, in practice, division by a term in any algebraic argument will require either an explicit assumption that the term is not zero, or a separate justification showing that the term can never be zero.

Abstract algebra

Similar statements are true in more general algebraic structures, such as rings and fields. In a field, every nonzero element is invertible under multiplication, so as above, division poses problems only when attempting to divide by zero. However, in other rings, division by nonzero elements may also pose problems. Consider, for example, the ring Z/6Z of integers mod 6. What meaning should we give to the expression :

This should be the solution x of the equation :

2x = 2 \quad

But this equation has two distinct solutions, x = 1 and x = 4, so the expression is undefined. The problem occurs because 2 is not invertible under multiplication.

Limits and division by zero

field At first glance it seems possible to define

by considering the limit of

as b approaches 0. For any nonzero a, it is known that :

\lim_  = \infty

and :

\lim_  = \infty

Therefore, we might consider defining

+\infty

for positive a, and

-\infty

for negative a. However, this definition is not generally useful, because positive and negative infinity are not real numbers, and the equation :

0 \, x = a

still has no solution for any finite a. Furthermore, there is no obvious definition of

that can be derived from considering the limit of a ratio. The limit :

\lim_

does not exist. Limits of the form :

\lim_

in which both f(x) and g(x) approach 0 as x approaches 0, may converge to any value or may not converge at all. See l'Hopital's rule for discussion and examples of limits of ratios.

In mathematical analysis

In distribution theory one can extend the function :

to a distribution on the whole space of real numbers (in effect by using Cauchy principal values). It does not, however, make sense to ask for a 'value' of this distribution at

x = 0

; a sophisticated answer refers to the singular support of the distribution.

Other number systems

Although division by zero is undefined with real numbers and integers, it is possible to consistently define division by zero in other mathematical structures, for instance on the Riemann sphere (see also poles in complex analysis). In hyperreal numbers and surreal numbers, division by non-zero infinitesimals is possible. If a number system forms a commutative ring, as do the integers, the real numbers, and the complex numbers, for instance, it can be extended to a wheel in which division by zero is always possible, but division has then a slightly different meaning.

Division by zero in computer arithmetic

The IEEE floating-point standard, supported by almost all modern processors, specifies that every floating point arithmetic operation, including division by zero, has a well-defined result. In IEEE 754 arithmetic, a/0 is positive infinity when a is positive, negative infinity when a is negative, and NaN (not a number) when a = 0. These definitions are derived from the properties of limits of ratios, as discussed above. Integer division by zero is usually handled differently from floating point since there is no integer representation for the result. Some processors generate an exception when an attempt is made to divide an integer by zero, although others will simply continue and simply generate an incorrect result for the division (often 0). If an exception is raised, the usual result is aborting whatever program it occurred in, although some programs (especially those that use fixed-point arithmetic where no dedicated floating-point hardware is available) will use behavior similar to the IEEE standard, using large positive and negative numbers to approximate infinities.

Even and odd numbers

In mathematics, any integer is either even or odd. If it is a multiple of two, it is an even number; otherwise, it is an odd number. Examples of even numbers are −4, 8, 0, and 70. Examples of odd numbers are −5, 1, and 71. The number zero is even, because it is equal to two multiplied by zero. The set of even numbers can be written: : Evens = 2Z = . The set of odd numbers can be shown like this: : Odds = 2Z + 1 = . A number expressed in the decimal numeral system is even or odd according to whether its last digit is even or odd. That is, if the last digit is 1, 3, 5, 7, or 9, then it's odd; otherwise it's 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 even or odd according to the sum of its digits. The even numbers form an ideal in the ring of integers, but the odd numbers do not. An integer is even if it is congruent to 0 modulo this ideal, in other words if it is congruent to 0 modulo 2, and odd if it is congruent to 1 modulo 2. All prime numbers are odd, with one exception: the prime number 2. All known perfect numbers are even; it is unknown whether any odd perfect numbers exist. Goldbach's conjecture states that every even integer greater than 2 can be represented as a sum of two prime numbers. Modern computer calculations have shown this conjecture to be true for integers up to at least 4 × 10¹⁴, but still no general proof has been found. The Feit-Thompson theorem states that a finite group is always solvable if its order is an odd number. This is an example of odd numbers playing a role in an advanced mathematical theorem where the method of application of the simple hypothesis of "odd order" is far from obvious. In wind instruments which are cylindrical and in effect closed at one end, such as the clarinet at the mouthpiece, the harmonics produced are odd multiples of the fundamental frequency. (With cylindrical pipes open at both ends, used for example in some organ stops such as the open diapason, the harmonics are even multiples of the same frequency, but this is the same as being all multiples of double the frequency and is usually perceived as such.) See harmonic series (music).

Arithmetic on even and odd numbers

The following laws can be verified using the properties of divisibility and the fact that 2 is a prime number:

Addition and subtraction

- even ± even = even;
- even ± odd = odd;
- odd ± odd = even.

Multiplication

- even
- even = even
- even
- odd = even
- odd
- odd = odd

Division

The division of two whole numbers does not necessarily result in a whole number. For example, 1 divided by 4 equals 1/4, which isn't even or odd, since the concepts even and odd apply only to integers. But when the quotient is an integer, it is even iff the numerator has more factors of two than the denominator. This will be correct it you add them up right!

Parity in mathematics

Parity is evenness or oddness of an integer. To say whether a number is even or odd is to specify its parity. The parity of a permutation (as defined in abstract algebra) is the parity (even or odd) of the number of transpositions into which the permutation can be decomposed. For example (ABC) to (BCA) is even because it can be done by swapping A and B then C and A (two transpositions). It can be shown that no permutation can be decomposed both in an even and in an odd number of transpositions. Hence the above is a suitable definition. See the article on even and odd permutations for an elaboration.

Composite numbers

A composite number is a positive integer which has a positive divisor other than one or itself. By definition, every integer greater than one is either a prime number or a composite number. The numbers zero and one are considered to be neither prime nor composite. The integer 14 is a composite number because it can be factored as 2 × 7.

Properties

- All even numbers greater than 2 are composite numbers.
- The smallest composite number is 4.
- Every composite number can be written as the product of (not necessarily distinct) primes. (Fundamental theorem of arithmetic)
- Also,

(n-1)! \,\,\, \equiv \,\, 0 \pmod

for all composite numbers n > 5.(Wilson's theorem)

Kinds of composite numbers

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 (the factors need not be distinct, hence squares of primes are included). 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 distinct prime factors and those with an even number of distinct prime factors. For the latter :

\mu(n) = (-1)^ = 1\,

(where μ is the Möbius function and x is half the total of prime factors), while for the former :

\mu(n) = (-1)^ = -1.\,

Note however that for prime numbers the function also returns -1, and that

\mu(1) = 1

. For a number n with one or more repeated prime factors,

\mu(n) = 0

. 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 (though the first two such numbers are 1 and 2).

Prime numbers

In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. Or for short: A prime number is a natural number with exactly two natural and distinct divisors. A natural number that is greater than one and is not a prime is called a composite number. The numbers zero and one are neither prime nor composite. The property of being a prime is called primality. Prime numbers are of fundamental importance in number theory. The sequence of prime numbers begins :2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, ... This is sequence A000040 in OEIS; see list of prime numbers for the first 500 primes. The set of all prime numbers is sometimes denoted by ℙ, a blackboard bold P. As 2 is the only even prime number, the term odd prime is used to refer to all prime numbers except 2. In the context of ring theory, a branch of abstract algebra, the term "prime element" has a specific meaning. Here, a ring element a is defined to be prime if whenever a divides bc for ring elements b and c, then a divides at least one of b or c. With this meaning, the additive inverse of any prime number is also prime. In other words, when considering the set of integers ℤ (Z) as a ring, −7 is a prime element. However, even among mathematicians, the term "prime number" generally means a positive prime integer.

Representing natural numbers as products of primes

The fundamental theorem of arithmetic states that every positive integer can be written as a product of primes in a unique way, i.e. unique except for the order. Primes are thus the "basic building blocks" of the natural numbers (The proof of this is below). For example, we can write :

23244 = 2^2 \times 3 \times 13 \times 149 \,

and any other such factorization of 23244 will be identical except for the order of the factors. See prime factorization algorithm for details for how to do this in practice for larger numbers. The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications. Proof: Every positive integer greater than 1 has a prime divisor. We prove this through contradiction; we assume that there exists a number greater than one that has no prime divisors. Then, as the set of positive integers greater than one with no prime divisors is not an empty set, the well-ordering property tells us that there is a least one positive integer n greater than 1 with no prime divisors. Since n has no prime divisors and n divides n, we see that n is not prime. Hence we can write n=ab with 1 How many prime numbers are there? There are infinitely many prime numbers. The oldest known proof for this statement is given by the Greek mathematician Euclid in his Elements (Book IX, Proposition 20). Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following: :Suppose you have a finite number of primes. Call this number m. Multiply all m primes together and add one (see Euclid number). The resulting number is not divisible by any of the finite set of primes, because dividing by any of these would give a remainder of one. And one is not divisible by any primes. Therefore it must either be prime itself, or be divisible by some other prime that was not included in the finite set. Either way, there must be at least m+1 primes. But this argument applies no matter what m is; it applies to m+1, too. So there are more primes than any given finite number. Lemma: For any natural number A which is greater than 1, there exists a prime divisor for A. :We can use proof by contradiction. Assume that there is a set of numbers that do not have prime divisors. We'll call this set K. By the well-ordering principle, there exist a minimal element k. k doesn't equal 1 because we convention above it. k also cannot be prime because it would otherwise have a prime divisor, namely itself. Therefore k must be composite. By definition a composite number is a non-prime number with at least one positive factor other than 1 and itself. Thus k can be written as k=ab. a and b are both less than k (a and b are positive integers that divide into k). Since k is the smallest value for which the theorem fails, then a and b must have prime divisors. And since k=ab, then k must have a prime divisor. Thus a contradiction occurs, and for any natural number A which is greater than 1, there exists a prime divisor for A. This previous argument explains why the product of m primes + 1 must be divisible by some prime not in the finite set of primes. Other mathematicians have given their own proofs. One of those (due to Euler) shows that the sum of the reciprocals of all prime numbers diverges to infinity. Kummer's is particularly elegant and Furstenberg provides one using general topology. Even though the total number of primes is infinite, one could still ask "approximately how many primes are there below 100,000" or "How likely is a random 100-digit number to be prime?" Questions like these are answered by the prime number theorem.

Finding prime numbers

The Sieve of Eratosthenes is a simple way and the Sieve of Atkin a fast way to compute the list of all prime numbers up to a given limit. In practice though, one usually wants to check if a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime N. After several iterations, they declare N to be "definitely composite" or "probably prime". These tests are not perfect. For a given test, there may be some composite numbers that will be declared "probably prime" no matter what witness is chosen. Such numbers are called pseudoprimes for that test. A new deterministic algorithm which finds whether a given number N is prime where the time required is a polynomial function of the number of digits of N (i.e. of the logarithm of N) has recently been described.

Some properties of primes

- If p is a prime number and p divides a product ab of integers, then p divides a or p divides b. This proposition was proved by Euclid and is known as Euclid's lemma. It is used in some proofs of the uniqueness of prime factorizations.
- The ring Z/nZ (see modular arithmetic) is a field if and only if n is a prime. Put another way: n is prime if and only if φ(n) = n − 1.
- If p is prime and a is any integer, then a^p − a is divisible by p (Fermat's little theorem).
- If p is a prime number other than 2 and 5, 1/p is always a recurring decimal, with a period of p-1 or a divisor of p-1. This can be deduced directly from Fermat's little theorem. 1/p expressed likewise in base q (i.e. other than base 10) has similar effect, provided that p is not a prime factor of q. The Wiki page on recurring decimal shows some of the interesting properties.
- An integer p > 1 is prime if and only if the factorial (p − 1)! + 1 is divisible by p (Wilson's theorem). Conversely, an integer n > 4 is composite if and only if (n − 1)! is divisible by n.
- If n is a positive integer greater than 1, then there is always a prime number p with n < p < 2n (Bertrand's postulate).
- Adding the reciprocals of all primes together results in a divergent infinite series (proof). More precisely, if S(x) denotes the sum of the reciprocals of all prime numbers p with p ≤ x, then S(x) = Θ(ln ln x) for x → ∞ (see Big O notation).
- For each prime number p > 2, there exists a natural number n such that p = 4n ± 1.
- For each prime number p > 3, there exists a natural number n such that p = 6n ± 1.
- In every arithmetic progression a, a + q, a + 2q, a + 3q,... where the positive integers a and q ≥ 1 are coprime, there are infinitely many primes (Dirichlet's theorem).
- The characteristic of every field is either zero or a prime number.
- If G is a finite group and pⁿ is the highest power of the prime p which divides the order of G, then G has a subgroup of order pⁿ. (Sylow theorems)
- If p is prime and G is a group with pⁿ elements, then G contains an element of order p.
- The prime number theorem says that the proportion of primes less than x is asymptotic to 1/ln x (in other words, as x gets very large, the likelihood that a number less than x is prime is inversely proportional to the number of digits in x).

Open questions

There are many open questions about prime numbers. The most significant of these is the Riemann hypothesis, which essentially says that the primes are as regularly distributed as possible. From a physical viewpoint, it roughly states that the irregularity in the distribution of primes only comes from random noise. From a mathematical viewpoint, it roughly states that the asymptotic distribution of primes (about 1/ log x of number less than x are primes, the prime number theorem) also holds for much shorter intervals of length about the square root of x (for intervals near x). This hypothesis is generally believed to be correct, in particular, the simplest assumption is that primes should have no significant irregularities without good reason. Other famous conjectures have a much greater chance of being true (in a formal sense, they follow from simple heuristic probabilistic arguments) with the lack of a solution more of a reflection of lack of good technical tools (so theoretical physicists would just regard them as being true):
- Goldbach's conjecture: Can every even integer greater than 2 be written as a sum of two primes?
- Twin prime conjecture: A twin prime is a pair of primes with difference 2, such as 11 and 13. Are there infinitely many twin primes?
- Polignac's conjecture: For every integer n, are there infinitely many pairs of consecutive primes which differ by 2n? (When n=1 this is the twin prime conjecture)
- Does the Fibonacci sequence contain an infinite number of primes?
- Are there infinitely many Mersenne primes and Fermat primes? The expected answers are yes, resp. no.
- Are there infinitely many primes of the form n² + 1?
- Legendre's conjecture: Is there always a prime number between n² and (n + 1)² for every n?
- Cramer's conjecture that

d(x)

, the largest gap between consecutive primes, among all primes less than x, is asymptotic to

\log^2 x

. This conjecture clearly implies the previous one, but its status is a little more unsure.
- Brocard's conjecture: Are there always at least four primes between the squares of successive primes > 2?

The largest known prime

The largest known prime, as of September 2005, is 2^25964951 − 1 (this number is 7,816,230 digits long); it is the 42nd known Mersenne prime. M_25964951 was found on February 18, 2005 by Martin Nowak, a member of a collaborative effort known as GIMPS. The next largest known prime is 2^24036583 − 1 (this number is 7,235,733 digits long); it is the 41st known Mersenne prime. M_24036583 was found on May 15, 2004 by Josh Findley (member of GIMPS) and it was announced in late May 2004. The third largest known prime is 2^20996011 − 1 (this number is 6,320,430 digits long); it is the 40th known Mersenne prime. M_20996011 was found on November 17, 2003 by Michael Shafer (and GIMPS) and announced in early December 2003. Historically, the largest known prime has almost always been a Mersenne prime since the dawn of electronic computers, because there exists a particularly fast primality test for numbers of this form, the Lucas-Lehmer test for Mersenne primes. The largest known prime that is not a Mersenne prime is 27653 × 2^9167433 + 1 (2,759,677 digits). This is also the fifth largest known prime of any form. It was found by the Seventeen or Bust project and it brings them one step closer to solving the Sierpinski problem. Some of the largest primes not known to have any particular form (that is, no simple formula such as that of Mersenne primes) have been found by taking a piece of semi-random binary data, converting it to a number n, multiplying it by 256^k for some positive integer k, and searching for possible primes within the interval [256^kn + 1, 256^k(n + 1) − 1]. In fact, as a publicity stunt against the Digital Millennium Copyright Act and other WIPO Copyright Treaty implementations, some people have applied this to various forms of DeCSS code, creating the set of illegal prime numbers. Such numbers, when converted to binary and executed as a computer program, perform acts encumbered by applicable law in one or more jurisdictions.

Applications

Extremely large prime numbers (that is, greater than 10¹⁰⁰) are used in several public key cryptography algorithms. Primes are also used for hash tables and pseudorandom number generators.

Primality tests

Main article primality test A primality test algorithm is an algorithm which tests a number for primality, i.e. whether the number is a prime number.
- AKS primality test
- Fermat primality test
- Lucas-Lehmer test
- Lucas-Lehmer primality test
- Solovay-Strassen primality test
- Miller-Rabin primality test A probable prime is an integer which, by virtue of having passed a certain test, is considered to be probably prime. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes.

Some special types of primes

A prime p is called primorial or prime-factorial if it has the form p = Π(n) ± 1 for some number n, where Π(n) stands for the product 2 · 3 · 5 · 7 · 11 · ... of all the primes ≤ n. A prime is called factorial if it is of the form n! ± 1. The first factorial primes are: :n! − 1 is prime for n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166,... :n! + 1 is prime for n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154... The largest known primorial prime is Π(24029) + 1, found by Caldwell in 1993. The largest known factorial prime is 3610! − 1 [Caldwell, 1993]. It is not known if there are infinitely many primorial or factorial primes. Primes of the form 2ⁿ − 1 are known as Mersenne primes, while primes of the form

2^ + 1

are known as Fermat primes. Prime numbers p where 2p + 1 is also prime are known as Sophie Germain primes. Other special types of prime numbers include Wieferich primes, Wilson primes, Wall-Sun-Sun primes, Wolstenholme primes, unique primes, Newman-Shanks-Williams primes (NSW primes), Smarandache-Wellin primes, Wagstaff primes and supersingular primes. The base-ten digit sequence of a prime can be a palindrome, as in the prime 10³¹⁵¹² + 9700079 · 10¹⁵⁷⁵³ + 1.

Prime gaps

Let p_n denote the n-th prime number (i.e. p₁ = 2, p₂ = 3, etc.). The gap g_n between the consecutive primes p_n and p_{n + 1} is the number of (composite) numbers between them, i.e. :g_n = p_{n + 1} − p_n − 1. (Slightly different definitions are sometimes used.) We have g₁ = 0, g₂ = g₃ = 1, and g₄ = 3. The sequence of prime gaps has been extensively studied. For any N, the sequence :(N + 1)! + 2, (N + 1)! + 3, ..., (N + 1)! + N + 1 is a sequence of N consecutive composite integers. Therefore, there exist gaps between primes which are arbitrarily large, i.e. for any natural number N, there is an integer n with g_n > N. (Choose n so that p_n is the greatest prime number less than (N + 1)! + 2.) On the other hand, the gaps get arbitrarily small in proportion to the primes: the quotient (g_n/p_n) approaches zero as n approaches infinity. We say that g_n is a maximal gap if g_m < g_n for all m < n. The largest known maximal gap is 1131, found by T. Nicely and B. Nyman in 1999. It is the 64th smallest maximal gap, and it occurs after the prime 1693182318746371. The largest prime gap with identified gap ends known as of November 22, 2005 has a length of 2254930 [http://hjem.get2net.dk/jka/math/primegaps/megagap2.htm]. Note that the twin prime conjecture simply asserts that g_n = 1 for infinitely many integers n.

Formulae yielding prime numbers

Main article formula for primes There is no formula for primes which is more efficient at finding primes than the methods mentioned above under "Finding prime numbers". Those which do exist have little practical value. The curious polynomial f(n) = n² − n + 41 yields primes for n = 0,..., 40, but f(41) is composite. It has been proved that there is no polynomial which only yields prime numbers in this fashion. There is a set of Diophantine equations in 9 variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers. This can be used to obtain a single formula with the property that all its positive values are prime. Another formula is based on Wilson's theorem mentioned above, and generates the number two many times and all other primes exactly once. There are other similar formulae which also produce primes.

Generalizations

The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics.

Prime elements in rings

One can define prime elements and irreducible elements in any integral domain. For the ring Z of integers, the set of prime elements equals the set of irreducible elements; it's . As an example, we consider the Gaussian integers Z[i], that is, complex numbers of the form a + bi with a and b in Z. This is an integral domain, and its prime elements are the Gaussian primes. Note that 2 is not a Gaussian prime, because it factors into the product of the two Gaussian primes (1 + i) and (1 − i). The element 3, however, remains prime in the Gaussian integers. In general, rational primes (i.e. prime elements in the ring Z of integers) of the form 4k + 3 are Gaussian primes, whereas rational primes of the form 4k + 1 are not.

Prime ideals

In ring theory, one generally replaces the notion of number with that of ideal. Prime ideals are an important tool and object of study in commutative algebra, algebraic number theory and algebraic geometry. The prime ideals of the ring of integers are the ideals (0), (2), (3), (5), (7), (11), ... A central problem in algebraic number theory is how a prime ideal factors when it is lifted to an extension field. For example, in the Gaussian integer example above, (2) ramifies into a prime power (1 + i and 1 − i generate the same prime ideal), prime ideals of the form (4k + 3) are inert (remain prime), and prime ideals of the form (4k + 1) split (are the product of 2 distinct prime ideals).

Primes in valuation theory

In class field theory yet another generalization is used. Given an arbitrary field K, one considers valuations on K, certain functions from K to the real numbers R. Every such valuation yields a topology on K, and two valuations are called equivalent if they yield the same topology. A prime of K (sometimes called a place of K) is an equivalence class of valuations. With this definition, the primes of the field Q of rational numbers are represented by the standard absolute value function (known as the "infinite prime") as well as by the p-adic valuations on Q, for every prime number p.

Quotes

:"Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate." — Leonhard Euler :"God may not play dice with the universe, but something strange is going on with the prime numbers." — Paul Erdős

Primes in pop culture

In an episode of Star Trek: The Next Generation, two mutually unintelligible sentient life forms use the beginning sequence of prime numbers to communicate the fact that they are intelligent, thinking beings. Similarly, in the movie Contact an extraterrestrial intelligence transmits primes.

References

- Karl Sabbagh, The Riemann Hypothesis: The Greatest Unsolved Problem in Mathematics. Farrar, Straus and Giroux; 340 pages
- John Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. Joseph Henry Press; 448 pages
- Marcus du Sautoy, The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics. HarperCollins; 352 pages
- H. Riesel, Prime Numbers and Computer Methods for Factorization, 2nd ed., Birkhäuser 1994.

External links

- [http://primes.utm.edu/curios/ Prime curios] at the prime pages
- The prime pages -- http://www.utm.edu/research/primes/
- [http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html MacTutor history of prime numbers]
- [http://www.easycalculation.com/prime-number.php Online Prime Number calculator]
- [http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html The "PRIMES is in P" FAQ]
- [http://wikisource.org/wiki/Prime_numbers_%282_-_20000%29 The first 20,000 primes] (through 224737) at Wikisource
- [http://www.primenumbers.net/prptop/prptop.php List of largest known probable primes]
- [http://www.primepuzzles.net/ The prime puzzles]
- [http://www.ibiblio.org/omdb/prime/ The Prime Project] generates a new prime number every time the page is loaded
- [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html An English translation of Euclid's proof that there are infinitely many primes]
- [http://wims.unice.fr/wims/wims.cgi?module=tool/number/primes.en Primes] from WIMS is an online prime generator.
- [http://members.surfeu.fi/kklaine/primebear.html The Prime Number Shitting Bear]
- [http://www.kwiznet.com/p/takeQuiz.php?ChapterID=1543&CurriculumID=5 Prime Factorization Worksheet] generates new questions every time the page is loaded
- [http://mathworld.wolfram.com/PrimeSpiral.html Prime Spiral pattern] (Wolfram)
- [http://www.numberspiral.com/index.html Number Spiral with prime patterns] (Sacks)
- [http://www.alpertron.com.ar/googolm1.pl?digits=12 12 digit primes] Known 12-digit prime factors of Googolplex - 1
- [http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier]
- [http://www.hermetic.ch/factors/factors.htm Factorizer] Windows software to find prime numbers and pairs of prime numbers less than 2,147,483,646. Category:Integer sequences
- ko:소수 (수론) ja:素数 th:จำนวนเฉพาะ

Division (mathematics)

:This article is about the arithmetic operation. For other uses, see Division (disambiguation). In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication, and sometimes it can be interpreted as repeated subtraction. Specifically, if :

c \times b = a

where b is not zero, then :

\frac ab = c

that is, a divided by b equals c. For instance,

\frac 63 = 2

since

2 \times 3 = 6\,

. In the above expression, a is called the dividend, b the divisor and c the quotient. Division by zero (i.e. where the divisor is zero) is usually not defined.

Notation

Division is most often shown by placing the dividend over the divisor with a horizontal line between them. For example, a divided by b is written

\frac ab

. This can be read out loud as "a divided by b". A way to express division all on one line is to write the dividend, then a slash, then the divisor, like this:

a/b\,

. This is the usual way to specify division in most computer programming languages since it can easily be typed as a simple sequence of characters. A typographical variation which is halfway between these two forms uses a slash but elevates the dividend, and lowers the divisor: ^a⁄_b Any of these forms can be used to display a fraction. A fraction is a division expression where both dividend and divisor are integers (although typically called the numerator and denominator), and there is no implication that the division needs to be evaluated further. A less common way to show division is to use the obelus (or division sign) in this manner:

a \div b

. This form is infrequent except in elementary arithmetic. The obelus is also used alone to represent the division operation itself, as for instance as a label on a key of a calculator. In some non-English-speaking cultures, "a divided by b" has sometimes been written a : b. However, in English usage the colon is restricted to expressing the related concept of ratios.

Computing division

With a knowledge of multiplication tables, two integers can be divided on paper using the method of long division. If the dividend has a fractional part (expressed as a decimal fraction), one can continue the algorithm past the ones place as far as desired. If the divisor has a fractional part, one can restate the problem by moving the decimal to the right in both numbers until the divisor has no fraction. Division can be calculated with an abacus by repeatedly placing the dividend on the abacus, and then subtracting the divisor the offset of each digit in the result, counting the number of divisions possible at each offset. In modular arithmetic, some numbers have a multiplicative inverse with respect to the modulus. In such a case, division can be calculated by multiplication. This approach is useful in computers that do not have a fast division instruction.

Division of integers

Division of integers is not closed. Apart from division by zero being undefined, the quotient will not be an integer unless the dividend is an integer multiple of the divisor; for example 26 cannot be divided by 10 to give an integer. In such a case there are four possible approaches. # Say that 26 cannot be divided by 10. # Give the answer as a decimal fraction or a mixed number, so

\frac = 2.6

26/10 = 2 \frac 35

. This is the approach usually taken in mathematics. # Give the answer as a quotient and a remainder, so

\frac = 2

remainder 6. # Give the quotient as the answer, so

\frac = 2

. This is sometimes called integer division. One has to be careful when performing division of integers in a computer program. Some programming languages, such as C, will treat division of integers as in case 4 above, so the answer will be an integer. Other languages, such as MATLAB, will first convert the integers to real numbers, and then give a real number as the answer, as in case 2 above.

Division of rational numbers

The result of dividing two rational numbers is another rational number when the divisor is not 0. We may define division of two rational numbers p/q and r/s by :

= (p \times s)/(q \times r).

All four quantities are integers, and only p may be 0. This definition ensures that division is the inverse operation of multiplication.

Division of real numbers

Division of two real numbers results in another real number when the divisor is not 0. It is defined such a/b = c if and only if a = cb and b ≠ 0.

Division of complex numbers

Dividing two complex numbers results in another complex number when the divisor is not 0, defined thus: :

=  + i.

All four quantities are real numbers. r and s may not both be 0. Division for complex numbers expressed in polar form is simpler and easier to remember than the definition above: :

= e^.

Again all four quantities are real numbers. r may not be 0.

Division of polynomials

One can define the division operation for polynomials. Then, as in the case of integers, one has a remainder. See polynomial long division.

Division in abstract algebra

In abstract algebras such as matrix algebras and quaternion algebras, fractions such as

are typically defined as

a \cdot

a \cdot b^

where

b

is presumed to be an invertible element (i.e. there exists a multiplicative inverse

b^

such that

bb^ = b^b = 1

where

1

is the multiplicative identity). In an integral domain where such elements may not exist, division can still be performed on equations of the form

ab = ac

ba = ca

by left or right cancellation, respectively. More generally "division" in the sense of "cancellation" can be done in any ring with the aforementioned cancellation properties. By a theorem of Wedderburn, all finite division rings are fields, hence every nonzero element of such a ring is invertible, so division by any nonzero element is possible in such a ring. To learn about when algebras (in the technical sense) have a division operation, refer to the page on division algebras. In particular Bott periodicity can be used to show that any real normed division algebra must be isomorphic to either the real numbers R, the complex numbers C, the quaternions H, or the octonions O.

Division and calculus

The derivative of the quotient of two functions is given by the quotient rule: :

' = \frac

There is no general method to integrate the quotient of two functions.

External links

- [http://www.mathsisfun.com/dividing-decimals.html Method for Dividing Decimals]
-
- [http://webhome.idirect.com/~totton/abacus/pages.htm#Division1 Division on a Japanese abacus] selected from [http://webhome.idirect.com/~totton/abacus/ Abacus: Mystery of the Bead]
- [http://webhome.idirect.com/~totton/suanpan/sh_div/ Chinese Short Division Techniques on a Suan Pan] Category:Elementary arithmetic Category:Arithmetic ja:除法 simple:Division th:การหาร

Quotient

In mathematics, a quotient is the end result of a division problem. For example, in the problem 6 ÷ 3, the quotient would be 2, while 6 would be called the dividend, and 3 the divisor. A quotient can also mean just the integral part of the result of dividing two integers. For example, the quotient of 13 ÷ 5 would be 2 while the remainder would be 3. For more, see the division algorithm. In more abstract branches of mathematics, the word quotient is often used to describe sets, spaces, or algebraic structures whose elements are the equivalence classes of some equivalence relation on another set, space, or algebraic structure. See:
- quotient set
- quotient group
- quotient ring
- quotient space (linear algebra)
- quotient space of a topological space
- quotient object
- right quotient and left quotient (operations on formal languages) The Quotient rule is a method for finding derivatives in calculus. Quotients also come up in certain tests, like the IQ test, which stands for Intelligence Quotient. In this case, your quotient is basically your score. In recent decades, as people begin to emphasize on full personal development, other similar quotients appeared. These include Emotional Quotient, Adversity Quotient, Creativity Quotient, etc. Category:Real numbers zh-tw:商數

Transitive relation

In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. In mathematical notation, this is: :

\forall a, b, c  \in X,\ a R b \and b R c \; \Rightarrow a R c

Counting transitive relations

Unlike other relation properties, it is not possible to find a general formula that counts the number of transitive relations on a finite set. However, there is a formula for finding the number of relations which are simultaneously reflexive, symmetric, and transitive

Examples

For example, "is greater than" and "is equal to" are transitive relations: if a = b and b = c, then a = c. On the other hand, "is the mother of" is not a transitive relation, because if Alice is the mother of Brenda, and Brenda is the mother of Claire, then Alice is not the mother of Claire. Examples of transitive relations include:
- "is equal to" (equality)
- "is a subset of" (set inclusion)
- "is less than" and "is less than or equal to" (inequality)
- "divides" (divisibility)

Other properties that require Transitivity

- preorder - A transitive relation that is also reflexive.
- partial order - A preorder that is antisymmetric.
- equivalence relation - a relation that is a preorder and symmetric.
- Total Ordering - a relation is a total order if it is transitive, antisymmetric, and total

External link

- [http://www.cut-the-knot.org/triangle/remarkable.shtml Transitivity in Action] at cut-the-knot Category:Set theory

Sources

- Discrete and Combinatorial Mathematics - Fifth Edition - by Ralph P. Grimaldi

Euclid's lemma

Euclid's lemma is a generalisation of Proposition 30 of Book VII of Euclid's Elements. The lemma states that :If a positive integer divides the product of two other positive integers, and the first and second integers are coprime, then the first integer divides the third integer. This can be written in notation: :If n|ab and gcd(n,a)=1 then n|b. Proposition 30, also known as Euclid's first theorem, states: :If a prime number divides the product of two positive integers, then the prime number divides at least one of the positive integers. That can be written as: :If p|ab then p|a or p|b. Often times, proposition 30 is called Euclid's lemma instead of the generalisation. A lemma is a "mini" theorem that is proven and used to prove a bigger theorem. Most of the time in mathematics textbooks Euclid's lemma is used to prove the fundamental theorem of arithmetic.

Proof of Proposition 30

Say p is a prime factor of ab, but also state that it is not a factor of a. Therefore,

rp = ab

, where r is the other corresponding factor to produce ab. As p is prime, and also because it is not a factor of a, a and p must be coprime. This means that two integers x and y can be found so that

1 = px + ay

(Bézout's identity). Multiply b on both sides: :

b = b(px + ay)

b = bpx + bay.

We stated previously that

rp = ab

, and so: :

b = bpx + rpy

b = p(bx + ry).

Therefore, p is a factor of b. This means that p must always exactly divide either a or b or both. Q.E.D.

Aliquot

In mathematics, an aliquot part (or simply aliquot) of an integer is any of its integer divisors. For instance, 2 is an aliquot of 12. The sum of all the aliquots of an integer n is the value σ(n) of the divisor function σ at n.

Aliquant

An aliquant part (or simply aliquant) is an integer that is not an exact divisor of a given quantity. For instance, 7 is an aliquant of 16. All numbers greater than half of a given quantity are aliquants of the given quantity.

Prime factor

In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. Two positive integers are coprime if and only if they have no prime factors in common. The integer 1 is coprime to every positive integer, including itself. This is because it has no prime factors; it is the empty product. The prime factorization of a positive integer is a list of the integer's prime factors, together with the maximum power of each prime factor that divides the integer exactly. The fundamental theorem of arithmetic says that every positive integer has a unique prime factorization. For a positive integer n, the number of prime factors of n and the sum of the prime factors of n (not counting multiplicity) are examples of arithmetic functions of n that are additive but not completely additive.

Examples

- The prime factors of 6 are 3 and 2. (6 = 3 × 2)
- 5 has only one prime factor: itself. (5 is prime)
- 100 has two prime factors: 2 and 5. (100 = 2² × 5²)
- 2, 4, 8, 16, etc. each have only one prime factor: 2. (2 is prime, 4 = 2², 8 = 2³, etc.)
- 1 has no prime factors. (1 is the empty product)

Fundamental theorem of arithmetic

In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 is either a prime number or can be written as a product of prime numbers. Furthermore this factorization is unique except for the order. For instance, we can write :6936 = 2³ · 3 · 17² or 1200 = 2⁴ · 3 · 5² and there are no other possible factorizations of 6936 or 1200 into prime numbers, if we ignore the ordering of the factors. To make the theorem work even for the number 1, we can think of 1 as being the product of zero prime numbers (see empty product).

Applications

The theorem establishes the importance of prime numbers. The prime numbers are the basic building blocks of the positive integers, in the sense that every positive integer can be constructed from primes, and there is essentially only one such construction. Knowing the prime number factorization of a number gives complete knowledge about all (prime and non-prime) divisors of that number. For instance, the above factorization of 6936 tells us that the positive divisors of 6936 are of the form :2^a · 3^b · 17^c with [0 ≤ a ≤ 3], [0 ≤ b ≤ 1], and [0 ≤ c ≤ 2]. This yields a total of 4 · 2 · 3 = 24 positive divisors. Once the prime factorizations of two numbers are known, their greatest common divisor and least common multiple can be found quickly. For instance, from the above we see that the greatest common divisor of 6936 and 1200 is 2³ · 3 = 24. However if the prime factorizations are not known, the use of Euclid's algorithm generally requires much less calculation than factoring the two numbers. The fundamental theorem ensures that additive and multiplicative arithmetic functions are completely determined by their values on the powers of prime numbers.

Proof

The theorem was essentially first proved by Euclid. Although at first sight it seems 'obvious', it does not hold in more general number systems, including many rings of algebraic integers. This was first pointed out by Ernst Kummer in 1843, in his work on Fermat's last theorem. The recognition of this failure is one of the earliest developments in algebraic number theory. The proof consists of two parts: first, we have to show that every number can indeed be written as a product of primes; then we have to show that any two such representations are essentially the same. Suppose there were a positive integer which cannot be written as a product of primes. Then there must be a smallest such number: let's call it n. This number n cannot be 1, because of our convention above. It cannot be a prime number either, since any prime number is a product of a single prime, itself. So it must be a composite number. Thus :n = ab where both a and b are positive integers smaller than n. Since n was the smallest number for which the theorem fails, both a and b can be written as products of primes. But then :n = ab can be written as a product of primes as well, a contradiction. This is a minimal counterexample argument. The uniqueness part of the proof hinges on the following fact: if a prime number p divides a product ab, then it divides a or it divides b (Euclid's lemma). This is a lemma, to prove first. For that, if p doesn't divide a, then p and a are coprime and Bézout's identity yields integers x and y such that :px + ay = 1. Multiplying with b yields :pbx + aby = b, and since both summands on the left-hand side are divisible by p, the right-hand side is also divisible by p. That proves the lemma. Now take two products of primes which are equal. Take any prime p from the first product. It divides the first product, and hence also the second. By the above fact, p must then divide at least one factor in the second product. But the factors are all primes themselves, so p must actually be equal to one of the factors of the second product. So we can cancel p from both products. Continuing in this fashion, we eventually see that the prime factors of the two products must match up precisely. Aliter: Another proof of the uniqueness of the prime factorization of a given integer uses infinite descent: Assume that a certain integer can be written as (at least) two different products of prime numbers, then there must exist a smallest integer s with such a property. Call the two products of s p₁ ... pm and q₁ ... qn. No p_i (with 1 ≤ i ≤ m) can be equal to any q_j (with 1 ≤ j ≤ n), as there would otherwise be a smaller integer factorizable in two ways (by removing prime factors common in both products) violating our assumption. We can now assume without loss of generality that p₁ is a prime factor smaller than any q_j (with 1 ≤ j ≤ n). Take q₁. Then there exist integers d and r such that :q₁/p₁ = d + r/p₁ and 0 < r < p₁ < q₁ (r can't be 0, as that would make q₁ a multiple of p₁ and not prime). We now get :p₂ ... pm = (d + r/p₁) q₂ ... qn = dq₂ ... qn + rq₂ ... qn/p₁. The second term in the last expression must be equal to an integer we call k, i.e. :k = rq₂ ... qn/p₁. This gives us :p₁k = rq₂ ... qn. The value of both sides of this equation is obviously smaller than s, but is still large enough to be factorizable. Since r is smaller than p₁, the two prime factorizations we get on each side after both k and r are written out as their product of primes must be different. This is in contradiction with s being the smallest integer factorizable in more than one way. Thus the original assumption must be false.
See also

- Prime factorization algorithm
- Integer factorization
- Prime signature
- Fundamental Theorem of Algebra
References

- Baker, Alan (1984). A Concise Introduction to the Theory of Numbers. Cambridge: Cambridge University Press. ISBN 0521286549
External links

- [http://www.cut-the-knot.org/blue/gcd_fta.shtml GCD and the Fundamental Theorem of Arithmetic] at cut-the-knot
- [http://planetmath.org/encyclopedia/ProofOfFundamentalTheoremOfArithmetic.html PlanetMath: Proof of fundamental theorem of arithmetic]
- [http://fermatslasttheorem.blogspot.com/2005/06/unique-factorization.html Fermat's Last Theorem Blog: Unique Factorization], A blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles. Category:Number theory Category:Mathematical theorems ko:정수론의 기본 정리 th:ทฤษฎีบทมูลฐานของเลขคณิต

Perfect number

In mathematics, a perfect number is defined as an integer which is the sum of its proper positive divisors, excluding itself. Six (6) is the first perfect number, because 1, 2 and 3 are its proper positive divisors and 1 + 2 + 3 = 6. The next perfect number is 28 = 1 + 2 + 4 + 7 + 14. The next perfect numbers are 496 and 8128 . These first four perfect numbers were the only ones known to the ancient Greeks.

Even perfect numbers

Euclid discovered that the first four perfect numbers are generated by the formula 2ⁿ⁻¹(2ⁿ − 1): :for n = 2: 2¹(2² − 1) = 6 :for n = 3: 2²(2³ − 1) = 28 :for n = 5: 2⁴(2⁵ − 1) = 496 :for n = 7: 2⁶(2⁷ − 1) = 8128 Noticing that 2ⁿ − 1 is a prime number in each instance, Euclid proved that the formula 2ⁿ⁻¹(2ⁿ − 1) gives an even perfect number whenever 2ⁿ − 1 is prime. Ancient mathematicians made many assumptions about perfect numbers based on the four they knew. Most of the assumptions were wrong. One of these assumptions was that since 2, 3, 5, and 7 are precisely the first four primes, the fifth perfect number would be obtained when n = 11, the fifth prime. However, 2¹¹ − 1 = 2047 = 23 · 89 is not prime and therefore n = 11 does not yield a perfect number. Two other wrong assumptions were:
- The fifth perfect number would have five digits since the first four had 1, 2, 3, and 4 digits respectively.
- The perfect numbers would alternately end in 6 or 8. The fifth perfect number (

33550336=2^(2^-1)

) has 8 digits, thus debunking the first assumption. For the second assumption, the fifth perfect number indeed ends with a 6. However, the sixth (8 589 869 056) also ends in a 6. It has been shown that the last digit of any even perfect number must be 6 or 8. In order for

2^n-1

to be prime, it is necessary that

n

should be prime. Prime numbers of the form 2ⁿ − 1 are known as Mersenne primes, after the seventeenth-century monk Marin Mersenne, who studied number theory and perfect numbers. Two millennia after Euclid, Euler proved that the formula 2ⁿ⁻¹(2ⁿ − 1) will yield all the even perfect numbers. Thus, every Mersenne prime will yield a distinct even perfect number—there is a concrete one-to-one association between even perfect numbers and Mersenne primes. This result is often referred to as the "Euclid-Euler Theorem." Only finitely many Mersenne primes are presently known, and it is unknown whether there are infinitely many of them. Thus it also remains uncertain whether there are infinitely many even perfect numbers. Every even perfect number is a triangular number. Since any even perfect number has the form 2ⁿ⁻¹(2ⁿ − 1), it is the sum of all natural numbers up to 2ⁿ − 1. This follows from the general formula stating that the sum of the first m positive integers equals (m² + m)/2. Furthermore, any even perfect number except the first one is the sum of the first 2^(n−1)/2 odd cubes: :

6 = 2^1(2^2-1) = 1+2+3, \,

28 = 2^2(2^3-1) = 1+2+3+4+5+6+7 = 1^3+3^3, \,

496 = 2^4(2^5-1) = 1+2+3+\cdots+29+30+31 = 1^3+3^3+5^3+7^3, \,

8128 = 2^6(2^7-1) = 1+2+3+\cdots+125+126+127 = 1^3+3^3+5^3+7^3+9^3+11^3+13^3+15^3. \,

Another interesting fact is that the reciprocals of the factors of a perfect number add up to 2:
- For 6, we have

1/6 + 1/3 + 1/2+ 1/1 = 2

;
- For 28, we have

1/28 + 1/14 + 1/7 + 1/4 + 1/2 + 1/1 = 2

, etc.

Odd perfect numbers

It is unknown whether there are any odd perfect numbers. Various results have been obtained, but none that have helped to locate one or otherwise resolve the question of their existence. Recently, Carl Pomerance and Joshua Zelinsky have both presented heuristics which strongly suggest that no odd perfect numbers exist. Any odd perfect number N must satisfy the following conditions:
- N is of the form ::

N=q^ p_1^ \ldots p_k^,

:where q, p₁, …, p_k are distinct primes and