Mathématiques · Arithmétique dans ℤ

Arithmétique dans ℤ

Divisibilité, congruences, PGCD, Bézout et Gauss, nombres premiers, Fermat et numération.

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

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

1. Définition et propriétés

Définition

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

Propriétés

Soient \(a\), \(b\), \(c\) des entiers relatifs :

✓ Si \(a\mid b\) et \(b\mid c\), alors \(a\mid c\) (transitivité).

✓ Si \(a\mid b\) et \(b\mid a\), alors \(|a|=|b|\).

✓ Si \(c\mid a\) et \(c\mid b\), alors \(c\mid(\alpha a+\beta b)\) pour tous \(\alpha,\beta\in\mathbb{Z}\).

2. Division euclidienne

Théorème

Soient \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^{*}\). Il existe un unique couple \((q;r)\in\mathbb{Z}\times\mathbb{N}\) 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\) ; \(b\mid a\iff r=0\).

Application 1

1) Montrer que pour tout \(n\in\mathbb{N}\) : \(5\mid2^{4n+1}+3\).

2) Déterminer les entiers relatifs \(n\) tels que \((n+5)\mid(2n+17)\).

3) Déterminer le quotient et le reste de la division euclidienne de \(-47\) par \(6\).

Solution :

1) \(5\mid2^{4n+1}+3\).

Par récurrence : pour \(n=0\), \(2^{1}+3=5\). Si \(2^{4n+1}+3=5k\), alors \(2^{4n+5}+3=16\times2^{4n+1}+3=16(5k-3)+3=80k-45=5(16k-9)\). Donc la propriété est vraie pour tout \(n\).

2) \((n+5)\mid(2n+17)\).

\(2n+17=2(n+5)+7\). Comme \((n+5)\mid2(n+5)\) : \((n+5)\mid(2n+17)\iff(n+5)\mid7\iff n+5\in\{-7;-1;1;7\}\).

Donc \(n\in\{-12;-6;-4;2\}\).

3) Division de \(-47\) par \(6\).

\(-47=6\times(-8)+1\) avec \(0\le1\lt 6\) : le quotient est \(-8\) et le reste est \(1\).

II. Congruences modulo \(n\)

Définition

Soit \(n\in\mathbb{N}^{*}\). Deux entiers \(a\) et \(b\) sont congrus modulo \(n\), et on écrit \(a\equiv b\ [n]\), si \(n\mid(a-b)\), c’est-à-dire si \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).

Propriétés

Soient \(n\in\mathbb{N}^{*}\) et \(a\), \(b\), \(c\), \(d\) des entiers :

✓ 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]\), alors \(a+c\equiv b+d\ [n]\) et \(ac\equiv bd\ [n]\).

✓ Si \(a\equiv b\ [n]\), alors pour tout \(k\in\mathbb{N}\) : \(a^{k}\equiv b^{k}\ [n]\).

✓ Tout entier \(a\) est congru modulo \(n\) à son reste \(r\) dans la division par \(n\) (\(0\le r\lt n\)).

Application 2

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

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

3) Résoudre dans \(\mathbb{Z}\) l’équation \(4x\equiv3\ [7]\).

4) Déterminer les entiers \(x\) tels que \(x\equiv2\ [5]\) et \(x\equiv3\ [7]\).

Solution :

1) Reste de \(5^{2026}\) modulo \(11\).

\(5^{2}=25\equiv3\ [11]\), donc \(5^{4}\equiv9\ [11]\) et \(5^{5}\equiv45\equiv1\ [11]\). Comme \(2026=5\times405+1\) : \(5^{2026}=(5^{5})^{405}\times5\equiv5\ [11]\). Le reste est \(5\).

2) Chiffre des unités de \(7^{2027}\).

\(7^{2}=49\equiv-1\ [10]\), donc \(7^{4}\equiv1\ [10]\). \(2027=4\times506+3\), donc \(7^{2027}\equiv7^{3}=343\equiv3\ [10]\) : le chiffre des unités est \(3\).

3) \(4x\equiv3\ [7]\).

\(2\times4=8\equiv1\ [7]\). En multipliant par \(2\) : \(4x\equiv3\ [7]\iff8x\equiv6\ [7]\iff x\equiv6\ [7]\). Les solutions sont \(x=6+7k\), \(k\in\mathbb{Z}\).

4) Système de congruences.

