Sign of Pascal

The Pascal sign is a mathematical method that allows you to get signs of divisibility by any number. A kind of "universal sign of divisibility."

Content

1 General view
2 Proof
3 Main special cases
- 3.1 The sign of divisibility by 2
- 3.2 Signs of divisibility into 3 and 9
- 3.3 Sign of divisibility by 4
- 3.4 The sign of divisibility by 5
- 3.5. Divisibility by 7
  - 3.5.1 Example
- 3.6 Sign of divisibility by 11
4 Literature

General view

Let there be a natural number $A$ ${\ displaystyle A}$ written in decimal notation as ${\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}$ ${\ displaystyle {\ overline {a_ {n} a_ {n-1} \ ldots a_ {2} a_ {1} a_ {0}}}}$ where $a_{0}$ ${\ displaystyle a_ {0}}$ - units $a_{1}$ ${\ displaystyle a_ {1}}$ - dozens, etc.

Let be $m$ ${\ displaystyle m}$ - an arbitrary natural number by which we want to divide and deduce the sign of divisibility into it.

We find a number of residues according to the following scheme:

r_{1}

{\ displaystyle r_ {1}}

- remainder of the division

10

{\ displaystyle 10}

on

m

{\ displaystyle m}

r_{2}

{\ displaystyle r_ {2}}

- remainder of the division

10\cdot r_{1}

{\ displaystyle 10 \ cdot r_ {1}}

on

m

{\ displaystyle m}

r_{3}

{\ displaystyle r_ {3}}

- remainder of the division

10\cdot r_{2}

{\ displaystyle 10 \ cdot r_ {2}}

on

m

{\ displaystyle m}

...

r_{n}

{\ displaystyle r_ {n}}

- remainder of the division

10\cdot r_{n-1}

{\ displaystyle 10 \ cdot r_ {n-1}}

on

m

{\ displaystyle m}

.

Formally:

r_{1}\equiv 10{\pmod {m}}

{\ displaystyle r_ {1} \ equiv 10 {\ pmod {m}}}

r_{i}\equiv 10\cdot r_{i-1}{\pmod {m}},\;i={\overline {2...n}}

{\ displaystyle r_ {i} \ equiv 10 \ cdot r_ {i-1} {\ pmod {m}}, \; i = {\ overline {2 ... n}}}

Since there are a finite number of residues (namely $m$ ${\ displaystyle m}$ ), then this process will loop (no later than through $m$ ${\ displaystyle m}$ steps) and then you can not continue it: Starting with some $i=i_{0}:~r_{i+p}=r_{i}$ ${\ displaystyle i = i_ {0}: ~ r_ {i + p} = r_ {i}}$ where $p$ ${\ displaystyle p}$ - the resulting period of the sequence $\{r_{i}\}$ ${\ displaystyle \ {r_ {i} \}}$ . For uniformity, we can assume that $r_{0}=1$ ${\ displaystyle r_ {0} = 1}$ .

Then $A$ ${\ displaystyle A}$ has the same remainder divided by $m$ ${\ displaystyle m}$ as the number

$r_{n}\cdot a_{n}+\ldots +r_{2}\cdot a_{2}+r_{1}\cdot a_{1}+a_{0}$ ${\ displaystyle r_ {n} \ cdot a_ {n} + \ ldots + r_ {2} \ cdot a_ {2} + r_ {1} \ cdot a_ {1} + a_ {0}}$ .

Proof

Using the fact that in an algebraic expression modulo $m$ ${\ displaystyle m}$ you can replace the numbers with their remainders from dividing by $m$ ${\ displaystyle m}$ we get:

