Divisibility

from Wikipedia, the free encyclopedia

Divisibility is a mathematical relationship between two whole numbers . A whole number can be divided by another whole number if there is no remainder left after division , ie if the “divided calculation works”.

For example, the number 8 is divisible by 4, since 8: 4 is exactly 2; 4, but also 2, is a divisor of 8. In contrast, the number 9 cannot be divided by 4, because 4 “goes” twice into 9, but a remainder of 1 remains.

The number 11 has only two factors: 1 and the number 11 itself. Such numbers are called prime numbers . The number 12, on the other hand, has many factors: 1, 2, 3, 4, 6 and 12. Such numbers are called highly composite numbers .

The function that assigns the number of its divisors to a natural number is a number-theoretic function (the number-of-divisors function ). In elementary number theory , the term divisibility is limited to natural numbers .

In algebra , however, the term divisibility on integrity rings , commutative rings and non-commutative rings extended.

Formal definition

An integer divides an integer if and only if there is an integer for which is. One then says " is a divisor of ", " divides ", " is divisible by ", or " is a multiple of " and writes formally:

.

For the opposite, if there is no integer for which is, one writes:

.

Especially for prime powers there is the following way of speaking: divides the whole number exactly , written

if the greatest power of the prime number is, the shares in formulas  ; Example: The exact divisibility of by having the coprimality of and result in formulas: The latter definition goes beyond prime powers; Example:

Inferences

Since applies to all , there is no divisor of and of any other number, i.e. for each

If you write the same fact in the form , you can see that every number is a divisor of .

This is the neutral element of multiplication; H. multiplication by does not change an output value. There is a multiplicative inverse to the elements , namely an element with . Such elements are called units of the ring. Units are trivial divisors of any whole number. The units of the ring of whole numbers are even the numbers . (The units of a ring form a multiplicative group .)

It applies and . If none of the trivial factors is a nontrivial factor or a real factor of . An integer that is not a unit and that only has the trivial divisors is called a prime element and, if it is, a prime number . If a prime number, then it is called a prime divisor or prime factor of .

The set of all divisors of a natural number is called the “ divisor of ”. The quasi-order of divisibility induces the structure of an association on it , which is why one speaks of the " divider association of ".

The set of all multiples of a natural number is called a multiple set . In the case of whole numbers , the power of this set is countably infinite .

Properties of divisibility

  • Every number has at least its trivial divisors, in particular the units are divisors of every whole number.
  • Every integer is a (trivial) factor of .
  • Every whole number divides itself ( reflexivity of the quasi-order ).
  • The smallest positive divisor of an integer is a prime divisor.

Be , , and whole numbers.

  • If so also applies and . When examining the concept of divisibility, one can restrict oneself to natural numbers.
  • If and , it follows ( transitivity of the quasi-order).
  • For the following applies: .
  • If and so also applies .
  • If and , then also applies to all whole numbers and .
  • Applies and so is or .

The natural numbers are the divisibility a quasi minor amount, even a complete distributive lattice whose links by LCM and GCD are given. The smallest element is the ( shares each other), the largest is the ( shared by each other).

Divisibility rules in the decimal system

Powers of two

  • A number is divisible by 2 if and only if its last digit is even (0, 2, 4, 6 or 8).
  • A number is divisible by 4 if and only if the number formed from its last two digits is divisible by 4.
  • A number is divisible by 8 if and only if the number that is formed from its last three digits is divisible by 8.
  • In general, a number is divisible by if and only if the number that is formed from its last digits is divisible by .

Powers of five

  • A number is divisible by 5 if and only if its last digit is divisible by 5 (0 or 5).
  • A number is divisible by 25 if and only if the number formed from its last two digits is divisible by 25 (00, 25, 50 or 75).
  • A number is divisible by 125 if and only if the number formed from its last three digits is divisible by 125.
  • In general, a number is divisible by if and only if the number that is formed from its last digits is divisible by .

