Mathématiques · Arithmétique dans ℤ

Arithmétique dans ℤ

Divisibilité, division euclidienne, congruences, Z/nZ, nombres premiers, PGCD, PPCM et algorithme d’Euclide.

Niveau
1ère Bac
Session
Semestre 2
Cours الدرس

I. Divisibilité dans \(\mathbb{Z}\)

Définition

Soient \(a\) et \(b\) deux entiers relatifs. On dit que \(a\) divise \(b\) (ou que \(b\) est un multiple de \(a\)) s’il existe \(k\in\mathbb{Z}\) tel que \(b=ka\). On note \(a\mid b\).

✓ Les diviseurs de \(12\) dans \(\mathbb{Z}\) sont \(\pm1\), \(\pm2\), \(\pm3\), \(\pm4\), \(\pm6\), \(\pm12\) ; tout entier divise \(0\) ; \(1\) et \(-1\) divisent tout entier.

✓ \(a\) et \(-a\) ont les mêmes diviseurs et les mêmes multiples : on se ramène souvent aux entiers naturels.

Propriétés

Pour tous entiers relatifs \(a\), \(b\), \(c\) :

✓ \(a\mid a\) ; si \(a\mid b\) et \(b\mid c\) alors \(a\mid c\) ;

✓ si \(a\mid b\) et \(b\mid a\) alors \(|a|=|b|\) ; si \(a\mid b\) et \(b\ne0\) alors \(|a|\le|b|\) ;

✓ si \(a\mid b\) et \(a\mid c\), alors \(a\mid(bu+cv)\) pour tous \(u,v\in\mathbb{Z}\) ;

✓ si \(a\mid b\), alors \(ac\mid bc\).

Démonstration

Troisième propriété : \(b=ka\) et \(c=k^{\prime}a\) donnent \(bu+cv=(ku+k^{\prime}v)a\) avec \(ku+k^{\prime}v\in\mathbb{Z}\).

Application 1

1) Montrer que pour tout \(n\in\mathbb{Z}\), \(n(n+1)\) est pair et que \(n^{3}-n\) est divisible par \(6\).

2) Déterminer les entiers relatifs \(n\) tels que \(n+3\) divise \(2n+11\).

3) Montrer que si \(a\mid(3n+2)\) et \(a\mid(5n+3)\), alors \(a\mid1\). Que peut-on en déduire ?

Solution :

1)

Parmi \(n\) et \(n+1\), l’un est pair : \(2\mid n(n+1)\). Ensuite \(n^{3}-n=(n-1)n(n+1)\) est le produit de trois entiers consécutifs : l’un est multiple de \(3\) et l’un au moins est pair, donc le produit s’écrit \(3k\) et il est pair ; \(k\) est alors pair, et le produit est multiple de \(6\).

2)

\(2n+11=2(n+3)+5\). Si \((n+3)\mid(2n+11)\), alors \((n+3)\mid[(2n+11)-2(n+3)]=5\). Donc \(n+3\in\{-5;-1;1;5\}\), soit \(n\in\{-8;-4;-2;2\}\). Réciproquement ces valeurs conviennent (\(n=2\) : \(5\mid15\) ; \(n=-2\) : \(1\mid7\) ; \(n=-4\) : \(-1\mid3\) ; \(n=-8\) : \(-5\mid-5\)).

3)

\(a\mid[3(5n+3)-5(3n+2)]=-1\), donc \(a=\pm1\) : les seuls diviseurs communs de \(3n+2\) et \(5n+3\) sont \(1\) et \(-1\).

Application 2

1) Déterminer les couples \((x;y)\) d’entiers relatifs tels que \(xy-2x-3y=1\).

2) Déterminer les entiers naturels \(x\) et \(y\) tels que \(x^{2}-y^{2}=15\).

Solution :

1)

\(xy-2x-3y+6=(x-3)(y-2)\), donc l’équation s’écrit \((x-3)(y-2)=7\). Les diviseurs de \(7\) donnent \((x-3;y-2)\in\{(1;7);(7;1);(-1;-7);(-7;-1)\}\), soit \((x;y)\in\{(4;9);(10;3);(2;-5);(-4;1)\}\).

2)

\((x-y)(x+y)=15\) avec \(0\le x-y\le x+y\) : \((x-y;x+y)\in\{(1;15);(3;5)\}\), d’où \((x;y)\in\{(8;7);(4;1)\}\).

II. Division euclidienne

Théorème

Soient \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^{*}\). Il existe un unique couple \((q;r)\) d’entiers relatifs tel que :

\[a=bq+r\quad\text{et}\quad0\le r\lt b\]

\(q\) est le quotient et \(r\) le reste de la division euclidienne de \(a\) par \(b\). On a \(b\mid a\iff r=0\).

Démonstration

Existence : \(q=E(\frac{a}{b})\) vérifie \(q\le\frac{a}{b}\lt q+1\), donc \(bq\le a\lt bq+b\), et \(r=a-bq\) convient. Unicité : si \(a=bq+r=bq^{\prime}+r^{\prime}\), alors \(b|q-q^{\prime}|=|r^{\prime}-r|\lt b\), donc \(q=q^{\prime}\), puis \(r=r^{\prime}\).

Remarque

Dans la division par \(b\), tout entier s’écrit sous l’une des formes \(bk\), \(bk+1\), …, \(bk+(b-1)\) (\(k\in\mathbb{Z}\)) : on peut raisonner en distinguant ces \(b\) cas.

Application 3

1) Effectuer la division euclidienne de \(2026\) par \(17\), puis celle de \(-2026\) par \(17\).