\(x\equiv2\ [5]\iff x=2+5k\). Alors \(x\equiv3\ [7]\iff5k\equiv1\ [7]\iff15k\equiv3\ [7]\iff k\equiv3\ [7]\) (car \(15\equiv1\ [7]\)).

Donc \(k=3+7m\) et \(x=2+5(3+7m)=17+35m\) : \(x\equiv17\ [35]\).

III. PGCD et PPCM

Définitions

Soient \(a\) et \(b\) deux entiers 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\).

✓ \(a\) et \(b\) sont premiers entre eux si \(a\wedge b=1\).

Propriétés

✓ Si \(a=bq+r\), alors \(a\wedge b=b\wedge r\) : c’est le principe de l’algorithme d’Euclide (le PGCD est le dernier reste non nul).

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

✓ \((a\wedge b)\times(a\vee b)=|ab|\) ; pour \(k\in\mathbb{N}^{*}\) : \((ka)\wedge(kb)=k(a\wedge b)\).

Application 3

1) Calculer \(2268\wedge1260\) par l’algorithme d’Euclide, puis \(2268\vee1260\).

2) Déterminer deux entiers \(u\) et \(v\) tels que \(1260u+2268v=2268\wedge1260\).

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

Solution :

1) Algorithme d’Euclide.

\(2268=1260\times1+1008\) ; \(1260=1008\times1+252\) ; \(1008=252\times4+0\). Le dernier reste non nul est \(252\) : \(2268\wedge1260=252\).

\(2268\vee1260=\frac{2268\times1260}{252}=2268\times5=11340\).

2) Coefficients.

En remontant les calculs : \(252=1260-1008=1260-(2268-1260)=2\times1260-2268\). Donc \(u=2\) et \(v=-1\) conviennent.

3) \((2n+3)\wedge(n+1)\).

Soit \(d\) un diviseur positif commun. Alors \(d\mid(2n+3)-2(n+1)=1\), donc \(d=1\) : les deux entiers sont premiers entre eux.

IV. Théorèmes de Bézout et de Gauss

Théorème de Bézout

✓ Si \(d=a\wedge b\), il existe des entiers \(u\) et \(v\) tels que \(au+bv=d\).

✓ \(a\wedge b=1\iff\) il existe des entiers \(u\) et \(v\) tels que \(au+bv=1\).

Théorème de Gauss

Soient \(a\), \(b\), \(c\) des entiers non nuls. Si \(a\mid bc\) et \(a\wedge b=1\), alors \(a\mid c\).

Démonstration

\(a\wedge b=1\), donc il existe \(u\), \(v\) tels que \(au+bv=1\) ; en multipliant par \(c\) : \(acu+bcv=c\). Or \(a\mid acu\) et \(a\mid bcv\) (car \(a\mid bc\)), donc \(a\mid c\).

Conséquences

✓ Si \(a\mid c\), \(b\mid c\) et \(a\wedge b=1\), alors \(ab\mid c\).

✓ L’équation \(ax+by=c\) (d’inconnues \(x,y\in\mathbb{Z}\)) admet des solutions si et seulement si \((a\wedge b)\mid c\).

Application 4

1) Résoudre dans \(\mathbb{Z}^{2}\) l’équation \(13x-8y=3\) (on remarquera que \((-1;-2)\) est une solution).

2) Résoudre dans \(\mathbb{Z}^{2}\) l’équation \(21x+15y=9\).

3) L’équation \(21x+15y=10\) admet-elle des solutions dans \(\mathbb{Z}^{2}\) ?

Solution :

1) \(13x-8y=3\).

\(13\times(-1)-8\times(-2)=-13+16=3\). Si \((x;y)\) est solution : \(13x-8y=13\times(-1)-8\times(-2)\), donc \(13(x+1)=8(y+2)\).

\(8\mid13(x+1)\) et \(8\wedge13=1\), donc (Gauss) \(8\mid x+1\) : \(x=-1+8k\) ; alors \(13\times8k=8(y+2)\) donne \(y=-2+13k\).

Réciproquement, ces couples sont solutions : \(S=\{(-1+8k;-2+13k)\ /\ k\in\mathbb{Z}\}\).

2) \(21x+15y=9\).

En divisant par \(3\) : \(7x+5y=3\), et \(7\times(-1)+5\times2=3\). Donc \(7(x+1)=5(2-y)\) ; comme \(5\wedge7=1\) : \(x=-1+5k\) et \(y=2-7k\).

\(S=\{(-1+5k;2-7k)\ /\ k\in\mathbb{Z}\}\).

3) \(21x+15y=10\).

\(21\wedge15=3\) et \(3\nmid10\) ; or \(3\mid21x+15y\) pour tous \(x\), \(y\) : l’équation n’a pas de solution.

V. Nombres premiers

Définition

Un entier naturel \(p\) est premier s’il admet exactement deux diviseurs positifs : \(1\) et \(p\).

Propriétés

✓ Tout entier \(n\ge2\) admet au moins un diviseur premier.

✓ Si \(n\ge2\) n’est divisible par aucun nombre premier \(p\) tel que \(p^{2}\le n\), alors \(n\) est premier.

✓ L’ensemble des nombres premiers est infini.

✓ Si un nombre premier \(p\) divise un produit \(ab\), alors \(p\mid a\) ou \(p\mid b\).

Théorème fondamental

Tout entier \(n\ge2\) s’écrit de façon unique (à l’ordre près) sous la forme \(n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}\), où les \(p_{i}\) sont des nombres premiers distincts et les \(\alpha_{i}\in\mathbb{N}^{*}\). Le nombre de diviseurs positifs de \(n\) est alors \((\alpha_{1}+1)(\alpha_{2}+1)\cdots(\alpha_{k}+1)\).

Petit théorème de Fermat

Soit \(p\) un nombre premier.

✓ Pour tout entier \(a\) : \(a^{p}\equiv a\ [p]\).

✓ Si de plus \(p\nmid a\) : \(a^{p-1}\equiv1\ [p]\).

Application 5

1) Les nombres \(391\) et \(1013\) sont-ils premiers ? En déduire la décomposition de \(2026\) en facteurs premiers.

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

3) En utilisant le petit théorème de Fermat, déterminer le reste de \(2^{2026}\) modulo \(13\).

4) Montrer que pour tout \(n\in\mathbb{Z}\) : \(33\mid n^{11}-n\).

Solution :

1) Primalité.

\(391=17\times23\) : il n’est pas premier. Pour \(1013\) : \(31^{2}=961\le1013\lt 32^{2}\), et aucun nombre premier \(p\le31\) (\(2,3,5,7,11,13,17,19,23,29,31\)) ne divise \(1013\) : il est premier.

Donc \(2026=2\times1013\) est la décomposition de \(2026\) en facteurs premiers.

2) Diviseurs de \(360\).

\(360=2^{3}\times3^{2}\times5\), donc \(360\) admet \((3+1)(2+1)(1+1)=24\) diviseurs positifs.

3) Reste de \(2^{2026}\) modulo \(13\).

\(13\) est premier et \(13\nmid2\), donc \(2^{12}\equiv1\ [13]\). \(2026=12\times168+10\), donc \(2^{2026}\equiv2^{10}=1024\ [13]\). Or \(1024=13\times78+10\) : le reste est \(10\).

4) \(33\mid n^{11}-n\).

Par Fermat avec \(p=11\) : \(n^{11}\equiv n\ [11]\), donc \(11\mid n^{11}-n\).

Par Fermat avec \(p=3\) : \(n^{3}\equiv n\ [3]\), donc \(n^{11}=n^{9}n^{2}=(n^{3})^{3}n^{2}\equiv n^{3}n^{2}=n^{5}=n^{3}n^{2}\equiv n\times n^{2}=n^{3}\equiv n\ [3]\), donc \(3\mid n^{11}-n\).

Comme \(3\wedge11=1\) : \(33\mid n^{11}-n\).

Application 6 : problème

Pour \(n\in\mathbb{N}\), on pose \(a_{n}=2^{n}+3^{n}\).

1) Déterminer, suivant les valeurs de \(n\), le reste de \(2^{n}\) et de \(3^{n}\) modulo \(5\).

2) En déduire les entiers \(n\) pour lesquels \(5\mid a_{n}\).

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

Solution :

1) Restes modulo 5.

\(2^{4}=16\equiv1\ [5]\) et \(3^{4}=81\equiv1\ [5]\) : les restes sont périodiques de période \(4\). Pour \(n=4k+r\) (\(r\in\{0;1;2;3\}\)) :