$A{\pmod {m}}=({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}){\pmod {m}}=({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}}}\cdot 10+a_{0}){\pmod {m}}$ ${\ displaystyle A {\ pmod {m}} = ({\ overline {a_ {n} a_ {n-1} \ ldots a_ {2} a_ {1} a_ {0}}}) {\ pmod {m} } = ({\ overline {a_ {n} a_ {n-1} \ ldots a_ {2} a_ {1}}} \ cdot 10 + a_ {0}) {\ pmod {m}}}$ $=({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}}}\cdot r_{1}+a_{0}r_{0}){\pmod {m}}$ ${\ displaystyle = ({\ overline {a_ {n} a_ {n-1} \ ldots a_ {2} a_ {1}}} \ cdot r_ {1} + a_ {0} r_ {0}) {\ pmod {m}}}$ $=(({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10+a_{1})\cdot r_{1}+a_{0}r_{0}){\pmod {m}}$ ${\ displaystyle = (({\ overline {a_ {n} a_ {n-1} \ ldots a_ {2}}} \ cdot 10 + a_ {1}) \ cdot r_ {1} + a_ {0} r_ { 0}) {\ pmod {m}}}$ $=({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10r_{1}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}$ ${\ displaystyle = ({\ overline {a_ {n} a_ {n-1} \ ldots a_ {2}}} \ cdot 10r_ {1} + a_ {1} r_ {1} + a_ {0} r_ {0 }) {\ pmod {m}}}$ $=({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot r_{2}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}=\ldots =$ ${\ displaystyle = ({\ overline {a_ {n} a_ {n-1} \ ldots a_ {2}}} \ cdot r_ {2} + a_ {1} r_ {1} + a_ {0} r_ {0 }) {\ pmod {m}} = \ ldots =}$ $(a_{n}r_{n}+\ldots +a_{2}r_{2}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}$ ${\ displaystyle (a_ {n} r_ {n} + \ ldots + a_ {2} r_ {2} + a_ {1} r_ {1} + a_ {0} r_ {0}) {\ pmod {m}} }$

Main special cases

Sign of divisibility by 2

Here $m=2$ ${\ displaystyle m = 2}$ . As $10~\vdots ~2$ ${\ displaystyle 10 ~ \ vdots ~ 2}$ then $r_{0}=1,~r_{i}=0,~i\in \mathbb {N}$ ${\ displaystyle r_ {0} = 1, ~ r_ {i} = 0, ~ i \ in \ mathbb {N}}$ . From here we get the well-known sign: the remainder of dividing the number by 2 is equal to the remainder of dividing its last digit by 2 , or usually: the number is divided by 2 if its last digit is even .

Signs of divisibility by 3 and 9

Here $m=3$ ${\ displaystyle m = 3}$ or $m=9$ ${\ displaystyle m = 9}$ . As $10^{i}\equiv 1{\pmod {3}},i\in \mathbb {N}$ ${\ displaystyle 10 ^ {i} \ equiv 1 {\ pmod {3}}, i \ in \ mathbb {N}}$ (the remainder of dividing 10 by 3 and by 9 is equal to 1 ), then all $r_{i}=1$ ${\ displaystyle r_ {i} = 1}$ . Therefore, the remainder of dividing the number by 3 (or 9) is equal to the remainder of dividing the sum of its numbers by 3 (respectively, 9) , or otherwise: the number is divided by 3 (or 9) if the sum of its numbers is divided by 3 (or 9) )

Sign of divisibility by 4

Here $m=4$ ${\ displaystyle m = 4}$ . We find the sequence of residues: $r_{0}=1,~r_{1}=2,~r_{i}=0,~i\in \mathbb {N}$ ${\ displaystyle r_ {0} = 1, ~ r_ {1} = 2, ~ r_ {i} = 0, ~ i \ in \ mathbb {N}}$ . From here we get the sign: the remainder of dividing the number by 4 is equal to the remainder of dividing $2\cdot a_{1}+a_{0}$ ${\ displaystyle 2 \ cdot a_ {1} + a_ {0}}$ by 4, or, noticing that the remainder depends only on the last 2 digits: the number is divided by 4 if the number consisting of its last 2 digits is divided by 4 .

Mark of Divisibility by 5

Here $m=5$ ${\ displaystyle m = 5}$ . As $10~\vdots ~5$ ${\ displaystyle 10 ~ \ vdots ~ 5}$ then $r_{0}=1,~r_{i}=0,~i\in \mathbb {N}$ ${\ displaystyle r_ {0} = 1, ~ r_ {i} = 0, ~ i \ in \ mathbb {N}}$ . From here we get the well-known sign: the remainder of dividing the number by 5 is equal to the remainder of dividing its last digit by 5 , or usually: the number is divided by 5 if its last digit is 0 or 5 .

Mark of Divisibility by 7

Here $m=7$ ${\ displaystyle m = 7}$ . Find the leftovers.

$10=1\cdot 7+3\Rightarrow r_{1}=3$ ${\ displaystyle 10 = 1 \ cdot 7 + 3 \ Rightarrow r_ {1} = 3}$
$10\cdot r_{1}=4\cdot 7+2\Rightarrow r_{2}=2$ ${\ displaystyle 10 \ cdot r_ {1} = 4 \ cdot 7 + 2 \ Rightarrow r_ {2} = 2}$
$10\cdot r_{2}=2\cdot 7+6\Rightarrow r_{3}=6$ ${\ displaystyle 10 \ cdot r_ {2} = 2 \ cdot 7 + 6 \ Rightarrow r_ {3} = 6}$
$10\cdot r_{3}=8\cdot 7+4\Rightarrow r_{4}=4$ ${\ displaystyle 10 \ cdot r_ {3} = 8 \ cdot 7 + 4 \ Rightarrow r_ {4} = 4}$
$10\cdot r_{4}=5\cdot 7+5\Rightarrow r_{5}=5$ ${\ displaystyle 10 \ cdot r_ {4} = 5 \ cdot 7 + 5 \ Rightarrow r_ {5} = 5}$
$10\cdot r_{5}=7\cdot 7+1\Rightarrow r_{6}=1=r_{0}$ ${\ displaystyle 10 \ cdot r_ {5} = 7 \ cdot 7 + 1 \ Rightarrow r_ {6} = 1 = r_ {0}}$ , the cycle is closed.

Therefore, for any number

A={\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}

{\ displaystyle A = {\ overline {a_ {n} a_ {n-1} \ ldots a_ {2} a_ {1} a_ {0}}}}

its remainder by dividing by 7 is equal to

a_{0}+3a_{1}+2a_{2}+6a_{3}+4a_{4}+5a_{5}+a_{6}+\ldots

{\ displaystyle a_ {0} + 3a_ {1} + 2a_ {2} + 6a_ {3} + 4a_ {4} + 5a_ {5} + a_ {6} + \ ldots}

.

Example

Consider the number 48916. As proved above,

48916\equiv 6+3\cdot 1+2\cdot 9+6\cdot 8+4\cdot 4=

{\ displaystyle 48916 \ equiv 6 + 3 \ cdot 1 + 2 \ cdot 9 + 6 \ cdot 8 + 4 \ cdot 4 =}

6+3+18+48+16=91\equiv 0{\pmod {7}}

{\ displaystyle 6 + 3 + 18 + 48 + 16 = 91 \ equiv 0 {\ pmod {7}}}

,

which means 48916 is divisible by 7.

Mark of Divisibility by 11

Here $m=11$ ${\ displaystyle m = 11}$ . As $10^{2n}=99\cdot 101\ldots 01+1\equiv 1{\pmod {11}}$ ${\ displaystyle 10 ^ {2n} = 99 \ cdot 101 \ ldots 01 + 1 \ equiv 1 {\ pmod {11}}}$ then all $r_{2i}=1$ ${\ displaystyle r_ {2i} = 1}$ , but $r_{2i-1}=10\equiv -1{\pmod {11}}$ ${\ displaystyle r_ {2i-1} = 10 \ equiv -1 {\ pmod {11}}}$ . From here you can get a simple sign of divisibility by 11:

the remainder of dividing the number by 11 is equal to the remainder of dividing its sum of digits, where each odd (starting from units) digit is taken with the “-” sign, by 11.

Simply put:

if you divide all the digits of a number into 2 groups - through one digit (all digits with odd positions will fall into one group, even digits into another), add all the digits in each group and subtract one received amount from another, then the remainder by dividing by 11 The result will be the same as the original number.

Literature

Vorobyov N. N. Signs of divisibility . - 4th ed. - M .: Nauka, 1988 .-- T. 39 .-- 94 p. - ( Popular lectures in mathematics ). - ISBN 5-02-013731-6 .

Sign of Pascal

Content

General view

Proof

Main special cases

Sign of divisibility by 2

Signs of divisibility by 3 and 9

Sign of divisibility by 4

Mark of Divisibility by 5

Mark of Divisibility by 7

Example

Mark of Divisibility by 11

Literature

More articles: