CHAPITRE XIX. — CODIVISEVRS ET GOMULTIPLBS

est nécessairement dt i. En faisant abstraction du diviseur i, commun à tous les nombres, on dit encore que deux nombres premiers entre eux n'ont aucun codiviseur.

Lorsque Ton multiplie deux nombres par un troisième, le reste de la division de Tun par l'autre se trouve multiplié par ce troisième; il en est de même de tous les restes obtenus dans la recherche de leur plus grand codiviseur. De môme, si l'on divise deux nombres par un de leurs facteurs communs, le reste de la division de l'un par l'autre, et leur plus grand codiviseur, sont divisés par ce troisième.

En particulier, lorsqu^on divise deux nombres par leur plus grand codiviseur, les quotients obtenus sont premiers entre eux. Réciproquement, si la division de deux nombres par un troisième donne des quotients premiers entre eux, le troisième nombre est le plus grand codiviseur des deux autres. On a ainsi une preuve de l'opération du plus grand codiviseur; en recommençant l'opération sur ces quotients, on doit trouver i pour plus grand codiviseur.

Exemple I. — Si N points sont rangés en cercle et qu'on les joigne de R en R, on passera par tous les points avant de revenir au point de départ, si R et N sont premiers entre eux.

En effet, supposons, s'il est possible, que l'on ne passe que par n points avant de revenir au point initial. I^renons un quelconque des points par lesquels on n'est pas encore passé et joignons encore de Ren R; nous formerons un second polygone de n côtés n'ayant aucun sommet commun avec le premier; car, s'il en était autrement, les deux polygones coïncideraient. En faisant de même pour les points qui restent, on forme ainsi h polygones de n côtés et, puisque tous les points ont été employés une seule fois, on a N = hn. Mais, en joignant de R en R, chaque polygone de n côtés se trouvant fermé, on a fait un certain nombre r de fois le tour de la circonférence; on a donc «R = rN; il résulte des deux égalités qui précèdent

N = A/i, ï\ = hr:

par conséquent, R et N auraient un codiviseur A, ce qui est contre l'hypothèse.

Plus généralement, si N et R ont h comme plus grand codiviseur, et si l'on pose N = hn et R = /ir, on forme, en joignant les points de R en R h polygones de n côtés.

Celle démonstration a été donnée par M. Mansion dans la Revue de l'Instruction publique en Belgique; 1869.

Exemple II. — On consid«'TC p lignes équidi<tantes de q points équidi«tant«, on a ainsi (p—i}(q — i) carrés égaux; on place un point au centre de chacun de ces carrés, et Ton forme un quinconce de

points. Le nombre minimum de circuits continus, sans répétition ni rebroussement, pour entourer tous les points du quinconce, en les séparant Tun de Tautre, est égal au plus grand codiviseur de /> et de q.

Ce curieux énoncé m*a été communiqué, en 1888, par M. Bresson, ancien élève de l'École Polytechnique. (Voir les \ofes , à la fin du Volume. )

191. Propriétés da plus grand codiviseur. — On aie théorème suivant : Les /-estes successifs obtenus dans la recherche du plus grand codiviseur de deux nombres positifs a et b sont les différences de deux multiples de a et de b. En d'autres termes, on a la relation

dans laquelle fp et gp sont deux entiers positifs. En effet, nous obser\'erons d'abord que le théorème est immédiatement vérifié pour le premier reste /'i , puisque l'on a

r, — rt — 670;

nous supposerons donc , =— q^ et g^ =^ i : mais si, dans l'égalité suivante, qui définit z'^,

Ts-r 6- riqi,

on n^mplace /'i par sa valeur, il vient

— ri = aqi— /)(i-r-qoqi);

nous avons ainsi

et les nombres /^ et g2 sont entiers, positifs, et respectivement plus grands que/i et ^|. Si nous portons les valeurs de /^ et de r^ dans l'égalité qui définit 7*3, c'est-à-dire

rz= ri— rjç,, il vient

ri= a(l -^ qiqi) -^ b (qoqtqt-^ qi-^ qo),