Checksum

The checksum (or digit sum ) is usually the sum of the digit values ​​of a natural number . For a number n = 36036 the decimal checksum q ( n ) = 3 + 6 + 0 + 3 + 6 = 18. The checksum (like the cross product ) depends on the number system used .

In addition to the checksum as the sum of the numerical values, there is

• the alternating checksum (alternating addition and subtraction of the digit values),
• Operations with digit pairs, triples, etc.,
• locally weighted procedures.

Definitions

Definition by the sum of the digit values

If the natural number becomes the base with as ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle b\geq 2}$

${\displaystyle n=\sum _{i=0}^{k-1}a_{i}\cdot b^{i}=a_{0}\cdot b^{0}+a_{1}\cdot b^{1}+a_{2}\cdot b^{2}+\dotsb +a_{k-1}\cdot b^{k-1}}$

represented ( -adic representation with the numerical values and ), then is the sum of their numerical values ${\displaystyle b}$ ${\displaystyle a_{i}\in \mathbb {N} _{0}}$ ${\displaystyle 0\leq a_{i}\leq b-1}$

${\displaystyle q_{b}(n)=\sum _{i=0}^{k-1}a_{i}=a_{0}+a_{1}+a_{2}+\dotsb +a_{k-1}}$

the checksum of . Alternatively, the checksum can also be saved as ${\displaystyle q_{b}}$ ${\displaystyle n}$

${\displaystyle q_{b}(n)=\sum _{i=0}^{k-1}{\frac {1}{b^{i}}}\underbrace {(n{\bmod {b}}^{i+1}-n{\bmod {b}}^{i})} _{=b^{i}\cdot a_{i}}}$

can be specified. It is

${\displaystyle k={\begin{cases}1,&{\text{wenn }}n=0,\\\lfloor \log _{b}{n}\rfloor +1,&{\text{wenn }}n\geq 1,\end{cases}}}$

the number of digits from . ${\displaystyle n}$

Note: Here are the mathematical modulo function and the Gaussian bracket . ${\displaystyle \operatorname {mod} }$ ${\displaystyle \lfloor \cdot \rfloor }$

Recursive definition

The recursive definition of the cross sum of the natural number to the base with is: ${\displaystyle q_{b}(n)}$ ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle b\geq 2}$

${\displaystyle q_{b}(n)={\begin{cases}n,&{\text{wenn }}0\leq n\leq b-1,\\n{\bmod {b}}+q_{b}\left(\left\lfloor {\frac {n}{b}}\right\rfloor \right),&{\text{wenn }}n\geq b.\end{cases}}}$

Graph course

Function graph of the checksums of the first 10 000 natural numbers in the decimal system

The graph of the checksum function has a characteristic curve. In the decimal system , it rises steadily for ten consecutive numbers ending with 0 to 9 - by 1 per step - and then falls for one number. However, the lowest and highest values ​​of the increase range shift from time to time by 1 upwards. ${\displaystyle q(n)}$ ${\displaystyle n}$

This behavior is repeated in every power of ten. At 10, 100, 1000 etc. it always falls to 1. This results in a self-similarity of the graph. ${\displaystyle q(n)}$

Only applies to , is for all larger numbers . There is no upper limit. ${\displaystyle n=0}$ ${\displaystyle q(n)=0}$ ${\displaystyle q(n)\geq 1}$ ${\displaystyle q(n)}$

application

Every time numbers are entered and transmitted, technical or human errors can occur. This is why test procedures exist to ensure data integrity. A simple checksum measure is the formation of the checksum .

Check digit of the ISBN

The cross sum of an ISBN -10 (outdated version) weighted with the factors (10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ) is always 0 modulo 11 (the number “X” has the numerical value of 10 and can appear in the last digit). This is achieved by the first 9 digits describing the product and adding a tenth digit (check digit) so that the above requirement is met.

Example: For the ISBN 3-442-54210-3 is

${\displaystyle 3\cdot 1+4\cdot 2+4\cdot 3+2\cdot 4+5\cdot 5+4\cdot 6+2\cdot 7+1\cdot 8+0\cdot 9+3\cdot 10=132}$

${\displaystyle 132{\bmod {1}}1=0}$

So this is a (formally) valid ISBN.

Checksum set

• Given the following:
  • a place value system with the base (where ), ${\displaystyle b=n+1}$ ${\displaystyle n\in \mathbb {N} }$
  • a divisor of (where ), ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle t\in \mathbb {N} }$
  • a natural number . ${\displaystyle a}$
• Then:
  • The number is divisible by exactly if its checksum (in this place value system) is divisible by . ${\displaystyle a}$ ${\displaystyle t}$ ${\displaystyle t}$

For example, in the decimal system, the base is 10, so . So is . Hence, the checksum rule can be used to check divisibility by 3 and by 9. ${\displaystyle n=9}$ ${\displaystyle t\in \{1,3,9\}}$

In the hexadecimal system is . So is . So you can use the checksum rule in the hexadecimal system to check divisibility by 3, by 5 and by 15. ${\displaystyle n=15}$ ${\displaystyle t\in \{1,3,5,15\}}$

In general, the cross sum of the representation of a number in the place value system with the base leaves the remainder modulo unchanged, i.e. ${\displaystyle q_{b}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (b-1)}$

${\displaystyle q_{b}(a)\equiv a{\pmod {b-1}}}$,

and the alternating checksum of the representation of a number in the place value system with the base leaves the remainder modulo unchanged, i.e. ${\displaystyle {\mathit {aqs}}_{b}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (b+1)}$

${\displaystyle {\mathit {aqs}}_{b}(a)\equiv a{\pmod {b+1}}}$.

Special case: trial of nine

→ Main article : Trial of nine

For the divisibility of a number by 3 or 9 , its checksum can be used as a representative: A number represented in decimal is divisible by 3 or 9 if its checksum is divisible by 3 or 9 without a remainder. In general, when dividing by 3 or 9, the remainder is the same as the checksum : ${\displaystyle n}$ ${\displaystyle q(n)}$ ${\displaystyle n}$ ${\displaystyle q(n)}$

${\displaystyle n\equiv q(n){\pmod {3}}}$ or. ${\displaystyle n\equiv q(n){\pmod {9}}}$

(Or to put it another way: the difference between a number and its checksum is always divisible by 9.)

More types

Single digit (or iterated) checksum

The cross-sum is formed from the simple cross-sum until only a single-digit number remains.

Example:

${\displaystyle q(93)=9+3=12;\quad q(12)=1+2=3}$

If the cross sum of a number k is a multi-digit number, the process can be repeated until the result only has one place in the respective number system . For the iterated checksums generated in this way (always one-digit), the following applies ( t , as above, is again the basis of the number system - 1): ${\displaystyle \operatorname {qs} (k,t)}$

${\displaystyle \operatorname {qs} (k,t)={\begin{cases}0,&{\text{wenn }}k=0,\\t,&{\text{wenn }}k{\bmod {t}}=0{\text{ und }}k\neq 0,\\k{\bmod {t}},&{\text{wenn }}k{\bmod {t}}\neq 0.\end{cases}}}$

Example in the decimal system:

${\displaystyle \operatorname {qs} (4582,9)=\operatorname {qs} (4+5+8+2,9)=\operatorname {qs} (19,9)=\operatorname {qs} (1+9,9)=\operatorname {qs} (10,9)=1}$,

and it is

${\displaystyle 4582{\bmod {9}}=1}$.

In particular, a positive natural number is divisible by 9 if and only if its iterated checksum in the decimal system is 9.

See also: hash function and the procedures mentioned there.

Alternating checksum

The alternating cross sum (also known as cross difference, pair cross sum or alternating sum) is obtained by alternately subtracting and adding the digits of a number. You can start on the left or right. The following starts from the right. So for the number n = 36036 the alternating checksum aqs ( n ) = 6 - 3 + 0 - 6 + 3 = 0.

The following procedure is equivalent to this (counting the digits should start again on the right):

1. Add to the value of the first digit that of the third, fifth, seventh, etc.
2. Add the fourth, sixth, eighth, etc. to the second digit.
3. If you now subtract the second from the first sum, you get the alternating cross sum.

For the divisibility of a number n by 11 , its alternating checksum aqs ( n ) can be used as a representative: A decimal number n is divisible by 11 if and only if its alternating checksum aqs ( n ) is divisible by 11 without a remainder.