Powers of ten

  • A number is divisible by 10 if and only if its last digit is a 0.
  • A number is divisible by 100 if and only if the number ends with 00.
  • A number is divisible by 1000 if and only if the number ends with 000.
  • In general, a number is divisible by exactly if its last digits are 0 each.

Products from two and five potencies

  • A number can be divided by 20 if and only if its penultimate digit is even (0, 2, 4, 6 or 8) and its last digit is 0.
  • A number is divisible by 40 if the number that is formed from the third from last and penultimate digits is divisible by 4 and the last digit is 0.
  • A number is divisible by 50 if and only if the number ends in 00 or 50.
  • In general, a number is divisible by if and only if the number that is formed from its last digits is divisible by .

Divisibility rules based on checksums

If you want to set up a divisibility rule with checksums for a number , you look for a multiple that is either or for any . In the first case, the divisibility can be checked with the non-alternating checksum, in the second case with the alternating checksum.

Corresponding factors exist for all numbers that are prime with 10 . However, the test is sometimes impractical for relatively small numbers (see for example the rules below for divisibility by 17 and 19).

Divisibility rules based on non-alternating checksums

If it is a multiple of the number under consideration, the rule of divisibility applies: "A number is divisible by if and only if its non-alternating checksum is divisible by ."

For example, it is a multiple of 3, so that divisibility by 3 can be checked using the (1's) checksum.

  • A number is divisible by 3 if and only if its sum is divisible by 3.
  • A number is divisible by 6 if and only if it is divisible by 2 and 3.
  • A number is divisible by 9 if and only if its checksum is divisible by 9.
  • A number is divisible by 11 if and only if its non-alternating 2-digit sum is divisible by 11. There is also a divisibility rule with the alternating checksum (see below).
  • A number is divisible by 21 if and only if its non-alternating 6-digit sum is divisible by 21.
  • A number is divisible by 27 if and only if its non-alternating 3-digit sum is divisible by 27.
  • A number is divisible by 33 if and only if its non-alternating 2-digit sum is divisible by 33.
  • A number is divisible by 37 if and only if its non-alternating 3-digit sum is divisible by 37.
  • A number is divisible by 41 if and only if its non-alternating 5 digits sum is divisible by 41.
  • A number is divisible by 99 if and only if its non-alternating 2-digit sum is divisible by 99.
  • A number is divisible by 111 if and only if its non-alternating 3-digit sum is divisible by 111.
  • A number is divisible by 333 if and only if its non-alternating 3-digit sum is divisible by 333.
  • A number is divisible by 999 if and only if its non-alternating 3-digit sum is divisible by 999.
  • In general, a number is divisible by if and only if its non-alternating checksum is divisible by .
  • In general, a number is divisible by ( repunit number ) if and only if its non-alternating checksum is divisible by .

The checksum does not have to be calculated in full; it is sufficient to consider the remainder of a digit (or group of digits) when dividing by . After each addition, the remainder can also be calculated when dividing by . To z. B. to determine whether 7654 is divisible by 3, one can calculate:

  • Digit 7: remainder when dividing by 3 is 1: sum 1 (checksum )
  • Digit 6: Remainder when dividing by 3 is 0: Sum 1 does not change (checksum )
  • Digit 5: this time without determining the remainder: Sum 1 + 5 = 6, remainder when dividing by 3 is 0 (checksum )
  • Digit 4: Sum 0 + 4 = 4, remainder when dividing by 3 is 1 (checksum )

Since the remainder calculated in the last step is not zero, 7654 is not divisible by 3.

Divisibility rules based on alternating checksums

On the other hand, if it is a multiple of the number under consideration , then the rule of divisibility applies: "A number is divisible by if and only if its alternating checksum is divisible by ."

For example, if you look at the number 7, you can see by trial and error that . This then results in the divisibility rule with an alternating 3-digit sum.

  • A number is divisible by 7 if and only if its alternating 3-digit sum is divisible by 7.
  • A number is divisible by 11 if and only if its alternating checksum is divisible by 11. There is also a divisibility rule with the non-alternating 2's checksum (see above).
  • A number is divisible by 13 if and only if its alternating 3-digit sum is divisible by 13.
  • A number is divisible by 17 if and only if its alternating digit is divisible by 17.
  • A number is divisible by 19 if and only if its alternating 9 digits are divisible by 19.
  • A number is divisible by 23 if and only if its alternating 11 digits are divisible by 23.
  • A number is divisible by 73 if and only if its alternating four-digit sum is divisible by 73.
  • A number is divisible by 77 if and only if its alternating 3-digit sum is divisible by 77.
  • A number is divisible by 91 if and only if its alternating 3-digit sum is divisible by 91.
  • A number is divisible by 101 if and only if its alternating 2's checksum is divisible by 101.
  • A number is divisible by 137 if and only if its alternating four-digit sum is divisible by 137.
  • A number is divisible by 143 if and only if its alternating 3-digit sum is divisible by 143.
  • A number is divisible by 1001 if and only if its alternating 3-digit sum is divisible by 1001.
  • In general, a number is divisible by if and only if its alternating checksum is divisible by .

Divisible by 7

In addition to the already mentioned divisibility rule using the alternating 3-digit checksum, there are other, partly simpler, divisibility rules for the 7. These result from considering multiples of the number that are close to powers of 10, for example in the next example . You subtract 98 repeatedly, reducing the hundreds by 1, but increasing the ones by two ( ). In the Babylonian Talmud there is the rule of divisibility, in which one ultimately only has to check whether a two-digit number is divisible by 7, in the following form: A number is split into two parts in the penultimate position. The digits before the penultimate digit form the number and the last two digits form the number . For example, 3815 is broken down into the numbers and . Now add one and double that. If the sum is divisible by 7, the original number is also divisible by 7. For 3815 you get this . Since 91 is divisible by 7, 3815 is also divisible by 7. With very large numbers you can repeat this process until you get a two-digit number at some point. To show the validity of the divisibility rule, consider the equation

Since 98 is divisible by 7, it is divisible by 7 if and only is divisible by 7.

For another divisibility rule, you split a number into its last digit and the rest . For example 3815 in the numbers and . Then the following theorem applies:

A number is divisible by 7 if and only if its double is divisible by 7, which is why you only have to check the divisibility of .

So for 3815 you have to check whether is divisible by 7. To do this, 371 can be broken down into 37 and 1 again. Since it is divisible by 7, 371 and 3815 are also divisible by 7. The reason for this method is that 21 is divisible by 7 and in order to bring the ones at the end of the number to 0, two tens must be subtracted for each one. Then you divide the resulting number by ten. If the number is divisible by 21, the remainder in this method is 0.

You can also split a number before the third to last digit so that the last three digits form the number and the digits in front of it form the number . Then you subtract from and check whether this difference is divisible by 7. There

and is divisible by 7 is divisible by 7 if and only if is divisible by 7.

Divisible by 17

One method to determine divisibility by 17 is based on the identity 17 · 6 = 102. Therefore, the following applies

You split the number to be checked into two parts before the penultimate digit, take twice the left part and subtract the right part (or vice versa). If the result is divisible by, this also applies to .

Example: . So what is divisible by 17.

Divisible by 19

To check whether it is divisible by 19, you split a number into its last digit and the remainder . For example 7904 in the numbers and . Then the following theorem applies:

A number is divisible by 19 if and only if it is divisible by 19.

For 7904 you have to check whether it is divisible by 19. To do this, you can split 798 into 79 and 8 again. Since it is divisible by 19, 798 and 7904 are also divisible by 19.

Divisibility rules for any number

To check the divisibility by any number, one uses its prime factorization . One then checks the divisibility by the individual prime powers of this decomposition.

For example, a number is divisible by exactly if it is divisible by and 3. This means that your last two digits must be 00, 25, 50 or 75 and the checksum must be divisible by three. In multiplicative composite numbers, the divisibility of an arbitrary portion factor is sufficient, so is, for example, by divisible, in which case the divisibility of the three factors is 4-cyclically in n.

Also compare divisibility for all of 10 relatively prime divisors .

Divisibility rules in any number systems

In a number system for the base , divisibility rules for factors can be found, which can be broken down into a prime factorization as small as possible numbers that are divisors of , or . should be as small as possible , only values ​​up to a maximum of 4 are useful for mental arithmetic .

: Divisor 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 21, 31, 32, 33, 63, 64, 65, ...
: Divisor 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 16, 20, 26, 27, 28, 40, 41, 80, 81, 82, ...
: please refer
: Divisor 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 18, 24, 25, 26, 31, 39, 62, 63, 78, 124, 125, 126, 156, 312, 313, 624, 625, 626, ...

The following divisibility rules use different place value systems :

  • A number is divisible by a number of the form if and only if the cross sum is divisible by in the representation for the base . The representation of the base results easily from the representation of the number in the dual system . To do this, the number is divided into groups of digits starting on the right ; the decimal value of the individual groups now corresponds to the values ​​of the digits in the representation for the base . For example, by divisible because in octal (base ) the checksum does.
  • A number is divisible by 27 if and only if its cross sum to base 1000 is divisible by 27. This checksum can be obtained by dividing its decimal representation into blocks of three starting on the right and adding the sum of these blocks.
  • A number is divisible by if and only if its representation as a basic number ends with a 0.

Further divisibility properties can be found in the article Congruence (number theory) .

Generalization of the concept of divisibility

Commutative rings

The concept of divisibility is also considered much more generally in commutative rings . The definition of divisibility in natural and whole numbers is adopted here directly:

It is a commutative ring. Are ring members, then divides , if another ring element with exists.

In rings shares if and only if the of produced principal ideal that of comprises generated formal: .

A simple example from the whole numbers: The main ideal generated by is the set of all multiples of , accordingly the set of all multiples of . , so is a divisor of .

The most fruitful divisibility properties are obtained in integrity rings , which are commutative unitary rings with zero divisors .

Non-commutative rings

In the case of non-commutative rings , you have to specify the side (left, right or two-sided) for the divisor and multiple property. This can no longer be expressed with the simple divisibility symbol “ ” (whose symmetrical shape already stands in the way of a reflection with inverse meaning) of the commutative case.

The left divisor of two elements is called , if one exists with . Then is also a right multiple of . This divisibility corresponds to the inclusion of legal ideals . Correspondingly, one defines right divisor , left multiple and, if valid for left and right, also two-sided divisor , two-sided multiple .

body

In structures in which a general division as the reverse of the multiplication is also possible ( bodies and skew bodies ), such as in real numbers , the theory of divisibility is trivial: every number (or every body element) is by every other number except divisible, d. H. also: all elements different from 0 are units .

See also

swell

Web links

Wiktionary: Divisibility  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. Explanation of series A274469 in OEIS
  2. Babylonian Talmud, Aboda Sara 9b. Cf. Benedict Zuckermann: The mathematical in the Talmud. Illumination and explanation of the Talmudic passages with mathematical content. Breslau 1878. (Annual report of the Jewish-theological seminar “Fraenckel'scher Foundation”.), Pp. 62–63.
  3. See Leonard E. Dickson : History of the Theory of Numbers. Volume I: Divisibility and Primality. Dover Publications, ISBN 978-0-486-44232-7 , p. 337.
  4. ^ Siegfried Moser: Playing with numbers. Humboldt-Taschenbuchverlag, Munich 1992.
  5. Proof of divisibility by 19