312. Calculez le PGCD de deux entiers avec des nombres premiers

Dans ce contenu, vous cherchez à calculer le $\pgcd$ des nombres $1961$ et $1591$ en utilisant des nombres premiers : vous testez successivement la divisibilité de ces deux nombres par $2\comma$ $3\comma$ $5\comma$ $7\comma$ et ainsi de suite, jusqu’à trouver un facteur premier commun.

Note. Dans tout ce qui suit, une propriété est utilisée à plusieurs reprises : si un nombre premier $p$ différent de $2$ et de $5$ divise un nombre de la forme $10n\comma$ alors il divise $n.$ C’est une conséquence du lemme d’Euclide, puisque $p$ ne divise pas $10 = 2\times 5.$

Divisibilité des nombres $1961$ et $1591$ par $2$

Les deux nombres $1961$ et $1591$ sont impairs : ni l’un ni l’autre n’est divisible par $2.$

\boxed{2 \nmid 1961 \text{ et } 2\nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $3$

La somme des chiffres de $1961$ est égale à $17$ qui n’est pas divisible par $3\comma$ donc $3$ n’est pas un diviseur de $1961.$

La somme des chiffres de $1591$ est égale à $16$ qui n’est pas divisible par $3\comma$ donc $3$ n’est pas un diviseur de $1591.$

\boxed{3 \nmid 1961 \text{ et } 3\nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $5$

Ni $1961$ ni $1591$ ne se termine par $0$ ou par $5.$ Ni $1961$ ni $1591$ n’est divisible par $5.$

\boxed{5 \nmid 1961 \text{ et } 5\nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $7$

Utilisez le fait que $21$ et $84$ sont des multiples de $7.$

Si $1961$ était un multiple de $7\comma$ alors $1961-21 = 1940$ en serait un. Comme $1940 = 194\times 10$ et comme $7$ ne divise pas $10\comma$ il en résulte que $7$ doit diviser $194.$ Alors $194-84 = 110$ est un multiple de $7\comma$ donc $11$ est un multiple de $7\comma$ ce qui est absurde.

Si $1591$ était un multiple de $7\comma$ alors $1591-21 = 1570$ en serait un. Il en résulte que $7$ doit diviser $157.$ Alors $157-7 = 150$ est un multiple de $7\comma$ donc $15$ est un multiple de $7\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $7.$

\boxed{7 \nmid 1961 \text{ et } 7\nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $11$

Vous partez du chiffre des unités de $1961$ et calculez la somme alternée de ses chiffres :

1-6+9-1 = 10-7 = 3.

Le nombre $3$ n’étant pas un multiple de $11\comma$ vous déduisez que $11$ n’est pas un diviseur de $1961.$

Vous partez du chiffre des unités de $1591$ et calculez la somme alternée de ses chiffres :

1-9+5-1 = 6-10 = -4.

Le nombre $-4$ n’étant pas un multiple de $11\comma$ vous déduisez que $11$ n’est pas un diviseur de $1591.$

Ni $1961$ ni $1591$ n’est divisible par $11.$

\boxed{11 \nmid 1961 \text{ et } 11 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $13$

Vous remarquez que le produit $13\times 7$ se termine par $1\comma$ puisque :

13\times 7 = 70+21=91.

Vous déduisez après multiplication par $10$ que $910$ est un autre multiple de $13.$

Par somme $91+910 = 1001.$

Le nombre $1001$ est un multiple de $13$ qui va permettre de conclure.

Supposez que $13$ soit un diviseur de $1961.$ Alors $1961-1001 = 960$ est un multiple de $13.$ Donc $96$ est un multiple de $13.$ Vous déduisez que $96-91 = 5$ est un multiple de $13\comma$ ce qui est absurde.

Supposez que $13$ soit un diviseur de $1591.$ Alors $1591-1001 = 590$ est un multiple de $13.$ Donc $59$ est un multiple de $13.$ Or $13\times 3 = 39$ est un multiple de $13\comma$ donc $59-39 = 20$ est un multiple de $13$ donc $2$ est un multiple de $13\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $13.$

\boxed{13 \nmid 1961 \text{ et } 13 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $17$

Le produit $17\times 3$ fournit $51$ comme multiple de $17.$ En multipliant par $2\comma$ il apparaît que $102$ est un multiple de $17.$

Supposez que $17$ soit un diviseur de $1961.$ Alors $1961-51 = 1910$ est un multiple de $17.$ Donc $191$ est un multiple de $17.$ Vous déduisez que $191-51 = 140$ est un multiple de $17\comma$ donc $14$ est un multiple de $17\comma$ ce qui est absurde.

Supposez que $17$ soit un diviseur de $1591.$ Alors $1591-51 = 1540$ est un multiple de $17.$ Donc $154$ est un multiple de $17.$ Vous déduisez que $154-102 = 52$ est un multiple de $17\comma$ donc $52-51 = 1$ est un multiple de $17\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $17.$

\boxed{17 \nmid 1961 \text{ et } 17 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $19$

Supposez que $19$ soit un diviseur de $1961.$ Alors $1961+19 = 1980$ est un multiple de $19.$ Donc $198$ est un multiple de $19.$ Vous déduisez que $198-190 = 8$ est un multiple de $19\comma$ ce qui est absurde.

Supposez que $19$ soit un diviseur de $1591.$ Alors $1591+19 = 1610$ est un multiple de $19.$ Donc $161$ est un multiple de $19.$ Vous déduisez que $161+19 = 180$ est un multiple de $19\comma$ donc $18$ est un multiple de $19\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $19.$

\boxed{19 \nmid 1961 \text{ et } 19 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $23$

Le produit $23\times 7$ fournit $161.$

Supposez que $23$ soit un diviseur de $1961.$ Alors $1961-161 = 1800$ est un multiple de $23.$ Donc $18$ est un multiple de $23\comma$ ce qui est absurde.

Supposez que $23$ soit un diviseur de $1591.$ Alors $1591-161 = 1430$ est un multiple de $23.$ Donc $143$ est un multiple de $23.$ Du coup $143-23 = 120$ est un multiple de $23$ donc $12$ est un multiple de $23\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $23.$

\boxed{23 \nmid 1961 \text{ et } 23 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $29$

Supposez que $29$ soit un diviseur de $1961.$ Alors $1961+29 = 1990$ est un multiple de $29.$ Donc $199$ est un multiple de $29.$ Or, $29\times 5 = 145$ est un multiple de $29\comma$ donc $199-145 = 54$ est un multiple de $29.$ Comme $54 = 2\times 27$ et que $29$ n’est pas un diviseur de $2\comma$ le nombre $29$ divise $27\comma$ ce qui est absurde.

Supposez que $29$ soit un diviseur de $1591.$ Alors $1591+29 = 1620$ est un multiple de $29.$ Donc $162$ est un multiple de $29.$ Or, $162 = 2\times 81.$ Comme $29$ n’est pas un diviseur de $2\comma$ le nombre $29$ divise $81.$ Donc $81+29 = 110$ est un multiple de $29$ et $11$ est un multiple de $29\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $29.$

\boxed{29 \nmid 1961 \text{ et } 29 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $31$

Supposez que $31$ soit un diviseur de $1961.$ Alors $1961-31 = 1930$ est un multiple de $31.$ Donc $193$ est un multiple de $31.$ Or, $31\times 3 = 93$ est un multiple de $31.$ Donc $193-93 = 100$ est un multiple de $31.$ Comme $100 = 2^2\times 5^2$ et que le nombre premier $31$ ne divise ni $2$ ni $5\comma$ c’est absurde.

Supposez que $31$ soit un diviseur de $1591.$ Alors $1591-31 = 1560$ est un multiple de $31.$ Donc $156$ est un multiple de $31.$ Or, $31\times 5 = 155$ est un multiple de $31.$ Donc $156-155 = 1$ est un multiple de $31\comma$ ce qui est absurde.

Ni $1961$ ni $1591$ n’est divisible par $31.$

\boxed{31 \nmid 1961 \text{ et } 31 \nmid 1591.}

Divisibilité des nombres $1961$ et $1591$ par $37$

Le produit $37\times 3$ fournit $111.$

Par différence, $1961-111 = 1850 = 185\times 10.$

Du coup, vous déduisez :

\begin{align*} 1961 &= 111 + 185\times 10\\ &= 37\times 3 + (111+ 74)\times 10\\ &= 37\times 3 + (37\times 3 + 37\times 2)\times 10\\ &=37\times 3 + 37\times 5\times 10\\ &=37 \times 3 + 37\times 50\\ &=37 \times 53. \end{align*}

Par différence, $1591-111 = 1480 = 148\times 10.$

Du coup, vous déduisez :

\begin{align*} 1591 &= 111 + 148\times 10\\ &= 37\times 3 + (74\times 2)\times 10\\ &= 37\times 3 + (37\times 2\times 2 )\times 10\\ &=37\times 3 + 37\times 40\\ &=37 \times 43. \end{align*}

Concluez

Vous allez utiliser le caractère multiplicatif du $\pgcd\comma$ démontré dans un autre article.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 313.

Il vient :

\begin{align*} \pgcd(1961,1591) &= \pgcd(37\times 53, 37\times 43)\\ &= 37 \times \pgcd(53, 43). \end{align*}

Le nombre $\pgcd(53, 43)$ est un diviseur positif de $43\comma$ qui est un nombre premier : $43$ n’admet que deux diviseurs positifs, $1$ et lui-même.

Si $\pgcd(53, 43) = 43$ alors $43$ divise $53$ donc $43$ divise $53-43 = 10$ ce qui est absurde.

Par conséquent, $\pgcd(53, 43) = 1.$

En définitive :

\boxed{\pgcd(1961,1591) = 37.}