\(r\)\(0\)\(1\)\(2\)\(3\)
\(2^{n}\) modulo \(5\)\(1\)\(2\)\(4\)\(3\)
\(3^{n}\) modulo \(5\)\(1\)\(3\)\(4\)\(2\)
\(a_{n}\) modulo \(5\)\(2\)\(0\)\(3\)\(0\)

2) \(5\mid a_{n}\).

D’après le tableau : \(5\mid a_{n}\iff n\equiv1\ [4]\) ou \(n\equiv3\ [4]\iff n\) est impair.

3) \(a_{n}\wedge a_{n+1}=1\).

Soit \(d=a_{n}\wedge a_{n+1}\). \(d\mid a_{n+1}-2a_{n}=3^{n+1}-2\times3^{n}=3^{n}\) et \(d\mid3a_{n}-a_{n+1}=3\times2^{n}-2^{n+1}=2^{n}\).

Donc \(d\) divise \(2^{n}\) et \(3^{n}\), qui sont premiers entre eux (aucun facteur premier commun) : \(d=1\).

Application 7

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

2) Montrer que si \(a\wedge c=1\) et \(b\wedge c=1\), alors \((ab)\wedge c=1\) (on pourra utiliser le théorème de Bézout).

3) En déduire que \((n^{2}+n)\wedge(2n+1)=1\).

Solution :

1) Deux PGCD.

\((2n+1)-2\times n=1\) : d’après Bézout, \(n\wedge(2n+1)=1\). De même \(2(n+1)-(2n+1)=1\), donc \((n+1)\wedge(2n+1)=1\).

2) Propriété générale.

Il existe \(u\), \(v\), \(u^{\prime}\), \(v^{\prime}\) tels que \(au+cv=1\) et \(bu^{\prime}+cv^{\prime}=1\). En multipliant membre à membre :

\(\displaystyle (au+cv)\left(bu^{\prime}+cv^{\prime}\right)=ab\left(uu^{\prime}\right)+c\left(auv^{\prime}+bu^{\prime}v+cvv^{\prime}\right)=1\)

On a écrit \(1=(ab)U+cV\) avec \(U=uu^{\prime}\) et \(V=auv^{\prime}+bu^{\prime}v+cvv^{\prime}\) entiers : d’après Bézout, \((ab)\wedge c=1\).

3) \((n^{2}+n)\wedge(2n+1)\).

\(n^{2}+n=n(n+1)\) ; d’après la question 2 (avec \(a=n\), \(b=n+1\), \(c=2n+1\)) et la question 1 : \((n^{2}+n)\wedge(2n+1)=1\).

Application 8

1) Déterminer les restes possibles de \(x^{2}\) modulo \(7\) lorsque \(x\) parcourt \(\mathbb{Z}\).

2) En déduire que si \(x^{2}+y^{2}\equiv0\ [7]\), alors \(7\mid x\) et \(7\mid y\).

3) L’équation \(x^{2}+y^{2}=7\) admet-elle des solutions dans \(\mathbb{Z}^{2}\) ?

Solution :

1) Carrés modulo \(7\).

Tout entier \(x\) est congru modulo \(7\) à l’un des entiers \(0,1,\ldots,6\) :

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

Les restes possibles de \(x^{2}\) modulo \(7\) sont \(0\), \(1\), \(2\) et \(4\).

2) \(x^{2}+y^{2}\equiv0\ [7]\).

Si \(x^{2}\equiv r\) et \(y^{2}\equiv s\ [7]\) avec \(r,s\in\{0;1;2;4\}\), alors \(r+s\equiv0\ [7]\). Les sommes possibles \(r+s\) sont \(0,1,2,3,4,5,6,8\) : seule \(r=s=0\) donne \(0\) modulo \(7\).

Donc \(x^{2}\equiv0\) et \(y^{2}\equiv0\ [7]\), c’est-à-dire (d’après le tableau) \(x\equiv0\) et \(y\equiv0\ [7]\) : \(7\mid x\) et \(7\mid y\).

3) L’équation \(x^{2}+y^{2}=7\).

Si \((x;y)\) était solution, alors \(x^{2}+y^{2}\equiv0\ [7]\), donc \(x=7x^{\prime}\) et \(y=7y^{\prime}\), et \(49(x^{\prime2}+y^{\prime2})=7\) : impossible car \(49\nmid7\). L’équation n’a pas de solution.

