User:Joris.deguet/draft
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].
Tape construction[edit]
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:
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.
First Tapes with B=10[edit]
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 ...
Tape usage to decide divisibility[edit]
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 1
- 1 3
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.
Correctness of the divisibility criterion[edit]
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 . Par exemple:
![{\displaystyle a\equiv b[c]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abc8e84a69a221e17c2213a61e3b45d571464e06)
![{\displaystyle 8\equiv 13\equiv 3[5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/136d3857d356bca96ad52ff73dab5b1f9340608e)
The argument requires two properties of the congruence relation:
![{\displaystyle a\equiv b[m],c\equiv d[m]\implies a*c\equiv b*d[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f029082c7e44c9f895aba16d1a5bfd4c4858ae9)
![{\displaystyle a\equiv b[m],c\equiv d[m]\implies a+c\equiv b+d[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a258351aae66d42eedccef6e382c89692307628)
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.
- by construction
- as a product of congruences
- as a sum of congruences
![{\displaystyle B^{i}\equiv t_{i}[D]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042435e7f9aeb6228f11c066d9782265190ef1fe)
![{\displaystyle d_{i}*B^{i}\equiv d_{i}*t_{i}[D]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/436ec8cfa52b2993c63f2fd9c57dd97ccf821795)
![{\displaystyle N=\sum _{i}d_{i}*B^{i}\equiv \sum _{i}d_{i}*t_{i}[D]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be497bd2562850012d7946270876dcc0dde0c838)
is the ith digit of the writing of N in base B, 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
O_O_O_O_O_O_O_O_O_O_OLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOL
cheeki breeki was here