Repeated use of the alternating checksum yields the remainder of the number when dividing by 11, with negative values ​​being normalized by adding 11. An aqs of 11 results in another formation of an aqs, which returns 0 (i.e. the remainder of the division of 11 by 11).

Example:

n = 2536874
4 + 8 + 3 + 2 = 17
7 + 6 + 5     = 18

17 - 18 = -1; -1 + 11 = 10

From this follows: The number 2536874 leaves the remainder 10 when divided by 11, so it is not divisible by 11.

Non-alternating k- sum

The non-alternating 2- digit sum of n = 36036 is q = 3 + 60 + 36 = 99. For all divisors of 99, i.e. for 3, 9, 11, 33 and 99, it is a divisibility criterion: The non-alternating 2-digit sum q one decimal number n is divisible by these numbers if and only if n is divisible by them.

The non-alternating 3- digit sum of n = 36036 is q = 36 + 036 = 72. For all factors of 999, i.e. for 3, 9, 27, 37, 111, 333 and 999, it is a divisibility criterion: The non-alternating 3-digit sum q of a decimal number n is divisible by these numbers if and only if n is divisible by them.

Note : The non-alternating k- sum is identical to the non-alternating sum of the base . It provides a divisibility criterion for all factors of . ${\displaystyle 10^{k}}$ ${\displaystyle 10^{k}-1}$

Alternating k sum of digits

The alternating double checksum of n = 36036 is q = 3 - 60 + 36 = −21. For 101 it is a divisibility criterion: The alternating 2's checksum q of a decimal number n is divisible by 101 if and only if n is divisible by 101.

The alternating 3- digit checksum of n = 36036 is q = −36 + 036 = 0. For all divisors of 1001, i.e. for 7, 11, 13, 77, 91, 143 and 1001, it is a divisibility criterion: The alternating 3-digit Check sum q of a decimal number n is divisible by these numbers if and only if n is divisible by the numbers.

Note : The alternating k- sum is identical to the alternating sum to the base . It provides a divisibility criterion for all factors of . ${\displaystyle 10^{k}}$ ${\displaystyle 10^{k}+1}$

Weighted checksum

Weighted checksums are a generalization , in which the digits are first multiplied by the values ​​of a number sequence and these results are then added. It begins with the least significant digit (the order does not matter with the simple checksum). The weighting sequence can be periodic or non-periodic. An example is the periodic sequence 1, 3, 2, −1, −3, −2, ... The weighted cross sum of the number 422625 is (starting with the lowest digit):

5 1 + 2 3 + 6 2 - 2 1 - 2 3 - 4 2 = 5 + 6 + 12 - 2 - 6 - 8 = 7

The cross sum weighted in this way provides a divisibility rule for the number 7. Such periodic sequences can also be found for other natural numbers, e.g. B.

• for 11 the sequence +1, −1, ... This supplies the so-called alternating checksum
• for 13 the sequence 1, −3, −4, −1, 3, 4, ...

For most dividers, however, it is not practical to check the divisibility by means of checksums, because there are only a few easily noticeable periodic weighting sequences.

If one wants to find a corresponding rule of divisibility for the natural number m , one considers the remainder of the powers of 10 when dividing by m . The remnants correspond to the weights sought.

Example: m = 7

1 ≡ 1 (mod 7)

10 ≡ 3 (mod 7)

100 ≡ 2 (mod 7)

1000 ≡ −1 (mod 7)

10000 ≡ −3 (mod 7)

100000 ≡ −2 (mod 7)

1000000 ≡ 1 (mod 7) (from here the remainders are repeated)

The weighting sequence is 1, 3, 2, −1, −3, −2, ...

See also

• Cross product

Web links

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

• Follow A007953 in OEIS

Individual evidence

1. ↑ Hans Schubart: Introduction to Classical and Modern Number Theory. Vieweg, Braunschweig 1974, ISBN 3-528-03313-4 , p. 47.
2. ↑ checksum. In: Herrmann Engesser (edit.): The small dictionary of mathematics. Bibliographisches Institut, Mannheim / Vienna / Zurich 1986, ISBN 3-411-02180-2 , p. 364.