Titane (./14) :
Ben les n chapeaux du théorème toussa 
Pourquoi 2 n chapeau1 c'est congru à 1 modulo 3 et que donc e1 il vaut 70 (dans l'exemple de wikipedia) ?
Ou mieux : est-ce que quelqu'un peut me poster les étapes de calcul dans le cas des 4545... ?
Je ne vais pas le faire dans le cas (pas simple) des 4545, je vais prendre un cas que je trouve plus facile que l’original :
On cherche N :
• congru à 3 modulo 8• congru à 7 modulo 13
C’est un cas plus simple pour 2 raisons : il n’y a que 2 équations, donc je n’aurai que 2 sous-pavés principaux à écrire (et vous à lire) ; les diviseurs 8 et 13 sont suffisamment grands pour visualiser plus facilement ce qui se passe.
Note : j’ai simplifié le problème en prenant des diviseurs
premiers entre eux, sinon ça devient beaucoup plus chiant (or c’est le cas en
./1, avec 4545 = 45*101).
Je parlais de visualiser ce qui se passe : on imaginera des petits pavés carrés tous identiques, et 2 grandes boîtes, la « boîte n°8 » pouvant contenir exactement 8 carreaux en largeur (la longueur étant indéterminée et extensible à volonté) et la « boîte n°13 » pouvant contenir exactement 13 carreaux en largeur (pareil, longueur sans importance).
Chacune de ces boîte se remplira en commençant par le « fond », rangée après rangée (on ne peut pas commencer une nouvelle rangée tant que toutes les rangées précédentes ne sont pas pleines).
Le problème posé revient donc à trouver un nombre N de carreaux tels que, placés dans la boîte n°8, on forme un paquet de rangées complètes et une rangée partielle avec 3 carreaux, tandis que placés dans la boîte n°13, on forme un paquet de rangées complètes et une rangée partielle avec 7 carreaux.
Pour commencer, prenons une poignée de 13 carreaux et plaçons-les dans la boîte n°13 (initialement vide) : cette poignée remplira tout juste la rangée du fond, aucune rangée incomplète (aucun reste) ; de même si on ajoute de nouvelles poignées de 13 carreaux, le « reste » reste nul.
Prenons ces mêmes poignées de 13 carreaux, mais rangeons-les maintenant dans la boîte n°8 : avec 1 poignée, on forme 1 rangée complète et une rangée partielle avec 5 carreaux, le reste vaut 5 ; avec 2 poignées, soit 26 carreaux, on forme 3 rangées complètes et une partielle avec 2 carreaux ; etc.
Or, comme 8 et 13 sont premiers entre eux (c’est important ici), il existe un théorème mathématique (celui de [url=
http://fr.wikipedia.org/wiki/Théorème_de_Bachet-Bézout]Bachet-Bézout[/url], que je ne démontrerai pas ici) disant qu’il
existe obligatoirement un certain nombre A de poignées de 13 carreaux tel que l’on puisse remplir la boîte n°8 avec un certain nombre de rangées complètes et une rangée partielle avec seulement 1 carreau, avec A compris entre 1 et 7 (avec 8 poignées de 13, on remplit 13 rangées de 8, et on se retrouve avec un reste nul, comme quand la boîte était vide).
Dit mathématiquement : il existe A dans [[1;7]] tel que 13×A soit congru à 1 modulo 8 (comme 8 est pair et 13 impair, je peux même dire que A est impair, mais il s’agit ici d’un cas particulier propre à cet exemple, je n’irai pas plus avant).
Ici, la seule chose qui nous importe est de savoir que ce A entre 1 et 7 existe, donc on peut tester à la main les 7 cas pour trouver A : en l’occurrence, 13×5 = 65 = 1+8×8, donc A=5.
Vidons nos boîtes, et prenons maintenant une plus grosse poignée de carreaux, une poignée de 65 : dans la boîte n°8, cette grosse poignée forme 8 (on s’en fout) rangées complètes et une rangée partielle avec 1 carreau ; dans la boîte n°13, cette même grosse poignées forme 5 rangées complètes, sans reste.
Mettons maintenant X (pas trop grand) grosses poignées de 65 carreaux : la boite n°8 aura alors une rangée partielle de X carreaux, tandis que la boîte n°13 gardera obstinément un reste nul !
Recommençons de zéro (boîtes vides), avec cette fois-ci des petites poignées de 8 carreaux seulement : maintenant, c’est la boîte n°8 qui aura toujours un reste nul à chaque poignée ajoutée, tandis que la boîte n°13 aura sa rangée partielle comportant successivement 8, puis 3, puis 11 carreaux, etc.
Réutilisons notre théorème mathématique qui nous dit maintenant : il existe B dans [[1;12]] tel que 8×B soit congru à 1 modulo 13 (là, les considérations de parité ne disent rien sur B, mais le multiplicateur de 13 sera impair).
On teste à la main les 12 valeurs possibles de B jusqu’à trouver la bonne : 8×5 = 40 = 1+13×3, donc B=5 (n’y voyez aucun lien avec A, c’est une coïncidence).
Cette fois, on prends donc des grosses poignées de 40 carreaux : dans la boîte n°13, cette grosse poignée forme 3 (on s’en fout) rangées complètes et une rangée partielle avec 1 carreau ; dans la boîte n°8, cette même grosse poignées forme 5 rangées complètes, sans reste.
Et donc, avec Y (pas trop grand) grosses poignées de 40 carreaux : la boite n°13 aura alors une rangée partielle de Y carreaux, tandis que la boîte n°8 gardera un reste nul.
Que se passe-t-il maintenant si on utilise X poignées de 65 carreaux
et Y poignées de 40 carreaux ?
Eh bien dans la boîte n°8, les Y poignées de 40 rempliront le fond sans reste, puis les X poignées de 65 formeront un reste de X, et ce, quelle que soit la valeur de Y !
De même, dans la boîte n°13, les X poignées de 65 rempliront le fond sans reste, puis les Y poignées de 40 formeront un reste de Y.
Il suffit donc, pour répondre au problème, de choisir X=3 et Y=7 (soit un total de 3×65+7×40=475 carreaux), et voilà, les conditions sont remplies !
Mais ce n’est pas tout : si on ajoute une nouvelle poignée de 8×13=104 carreaux, on remplira soit 13 rangées pleines dans la boîte n°8, soit 8 rangées pleines dans la boîte n°13, donc on ne change le reste ni dans un cas ni dans l’autre, quel que soit le nombre de poignées de 104 carreaux que l’on ajoute… on que l’on enlève !
On peut donc retirer autant de fois que possible des lots de 104 carreaux à notre tas de 475 (on fait 475 modulo 104), jusqu’à en avoir plus que 59.
On vérifiera que l’on a 59 = 3+8×7 = 7+13×4.
Donc N = 59 modulo 104.
Pour répondre plus précisément à ta question, c’est donc le passage, par exemple, des petites poignées de 13 aux grosses poignées de 65 (afin de former un reste valant exactement 1 dans la boîte n°8) qui explique que l’on prenne 70 (qui, modulo 3, donne 1) au lieu de 35 (qui, modulo 3, donne 2).
Voilà, j’espère que mon pavé n’est pas trop indigeste et qu’il aura donné un éclaircissement suffisant sur le problème.
Notez que j’ai passé sous silence le cas où les diviseurs ne sont pas premiers entre eux : il faut alors triturer les équations pour trouver un système équivalent avec des diviseurs tous premiers entre eux, c’est assez relou.
Oh et sinon, il y a aussi la méthode des substitutions successives qui permet de traiter de la même manière tous les cas (diviseurs premiers entre eux ou non), mais c’est vraiment hyper-long à faire à la main (des 4 équations de
./1, on passe à un système de 3 équations, puis de 2, et enfin de 1, puis on remonte les résultats d’un système au précédent jusqu’à revenir à l’initial, ce qui demande donc une longueur de papier « en n^2 », avec n le nombre initial d’équations), mais ça se fait (mais ce n’est plus le théorème des restes chinois qui, lui, est « en n »).
Edit: Oh punaise, le pavé !
Ça se voit, que je suis mauvais prof/didacticien ^^" ?
Flemme de relire, j’espère ne pas avoir laissé trop de conneries…
.
…
.
