École AVOSZ

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

Rédigé par Yannis TRIANTAPHYLIDESon 06/11/202306/11/2023| Pour tous

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.}

311. Décomposez des entiers en produits de nombres premiers

Rédigé par Yannis TRIANTAPHYLIDESon 28/10/202329/10/2023| Pour tous

Le nombre $600$

Ce nombre comportant deux zéros, vous utilisez la multiplication par $10$ deux fois.

\begin{align*} 600 &= 6 \times 100\\ &=6\times 10\times 10. \end{align*}

Comme :

\begin{align*} 6 &= 2\times 3\\ 10 &= 2\times 5 \end{align*}

vous déduisez :

\begin{align*} 600 &= (2\times 3)\times (2\times 5)\times (2\times 5)\\ &= 2\times 3\times 2\times 5\times 2\times 5\\ &= 2\times 2 \times 2\times 3\times 5\times 5. \end{align*}

Avec les puissances vous avez :

\boxed{600 = 2^3\times 3\times 5^2.}

Le nombre $851$

Il est beaucoup plus délicat de décomposer ce nombre sans calculatrice. Il convient d’analyser la situation en cherchant à déterminer un nombre premier susceptible de diviser $851.$

Le nombre premier $2$ est exclu : le nombre $851$ finit par $1$ et il est impair.
La somme des chiffres de $851$ est égale à $8+5+1 = 14.$ Comme $14$ n’est pas un multiple de $3$, le nombre $851$ n’en est pas un non plus.
Comme $851$ ne finit ni par $0$ ni par $5$, il n’est pas divisible par $5.$
Supposez que $851$ soit divisible par $7.$ Comme $21$ est un multiple de $7$, par différence, $851-21 = 830$ serait divisible par $7.$ Comme $830 = 83\times 10 = 83\times 2\times 5$ vous déduisez que $7$ est un diviseur de $83.$ Le nombre $70$ est un multiple de $7.$ Par différence $83-70 = 13.$ Ainsi $13$ serait un multiple de $7$ ce qui est absurde. Donc $7$ n’est pas un diviseur de $851.$
La somme alternée des chiffres de $851$ en partant des unités est $1-5+8 = 4.$ Comme $4$ n’est pas un multiple de $11$ vous déduisez que $851$ n’en est pas un non plus.
Supposez que $851$ soit divisible par $13.$ Comme $39$ est un multiple de $13$, par somme, vous déduisez que $851+39= 890$ est divisible par $13.$ Du coup, $89$ est divisible par $13.$ Donc $89-39 = 50$ est divisible par $13$ donc $5$ est divisible par $13$ ce qui est absurde. Donc $13$ n’est pas un diviseur de $851.$
Supposez que $851$ soit divisible par $17.$ Comme $17\times 3 = 51$ par différence, vous déduisez que $851-51 = 800$ est divisible par $17$, donc $8$ est divisible par $17$ ce qui est absurde. Donc $17$ n’est pas un diviseur de $851.$
Supposez que $851$ soit divisible par $19.$ Comme $851+19 = 860$ vous déduisez que $19$ divise $86.$ Or $19\times 4 = 76$ et par différence $19$ divise $86-76 = 10$ donc $10$ est divisible par $19$ ce qui est absurde. Donc $19$ n’est pas un diviseur de $851.$
Pour la division par $23$ vous constatez déjà que $23\times 3 = 69.$ Or :

\begin{align*} 851+69 &= 920\\ &= 92\times 10 \\ &= 23\times 4\times 10\\ &= 23\times 40. \end{align*}

Vous en déduisez que :

\begin{align*} 851 &= 23\times 40 - 69\\ &= 23\times 40 - 23\times 3\\ &= 23 \times 37. \end{align*}

Comme $37$ est un nombre premier, il n’y a pas lieu de le décomposer.

Une décomposition en produit de facteurs premiers de $851$ est :

\boxed{851 = 23\times 37.}

Le nombre $1449$

La somme des chiffres de $1449$ vaut $18$ qui est un multiple de $9$, donc $1449$ est un multiple de $9.$

Partez de :

\begin{align*} 144 &= 90 + 54\\ &= 9\times 10 + 9\times 6\\ &=9\times 16. \end{align*}

Vous déduisez alors :

\begin{align*} 1440 &= 9\times 160\\ 1449 &= 9\times 161. \end{align*}

Reste à s’occuper du nombre $161.$

Etant impair, le nombre $161$ n’est pas divisible par $2.$
La somme des chiffres de $161$ vaut $8$ donc $161$ n’est pas divisible par $3.$
Le nombre $161$ n’est pas divisible par $5$ puisqu’il ne finit ni par $0$ ni par $5.$

Cependant :

\begin{align*} 161 &= 140 + 21\\ &= 7\times 20 + 7\times 3\\ &= 7 \times 23. \end{align*}

Ainsi vous obtenez :

\begin{align*} 1449 &= 9\times 7\times 23. \end{align*}

Une décomposition en produit de nombres premiers de $1449$ est :

\boxed{1449 = 3\times 3\times 7\times 23.}

310. Le théorème de Gauss démontré directement

Rédigé par Yannis TRIANTAPHYLIDESon 24/10/202324/10/2023| Niveau Prépa

Dans cet article, vous allez démontrer que le théorème de Gauss directement, sans utiliser le théorème de Bézout, dont vous trouverez une démonstration directe dans le contenu rédigé dans l'article 308.

Le théorème de Gauss énonce que, quels que soient $a$, $b$ et $c$ trois entiers relatifs, $a$ étant non nul :

\left\{\begin{array}{l} a\mid bc\\ \mathrm{PGCD}(a,b)=1 \end{array} \right. \implies a \mid c.

Pour effectuer une démonstration directe, vous fixez trois entiers relatifs $a$, $b$ et $c$, avec $a\neq 0$ tels que :

\left\{\begin{array}{l} a\mid bc\\ \mathrm{PGCD}(a,b)=1. \end{array} \right.

Introduisez une partie de l’ensemble des entiers naturels

Soit $A$ la partie de $\N$ définie par :

A=\{n\in\NN, a\mid nc\}.

Si $a$ est positif, alors $a>0$ et par suite :

\left\{\begin{array}{l} a\mid ac\\ a\in\NN. \end{array} \right.

Vous en déduisez que $a\in A.$

Si $a$ est négatif vous posez $a’ = -a$ et $a’ >0.$ Il vient :

\left\{\begin{array}{l} a\mid a' \mid a'c\\ a'\in\NN. \end{array} \right.

Donc $a’\in A.$

L’ensemble $A$ est non vide dans tous les cas. Comme $A\subset \N$, l’ensemble $A$ admet un plus petit élément que vous notez $m.$ L’entier $m$ vérifie les deux propriétés suivantes :

\boxed{\left\{\begin{array}{l} a\mid mc\\ m\in\NN. \end{array} \right.}

Démontrez que $m$ divise $a$

Comme $m\in\NN$ vous effectuez la division euclidienne de $a$ par $m.$ Il existe un entier relatif $q$ et un entier $r\in\llbracket 0, m-1\rrbracket$ tels que :

a = mq+r.

Supposez que $r$ soit non nul.

Vous multipliez l’égalité précédente par $c$ :

ac = mcq+rc.

Comme :

\left\{\begin{array}{l} a\mid ac\\ a\mid mc \mid mcq \end{array} \right.

vous déduisez que :

a\mid rc.

Or, $r\in\NN$ donc $r\in A$, donc $r\geq m$ puisque $m$ est le plus petit élément de $A$. Cela contredit l’inégalité $r\leq m-1.$

Donc $r=0$ et par suite $a=mq.$ Du coup :

\boxed{m\mid a.}

Démontrez que $m$ divise $b$

Comme $m\in\NN$ vous effectuez la division euclidienne de $b$ par $m.$ Il existe un entier relatif $q’$ et un entier $r’\in\llbracket 0, m-1\rrbracket$ tels que :

b = mq'+r'.

Supposez que $r’$ soit non nul.

Vous multipliez l’égalité précédente par $c$ :

bc = mcq'+r'c.

Par hypothèse :

a\mid bc.

Or :

a\mid mc \mid mcq'.

Vous en déduisez que :

a\mid r'c.

Or, $r’\in\NN$ donc $r’\in A$ donc $r’\geq m$ puisque $m$ est le plus petit élément de $A.$ Cela contredit l’inégalité $r’\leq m-1.$

Donc $r’=0$ et $b=mq’$ d’où :

\boxed{m\mid b.}

Concluez

L’entier $m$ strictement positif divise $a$ et $b$ à la fois. Par définition du $\mathrm{PGCD}$ il vient $m\leq \mathrm{PGCD}(a,b)$ d’où $m\leq 1.$ Comme $m>0$, vous déduisez $m=1.$

Comme $a\mid mc$ vous avez obtenu le résultat annoncé :

\boxed{a\mid c.}

309. Le théorème chinois

Rédigé par Yannis TRIANTAPHYLIDESon 24/10/202324/10/2023| Niveau Prépa

Soient $n_1$ et $n_2$ deux entiers supérieurs ou égaux à $2$ premiers entre eux et soient $a_1$ et $a_2$ deux entiers relatifs.

Le théorème chinois énonce alors que le système de congruences $\mathscr{S}$ :

\left\{\begin{align*} x \equiv a_1\quad [n_1]\\ x \equiv a_2\quad [n_2] \end{align*} \right.

où l’inconnue $x$ est un entier relatif, admet une infinité de solutions et que deux solutions quelconques de ce système sont congrues modulo le produit $n_1n_2.$

Un préalable avant l’analyse

Comme les entiers $n_1$ et $n_2$ sont premiers entre eux, il vient $\mathrm{PGCD}(n_1,n_2)=1.$

D’après le théorème de Bézout (une démonstration directe est donnée dans le contenu rédigé dans l'article 308), il existe deux entiers relatifs $u_1$ et $u_2$ tels que :

u_1n_1+u_2n_2 = 1.

Analysez le système

Supposez qu’il existe un entier relatif $x$ qui soit solution du système :

\left\{\begin{align*} x \equiv a_1\quad [n_1]\\ x \equiv a_2\quad [n_2] \end{align*} \right.

il existe alors deux entiers relatifs $k_1$ et $k_2$ tels que :

\left\{\begin{align*} x &= a_1+k_1n_1\\ x&= a_2+k_2n_2. \end{align*} \right.

Par soustraction, vous en déduisez les égalités suivantes :

\begin{align*} 0 &= a_2-a_1+k_2 n_2 - k_1n_1 \\ k_1n_1 - k_2 n_2 &= a_2-a_1. \end{align*}

Multipliez maintenant l’égalité $u_1n_1+u_2n_2 = 1$ par $a_2-a_1$, il vient :

(a_2-a_1)u_1n_1+(a_2-a_1)u_2n_2 = a_2-a_1.

Par soustraction, vous éliminez $a_2-a_1$ :

[k_1 - (a_2-a_1)u_1]n_1+[-k_2-(a_2-a_1)u_2]n_2 = 0.

Vous en déduisez que :

[k_1 - (a_2-a_1)u_1]n_1 = [k_2+(a_2-a_1)u_2]n_2.

Du coup :

n_1 \mid [k_2+(a_2-a_1)u_2]n_2.

Comme $n_1$ et $n_2$ sont premiers entre eux avec $n_1\in\NN$, vous appliquez le théorème de Gauss (vous en trouverez une démonstration indépendante et directe, dans le contenu rédigé dans l'article 310) et déduisez que :

n_1 \mid k_2+(a_2-a_1)u_2.

Il existe donc un entier relatif $t$ tel que :

k_2+(a_2-a_1)u_2 = tn_1.

Cela s’écrit :

k_2 = tn_1+(a_1-a_2)u_2.

Vous en déduisez que :

\begin{align*} x &= a_2+k_2n_2\\ &= a_2+( tn_1+(a_1-a_2)u_2)n_2\\ &=a_2+(a_1-a_2)u_2n_2+tn_1n_2\\ &=a_1u_2n_2+a_2(1-u_2n_2)+tn_1n_2\\ &=a_1u_2n_2+a_2(u_1n_1)+tn_1n_2. \end{align*}

Ainsi vous avez démontré que :

\boxed{x \equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2].}

Note. L’analyse démontre que deux solutions du système de congruences $\mathscr{S}$ sont congrues entre-elles modulo $n_1n_2.$ En effet, soient $x_1$ et $x_2$ deux solutions quelconques de $\mathscr{S}$. Alors :

\begin{align*} x_1 &\equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2]\\ x_2 &\equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2]. \end{align*}

Par soustraction, il vient :

\begin{align*} x_1-x_2 \equiv 0 \quad [n_1n_2]\\ x_1 \equiv x_2 \quad [n_1n_2]. \end{align*}

Synthèse

Soit $t$ un entier relatif. Posez :

x = u_1n_1a_2+ u_2n_2a_1 + tn_1n_2.

Modulo $n_1$, il vient :

\begin{align*} x&\equiv u_2n_2a_1\quad [n_1]\\ x &\equiv (1-u_1n_1)a_1 \quad [n_1]\\ x &\equiv a_1-u_1n_1a_1 \quad [n_1]\\ x &\equiv a_1 \quad [n_1]. \end{align*}

De même, modulo $n_2$ :

\begin{align*} x&\equiv u_1n_1a_2\quad [n_2]\\ x &\equiv (1-u_2n_2)a_2 \quad [n_2]\\ x &\equiv a_2-u_2n_2a_2 \quad [n_2]\\ x &\equiv a_2 \quad [n_2]. \end{align*}

Ainsi, $x$ est bien solution du système de congruences $\mathscr{S}$.

Note. La synthèse démontre que le système de congruences $\mathscr{S}$ admet une infinité de solutions : à chaque valeur de l’entier $t$, l’entier $u_1n_1a_2+ u_2n_2a_1 + tn_1n_2$ est bien solution. D’autre part, l’ensemble

\{u_1n_1a_2+ u_2n_2a_1 + tn_1n_2, t\in\Z\}

est bien infini compte tenu de l’injectivité de l’application $t\mapsto u_1n_1a_2+ u_2n_2a_1 + tn_1n_2$ qui va de $\Z$ dans $\Z$.

Concluez

D’après l’analyse-synthèse effectuée, il vient d’être démontré que, pour tout entier relatif $x$ :

\boxed{\begin{align*} \begin{align*} \left\{\begin{align*} x \equiv a_1\quad [n_1]\\ x \equiv a_2\quad [n_2] \end{align*} \right. &\Longleftrightarrow \left(\exists t\in\Z, x = u_1n_1a_2+ u_2n_2a_1 + tn_1n_2\right) \\ &\Longleftrightarrow x\equiv u_1n_1a_2+ u_2n_2a_1 \quad [n_1n_2]. \end{align*} \end{align*}}

Le système de congruences $\mathscr{S}$ admet une infinité de solutions, toutes congrues entre elles modulo $n_1n_2.$
Le théorème chinois est ainsi démontré.

308. Le théorème de Bézout sans l’algorithme d’Euclide

Rédigé par Yannis TRIANTAPHYLIDESon 10/10/202329/03/2024| Niveau Prépa

L’objectif de cet article est de construire une preuve directe du résultat suivant. Etant donnés deux nombres entiers relatifs $a$ et $b$ non simultanément nuls, il existe deux nombres entiers relatifs $u$ et $v$, appelés coefficients de Bézout, tels que :

\mathrm{PGCD}(a,b) = au+bv.

Ce résultat sera appelé théorème de Bézout. Très souvent, ce théorème est démontré à partir de l’algorithme d’Euclide. Une approche différente est proposée ici.

De façon formelle, ce théorème s’écrit ainsi :

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \exists(u,v)\in\Z^2,\mathrm{PGCD}(a,b) =au+bv.}

Note. En aucun cas les nombres $u$ et $v$ ne sont uniquement déterminés par $a$ et $b.$ Seule l’existence de ces deux nombres importe dans le théorème susmentionné.

Note. Vous souhaitez calculer effectivement des coefficients de Bézout ? Reportez-vous au contenu rédigé dans l'article 174.

Vous vous rappelez que, quels que soient les entiers $a$ et $b$ non simultanément nuls, le $\mathrm{PGCD}$ de $a$ et de $b$, noté $\mathrm{PGCD}(a,b)$ désigne le maximum de l’ensemble suivant :

\{n\in\NN, n\mid a \text{ et } n\mid b\}.

Ainsi :

\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \mathrm{PGCD}(a,b) = \max \{n\in\NN, n\mid a \text{ et } n\mid b\}.

Note. Le $\mathrm{PGCD}$ de deux nombres nuls n’est pas défini, c’est la raison pour laquelle on suppose $(a,b)\neq (0,0).$

Dans toute la suite, $a$ et $b$ désignent deux entiers fixés, non simultanément nuls.

Etudiez un ensemble

Soit $A$ l’ensemble suivant :

A = \{n\in\NN, \exists(u,v)\in\Z^2, n=au+bv\}.

Vous allez dans un premier temps justifier que $A$ est non vide.

Supposez que $a$ soit non nul. Si $a$ est positif, en prenant $u=1$ et $v=0$ vous constatez que $au+bv\in\NN$ donc $au+bv\in A.$

Si $a$ est négatif, vous prenez $u=-1$ et $v=0.$ Vous constatez encore que $au+bv\in\NN$ donc $au+bv\in A.$

Si $a$ est nul, vous déduisez que $b\neq 0.$ Cela provient du fait que $(a,b)\neq (0,0).$ De même, si $b$ est positif, alors en posant $u=0$ et $v=1$, vous avez $au+bv\in\NN$ donc $au+bv\in A.$ Si $b$ est négatif, alors vous posez $u=0$ et $v=-1$ et il vient $au+bv\in\NN$ donc $au+bv\in A.$

Comme $A$ est une partie de $\N$ qui est non vide, elle admet un plus petit élément, qui sera noté $k.$

Justifiez que $k$ est le $\mathrm{PGCD}$ des nombres $a$ et $b$

Comme $k\in A$ vous déduisez que $k\in\NN$ et qu’il existe un couple $(u,v)\in\Z^2$ tel que $k=au+bv.$

Le nombre $k$ est un diviseur commun à $a$ et à $b$

Vous effectuez la division euclidienne de $a$ par $k.$ Il existe $q\in\Z$ et $r\in\llbracket 0, k-1\rrbracket$ tels que :

a = kq+r.

Si $r$ est différent de $0$, alors vous avez :

\begin{align*} r &= a-kq\\ &=a-(au+bv)q\\ &=a(1-uq)+b(-vq). \end{align*}

Comme $(1-uq, -vq)\in\Z^2$, avec $r>0$ vous déduisez que $r\in A.$ Or $r< k$ et $k$ est le plus petit élément de $A$ ce qui est impossible.

Donc $r = 0$ et par suite $a = kq$ donc $k\mid a.$

De même, vous effectuez la division euclidienne de $b$ par $k.$ Il existe $q’\in\Z$ et $r’\in\llbracket 0, k-1\rrbracket$ tels que :

b = kq'+r'.

Si $r’$ est différent de $0$, alors vous avez :

\begin{align*} r' &= b-kq'\\ &=b-(au+bv)q'\\ &=a(-uq')+b(1-vq'). \end{align*}

Comme $(-uq’, 1-vq’)\in\Z^2$, avec $r’>0$ vous déduisez que $r’\in A.$ Or $r'< k$ et $k$ est le plus petit élément de $A$ ce qui est impossible.

Donc $r’ = 0$ et par suite $b = kq’$ donc $k\mid b.$

Comme $k\in\NN$ avec $k\mid a$ et $k\mid b$ vous déduisez $\boxed{k\leq \mathrm{PGCD}(a,b).}$

Le $\mathrm{PGCD}$ de $a$ et de $b$ est inférieur à $k$

Posez $m = \mathrm{PGCD}(a,b).$ Alors $m$ est nombre entier naturel non nul tel que $m\mid a $ et $m\mid b.$

Alors il existe deux entiers relatifs $a’$ et $b’$ tels que :

\begin{align*} a &= ma'\\ b &= mb'. \end{align*}

Or, la relation $k =au+bv$ fournit :

\begin{align*} k &= ma'u+mb'v\\ &= m(a'u+b'v). \end{align*}

La stricte positivité de $k$ et de $m$ fournit $a’u+b’v \in\NN.$

Cela s’écrit :

\begin{align*} a'u+b'v &\geq 1\\ m(a'u+b'v) &\geq m\\ k &\geq m. \end{align*}

Ainsi, $\boxed{\mathrm{PGCD}(a,b)\leq k.}$

Concluez

Il vient d’être démontré que $k = \mathrm{PGCD}(a,b)$ et que :

\mathrm{PGCD }(a,b)=\min \{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.

En particulier :

\mathrm{PGCD}(a,b)\in\{n\in\NN, \exists(p,q)\in\Z^2, n=ap+bq\}.

Le théorème de Bézout est bien démontré.

\boxed{\forall (a,b)\in\Z^2\setminus\{(0,0)\}, \exists(u,v)\in\Z^2,\mathrm{PGCD}(a,b) =au+bv.}

307. Critères de divisibilité (2/2)

Rédigé par Yannis TRIANTAPHYLIDESon 08/10/202308/10/2023| Pour tous

Dans la suite du contenu rédigé dans l'article 306 vous vous intéressez à déterminer, pour un exemple détaillé, si le nombre $499\ 358$ est divisible par le nombre premier $19.$

Un premier nombre magique

Vous allez chercher un nombre magique de $19$ qui soit de taille convenable.

Essayez d’en trouver un qui finit par la séquence de chiffres $0\cdots 01.$ Vous commencez par construire un multiple de $19$ qui finit par $1.$

19\times 9 = 171.

Vous prenez ensuite un multiple de $19$ qui finit par $3$ :

19\times 7 = 133.

Par somme :

\begin{align*} 19\times 79 &= 19\times 7\times 10 + 19\times 9\\ &=1330 + 171\\ &=1501. \end{align*}

Vous prenez ensuite un multiple de $19$ qui finit par $5$ :

19\times 5 = 95.

Par somme :

\begin{align*} 19\times 579 &= 19\times 5\times 100 + 19\times 79\\ &=9500+1501\\ &=11001. \end{align*}

Vous prenez ensuite un multiple de $19$ qui finit par $9$ :

19\times 1 = 19.

Par somme :

\begin{align*} 19\times 1579 &= 19\times 1\times 1000 + 19\times 579\\ &=19000+11001\\ &=30001. \end{align*}

Ainsi, $30\ 001$ est un nombre magique de $19.$

Passez au test de divisibilité de $499\ 358$ par $19$

Le nombre magique $30\ 001$ va permettre d’éliminer le chiffre $8$ termine le nombre $499\ 358$. Vous procédez comme suit :

\begin{align*} 499\ 358 - 8\times 30\ 001 &=499\ 358 - 8\times 30\ 000 -8\\ &= 499\ 350-240\ 000\\ &=25\ 935 \times 10. \end{align*}

Vous testez maintenant la divisibilité du nombre $25\ 935$ par $19.$ Sa proximité avec $30\ 001$ amène à calculer la différence :

\begin{align*} 30\ 001 - 25\ 935 &=29\ 999-25\ 935 + 2\\ &=4\ 064+2\\ &=4\ 066. \end{align*}

Testez la divisibilité de $4\ 066$ par $19$

Le nombre magique $30\ 001$ n’est plus utile à ce stade étant donné qu’il est trop grand. Pour en chercher un autre, vous pouvez construire ceux qui finiront par une séquence de $9.$

Comme :

19\times 1 = 19

vous continuez en prenant :

19\times 2 = 38.

Par somme, il vient :

\begin{align*} 19\times 21 &= 19\times 2\times 10 + 19\times 1\\ &=380+19\\ &=399. \end{align*}

Ainsi, $399$ est un nombre magique de $19.$

Vous allez éliminer le chiffre $6$ qui termine le nombre $4066$ comme suit :

\begin{align*} 4066 + 6\times 399 &= 4066+6\times 400 - 6\\ &=4060+2400\\ &=646\times 10. \end{align*}

Compte tenu de la proximité de $646$ avec $399$ vous calculez la différence :

\begin{align*} 646 -399 &= 646-400+1\\ &=247. \end{align*}

A ce stade il reste à utiliser $19$ qui est un nombre magique de $19$ :

\begin{align*} 247 + 7\times 19 &= 247+7\times 20 -7\\ &=240+140\\ &=38\times 10. \end{align*}

Comme $38 = 2\times 19$ vous déduisez que :

$247$ est un multiple de $19$ ;
$646$ est un multiple de $19$ ;
$4066$ est un multiple de $19$ ;
$25\ 935$ est un multiple de $19.$

Concluez

Finalement, $499\ 358$ est un multiple de $19.$

Pour aller plus loin, avec une autre approche

Il a été vu que le nombre $11\ 001$ est un multiple de $19$ au sein de cet article. Ce nombre se révèle excellent pour tester la divisibilité de $499\ 358$ par $19.$ En effet :

\begin{align*} 499\ 358 - 358\times 11001 &=499\ 358 - 358\times 11\ 000 - 358\\ &=499\ 000-3938\ 000\\ &=-1000(3938-499)\\ &=-1000(3938-500+1)\\ &=-1000\times 3439. \end{align*}

Vous êtes passé d’un nombre de $6$ chiffres à un nombre de $4$ chiffres.

Vous retranchez $19$ à $3439$ :

\begin{align*} 3439-19 &= 3420\\ &=342\times 10. \end{align*}

Comme $399$ est un nombre magique de $19$, vous calculez ensuite :

\begin{align*} 399-342 &= 57. \end{align*}

Comme $19\times 3 = 57$ vous déduisez bien que $499\ 358$ est un multiple de $19.$

306. Critères de divisibilité (1/2)

Rédigé par Yannis TRIANTAPHYLIDESon 02/10/202308/10/2023| Pour tous

Dans cet article, vous vous intéressez à déterminer des stratégies pour savoir si un nombre est divisible par certains nombres premiers.

Le nombre $301994$ est-il divisible par $37$ ?

Vous cherchez d’abord un nombre magique qui soit divisible par $37.$

Comme :

37\times 3 = 111

vous déduisez après multiplication par $9$ :

37\times 27 = 999.

Comme $301\times 999$ est un multiple de $37$, vous effectuez l’opération :

\begin{align*} 301994 + 994 \times 999&= 301\ 994 + 994\times 1000 - 994 \\ &= 301\ 000+994\ 000\\ &= 1295\ 000\\ &= 1295\times 1000. \end{align*}

Vous poursuivez :

\begin{align*} 1295 - 999 &= 1295-1000+1\\ &=296. \end{align*}

Puis :

\begin{align*} 296-2\times 111 &= 296-222\\ &=74\\ &=2\times 37. \end{align*}

En définitive, $301994$ est divisible par $37.$

Le nombre $651742$ est-il divisible par $13$ ?

Il s’agit de construire un nombre magique pour $13.$

Après multiplication par $7$ :

13\times 7 = 91.

Du coup :

13\times 70 = 910.

Par somme, il vient :

13\times 77 = 1001.

Maintenant vous décomposez $651742$ :

\begin{align*} 651742 &= 651\times 1000 + 742\\ &= 651\times 1001 + 742 - 651\\ &=651\times 1001 + 91\\ &=651\times 1001+13\times 7. \end{align*}

Vous déduisez que $651742$ est somme de deux multiples de $13$.

En définitive, $651742$ est divisible par $13.$

Le nombre $33031$ est-il divisible par $17$ ?

Vous commencez par :

17\times 3 = 51.

Puis :

17\times 5 = 85.

Vous multipliez par $10$ et vous obtenez :

17\times 50 = 850.

Du coup :

17\times 53 = 901.

Vous éliminez les chiffres des unités et des dizaines de $33031$ par soustraction :

\begin{align*} 33031 - 31\times 901 &= 33000 + 31 - 31\times 901\\ &=33000-31\times 900\\ &=330\times 100 - 279\times 100\\ &=51 \times 100. \end{align*}

Comme $51$ est un multiple de $17$ vous déduisez que $33031$ est un multiple de $17.$

305. Factorisation de certains nombres entiers (3/3)

Rédigé par Yannis TRIANTAPHYLIDESon 21/09/202307/10/2023| Pour tous

Soit $p$ un nombre premier. Vous appellerez nombre magique de $p$ tout multiple de $p$ :

soit qui ne comporte que des $9$ excepté, éventuellement son chiffre le plus à gauche ;
soit un nombre qui finit par une séquence $0\cdots 01$ et comportant à gauche de cette séquence un chiffre non nul.

Exemples. Le nombre $299$ est un nombre magique de $13$, puisque $299 = 13\times 23.$
Le nombre $10\ 001$ est un nombre magique de $73$ puisque $10\ 001 = 73\times 137.$

Attention cependant : $2701 = 73\times 37.$ Or, $2701$ n’est pas magique puisque, à gauche de sa séquence $01$ il comporte deux chiffres au lieu d’un seul.

Note. Un nombre magique de $p$ où $p$ est un nombre premier désigne tout multiple de $p$ de la forme $a\times 10^b \pm 1$ où $a\in\llbracket 1, 9\rrbracket$ et $b\in\NN.$

Pourquoi des nombres magiques ?

Ils sont utiles pour effectuer des tests de divisibilité.

Exemple : est-ce que $2327$ est un multiple de $13$ ?

Il a été cité le nombre magique $299$ qui est un multiple de $13.$ Ainsi, il va être possible d’éliminer les deux derniers chiffres de $2327$ comme suit. Vous ajoutez à $2327$ un multiple de $13$ pour former un nombre qui finit par deux zéros.

\begin{align*} 2327 + 999\times 27 &= 2327 + (1000-1)\times 27\\ &= 2327 + 27000 - 27\\ &=2300+27000\\ &=29300. \end{align*}

Reste à savoir si $293$ est un multiple de $13$ ou non.

Par différence :

\begin{align*} 299-293 = 6. \end{align*}

Comme $6$ n’est pas un multiple de $13$, le nombre $293$ n’en est pas un non plus.

La décomposition en facteurs premiers de $293$ ne fait pas apparaître le nombre $13.$ Comme $29300=293 \times (5\times 2)^2$, la décomposition en facteurs premiers de $29300$ ne fait pas apparaître le nombre premier $13.$

Donc $13$ n’est pas un diviseur de $29300.$ Par suite, $2327$ n’est pas un multiple de $13.$ Ainsi, $13$ sera éliminé de la recherche des nombres premiers divisant $2327.$

Tableau des premiers nombres magiques

Les multiples de $2$, $3$ et $5$ étant rapidement reconnaissables, les nombres premiers $2$, $3$ et $5$ ont été omis dans le tableau. Ci-dessous se trouvent des nombres magiques à $4$ chiffres maximum pour les nombres premiers inférieurs ou égaux à $100$ et supérieurs ou égaux à $7.$

\begin{array}{|c|c|c|c|} \hline p & \text{2 chiffres} & \text{3 chiffres} & \text{4 chiffres}\\ \hline 7 & 21, 49, 91& 301, 399 & 1001, 5999, 8001 \\ \hline 11 & 11, 99 & &1001, 9999 \\ \hline 13 & 39,91 & 299 & 1001 \\ \hline 17 & 51 & 799, 901 & 6001 \\ \hline 19 & 19 & 399 & 7999 \\ \hline 23 & 69 & 299 & 2001 \\ \hline 29 & 29 & 899 & 2001 \\ \hline 31 & 31 & 899 & 3999 \\ \hline 37 & & 999 & \\ \hline 41 & 41 & & \\ \hline 43 & & 301 & 3999 \\ \hline 47 & & 799 & \\ \hline 53 & &901 & \\ \hline 59 & 59 & & \\ \hline 61 & 61 & & \\ \hline 67 & & 201 & \\ \hline 71 & 71 & & \\ \hline 73 & & & \\ \hline 79 & 79 & & \\ \hline 83 & & & \\ \hline 89 & 89 & 801 & \\ \hline 97 & & & \\ \hline \end{array}

Les nombres premiers inférieurs ou égaux à $31$ possèdent plusieurs nombres magiques.

De $37$ jusqu’à $97$ les nombres premiers n’admettent qu’un seul nombre magique ou aucun, à l’exception de $43$ qui en admet deux.

Vous constatez la présence de $3$ nombres premiers délicats, à savoir $73$, $83$ et $97$ qui ne possèdent pas de multiples magiques comportant moins de quatre chiffres.

Pour en savoir davantage, vous poussez la recherche jusqu’à trouver le nombre magique suivant, pour les nombres premiers du tableau précédent n’ayant qu’au plus un seul nombre magique.

Allez plus loin avec les grands nombres

La palme reviendra au nombre premier $83$ qui admet comme premier nombre magique un nombre à $16$ chiffres, ce qui rend en pratique le résultat difficilement applicable.

$999\ 999$ est un nombre magique de $37.$
$99\ 999$ est un nombre magique de $41.$
$300\ 001$ est un nombre magique de $47.$
$40\ 000\ 001$ est un nombre magique de $53.$
$20\ 001$ est un nombre magique de $59.$
$9\ 000\ 001$ est un nombre magique de $61.$
$39\ 999$ est un nombre magique de $67.$
$1\ 999\ 999$ est un nombre magique de $71.$
$10\ 001$ est un nombre magique de $73.$
$9\ 999\ 999\ 999\ 999$ est un nombre magique de $79.$
$2\ 999\ 999\ 999\ 999\ 999$ est un nombre magique de $83.$
$599\ 999\ 999$ est un nombre magique de $97.$

Ces résultats ne sauraient être accompagnés d’une technique permettant de les construire. Vous trouverez ci-dessous le cas d’un nombre magique pour $73.$

Comment construire un nombre magique ?

Soit à trouver un nombre magique de $73$ qui finit par la séquence de chiffres $0\cdots01.$

Vous partez de $73$ et cherchez un chiffre qui lui sera multiplié obtenir un nombre finissant par le chiffre $1.$

Vous n’avez pas le choix c’est le chiffre $7$ que vous devez choisir :

73\times 7 = 511.

Partant de $511$ vous devez trouver un multiple de $73$ qui finit par la séquence $90.$ Là encore le choix est vite réduit :

\begin{align*} 73\times 3 &= 219\\ 73\times 30 &= 2190. \end{align*}

Par somme, il vient :

\begin{align*} 73\times 37 &= 73\times 30 + 73\times 7\\ &=2190+511\\ &=2701. \end{align*}

Pour que le chiffre $7$ de $2701$ passe à $0$, dans l’idée d’avoir une séquence qui finit par $001$, vous n’avez guère le choix :

\begin{align*} 73\times 1 &= 73\\ 73\times 100 &= 7300. \end{align*}

Par somme, il vient :

\begin{align*} 73\times 137 &= 7300+ 2701\\ &=10001. \end{align*}

Concluez

Les nombres magiques resteront utiles et pratiques pour effectuer une décomposition mentale de nombres entiers en produit de facteurs premiers, à condition que le nombre de chiffres ne soit pas trop important.

Les nombres magiques commencent à montrer leurs limites quand il s’agit d’effectuer des tests sur des grands nombres, un domaine qui fait l’objet de nombreux travaux mathématiques encore aujourd’hui.

304. Factorisation de certains nombres entiers (2/3)

Rédigé par Yannis TRIANTAPHYLIDESon 21/09/202330/09/2023| Pour tous

Ce texte se situe dans le prolongement du contenu rédigé dans l'article 303.

Testez le nombre $501$

Comme $501$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $501$ n’est pas divisible par $2.$
La somme des chiffres de $501$ vaut $6$ qui est un multiple de $3$ donc $501$ est divisible par $3.$ La soustraction $501-21 = 480$ permet de se ramener à $48.$ Or, $48-30 = 18.$ Donc $48 = 30+18.$
En factorisant par $3$, vous obtenez $48 = 3\times (10+6) = 3\times 16$ donc $480 = 3\times 160.$ Enfin, $501 = 21+480 = 3\times 7+3\times 160$ donc $501 = 3\times 167.$
La somme des chiffres de $167$ vaut $14$ qui n’est pas un multiple de $3$ donc $167$ n’est pas divisible par $3.$
Le nombre $167$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $167$ par $7.$ En effectuant la soustraction $167-7$ vous trouvez $160.$ Or, ni $16$ et $10$ ne sont des multiples de $7$, donc $160$ n’est pas un multiple de $7$ et $167$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $167$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $7-6+1 = 2$ qui n’est pas multiple de $11.$ Donc $167$ n’est pas un multiple de $11.$
Le nombre premier qui suit est $13.$ Or, $13^2 = 169$ et $169>167$ donc $167$ est un nombre premier.

En définitive :

\boxed{501 = 3\times 167.}

Testez le nombre $599$

Comme $599$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $599$ n’est pas divisible par $2.$
La somme des chiffres de $599$ vaut $23$ qui n’est pas un multiple de $3$ donc $599$ n’est pas divisible par $3.$
Le nombre $599$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $599$ par $7.$ Il a été vu que $399$ est un multiple de $7.$ En effectuant la soustraction $599-399$ vous trouvez $200.$ Or, ni $20$ ni $10$ ne sont des multiples de $7$, donc $200$ n’est pas un multiple de $7$ et $599$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $599$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $9-9+5 = 5$ qui n’est pas multiple de $11.$ Donc $599$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $599$ par $13.$ Il a été vu que $299$ est un multiple de $13.$ En effectuant la soustraction $599-299$ vous arrivez à $300.$ Comme $30$ n’est pas un multiple de $13$ et comme $10$ n’en est pas un non plus, vous déduisez que $300$ n’est pas un multiple de $13.$ Donc $599$ n’est pas un multiple de $13.$
Passez maintenant à la divisibilité de $599$ par $17.$ Le triple de $17$ vaut $51.$ Par somme $599+51 = 650.$ Or, $65$ n’est pas un multiple de $17.$ $10$ n’est pas non plus un multiple de $17$. Donc $650$ n’est pas un multiple de $17.$ Donc $599$ n’est pas un multiple de $17.$
Passez maintenant à la divisibilité de $599$ par $19.$ Par différence $599-19 = 580.$ Or, $58$ n’est pas un multiple de $19.$ $10$ n’est pas non plus un multiple de $19$. Donc $580$ n’est pas un multiple de $19.$ Donc $599$ n’est pas un multiple de $19.$
Passez maintenant à la divisibilité de $599$ par $23.$ Il a été vu que $299$ est un multiple de $23.$ Par différence $599-299 = 300.$ Or, $30$ n’est pas un multiple de $23.$ $10$ n’est pas non plus un multiple de $23$. Donc $300$ n’est pas un multiple de $23.$ Donc $599$ n’est pas un multiple de $23.$
Le nombre premier qui suit est $29.$ Or, $29^2 = 841.$ Comme $841 > 599$ l’analyse est terminée.

\boxed{\text{Le nombre }599\text{ est premier}.}

Testez le nombre $601$

Comme $601$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $601$ n’est pas divisible par $2.$
La somme des chiffres de $601$ vaut $7$ qui n’est pas un multiple de $3$ donc $601$ n’est pas divisible par $3.$
Le nombre $601$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $599$ par $7.$ Il a été vu que $399$ est un multiple de $7.$ En effectuant la somme $601+399$ vous trouvez $1000.$ Or, ni $100$ et ni $10$ ne sont des multiples de $7$, donc $1000$ n’est pas un multiple de $7$ et $601$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $601$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $6-0+1 = 7$ qui n’est pas multiple de $11.$ Donc $601$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $601$ par $13.$ Il a été vu que $299$ est un multiple de $13.$ En effectuant la somme $601+299$ vous arrivez à $900.$ Comme $90$ n’est pas un multiple de $13$ et comme $10$ n’en est pas un non plus, vous déduisez que $900$ n’est pas un multiple de $13.$ Donc $601$ n’est pas un multiple de $13.$
Passez maintenant à la divisibilité de $601$ par $17.$ Le triple de $17$ vaut $51.$ Par différence $601-51 = 550.$ Or, $55$ n’est pas un multiple de $17.$ $10$ n’est pas non plus un multiple de $17$. Donc $550$ n’est pas un multiple de $17.$ Donc $601$ n’est pas un multiple de $17.$
Passez maintenant à la divisibilité de $601$ par $19.$ Par somme, $601+19 = 620.$ Or, $62$ n’est pas un multiple de $19.$ $10$ n’est pas non plus un multiple de $19$. Donc $620$ n’est pas un multiple de $19.$ Donc $601$ n’est pas un multiple de $19.$
Passez maintenant à la divisibilité de $601$ par $23.$ Il a été vu que $299$ est un multiple de $23.$ Par somme $601+299 = 900.$ Or, $90$ n’est pas un multiple de $23.$ $10$ n’est pas non plus un multiple de $23$. Donc $900$ n’est pas un multiple de $23.$ Donc $601$ n’est pas un multiple de $23.$
Le nombre premier qui suit est $29.$ Or, $29^2 = 841.$ Comme $841 > 601$ l’analyse est terminée.

\boxed{\text{Le nombre }601\text{ est premier}.}

Testez le nombre $699$

Comme $699$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $699$ n’est pas divisible par $2.$
La somme des chiffres de $699$ vaut $24$ qui est un multiple de $3$ donc $699$ est divisible par $3$, avec $699=3\times 233.$
La somme des chiffres de $233$ vaut $8$ qui n’est pas un multiple de $3$ donc $233$ n’est pas divisible par $3.$
Le nombre $233$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $233$ par $7.$ Par somme $233+7 = 240.$ Or ni $24$ ni $10$ ne sont des multiples de $7$ donc $240$ n’est pas un multiple de $7.$ $233$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $233$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $3-3+2 = 2$ qui n’est pas multiple de $11.$ Donc $233$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $233$ par $13.$ Par différence, $233-13 = 220.$ Or ni $22$ ni $10$ ne sont des multiples de $13$ donc $220$ n’est pas un multiple de $7.$ $233$ n’en est pas un non plus.
Le nombre premier qui suit est $17$, or $17^2 = 289.$ Comme $289 > 233$ vous déduisez que $233$ est premier.

En définitive :

\boxed{699 = 3\times 233.}

Testez le nombre $701$

Comme $701$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $701$ n’est pas divisible par $2.$
La somme des chiffres de $701$ vaut $8$ qui n’est pas un multiple de $3$ donc $701$ n’est pas divisible par $3.$
Le nombre $701$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $701$ par $7.$ Par somme, $701+399 = 1100.$ Or ni $11$ ni $100$ ne sont des multiples de $7$ donc $1100$ n’est pas un multiple de $7.$ $701$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $701$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $1-0+7 = 8$ qui n’est pas multiple de $11.$ Donc $701$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $701$ par $13.$ Par somme, $701+299 = 1000.$ Or ni $100$ ni $10$ ne sont des multiples de $13$ donc $1000$ n’est pas un multiple de $13.$ $701$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $701$ par $17.$ Par différence, $701-51 = 650.$ Or ni $65$ ni $10$ ne sont des multiples de $17$ donc $650$ n’est pas un multiple de $17.$ $701$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $701$ par $19.$ Par somme, $701+19 = 720.$ Or ni $72$ ni $10$ ne sont des multiples de $19$ donc $720$ n’est pas un multiple de $19.$ $701$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $701$ par $23.$ Par somme, $701+299 = 1000.$ Or ni $100$ ni $10$ ne sont des multiples de $23$ donc $1000$ n’est pas un multiple de $23.$ $701$ n’en est pas un non plus.
Le nombre premier qui suit est $29.$ Or $29^2 = 841.$ Comme $841 > 701$ l’analyse est terminée.

\boxed{\text{Le nombre }701\text{ est premier}.}

Testez le nombre $799$

Comme $799$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $799$ n’est pas divisible par $2.$
La somme des chiffres de $799$ vaut $25$ qui n’est pas un multiple de $3$ donc $799$ n’est pas divisible par $3.$
Le nombre $799$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $799$ par $7.$ Par différence, $799-49 = 750.$ Or ni $75$ ni $10$ ne sont des multiples de $7$ donc $750$ n’est pas un multiple de $7.$ $799$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $799$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $9-9+7 = 7$ qui n’est pas multiple de $11.$ Donc $799$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $799$ par $13.$ Par différence, $799-299 = 500.$ Or ni $50$ ni $10$ ne sont des multiples de $13$ donc $500$ n’est pas un multiple de $13.$ $799$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $799$ par $17.$ Par somme, $799+51 = 850.$ Or $85 = 17\times 5$ donc $850 = 17\times 50.$ Donc $799 = 17\times 47.$
Comme $17^2 = 289$ et comme $289 > 47$ vous déduisez que $47$ est un nombre premier.

En définitive :

\boxed{799 = 17\times 47.}

Testez le nombre $801$

Comme $801$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $801$ n’est pas divisible par $2.$
La somme des chiffres de $801$ vaut $9$ qui est un multiple de $3.$ Par somme $801+99 = 900$ donc $801 = 900-99.$ Après factorisation par $3$ il vient $801 = 3\times 300 – 3\times 33$ d’où $801 = 3\times 267.$
La somme des chiffres de $267$ vaut $3$ qui est un multiple de $3.$ Par somme $267+3 = 270$ donc $267 = 270-3.$ Après factorisation par $3$ il vient $267 = 3\times 90 – 3\times 1$ d’où $267 = 3\times 89.$
La somme des chiffres de $89$ vaut $17$ qui n’est pas un multiple de $3.$ Donc $89$ n’est pas un multiple de $3.$
Le nombre $89$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $89$ par $7.$ Par différence, $89-49 = 40.$ Or ni $4$ ni $10$ ne sont des multiples de $7$ donc $40$ n’est pas un multiple de $7.$ $89$ n’en est pas un non plus.
Le nombre premier qui suit est $11.$ Or $11^2 = 121$ et $121>89$ donc $89$ est premier.

En définitive :

\boxed{801 = 3\times 3\times 89.}

Testez le nombre $899$

Comme $899$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $899$ n’est pas divisible par $2.$
La somme des chiffres de $899$ vaut $26$ qui n’est pas un multiple de $3.$ Donc $899$ n’est pas un multiple de $3.$
Le nombre $899$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $899$ par $7.$ Par différence, $899-399 = 500.$ Or ni $50$ ni $10$ ne sont des multiples de $7$ donc $899$ n’est pas un multiple de $7.$
Passez maintenant à la divisibilité de $899$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $9-9+8 = 8$ qui n’est pas multiple de $11.$ Donc $899$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $899$ par $13.$ Par différence, $899-299 = 600.$ Or ni $60$ ni $10$ ne sont des multiples de $13$ donc $600$ n’est pas un multiple de $13.$ $899$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $899$ par $19.$ Par différence, $899-19 = 880.$ Or ni $88$ ni $10$ ne sont des multiples de $19$ donc $880$ n’est pas un multiple de $19$. Ainsi $899$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $899$ par $29.$ Par différence, $899-29 = 870.$ Or $87 = 3\times 29$ donc $870 = 29\times 30$ et $899 = 29\times 31.$
$31$ n’étant pas divisible par $29$ vous retrouvez que $31$ est un nombre premier.

Du coup :

\boxed{899 = 29\times 31.}

Testez le nombre $901$

Comme $901$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $901$ n’est pas divisible par $2.$
La somme des chiffres de $901$ vaut $10$ qui n’est pas un multiple de $3.$ Donc $901$ n’est pas un multiple de $3.$
Le nombre $901$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $901$ par $7.$ Par différence, $901-301 = 600.$ Or ni $60$ ni $10$ ne sont des multiples de $7$ donc $901$ n’est pas un multiple de $7.$
Passez maintenant à la divisibilité de $901$ par $11.$ En effectuant la somme alternée de ses chiffres en partant des unités, il vient $1-0+9 = 10$ qui n’est pas multiple de $11.$ Donc $901$ n’est pas un multiple de $11.$
Passez maintenant à la divisibilité de $901$ par $13.$ Par somme, $901+299 = 1200.$ Or ni $12$ ni $100$ ne sont des multiples de $13$ donc $1200$ n’est pas un multiple de $13.$ $901$ n’en est pas un non plus.
Passez maintenant à la divisibilité de $901$ par $17.$ Par somme, $901+799 = 1700.$ Or $799 = 17\times 47$ et $1700 = 17\times 100$ donc par différence $901 = 1700-799 = 17\times 100 – 17\times 47$ d’où $901 = 17\times 53.$
Par somme $53+17 = 70.$ Or ni $7$ ni $10$ ne sont des multiples de $17$ donc $53$ n’est pas divisible par $17.$
Le nombre premier qui suit est $19.$ Or $19^2 = 361$ et $361 > 53$ donc $53$ est premier.

En définitive :

\boxed{901 = 17\times 53.}

Testez le nombre $999$

Comme $999$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $999$ n’est pas divisible par $2.$
D’autre part, $999 = 3\times 333.$
De même $333 = 3\times 111.$
La somme des chiffres de $111$ est $3$ donc $111$ est divisible par $3.$ Par somme $111+9 = 120$ donc par différence $111 = 120-9 = 3\times 40-4\times 3 = 3\times 37.$
La somme des chiffres de $37$ est $10$ qui n’est pas un multiple de $3$ donc $37$ n’est pas divisible par $3.$
Le nombre $37$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Comme $7^2 = 49$ et comme $49>37$ vous retrouvez que $37$ est un nombre premier.

Finalement :

\boxed{999 = 3\times 3\times 3 \times 37.}

303. Factorisation de certains nombres entiers (1/3)

Rédigé par Yannis TRIANTAPHYLIDESon 19/09/202322/09/2023| Pour tous

Vous vous intéressez à des nombres entiers de deux sortes :

ceux dont les derniers chiffres ne sont que des $9$ comme $99$, $199$…
ceux dont le dernier chiffre est $1$, le premier chiffre étant supérieur à $1$ et tous les autres égaux à $0$ (exemples : $101$, $201$…)

Pour de tels nombres vous allez chercher ceux qui sont premiers et si ce n’est pas le cas, vous les factoriserez comme produits de nombres premiers.

Quelques généralités

Nombres premiers

Pour rappel, un entier naturel est dit premier, si et seulement si, il admet exactement deux diviseurs. Ainsi $1$ n’est pas premier car il admet un seul diviseur. $2$ est premier car il n’est divisible que par $1$ et $2.$ Par contre, $9$ n’est pas premier puisqu’il est divisible par $1$, $3$ et $9.$

Une propriété essentielle des nombres premiers réside dans le lemme d’Euclide. Si $p$ est un nombre premier divisant un produit $ab$ de deux entiers naturels $a$ et $b$, alors $p$ divise $a$ ou $p$ divise $b.$ Une preuve directe de ce résultat se trouve dans le contenu rédigé dans l'article 126. Elle utilise des outils plus avancés que ceux décrits dans cet article.

La contraposée de ce lemme sera beaucoup utilisée dans cet article : si $a$ et $b$ sont deux entiers qui ne sont ni l’un ni l’autre multiples d’un nombre premier $p$, alors le produit $ab$ n’est pas un multiple de $p.$

Tout nombre entier supérieur ou égal à $2$ qui n’est pas premier est dit composé. Tout nombre composé admet un diviseur premier inférieur ou égal à sa racine carrée. Ce résultat est important car il permet d’en déduire, toujours par contraposée, que si un nombre supérieur ou égal à $2$ n’admet aucun diviseur premier inférieur ou égal à sa racine carrée, alors il est premier.

Tests de divisibilité par $2$, $3$, $5$ et $11$

Un nombre entier est divisible par $2$, si et seulement si, son chiffre des unités est pair.

Un nombre entier est divisible par $3$, si et seulement si, la somme de ses chiffres est divisible par $3.$

Un nombre entier est divisible par $5$, si et seulement si, son chiffre des unités est $0$ ou $5.$

Un nombre entier est divisible par $11$, si et seulement si, la somme alternée de ses chiffres en partant des unités est divisible par $11.$

La méthode qui sera utilisée suppose que le nombre à tester ne soit pas trop grand. Elle effectue des tests de divisibilité par des nombres premiers.

Testez le nombre $99$

Vous allez systématiquement suivre la démarche suivante, en essayant de voir si $99$ peut être d’abord divisé par un nombre premier, en commençant par $2$.

Comme $99$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $99$ n’est pas divisible par $2$.
Vous passez au nombre premier suivant qui est $3.$
Il apparaît que $99$ est divisible par $3$, puisque $99 = 3\times 33.$
Vous recommencez maintenant avec le nombre $33$, mais inutile de repartir du départ pour les nombres premiers. Vous êtes toujours à $3$ comme nombre premier. Vous testez si $33$ est un divisible par $3$. C’est bien le cas puisque $33 = 3\times 11.$
Continuant avec $11$, vous souhaitez savoir s’il est divisible par $3$. La somme de ses chiffres est égale à $2$ qui n’est pas un multiple de $3$, donc $11$ n’est pas divisible par $3.$ Il vous faut donc passer au nombre premier qui suit, qui est $5.$
Or, comme $5^2 = 25$ et que $25 > 11$ il apparaît que $11$ ne peut être composé. Donc il est premier.

En définitive, une factorisation en produit de nombres premiers de $99$ est :

\boxed{99 = 3\times 3 \times 11.}

Testez le nombre $101$

Comme $101$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $101$ n’est pas divisible par $2.$
La somme des chiffres de $101$ vaut $2$ qui n’est pas un multiple de $3$ donc $101$ n’est pas divisible par $3.$
Le nombre $101$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $101$ par $7.$ Comme $70$ est un multiple de $7$, vous calculez la différence $101-70 = 31.$ Vous poursuivez avec $31$ auquel vous retirez un multiple de $7$. Le nombre $28$ convient bien. $31-28 = 3.$ Comme $3$ n’est pas un multiple de $7$, il en résulte que $31$ ne l’est pas non plus et donc $101$ non plus. $101$ n’est pas divisible par $7.$
Le nombre premier qui suit est $11.$ Or $11^2 = 121$ et $121 > 101.$ Par suite, $101$ ne peut être composé.

\boxed{\text{Le nombre }101\text{ est premier}.}

Testez le nombre $199$

Comme $199$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $199$ n’est pas divisible par $2.$
La somme des chiffres de $199$ vaut $19$ qui n’est pas un multiple de $3$ donc $199$ n’est pas divisible par $3.$
Le nombre $199$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $199$ par $7.$ Comme $210$ est un multiple de $7$, vous calculez la différence $210-199 = 11.$ Comme $11$ n’est pas un multiple de $7$, il en résulte que $199$ n’est pas divisible par $7.$
Le nombre premier qui suit est $11.$ Effectuez la somme alternée des chiffres de $199$ en commençant par son chiffre des unités. Cela fournit $9-9+1 = 1.$ Comme $1$ n’est pas un multiple de $11$ vous déduisez que $199$ n’est pas un multiple de $11.$
Le nombre premier qui suit est $13.$ Comme $39$ est un multiple de $13$ vous effectuez la soustraction $199-39 = 160.$ Maintenant, $16$ n’est pas un multiple de $13.$ Or $10$ n’est pas un multiple de $13$ non plus, donc, par contraposée du lemme d’Euclide, vous déduisez que $160$ n’est pas un multiple de $13.$ Donc $199$ n’est pas un multiple de $13.$
Le nombre premier qui suit est $17.$ Or, $17^2 = 289$ et $289>199$ donc $199$ n’est pas composé.

\boxed{\text{Le nombre }199\text{ est premier}.}

Testez le nombre $201$

Comme $201$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $201$ n’est pas divisible par $2.$
La somme des chiffres de $201$ vaut $3$ donc $201$ est divisible par $3.$ Vous cherchez à déterminer le quotient de la division de $201$ par $3.$ En ajoutant $9$, multiple de $3$ à $201$, vous obtenez $201+9 = 210$ soit $210-9=201.$ En divisant par $3$ cette égalité, il vient $70-3 = 67.$ Donc $201 = 3\times 67.$
La somme des chiffres de $67$ est égale à $13$ qui n’est pas un multiple de $3$ donc $67$ n’est pas un multiple de $3.$
Le nombre $67$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $67$ par $7.$ Comme $70$ est un multiple de $7$, vous effectuez la soustraction $70-67=3$ qui n’est pas un multiple de $7.$ Donc $67$ n’est pas un multiple de $7.$
Le nombre premier qui suit est $11$ et $11^2=121.$ Or $121 > 67$ donc $67$ est un nombre premier.

En définitive, une factorisation en produit de nombres premiers de $201$ est :

\boxed{201 = 3\times 67.}

Testez le nombre $299$

Comme $299$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $299$ n’est pas divisible par $2.$
La somme des chiffres de $299$ vaut $20$ qui n’est pas un multiple de $3$ donc $299$ n’est pas divisible par $3.$
Le nombre $299$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $299$ par $7.$ Comme $49$ est un multiple de $7$, vous calculez la différence $299-49 = 250.$ Comme $25$ n’est pas un multiple de $7$, et comme $10$ n’est pas un multiple de $7$, la contraposée du lemme d’Euclide permet d’en déduire que $299$ n’est pas divisible par $7.$
Le nombre premier qui suit est $11.$ Vous calculez la somme alternée des chiffres de $299$ en partant du chiffre des unités. $9-9+2 = 2.$ Or $2$ n’est pas un multiple de $11$ donc $299$ n’est pas un multiple de $11.$
Le nombre premier qui suit est $13.$ Comme $39$ est un multiple de $13$ vous effectuez la soustraction $299-39 = 260.$ Or $26$ est un multiple de $13.$ De $26 = 13\times 2$ vous déduisez $260 = 13\times 20.$ Or $39 = 13\times 3.$ Par somme vous déduisez $299 = 13\times 23.$
Comme $13^2 = 169$ et comme $169 > 23$, vous déduisez que $23$ est un nombre premier.

En définitive, une factorisation en produit de nombres premiers de $299$ est :

\boxed{299 = 13\times 23.}

Testez le nombre $301$

Comme $301$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $301$ n’est pas divisible par $2.$
La somme des chiffres de $301$ vaut $4$ qui n’est pas un multiple de $3$ donc $301$ n’est pas divisible par $3.$
Le nombre $301$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $301$ par $7.$ Comme $21$ est un multiple de $7$, vous calculez la différence $301-21= 280.$ Comme $28 = 7\times 4$ il vient $280 = 7\times 40.$ Or $21 = 7\times 3$ et par somme $301 = 7\times 43.$
Comme $43$ n’est pas un multiple de $7$ et comme $7^2 = 49$ vous avez $49 > 43$ donc $43$ est un nombre premier.

En définitive, une factorisation en produit de nombres premiers de $301$ est :

\boxed{301 = 7\times 43.}

Testez le nombre $399$

Comme $399$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $399$ n’est pas divisible par $2.$
La somme des chiffres de $399$ vaut $21$ qui est un multiple de $3$. En décomposant vous avez $399 = 300+99$ d’où après division par $3$, $100+33 = 133$ donc $399=3\times 133.$
La somme des chiffres du nombre $133$ est égale à $7$ qui n’est pas un multiple de $3$ donc $133$ n’est pas divisible par $3.$
Le nombre $133$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $133$ par $7.$ Partant de $21 = 7\times 3$, après multiplication par $3$, il vient $63 = 7\times 9.$ Par soustraction, $133-63 = 70$ qui est un multiple de $7$ donc $133$ est un multiple de $7.$ La décomposition $133 = 63+70$ fournit, après division par $7$, $9+10 = 19.$ Donc $133 = 7\times 19.$
Comme $7^2 = 49$ et comme $49 > 19$ il s’ensuit que $19$ est un nombre premier.

En définitive, une factorisation en produit de nombres premiers de $399$ est :

\boxed{399 = 3\times 7\times 19.}

Testez le nombre $401$

Comme $401$ a son chiffre des unités qui est $1$, un chiffre impair, vous déduisez que $401$ n’est pas divisible par $2.$
La somme des chiffres de $401$ vaut $5$ qui n’est pas un multiple de $3$ donc $401$ n’est pas divisible par $3.$
Le nombre $401$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $401$ par $7.$ Partant de $399$ qui est un multiple de $7$, vous effectuez la soustraction $401-399 = 2.$ $2$ n’étant pas un multiple de $7$ vous déduisez que $401$ n’est pas un multiple de $7.$
Le nombre premier qui suit est $11.$ Vous calculez la somme alternée des chiffres de $401$ en partant du chiffre des unités. $1-0+4 = 5.$ Or $5$ n’est pas un multiple de $11$ donc $401$ n’est pas un multiple de $11.$
Le nombre premier qui suit est $13.$ Comme $39$ est un multiple de $13$ vous effectuez l’addition $401+39 = 440.$ Or, ni $44$ ni $10$ ne sont des multiples de $13.$ Par contraposée du lemme d’Euclide, le produit $440$ n’est pas un multiple de $13$ donc $401$ n’est pas un multiple de $13.$
Le nombre premier qui suit est $17.$ Comme $51 = 17\times 3$ vous effectuez la soustraction $401-51 = 350.$ Or, $35$ n’est pas un multiple de $17.$ $10$ n’en est pas un non plus. Par contraposée du lemme d’Euclide, le produit $350$ n’est pas un multiple de $17$ donc $401$ n’est pas un multiple de $17.$
Le nombre premier qui suit est $19.$ Vous effectuez l’addition $401+19 =420.$ Or, $42$ n’est pas un multiple de $19.$ $10$ n’en est pas un non plus. Par contraposée du lemme d’Euclide, le produit $420$ n’est pas un multiple de $19$ donc $401$ n’est pas un multiple de $19.$
Le nombre premier qui suit est $23.$ Or $23^2 = 529.$ Comme $529>401$ vous aboutissez à la conclusion suivante.

\boxed{\text{Le nombre }401\text{ est premier}.}

Testez le nombre $499$

Comme $499$ a son chiffre des unités qui est $9$, un chiffre impair, vous déduisez que $499$ n’est pas divisible par $2.$
La somme des chiffres de $499$ vaut $22$ qui n’est pas un multiple de $3$ donc $499$ n’est pas divisible par $3.$
Le nombre $499$ ne finit ni par $0$, ni par $5$ donc il n’est pas divisible par $5.$
Passez maintenant à la divisibilité de $499$ par $7.$ Partant de $399$ qui est un multiple de $7$, vous effectuez la soustraction $499-399 = 100.$ $10$ n’étant pas un multiple de $7$, par produit de $10$ avec lui-même, la contraposée du lemme d’Euclide permet de déduire que $100$ n’est pas un multiple de $7.$ Le nombre $499$ n’est pas un multiple de $7.$
Le nombre premier qui suit est $13.$ Un nombre utile est ici $299 = 13\times 23.$ vous effectuez la soustraction $499-299 = 200.$ Comme $20$ et $10$ ne sont pas des multiples de $13$, le produit $200$ n’en est pas un non plus, donc $499$ n’est pas un multiple de $13.$
Le nombre premier qui suit est $17.$ Un multiple commode de $17$ est $51.$ Par somme $499+51 = 550.$ Or, $5$ et $11$ ne sont pas des multiples de $17$ donc $55$ n’en est pas un. $10$ n’est pas un multiple de $17$ donc $550$ non plus. Du coup, $499$ n’est pas un multiple de $17.$
Le nombre premier qui suit est $19.$ Or, $399$ est un multiple de $19.$ Vous formez la différence $499-399 = 100.$
Comme $10$ et $10$ ne sont pas des multiples de $19$, le produit $100$ n’est pas un multiple de $19.$ Donc $499$ n’est pas un multiple de $19.$
Le nombre premier qui suit est $23.$ Comme $23^2 = 529$ et comme $529>499$ vous en déduisez ce qui suit.

\boxed{\text{Le nombre }499\text{ est premier}.}