User:Joris.deguet/draft

From Wikipedia, the free encyclopedia

In the course of translation

Les rubans de Pascal correspondent à une technique servant à déterminer si un nombre entier N est divisible par un autre entier D en utilisant les chiffres de l'écriture de N dans une base B. Les fondements théoriques de cette méthode relèvent de la théorie de congruence. It is interesting to note that Blaise Pascal has proposed his methode long before congruence theory was established.

Pascal described this method in "De numeribus multiplicibus"^[1].

1 Tape construction
2 First Tapes with B=10
3 Tape usage to decide divisibility
4 Correctness of the divisibility criterion
5 Some properties of tapes
6 See also

[edit] Tape construction

In the following, N holds for the number we want to divide by a number D and B is the base in which N is written.

The principle behind tape is to identify remainers for every exponent of the base B in the division by D. For a radix of B=10 and to divide by D=7, this gives:

$100 = 0 * 7 + 1$
$101 = 1 * 7 + 3$
$102 = 14 * 7 + 2$
$103 = ? * 7 + 6$
$104 = ? * 7 + 4$
$105 = ? * 7 + 5$
$106 = ? * 7 + 1$
$107 = ? * 7 + 3$
$108 = ? * 7 + 2$
$109 = ? * 7 + 6$

This produces the tape 1,3,2,6,4,5,1,3,2,6 ... which looks periodic. This is the Pascal tape for the radix B and divider D. The tape will be used to determine if D divides N.

[edit] First Tapes with B=10

The first tapes for the base B=10 are:

0 ....
1,0 ...
1,1 ...
1,2,0 ...
1,0 ...
1,4,4 ...
1,3,2,6,4,5,1,3,2,6 ...
1,2,4,0 ...
1,1 ...

[edit] Tape usage to decide divisibility

L'utilisation d'un ruban de Pascal pour tester la divisibilité passe par la transformation du nombre fourni en un autre plus petit ayant le même reste dans la division par D.

En commençant par un exemple, on cherche a savoir si 123456789 est divisible par 3. Le ruban de Pascal de 3 est 1,1,1,1,1 ... Le nouveau nombre est donc 1*1 + 1*2 +1*3 +1*4 +1*5 + 1*6 + 1*7 + 1*8 + 1*9 = 1+2+3+4+5+6+7+8+9 = 45.

Est-ce que 123456789 est divisible par 7? Il faut commencer par aligner le nombre avec le ruban de 7 en commençant par la droite, pour cela on écrit 123456789 à l'envers:

9 8 7 6 5 4 3 2 1
1 3 2 6 4 5 1 3 2

Ensuite, on fait la somme des produits entre chiffre et élément du ruban: 9*1 + 8*3 + 7*2 + 6*6 + 5*4 + 4*5 + 3*1 + 2*3 + 1*2 = 134. Si on le souhaite, on peut alors recommencer:

4 3 1
1 3 2

Ce qui nous donne 4*1 + 3*3 + 1*2 = 15. Essayons encore une fois:

5 + 3 = 9. 9 n'est pas multiple de 7, 123456789 non plus, tout comme 134 ou 15. Par ailleurs, tous ces nombres ont le même reste dans une division par 7, ce reste est 2.

Par commodité, on peut aussi écrire le ruban de droite à gauche, et dans ce cas garder l'ordre naturel des chiffres dans l'écriture de N.

[edit] Correctness of the divisibility criterion

L'explication du fonctionnement des rubans de Pascal se fait naturellement à travers les congruences. On dit que a congrue à b modulo c si le reste de la division entière de a par c est égal au reste de la division de b par c (ou encore que a-b est multiple de c). On le note $a \equiv b [c]$ . Par exemple:

$8 \equiv 13 \equiv 3 [5]$

The argument requires two properties of the congruence relation:

$a \equiv b [m], c \equiv d [m] \implies a*c \equiv b*d [m]$
$a \equiv b [m], c \equiv d [m] \implies a+c \equiv b+d [m]$

The goal is to demonstrate that:

the sum of products (tape's element * digit)
the number

belong to the same equivalence class for the congruence relation.

$B^i \equiv t_i [D]$ by construction
$d_i * B^i \equiv d_i * t_i [D]$ as a product of congruences
$N=\sum_i d_i * B^i \equiv \sum_i d_i * t_i [D]$ as a sum of congruences

$d i$ is the ith digit of the writing of N in base B, $t i$ is the ith element of the tape for D in base B. The consequence of the last line is that if N is a multiple of D, so is

∑	c_i * r_i
i

[edit] Some properties of tapes

The number of possible remainders in a division by D is equal to D (from 0 to D-1); this makes the tape repetitive.
If 0 appears on the tape, every following element is 0 because if $B p$ is a multiple of D, every following powers that are multiples of $B p$ are also multiples of D.
If 0 does not appear, there must be a repetition of a non zero remainder. Therefore, there is a $B^p \equiv B^m [D]$ . Then $B^{p+k} \equiv B^{m+k} [D]$ , which makes the tape periodic of period m-p. The number of possible remainders is D-1 (0 is excluded), the period is inferior or equal to D-1.