VI. Systèmes de numération

Théorème et définition

Soit \(b\ge2\) un entier naturel. Tout entier naturel \(n\ge1\) s’écrit de façon unique sous la forme :

\(\displaystyle n=a_{p}b^{p}+a_{p-1}b^{p-1}+\cdots+a_{1}b+a_{0}\)

où \(p\in\mathbb{N}\), les \(a_{i}\) sont des entiers tels que \(0\le a_{i}\le b-1\), et \(a_{p}\ne0\). On note \(n=\overline{a_{p}a_{p-1}\cdots a_{1}a_{0}}_{(b)}\) : c’est l’écriture de \(n\) en base \(b\), et les \(a_{i}\) sont ses chiffres.

✓ En base \(10\) (système décimal), on n’écrit pas l’indice : \(2026=2\times10^{3}+0\times10^{2}+2\times10+6\).

✓ En base \(2\) (système binaire), les chiffres sont \(0\) et \(1\) ; en base \(16\) (système hexadécimal), on utilise les chiffres \(0\), …, \(9\), puis \(A=10\), \(B=11\), …, \(F=15\).

Méthode

Pour écrire \(n\) en base \(b\), on effectue des divisions euclidiennes successives par \(b\) : \(n=bq_{0}+a_{0}\), puis \(q_{0}=bq_{1}+a_{1}\), et ainsi de suite jusqu’au premier quotient nul. Les restes successifs \(a_{0}\), \(a_{1}\), … sont les chiffres de \(n\), en commençant par celui des unités.

Critères de divisibilité (base 10)

Soit \(n=\overline{a_{p}\cdots a_{1}a_{0}}\) écrit en base \(10\) :

✓ \(10\equiv0\ [2]\) et \([5]\) : \(n\equiv a_{0}\) modulo \(2\) et modulo \(5\) ; \(100\equiv0\ [4]\) : \(n\equiv\overline{a_{1}a_{0}}\ [4]\).

✓ \(10\equiv1\ [9]\) : \(n\equiv a_{0}+a_{1}+\cdots+a_{p}\ [9]\) (et donc aussi modulo \(3\)).

✓ \(10\equiv-1\ [11]\) : \(n\equiv a_{0}-a_{1}+a_{2}-\cdots+(-1)^{p}a_{p}\ [11]\).

Application 9 : numération

1) Écrire l’entier \(2026\) en base \(2\), puis en base \(7\).

2) Écrire en base \(10\) les entiers \(\overline{2A5}_{(16)}\) et \(\overline{110101}_{(2)}\).

3) Montrer que tout entier qui s’écrit \(\overline{abcabc}\) en base \(10\) est divisible par \(7\), par \(11\) et par \(13\).

4) Déterminer les chiffres \(x\) et \(y\) pour lesquels l’entier \(\overline{3x5y}\) est divisible par \(36\).

Solution :

1) \(2026\) en base \(2\) et en base \(7\).

Divisions successives par \(2\) : \(2026=2\times1013+0\) ; \(1013=2\times506+1\) ; \(506=2\times253+0\) ; \(253=2\times126+1\) ; \(126=2\times63+0\) ; \(63=2\times31+1\) ; \(31=2\times15+1\) ; \(15=2\times7+1\) ; \(7=2\times3+1\) ; \(3=2\times1+1\) ; \(1=2\times0+1\).

En lisant les restes du dernier au premier : \(2026=\overline{11111101010}_{(2)}\).

Par \(7\) : \(2026=7\times289+3\) ; \(289=7\times41+2\) ; \(41=7\times5+6\) ; \(5=7\times0+5\). Donc \(2026=\overline{5623}_{(7)}\) (vérification : \(5\times343+6\times49+2\times7+3=2026\)).

2) Retour en base 10.

\(\overline{2A5}_{(16)}=2\times16^{2}+10\times16+5=512+160+5=677\) ; \(\overline{110101}_{(2)}=2^{5}+2^{4}+2^{2}+1=53\).

3) Les entiers \(\overline{abcabc}\).

\(\overline{abcabc}=\overline{abc}\times1000+\overline{abc}=\overline{abc}\times1001\), et \(1001=7\times11\times13\) : l’entier est divisible par \(7\), \(11\) et \(13\).

4) Divisibilité de \(\overline{3x5y}\) par \(36\).

\(36=4\times9\) avec \(4\wedge9=1\) : \(36\mid n\iff4\mid n\) et \(9\mid n\).

\(4\mid n\iff4\mid\overline{5y}\iff\overline{5y}\in\{52;56\}\iff y\in\{2;6\}\). Et \(9\mid n\iff9\mid3+x+5+y\).

➢ Si \(y=2\) : \(9\mid x+10\iff x=8\) ; on obtient \(3852=36\times107\).

➢ Si \(y=6\) : \(9\mid x+14\iff x=4\) ; on obtient \(3456=36\times96\).

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

Divisibilité et division euclidienne

Facile

1) Montrer que pour tout \(n\in\mathbb{Z}\) : \(3\mid n^{3}+2n\).

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

3) Déterminer le quotient et le reste de la division euclidienne de \(-100\) par \(7\).

Afficher la correctionMasquer la correction

1) Divisibilité par 3.

\(n^{3}+2n=n^{3}-n+3n=(n-1)n(n+1)+3n\). Parmi trois entiers consécutifs, l’un est multiple de \(3\), donc \(3\mid(n-1)n(n+1)\), et \(3\mid3n\) : \(3\mid n^{3}+2n\).

2) Diviseurs.

\(3n+17=3(n+3)+8\), donc \((n+3)\mid(3n+17)\iff(n+3)\mid8\iff n+3\in\{-8;-4;-2;-1;1;2;4;8\}\).

Donc \(n\) est l’un des entiers \(-11\), \(-7\), \(-5\), \(-4\), \(-2\), \(-1\), \(1\) et \(5\).

3) Division euclidienne.

\(-100=7\times(-15)+5\) avec \(0\le5\lt 7\) : le quotient est \(-15\) et le reste \(5\).

Exercice 2

Congruences

Facile

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

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

3) Résoudre dans \(\mathbb{Z}\) l’équation \(5x\equiv3\ [12]\).

Afficher la correctionMasquer la correction

1) \(3^{2026}\) modulo \(7\).

\(3^{3}=27\equiv-1\ [7]\), donc \(3^{6}\equiv1\ [7]\). \(2026=6\times337+4\), donc \(3^{2026}\equiv3^{4}=81\equiv4\ [7]\) : le reste est \(4\).

2) Chiffre des unités.

\(2026\equiv6\ [10]\) et \(6^{2}=36\equiv6\ [10]\), donc par récurrence \(6^{k}\equiv6\ [10]\) pour \(k\ge1\) : le chiffre des unités est \(6\).

3) Équation.

\(5\times5=25\equiv1\ [12]\) : en multipliant par \(5\), \(5x\equiv3\iff x\equiv15\equiv3\ [12]\). Les solutions sont \(x=3+12k\), \(k\in\mathbb{Z}\).

Exercice 3

PGCD et équation diophantienne

Moyen

1) Calculer \(1547\wedge560\) par l’algorithme d’Euclide.

2) Résoudre dans \(\mathbb{Z}^{2}\) l’équation \(17x-12y=5\).

3) En déduire les entiers naturels \(n\) tels que \(n\equiv3\ [12]\) et \(n\equiv8\ [17]\) (on pourra écrire \(n=3+12y=8+17x\)), et donner le plus petit d’entre eux.

Afficher la correctionMasquer la correction

1) Algorithme d’Euclide.

\(1547=560\times2+427\) ; \(560=427\times1+133\) ; \(427=133\times3+28\) ; \(133=28\times4+21\) ; \(28=21\times1+7\) ; \(21=7\times3+0\). Donc \(1547\wedge560=7\).

2) Équation.

\((1;1)\) est solution : \(17-12=5\). Si \((x;y)\) est solution : \(17(x-1)=12(y-1)\). Comme \(17\wedge12=1\), Gauss donne \(12\mid x-1\) : \(x=1+12k\), puis \(y=1+17k\).

Réciproquement, ces couples conviennent : \(S=\{(1+12k;1+17k)\ /\ k\in\mathbb{Z}\}\).

3) Système de congruences.

\(n=3+12y=8+17x\iff17x-12y=-5\). Les solutions sont les opposées de celles de 2) : \(x=-1-12k\), \(y=-1-17k\). Donc \(n=3+12(-1-17k)=-9-204k\).

Les entiers cherchés sont ceux de la forme \(n=195+204m\) (\(m\in\mathbb{N}\)), et le plus petit est \(195\) (vérification : \(195=12\times16+3\) et \(195=17\times11+8\)).

Exercice 4

Petit théorème de Fermat

Moyen

1) Montrer que pour tout \(n\in\mathbb{Z}\) : \(7\mid n^{7}-n\).

2) Déterminer le reste de \(2^{100}\) modulo \(11\).

3) Montrer que \(13\mid2^{70}+3^{70}\).

Afficher la correctionMasquer la correction

1) Divisibilité.

\(7\) est premier : d’après le petit théorème de Fermat, \(n^{7}\equiv n\ [7]\), donc \(7\mid n^{7}-n\).

2) \(2^{100}\) modulo \(11\).

\(11\) est premier et \(11\nmid2\) : \(2^{10}\equiv1\ [11]\), donc \(2^{100}=(2^{10})^{10}\equiv1\ [11]\) : le reste est \(1\).

3) Divisibilité par \(13\).

Fermat : \(2^{12}\equiv1\ [13]\). \(70=12\times5+10\), donc \(2^{70}\equiv2^{10}=1024\equiv10\ [13]\) (car \(1024=13\times78+10\)).

\(3^{3}=27\equiv1\ [13]\) et \(70=3\times23+1\), donc \(3^{70}\equiv3\ [13]\). Ainsi \(2^{70}+3^{70}\equiv10+3=13\equiv0\ [13]\).

Exercice 5

Un PGCD dépendant d’un paramètre

Difficile

Pour \(n\in\mathbb{N}\), on pose \(a=2n+1\), \(b=n^{2}+n+1\) et \(d=a\wedge b\).

1) Calculer \(4b-a^{2}\) et en déduire que \(d\) divise \(3\).

2) Montrer que \(d=3\) si et seulement si \(n\equiv1\ [3]\).

3) Calculer \(d\) pour \(n=2026\) et pour \(n=2027\).

Afficher la correctionMasquer la correction

1) Diviseur de 3.

\(4b-a^{2}=4n^{2}+4n+4-(4n^{2}+4n+1)=3\). Comme \(d\mid a\) et \(d\mid b\), \(d\mid4b-a^{2}=3\) : \(d\in\{1;3\}\).

2) Cas \(d=3\).

Si \(d=3\), alors \(3\mid2n+1\), soit \(2n\equiv-1\equiv2\ [3]\), d’où \(n\equiv1\ [3]\) (on multiplie par \(2\), inverse de \(2\) modulo \(3\)).

Réciproquement, si \(n\equiv1\ [3]\) : \(a\equiv3\equiv0\ [3]\) et \(b\equiv1+1+1\equiv0\ [3]\), donc \(3\mid d\) et \(d=3\).

3) Applications.

\(2026=3\times675+1\equiv1\ [3]\) : \(d=3\). \(2027\equiv2\ [3]\) : \(d=1\).

Exercice 6

Une divisibilité remarquable

Difficile

On veut montrer que pour tout \(n\in\mathbb{Z}\) : \(2730\mid n^{13}-n\).

1) Décomposer \(2730\) en produit de facteurs premiers.

2) Soit \(p\) un nombre premier tel que \((p-1)\mid12\). Montrer que pour tout \(n\in\mathbb{Z}\) : \(p\mid n^{13}-n\) (distinguer les cas \(p\mid n\) et \(p\nmid n\)).

3) Conclure.

Afficher la correctionMasquer la correction

1) Décomposition.

\(2730=2\times1365=2\times3\times455=2\times3\times5\times91=2\times3\times5\times7\times13\).

2) Un nombre premier.

Si \(p\mid n\) : \(p\mid n^{13}\) et \(p\mid n\), donc \(p\mid n^{13}-n\).

Si \(p\nmid n\) : Fermat donne \(n^{p-1}\equiv1\ [p]\). On écrit \(12=(p-1)q\) ; alors \(n^{12}=(n^{p-1})^{q}\equiv1\ [p]\) et \(n^{13}\equiv n\ [p]\).

3) Conclusion.

Les nombres premiers \(2\), \(3\), \(5\), \(7\), \(13\) vérifient \(p-1\in\{1;2;4;6;12\}\), qui divisent tous \(12\). Chacun divise \(n^{13}-n\) ; étant premiers entre eux deux à deux, leur produit \(2730\) divise \(n^{13}-n\).