2) Dans la division euclidienne de \(a\) par \(b\), le quotient est \(12\) et le reste \(7\). Sachant que \(a+b=228\), déterminer \(a\) et \(b\).

3) Montrer que pour tout \(n\in\mathbb{Z}\), \(n(n^{2}+2)\) est divisible par \(3\).

Solution :

1)

\(17\times119=2023\) : \(2026=17\times119+3\) avec \(0\le3\lt 17\). Alors \(-2026=17\times(-119)-3=17\times(-120)+14\) avec \(0\le14\lt 17\) : quotient \(-120\), reste \(14\).

2)

\(a=12b+7\) avec \(7\lt b\). Alors \(13b+7=228\), \(b=17\) et \(a=211\) ; on a bien \(7\lt 17\).

3)

Si \(n=3k\) : évident. Si \(n=3k+1\) : \(n^{2}+2=9k^{2}+6k+3=3(3k^{2}+2k+1)\). Si \(n=3k+2\) : \(n^{2}+2=9k^{2}+12k+6=3(3k^{2}+4k+2)\). Dans tous les cas, \(3\) divise le produit.

Application 4

1) Montrer que le carré de tout entier est de la forme \(4k\) ou \(4k+1\) (\(k\in\mathbb{Z}\)).

2) En déduire qu’un entier de la forme \(4k+3\) n’est jamais la somme de deux carrés d’entiers.

3) Montrer que le carré de tout entier impair est de la forme \(8k+1\).

Solution :

1)

Si \(n=2m\) : \(n^{2}=4m^{2}\). Si \(n=2m+1\) : \(n^{2}=4(m^{2}+m)+1\).

2)

La somme de deux carrés est de la forme \(4k\), \(4k+1\) ou \(4k+2\) (restes \(0+0\), \(0+1\), \(1+1\)) : jamais \(4k+3\).

3)

\((2m+1)^{2}=4m(m+1)+1\) et \(m(m+1)\) est pair : \(m(m+1)=2k\), d’où \((2m+1)^{2}=8k+1\).

III. Congruences modulo \(n\)

Définition

Soit \(n\in\mathbb{N}^{*}\). Deux entiers \(a\) et \(b\) sont congrus modulo \(n\) si \(n\mid(a-b)\). On note \(a\equiv b\ [n]\).

✓ \(a\equiv b\ [n]\) si et seulement si \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\) ;

✓ si \(r\) est le reste de la division de \(a\) par \(n\), alors \(a\equiv r\ [n]\) ; \(n\mid a\iff a\equiv0\ [n]\).

Propriétés

Pour tous entiers \(a\), \(b\), \(c\), \(d\) et tout \(k\in\mathbb{N}\) :

✓ \(a\equiv a\ [n]\) ; si \(a\equiv b\ [n]\) alors \(b\equiv a\ [n]\) ; si \(a\equiv b\ [n]\) et \(b\equiv c\ [n]\) alors \(a\equiv c\ [n]\) ;

✓ si \(a\equiv b\ [n]\) et \(c\equiv d\ [n]\) : \(a+c\equiv b+d\ [n]\) et \(ac\equiv bd\ [n]\) ;

✓ si \(a\equiv b\ [n]\) : \(a^{k}\equiv b^{k}\ [n]\).

Démonstration

Produit : \(ac-bd=a(c-d)+d(a-b)\) est une somme de multiples de \(n\). Puissance : récurrence sur \(k\) à partir du produit.

Application 5

1) Déterminer le reste de la division euclidienne de \(2^{2026}\) par \(7\).

2) Déterminer le chiffre des unités de \(7^{2026}\).

3) Montrer que pour tout \(n\in\mathbb{N}\), \(3^{2n}-2^{n}\) est divisible par \(7\), et que \(2^{3n}-1\) est divisible par \(7\).

Solution :

1)

\(2^{3}=8\equiv1\ [7]\) et \(2026=3\times675+1\) : \(2^{2026}=(2^{3})^{675}\times2\equiv1\times2\ [7]\). Le reste est \(2\).

2)

On travaille modulo \(10\) : \(7^{2}=49\equiv-1\ [10]\), donc \(7^{4}\equiv1\ [10]\). \(2026=4\times506+2\) : \(7^{2026}\equiv7^{2}\equiv9\ [10]\). Le chiffre des unités est \(9\).

3)

\(3^{2n}=9^{n}\) et \(9\equiv2\ [7]\), donc \(9^{n}\equiv2^{n}\ [7]\) et \(7\mid(3^{2n}-2^{n})\). De même \(2^{3n}=8^{n}\equiv1^{n}=1\ [7]\).

Application 6

On pose, pour tout \(n\in\mathbb{N}\), \(u_{n}=4^{n}+15n-1\).

1) Calculer \(u_{0}\), \(u_{1}\), \(u_{2}\) et vérifier qu’ils sont divisibles par \(9\).

2) Montrer que \(u_{n+1}=4u_{n}-45n+18\), puis démontrer par récurrence que \(9\mid u_{n}\) pour tout \(n\).

Solution :

1)

\(u_{0}=0\), \(u_{1}=18\), \(u_{2}=45\) : tous multiples de \(9\).

2)

\(u_{n+1}=4\times4^{n}+15n+14\) et \(4u_{n}=4\times4^{n}+60n-4\), d’où \(u_{n+1}-4u_{n}=-45n+18\). Si \(u_{n}\equiv0\ [9]\), alors \(u_{n+1}\equiv4\times0-45n+18\equiv0\ [9]\) car \(45\) et \(18\) sont multiples de \(9\). Comme \(u_{0}=0\), la propriété est vraie pour tout \(n\).

Application 7

1) Dresser le tableau des restes de \(n^{2}\) modulo \(5\) suivant le reste de \(n\) modulo \(5\).

2) En déduire que l’équation \(x^{2}-5y^{2}=3\) n’a pas de solution dans \(\mathbb{Z}^{2}\).

3) Résoudre dans \(\mathbb{Z}\) la congruence \(3x\equiv2\ [5]\).

Solution :

1)

\(n\equiv\ldots\ [5]\)\(0\)\(1\)\(2\)\(3\)\(4\)
\(n^{2}\equiv\ldots\ [5]\)\(0\)\(1\)\(4\)\(4\)\(1\)

2)

Si \(x^{2}-5y^{2}=3\), alors \(x^{2}\equiv3\ [5]\), ce qui est impossible d’après le tableau.

3)

On essaie \(x\equiv0,1,2,3,4\ [5]\) : \(3x\equiv0,3,1,4,2\). Donc \(3x\equiv2\ [5]\iff x\equiv4\ [5]\), c’est-à-dire \(x=5k+4\) (\(k\in\mathbb{Z}\)).

1. Critères de divisibilité

Propriété

Soit \(N=\overline{a_{p}a_{p-1}\ldots a_{1}a_{0}}=a_{p}10^{p}+\ldots+a_{1}10+a_{0}\) un entier écrit en base dix.

✓ \(10\equiv1\ [3]\) et \(10\equiv1\ [9]\) : \(N\equiv a_{p}+\ldots+a_{1}+a_{0}\) modulo \(3\) et modulo \(9\) ; \(N\) est divisible par \(3\) (resp. \(9\)) si et seulement si la somme de ses chiffres l’est.

✓ \(10\equiv-1\ [11]\) : \(N\equiv a_{0}-a_{1}+a_{2}-\ldots\ [11]\) ; \(N\) est divisible par \(11\) si et seulement si la somme alternée de ses chiffres (à partir des unités) l’est.

✓ \(N\equiv a_{0}\ [10]\) et \(N\equiv\overline{a_{1}a_{0}}\ [4]\) (car \(100\equiv0\ [4]\)).

Application 8

1) Le nombre \(123456789\) est-il divisible par \(9\) ? par \(4\) ?

2) Le nombre \(918082\) est-il divisible par \(11\) ?

3) Déterminer les chiffres \(x\) et \(y\) pour que le nombre \(\overline{3x52y}\) soit divisible par \(4\) et par \(9\).

Solution :

1)

Somme des chiffres \(45\), divisible par \(9\) : oui. Les deux derniers chiffres forment \(89\), non divisible par \(4\) : non.

2)

Somme alternée à partir des unités : \(2-8+0-8+1-9=-22\), divisible par \(11\) : oui (\(918082=11\times83462\)).

3)

Divisible par \(4\) : \(\overline{2y}\in\{20;24;28\}\), soit \(y\in\{0;4;8\}\). Divisible par \(9\) : \(3+x+5+2+y=10+x+y\) multiple de \(9\), soit \(x+y\in\{8;17\}\). Couples : \((x;y)\in\{(8;0);(4;4);(0;8);(9;8)\}\), nombres \(38520\), \(34524\), \(30528\), \(39528\).

IV. L’ensemble \(\mathbb{Z}/n\mathbb{Z}\)

Définition

Soit \(n\ge2\). Pour \(a\in\mathbb{Z}\), la classe de \(a\) modulo \(n\) est l’ensemble \(\overline{a}=\{b\in\mathbb{Z}\ /\ b\equiv a\ [n]\}=\{a+kn\ /\ k\in\mathbb{Z}\}\). Il y a exactement \(n\) classes, celles des restes possibles :

\[\mathbb{Z}/n\mathbb{Z}=\left\{\overline{0};\overline{1};\ldots;\overline{n-1}\right\}\]

On a \(\overline{a}=\overline{b}\iff a\equiv b\ [n]\). On définit \(\overline{a}+\overline{b}=\overline{a+b}\) et \(\overline{a}\times\overline{b}=\overline{ab}\) (ces définitions ne dépendent pas des représentants, grâce aux propriétés des congruences).

Exemple

Table d’addition de \(\mathbb{Z}/5\mathbb{Z}\) :

\(+\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)\(\overline{4}\)
\(\overline{0}\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)\(\overline{4}\)
\(\overline{1}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)\(\overline{4}\)\(\overline{0}\)
\(\overline{2}\)\(\overline{2}\)\(\overline{3}\)\(\overline{4}\)\(\overline{0}\)\(\overline{1}\)
\(\overline{3}\)\(\overline{3}\)\(\overline{4}\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)
\(\overline{4}\)\(\overline{4}\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)

Table de multiplication de \(\mathbb{Z}/5\mathbb{Z}\) :

\(\times\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)\(\overline{4}\)
\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)
\(\overline{1}\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)\(\overline{4}\)
\(\overline{2}\)\(\overline{0}\)\(\overline{2}\)\(\overline{4}\)\(\overline{1}\)\(\overline{3}\)
\(\overline{3}\)\(\overline{0}\)\(\overline{3}\)\(\overline{1}\)\(\overline{4}\)\(\overline{2}\)
\(\overline{4}\)\(\overline{0}\)\(\overline{4}\)\(\overline{3}\)\(\overline{2}\)\(\overline{1}\)

Application 9

1) Dans \(\mathbb{Z}/7\mathbb{Z}\), résoudre l’équation \(\overline{3}x+\overline{2}=\overline{0}\).

2) Dans \(\mathbb{Z}/6\mathbb{Z}\), calculer \(\overline{2}\times\overline{3}\). Que remarque-t-on ?

3) Résoudre dans \(\mathbb{Z}/8\mathbb{Z}\) l’équation \(x^{2}=\overline{1}\).

Solution :

1)

\(\overline{3}x=-\overline{2}=\overline{5}\). Comme \(\overline{3}\times\overline{5}=\overline{15}=\overline{1}\), on multiplie par \(\overline{5}\) : \(x=\overline{25}=\overline{4}\). Vérification : \(\overline{12}+\overline{2}=\overline{14}=\overline{0}\).

2)

\(\overline{2}\times\overline{3}=\overline{6}=\overline{0}\) : dans \(\mathbb{Z}/6\mathbb{Z}\), un produit peut être nul sans qu’aucun facteur soit nul.

3)

Les carrés de \(\overline{0}\), …, \(\overline{7}\) sont \(\overline{0}\), \(\overline{1}\), \(\overline{4}\), \(\overline{1}\), \(\overline{0}\), \(\overline{1}\), \(\overline{4}\), \(\overline{1}\) : les solutions sont \(\overline{1}\), \(\overline{3}\), \(\overline{5}\), \(\overline{7}\).

Application 10

1) Résoudre dans \(\mathbb{Z}/6\mathbb{Z}\) l’équation \(x^{2}+x=\overline{0}\). Combien de solutions trouve-t-on ? Comparer avec l’équation \(x^{2}+x=0\) dans \(\mathbb{R}\).

2) Résoudre dans \(\mathbb{Z}/5\mathbb{Z}\) l’équation \(x^{2}+x=\overline{0}\), puis l’équation \(x^{2}=\overline{2}\).

Solution :

1)

On calcule \(x(x+1)\) pour \(x=\overline{0}\), …, \(\overline{5}\) : \(\overline{0}\), \(\overline{2}\), \(\overline{6}=\overline{0}\), \(\overline{12}=\overline{0}\), \(\overline{20}=\overline{2}\), \(\overline{30}=\overline{0}\). Solutions : \(\overline{0}\), \(\overline{2}\), \(\overline{3}\), \(\overline{5}\) ; quatre solutions, alors que dans \(\mathbb{R}\) l’équation n’en a que deux.

2)

Dans \(\mathbb{Z}/5\mathbb{Z}\), la table de multiplication montre qu’un produit est nul seulement si un facteur est nul : \(x=\overline{0}\) ou \(x=-\overline{1}=\overline{4}\). Les carrés dans \(\mathbb{Z}/5\mathbb{Z}\) sont \(\overline{0}\), \(\overline{1}\), \(\overline{4}\) : l’équation \(x^{2}=\overline{2}\) n’a pas de solution.

V. Nombres premiers

Définition

Un entier naturel \(p\) est premier s’il a exactement deux diviseurs positifs : \(1\) et \(p\). Les premiers nombres premiers sont \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\), \(23\), \(29\)… (\(1\) n’est pas premier).

Propriétés

✓ Tout entier \(n\ge2\) admet au moins un diviseur premier : son plus petit diviseur strictement supérieur à \(1\).

✓ Si \(n\ge2\) n’est pas premier, il admet un diviseur premier \(p\) tel que \(p^{2}\le n\). Donc : si aucun nombre premier \(p\) vérifiant \(p^{2}\le n\) ne divise \(n\), alors \(n\) est premier.

✓ Il existe une infinité de nombres premiers.

Démonstration

1) Soit \(p\) le plus petit diviseur de \(n\) supérieur à \(1\) ; un diviseur \(d\) de \(p\) avec \(1\lt d\lt p\) diviserait \(n\) et contredirait le choix de \(p\).

2) Si \(n=ab\) avec \(1\lt a\le b\lt n\), alors \(a^{2}\le ab=n\), et un diviseur premier de \(a\) convient.

3) Si \(p_{1}\), …, \(p_{k}\) étaient tous les nombres premiers, l’entier \(N=p_{1}p_{2}\cdots p_{k}+1\) aurait un diviseur premier \(p_{i}\), qui diviserait \(N-p_{1}\cdots p_{k}=1\) : absurde.

Application 11

1) Les nombres \(391\) et \(401\) sont-ils premiers ?

2) Montrer que si \(p\) est un nombre premier supérieur ou égal à \(5\), alors \(24\) divise \(p^{2}-1\).

Solution :

1)

\(19^{2}=361\le391\lt 400=20^{2}\) : on teste \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\) ; on trouve \(391=17\times23\), non premier. Pour \(401\) (\(20^{2}=400\le401\lt 441\)) : \(401\) n’est divisible par aucun des nombres \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\) (restes \(1\), \(2\), \(1\), \(2\), \(5\), \(11\), \(10\), \(2\)) : \(401\) est premier.

2)

\(p^{2}-1=(p-1)(p+1)\). \(p\) est impair : \(p-1\) et \(p+1\) sont deux pairs consécutifs, l’un est multiple de \(4\), donc \(8\mid p^{2}-1\). Parmi \(p-1\), \(p\), \(p+1\), l’un est multiple de \(3\), et ce n’est pas \(p\) : \(3\mid p^{2}-1\). Donc \(24\mid p^{2}-1\).

Décomposition en produit de facteurs premiers (admis)

Tout entier \(n\ge2\) s’écrit de manière unique (à l’ordre près) \(n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}\), où \(p_{1}\lt p_{2}\lt \ldots\lt p_{k}\) sont des nombres premiers et les \(\alpha_{i}\) des entiers naturels non nuls.

✓ Les diviseurs positifs de \(n\) sont les entiers \(p_{1}^{\beta_{1}}\cdots p_{k}^{\beta_{k}}\) avec \(0\le\beta_{i}\le\alpha_{i}\) ; leur nombre est \((\alpha_{1}+1)(\alpha_{2}+1)\cdots(\alpha_{k}+1)\).

Application 12

1) Décomposer \(2520\) en produit de facteurs premiers et déterminer le nombre de ses diviseurs positifs.

2) Déterminer le plus petit entier naturel \(m\) tel que \(2520m\) soit le carré d’un entier.

3) Déterminer les entiers naturels \(n\) qui ont exactement \(3\) diviseurs positifs.

Solution :

1)

\(2520=2\times1260=2^{2}\times630=2^{3}\times315=2^{3}\times3^{2}\times35=2^{3}\times3^{2}\times5\times7\). Nombre de diviseurs : \(4\times3\times2\times2=48\).

2)

Un carré a tous ses exposants pairs : il faut multiplier par \(2\times5\times7\). Donc \(m=70\) et \(2520\times70=176400=420^{2}\).

3)

\((\alpha_{1}+1)\cdots(\alpha_{k}+1)=3\) impose \(k=1\) et \(\alpha_{1}=2\) : \(n=p^{2}\) avec \(p\) premier (\(4\), \(9\), \(25\), \(49\)…).

Application 13

1) Déterminer le nombre de diviseurs positifs de \(10^{n}\) (\(n\in\mathbb{N}\)), puis l’entier \(n\) pour lequel \(10^{n}\) a exactement \(49\) diviseurs.

2) Déterminer le plus petit entier naturel ayant exactement \(6\) diviseurs positifs.

Solution :

1)

\(10^{n}=2^{n}\times5^{n}\) a \((n+1)^{2}\) diviseurs. \((n+1)^{2}=49\iff n=6\).

2)

\(6=6\times1=3\times2\) : \(n=p^{5}\) ou \(n=p^{2}q\) (\(p\ne q\) premiers). Les plus petits sont \(2^{5}=32\) et \(2^{2}\times3=12\) : la réponse est \(12\) (diviseurs \(1\), \(2\), \(3\), \(4\), \(6\), \(12\)).

VI. PGCD et PPCM

Définitions

Soient \(a\) et \(b\) deux entiers naturels non nuls.

✓ Le PGCD de \(a\) et \(b\), noté \(a\wedge b\), est le plus grand diviseur positif commun à \(a\) et \(b\).

✓ Le PPCM de \(a\) et \(b\), noté \(a\vee b\), est le plus petit multiple strictement positif commun à \(a\) et \(b\).

✓ On étend aux entiers relatifs non nuls : \(a\wedge b=|a|\wedge|b|\) et \(a\vee b=|a|\vee|b|\).

Propriétés

✓ Si \(a=\prod p_{i}^{\alpha_{i}}\) et \(b=\prod p_{i}^{\beta_{i}}\) (exposants éventuellement nuls), alors \(a\wedge b=\prod p_{i}^{\min(\alpha_{i};\beta_{i})}\) et \(a\vee b=\prod p_{i}^{\max(\alpha_{i};\beta_{i})}\).

✓ \((a\wedge b)\times(a\vee b)=|ab|\).

✓ Les diviseurs communs de \(a\) et \(b\) sont les diviseurs de \(a\wedge b\) ; les multiples communs de \(a\) et \(b\) sont les multiples de \(a\vee b\).

✓ Pour tout \(k\in\mathbb{N}^{*}\) : \((ka)\wedge(kb)=k(a\wedge b)\).

Application 14

1) Décomposer \(1188\), puis calculer \(2520\wedge1188\) et \(2520\vee1188\). Vérifier la relation \((a\wedge b)(a\vee b)=ab\).

2) Déterminer les diviseurs positifs communs à \(2520\) et \(1188\).

Solution :

1)

\(1188=2^{2}\times3^{3}\times11\) et \(2520=2^{3}\times3^{2}\times5\times7\). \(2520\wedge1188=2^{2}\times3^{2}=36\) et \(2520\vee1188=2^{3}\times3^{3}\times5\times7\times11=83160\). On a \(36\times83160=2993760=2520\times1188\).

2)

Ce sont les diviseurs de \(36\) : \(1\), \(2\), \(3\), \(4\), \(6\), \(9\), \(12\), \(18\), \(36\).

Algorithme d’Euclide

Si \(a=bq+r\) (division euclidienne, \(b\ge1\)), alors \(a\wedge b=b\wedge r\) (les diviseurs communs à \(a\) et \(b\) sont ceux communs à \(b\) et \(r\)). On divise successivement jusqu’à obtenir un reste nul : le PGCD est le dernier reste non nul.

Application 15

1) Calculer \(1071\wedge462\) par l’algorithme d’Euclide, puis \(1071\vee462\).

2) Montrer que pour tout \(n\in\mathbb{N}^{*}\) : \((3n+1)\wedge(2n+1)=1\).

Solution :

1)

\(1071=2\times462+147\) ; \(462=3\times147+21\) ; \(147=7\times21+0\). Donc \(1071\wedge462=21\) et \(1071\vee462=\frac{1071\times462}{21}=23562\).

2)

\(3n+1=1\times(2n+1)+n\), donc \((3n+1)\wedge(2n+1)=(2n+1)\wedge n\) ; puis \(2n+1=2\times n+1\) donne \((2n+1)\wedge n=n\wedge1=1\).

Application 16

1) Déterminer les couples \((a;b)\) d’entiers naturels tels que \(a\wedge b=6\) et \(a\vee b=72\).

2) Déterminer les couples \((a;b)\) d’entiers naturels tels que \(a+b=96\) et \(a\wedge b=12\).

Solution :

1)

\(a=6a^{\prime}\), \(b=6b^{\prime}\) avec \(a^{\prime}\wedge b^{\prime}=1\) ; \(ab=6\times72\) donne \(a^{\prime}b^{\prime}=12\). Les couples \((a^{\prime};b^{\prime})\) sans diviseur commun autre que \(1\) : \((1;12)\), \((3;4)\), \((4;3)\), \((12;1)\) (\((2;6)\) et \((6;2)\) sont exclus). D’où \((a;b)\in\{(6;72);(18;24);(24;18);(72;6)\}\).

2)

\(a=12a^{\prime}\), \(b=12b^{\prime}\) avec \(a^{\prime}+b^{\prime}=8\) et \(a^{\prime}\wedge b^{\prime}=1\) : \((1;7)\), \((3;5)\), \((5;3)\), \((7;1)\). D’où \((a;b)\in\{(12;84);(36;60);(60;36);(84;12)\}\).

Application 17

1) Rendre irréductibles les fractions \(\frac{1188}{2520}\) et \(\frac{1071}{462}\).

2) Déterminer les entiers naturels \(n\) pour lesquels \(\frac{n+7}{n+2}\) est un entier.

3) Deux phares s’allument ensemble à minuit ; l’un s’allume toutes les \(18\) secondes, l’autre toutes les \(24\) secondes. Au bout de combien de temps s’allument-ils de nouveau ensemble ?

Solution :

1)

\(1188\wedge2520=36\) : \(\frac{1188}{2520}=\frac{33}{70}\). \(1071\wedge462=21\) : \(\frac{1071}{462}=\frac{51}{22}\).

2)

\(n+7=(n+2)+5\) : il faut \((n+2)\mid5\) avec \(n+2\ge2\), donc \(n+2=5\) et \(n=3\) (on obtient \(\frac{10}{5}=2\)).

3)

\(18\vee24=2^{3}\times3^{2}=72\) : au bout de \(72\) secondes.

Exercices corrigés تمارين محلولة 12
Exercice 1

Divisibilité

Facile

1) Déterminer les entiers relatifs \(n\) tels que \(n-2\) divise \(3n+4\).

2) Montrer que pour tout \(n\in\mathbb{Z}\), \(n^{2}+n+1\) est impair.

3) Montrer que si \(7\mid(a+2b)\), alors \(7\mid(3a-b)\).

Afficher la correctionMasquer la correction

1)

\(3n+4=3(n-2)+10\), donc \((n-2)\mid10\) : \(n-2\in\{\pm1;\pm2;\pm5;\pm10\}\), soit \(n\in\{-8;-3;0;1;3;4;7;12\}\).

2)

\(n^{2}+n=n(n+1)\) est pair, donc \(n^{2}+n+1\) est impair.

3)

\(3a-b=3(a+2b)-7b\) : somme de deux multiples de \(7\).

Exercice 2

Division euclidienne

Facile

1) Effectuer la division euclidienne de \(-157\) par \(12\).

2) Le reste de la division de \(a\) par \(11\) est \(5\). Quel est le reste de la division de \(3a+7\) par \(11\) ? de \(a^{2}\) par \(11\) ?

3) Déterminer les entiers naturels \(a\) dont le quotient et le reste dans la division par \(7\) sont égaux.

Afficher la correctionMasquer la correction

1)

\(-157=12\times(-14)+11\) avec \(0\le11\lt 12\).

2)

\(a=11q+5\) : \(3a+7=33q+22=11(3q+2)\), reste \(0\). \(a^{2}=121q^{2}+110q+25=11(11q^{2}+10q+2)+3\), reste \(3\).

3)

\(a=7q+q=8q\) avec \(0\le q\lt 7\) : \(a\in\{0;8;16;24;32;40;48\}\).

Exercice 3

Congruences et restes

Facile

1) Déterminer le reste de la division euclidienne de \(3^{100}\) par \(5\), et de \(5^{2026}\) par \(13\).

2) Déterminer le chiffre des unités de \(2^{2026}\).

3) Montrer que pour tout \(n\in\mathbb{N}\), \(5^{n}-1\) est divisible par \(4\).

Afficher la correctionMasquer la correction

1)

\(3^{4}=81\equiv1\ [5]\) et \(100=4\times25\) : reste \(1\). \(5^{2}=25\equiv-1\ [13]\), donc \(5^{4}\equiv1\ [13]\) ; \(2026=4\times506+2\) : \(5^{2026}\equiv5^{2}\equiv12\ [13]\), reste \(12\).

2)

Modulo \(10\) : \(2^{1}\), \(2^{2}\), \(2^{3}\), \(2^{4}\), \(2^{5}\) se terminent par \(2\), \(4\), \(8\), \(6\), \(2\) ; le cycle est de longueur \(4\) à partir de \(2^{1}\). \(2026=4\times506+2\) : \(2^{2026}\) se termine par \(4\).

3)

\(5\equiv1\ [4]\), donc \(5^{n}\equiv1\ [4]\).

Exercice 4

Critères de divisibilité

Facile

1) Déterminer le chiffre \(x\) pour que \(\overline{7x34}\) soit divisible par \(3\).

2) Le nombre \(\overline{2x5y}\) est divisible par \(5\) et par \(9\). Déterminer les chiffres \(x\) et \(y\).

3) Montrer qu’un nombre de la forme \(\overline{abcabc}\) est divisible par \(7\), \(11\) et \(13\).

Afficher la correctionMasquer la correction

1)

\(7+x+3+4=14+x\) multiple de \(3\) : \(x\in\{1;4;7\}\).

2)

\(y\in\{0;5\}\). Si \(y=0\) : \(7+x\) multiple de \(9\), \(x=2\). Si \(y=5\) : \(12+x\) multiple de \(9\), \(x=6\). Nombres \(2250\) et \(2655\).

3)

\(\overline{abcabc}=1000\times\overline{abc}+\overline{abc}=1001\times\overline{abc}\) et \(1001=7\times11\times13\).

Exercice 5

Équations dans Z

Moyen

1) Déterminer les couples \((x;y)\) d’entiers relatifs tels que \(xy=2x+y+5\).

2) Montrer que l’équation \(x^{2}=3y+2\) n’a pas de solution dans \(\mathbb{Z}^{2}\).

3) Montrer que l’équation \(x^{2}+y^{2}=2027\) n’a pas de solution dans \(\mathbb{Z}^{2}\).

Afficher la correctionMasquer la correction

1)

\(xy-2x-y=5\iff(x-1)(y-2)=7\). Donc \((x-1;y-2)\in\{(1;7);(7;1);\) \((-1;-7);(-7;-1)\}\) et \((x;y)\in\{(2;9);(8;3);\) \((0;-5);(-6;1)\}\).

2)

Modulo \(3\), un carré est congru à \(0\) ou \(1\) (\(0^{2}\), \(1^{2}\), \(2^{2}=4\equiv1\)) ; or \(3y+2\equiv2\ [3]\) : impossible.

3)

\(2027=4\times506+3\equiv3\ [4]\), et une somme de deux carrés est congrue à \(0\), \(1\) ou \(2\) modulo \(4\).

Exercice 6

Nombres premiers

Moyen

1) Le nombre \(667\) est-il premier ? et \(673\) ?

2) Montrer que si \(n\ge2\), l’entier \(n^{4}+4\) n’est pas premier. (On vérifiera que \(n^{4}+4=(n^{2}+2)^{2}-(2n)^{2}\).)

3) Déterminer les entiers naturels \(n\) tels que \(n^{2}-1\) soit premier.

Afficher la correctionMasquer la correction

1)

\(25^{2}=625\le667\lt 676=26^{2}\) ; en testant les premiers jusqu’à \(23\) : \(667=23\times29\), non premier. \(673\) : \(25^{2}\le673\lt 26^{2}\) ; aucun des nombres \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\), \(23\) ne le divise : \(673\) est premier.

2)

\(n^{4}+4=(n^{2}+2)^{2}-4n^{2}=(n^{2}-2n+2)(n^{2}+2n+2)\). Pour \(n\ge2\) : \(n^{2}-2n+2=(n-1)^{2}+1\ge2\) et \(n^{2}+2n+2\gt n^{2}-2n+2\) ; c’est un produit de deux entiers supérieurs à \(1\).

3)

\(n^{2}-1=(n-1)(n+1)\) premier impose \(n-1=1\), soit \(n=2\) ; alors \(n^{2}-1=3\) est premier.

Exercice 7

Récurrence et divisibilité

Moyen

1) Montrer par récurrence que pour tout \(n\in\mathbb{N}\), \(3^{2n+1}+2^{n+2}\) est divisible par \(7\).

2) Retrouver ce résultat à l’aide des congruences.

Afficher la correctionMasquer la correction

1)

Pour \(n=0\) : \(3+4=7\). Si \(3^{2n+1}+2^{n+2}=7k\), alors \(3^{2n+3}+2^{n+3}=9\times3^{2n+1}+2\times2^{n+2}=9(7k-2^{n+2})+2\times2^{n+2}=63k-7\times2^{n+2}\), multiple de \(7\).

2)

\(3^{2n+1}=3\times9^{n}\equiv3\times2^{n}\ [7]\) et \(2^{n+2}=4\times2^{n}\) : la somme est congrue à \(7\times2^{n}\equiv0\ [7]\).

Exercice 8

Calculs dans Z/nZ

Moyen

1) Dresser la table de multiplication de \(\mathbb{Z}/4\mathbb{Z}\).

2) Résoudre dans \(\mathbb{Z}/4\mathbb{Z}\) : \(\overline{2}x=\overline{0}\) et \(\overline{3}x+\overline{1}=\overline{2}\).

3) Résoudre dans \(\mathbb{Z}/11\mathbb{Z}\) : \(\overline{4}x=\overline{5}\).

Afficher la correctionMasquer la correction

1)

\(\times\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)
\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)\(\overline{0}\)
\(\overline{1}\)\(\overline{0}\)\(\overline{1}\)\(\overline{2}\)\(\overline{3}\)
\(\overline{2}\)\(\overline{0}\)\(\overline{2}\)\(\overline{0}\)\(\overline{2}\)
\(\overline{3}\)\(\overline{0}\)\(\overline{3}\)\(\overline{2}\)\(\overline{1}\)

2)

\(\overline{2}x=\overline{0}\iff x\in\{\overline{0};\overline{2}\}\). \(\overline{3}x=\overline{1}\) : d’après la table, \(x=\overline{3}\).

3)

\(\overline{4}\times\overline{3}=\overline{12}=\overline{1}\) : on multiplie par \(\overline{3}\), \(x=\overline{15}=\overline{4}\). Vérification : \(\overline{16}=\overline{5}\).

Exercice 9

PGCD et PPCM

Moyen

1) Calculer \(4851\wedge1386\) par l’algorithme d’Euclide, puis \(4851\vee1386\).

2) Retrouver ces résultats par décomposition en facteurs premiers.

3) Déterminer les couples \((a;b)\) d’entiers naturels tels que \(a\wedge b=15\) et \(ab=2700\).

Afficher la correctionMasquer la correction

1)

\(4851=3\times1386+693\) ; \(1386=2\times693+0\) : \(4851\wedge1386=693\) et \(4851\vee1386=\frac{4851\times1386}{693}=9702\).

2)

\(4851=3^{2}\times7^{2}\times11\) et \(1386=2\times3^{2}\times7\times11\) : PGCD \(3^{2}\times7\times11=693\), PPCM \(2\times3^{2}\times7^{2}\times11=9702\).

3)

\(a=15a^{\prime}\), \(b=15b^{\prime}\), \(a^{\prime}b^{\prime}=12\) sans diviseur commun autre que \(1\) : \((1;12)\), \((3;4)\), \((4;3)\), \((12;1)\). D’où \((15;180)\), \((45;60)\), \((60;45)\), \((180;15)\).

Exercice 10

PGCD dépendant de n

Difficile

Soit \(n\in\mathbb{N}\). On pose \(a=2n+5\) et \(b=n+1\).

1) Montrer que \(a\wedge b=b\wedge3\). En déduire les valeurs possibles de \(a\wedge b\).

2) Déterminer les entiers \(n\) pour lesquels \(a\wedge b=3\).

3) Pour quelles valeurs de \(n\) la fraction \(\frac{2n+5}{n+1}\) est-elle irréductible ?

Afficher la correctionMasquer la correction

1)

\(a=2b+3\) : \(a\wedge b=b\wedge3\), qui divise \(3\) : \(a\wedge b\in\{1;3\}\).

2)

\(a\wedge b=3\iff3\mid(n+1)\iff n\equiv2\ [3]\), c’est-à-dire \(n=3k+2\).

3)

Irréductible \(\iff a\wedge b=1\iff n\equiv0\) ou \(n\equiv1\ [3]\).

Exercice 11

Restes des puissances et une suite

Difficile

1) Déterminer, suivant \(n\in\mathbb{N}\), le reste de la division de \(2^{n}\) par \(9\).

2) En déduire les entiers \(n\) tels que \(2^{n}+1\equiv0\ [9]\).

3) Montrer que \(2^{3n}\equiv(-1)^{n}\ [9]\) et en déduire, suivant la parité de \(n\), le reste de \(2^{6n}+2^{3n}+1\) modulo \(9\). Déterminer enfin le reste de \(1+2+2^{2}+\ldots+2^{2026}\) modulo \(9\).

Afficher la correctionMasquer la correction

1)

\(2^{0},\ldots,2^{6}\equiv1,2,4,8,7,5,1\ [9]\) : \(2^{6}\equiv1\ [9]\), les restes se répètent avec la période \(6\). Si \(n=6k+r\) (\(0\le r\le5\)), le reste est \(1\), \(2\), \(4\), \(8\), \(7\), \(5\) selon que \(r=0,1,2,3,4,5\).

2)

\(2^{n}\equiv-1\equiv8\ [9]\iff n\equiv3\ [6]\), c’est-à-dire \(n=6k+3\).

3)

\(2^{3}=8\equiv-1\ [9]\), donc \(2^{3n}\equiv(-1)^{n}\ [9]\), et \(2^{6n}=(2^{3n})^{2}\equiv1\ [9]\). Pour \(n\) pair, la somme est congrue à \(1+1+1=3\) ; pour \(n\) impair, à \(1-1+1=1\). Pour la somme, \(\sum_{k=0}^{2026}{2^{k}}=2^{2027}-1\) ; \(2027=6\times337+5\), donc \(2^{2027}\equiv5\ [9]\) et la somme est congrue à \(4\) modulo \(9\).

Exercice 12

Nombres de diviseurs et carrés

Difficile

1) Montrer qu’un entier \(n\ge1\) a un nombre impair de diviseurs positifs si et seulement si \(n\) est un carré.

2) Déterminer le plus petit entier naturel ayant exactement \(12\) diviseurs positifs.

3) Déterminer les entiers \(n=2^{a}\times3^{b}\) (\(a,b\in\mathbb{N}\)) dont la somme des diviseurs positifs est \(28\).

Afficher la correctionMasquer la correction

1)

Avec \(n=\prod p_{i}^{\alpha_{i}}\), le nombre de diviseurs \(\prod(\alpha_{i}+1)\) est impair si et seulement si tous les \(\alpha_{i}+1\) sont impairs, c’est-à-dire tous les \(\alpha_{i}\) pairs : \(n\) est un carré.

2)

\(12=12=6\times2=4\times3=3\times2\times2\) donne les formes \(p^{11}\), \(p^{5}q\), \(p^{3}q^{2}\), \(p^{2}qr\). Les plus petites valeurs : \(2^{11}=2048\), \(2^{5}\times3=96\), \(2^{3}\times3^{2}=72\), \(2^{2}\times3\times5=60\). Réponse : \(60\).

3)

La somme des diviseurs de \(2^{a}3^{b}\) est \((1+2+\ldots+2^{a})(1+3+\ldots+3^{b})=(2^{a+1}-1)\times\frac{3^{b+1}-1}{2}\). Les facteurs possibles du premier type sont \(1\), \(3\), \(7\), \(15\), … et du second \(1\), \(4\), \(13\), \(40\), …. Le produit vaut \(28\) pour \(7\times4\) : \(a=2\), \(b=1\), \(n=12\) (diviseurs \(1+2+3+4+6+12=28\)).