Votre navigateur n'accepte pas le Javascript.La navigation sur ce site risque de ne pas fonctionner correctement.

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

Dans cet article, vous cherchez à calculer le $\mathrm{PGCD}$ des nombres $1961$ et $1591$ en utilisant des nombres premiers.

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

Les deux nombres $1961$ et $1591$ sont impairs, ni l’un ni l’autre ne sont divisibles 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$, 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$, 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 finit pas $0$ ou $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$ est un multiple de $7$ ainsi que $84.$

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

Si $1591$ était un multiple de $7$, 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$, donc $15$ est un multiple de $7$. Contradiction.

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.

$3$ n’étant pas un multiple de $11$, 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.

$-4$ n’étant pas un multiple de $11$, 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$ finit par $1$, 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$, contradiction.

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$, donc $59-39 = 20$ est un multiple de $13$ donc $2$ est un multiple de $13$, contradiction.

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$, 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 $13$, donc $14$ est un multiple de $17$, contradiction.

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$, donc $52-51 = 1$ est un multiple de $17$, contradiction.

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$, contradiction.

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$, donc $18$ est un multiple de $19$, contradiction.

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$, contradiction.

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$, contradiction.

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 = 1980$ est un multiple de $29.$ Donc $198$ est un multiple de $29$. Or, $198 = 2\times 99.$ Comme $29$ n’est pas un diviseur de $2$, $29$ divise $99.$ Donc $99-29 = 70$ est un multiple de $29$ et $7$ est un multiple de $29$, contradiction.

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$, $29$ divise $81.$ Donc $81+29 = 110$ est un multiple de $29$ et $11$ est un multiple de $29$, contradiction.

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$ donc $31$ est un diviseur de $1$, contradiction.

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$, contradiction.

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

Il vient :

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

Le nombre $\mathrm{PGCD}(53, 43)$ est un diviseur de $43$ qui est un nombre premier : $43$ n’admet que deux diviseurs, $1$ et lui-même.

Si $\mathrm{PGCD}(53, 43) = 43$ alors $43$ divise $53$ donc $43$ divise $53-43 = 10$ ce qui est absurde.

Par conséquent, $\mathrm{PGCD}(53, 43) = 1.$

En définitive :

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

Partagez!

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.

Aidez-moi sur Facebook!

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Lisez d'autres articles!

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira!