Aller au contenu

Arithmétique dans Z 2 bac SM : cours et résumé

Type
Cours
Lecture
14 min

Deux entiers relatifs aa et bb sont premiers entre eux si a∧b=1a\wedge b=1. Le théorème de Bézout dit que c'est le cas si et seulement s'il existe u,v∈Z{u,v\in\mathbb{Z}} tels que au+bv=1au+bv=1. Le théorème de Gauss en déduit : si a∣bca\mid bc et a∧b=1a\wedge b=1, alors a∣ca\mid c. Le petit théorème de Fermat donne, pour pp premier ne divisant pas aa, ap−1≡1 [p]a^{p-1}\equiv1\ [p]. Exemple : 9×4−7×5=1{9\times4-7\times5=1}, donc 9 et 7 sont premiers entre eux ; si 9 divise 7c7c, alors 9 divise cc.

Chapitre du semestre 2 de la 2e année du baccalauréat sciences mathématiques (option française), seule filière qui l'étudie. À la fin du chapitre, on sait calculer des coefficients de Bézout, résoudre ax+by=cax+by=c et une congruence linéaire, utiliser Fermat pour une grande puissance et écrire un entier dans une base donnée.

Sommaire9 parties

Résumé de cours : arithmétique dans Z en 2 bac SM

aa, bb, cc sont des entiers relatifs non nuls, n≥2n\geq2 un entier, pp un nombre premier, d=a∧bd=a\wedge b, a=dαa=d\alpha et b=dβb=d\beta.

NotionÀ retenir
Premiers entre euxa∧b=1a\wedge b=1 : seuls diviseurs communs 11 et −1-1
Caractérisationpour δ∈N∗\delta\in\mathbb{N}^* : a∧b=δ  ⟺  a=δα′, b=δβ′a\wedge b=\delta\iff a=\delta\alpha^{\prime},\ b=\delta\beta^{\prime} avec α′∧β′=1{\alpha^{\prime}\wedge\beta^{\prime}=1}
Bézoutil existe u,vu,v : au+bv=a∧bau+bv=a\wedge b
a∧b=1  ⟺  ∃ u,v∈Z, au+bv=1a\wedge b=1\iff{\exists\,u,v\in\mathbb{Z}},\ au+bv=1
Gaussa∣bca\mid bc et a∧b=1⇒a∣ca\wedge b=1\Rightarrow a\mid c
Conséquencesa∣ca\mid c, b∣cb\mid c, a∧b=1⇒ab∣ca\wedge b=1\Rightarrow ab\mid c
p∣ab⇒p∣ap\mid ab\Rightarrow p\mid a ou p∣bp\mid b
Décompositiontout n≥2n\geq2 est un produit de nombres premiers, unique à l'ordre près (théorème fondamental de l'arithmétique)
Équationax+by=cax+by=c a des solutions   ⟺  d∣c\iff d\mid c
x=x0+βkx=x_0+\beta k, y=y0−αky=y_0-\alpha k, k∈Zk\in\mathbb{Z}
Simplificationac≡bc [n]  ⟺  a≡b [nc∧n]ac\equiv bc\ [n]\iff a\equiv b\ \left[\frac{n}{c\wedge n}\right]
Inversea‾\overline{a} inversible dans Z/nZ  ⟺  a∧n=1\mathbb{Z}/n\mathbb{Z}\iff{a\wedge n=1}
dans Z/pZ\mathbb{Z}/p\mathbb{Z}, toute classe non nulle
Fermatap≡a [p]a^p\equiv a\ [p] pour tout a∈Za\in\mathbb{Z}
p∤a⇒ap−1≡1 [p]p\nmid a\Rightarrow a^{p-1}\equiv1\ [p]
Base bN=akbk+⋯+a1b+a0N=a_kb^k+\dots+a_1b+a_0, 0≤ai≤b−10\leq a_i\leq b-1, ak≠0a_k\neq0
chiffres : restes des divisions successives par bb
CritèresN≡N\equiv somme des chiffres [9][9]
N≡a0−a1+a2−… [11]N\equiv a_0-a_1+a_2-\dots\ [11]
PDF A4 · 1 page · 110 KoTélécharger le résumé (PDF)

Rappels de 1 bac SM : divisibilité, PGCD et congruences

Le chapitre s'appuie sur l'arithmétique dans Z de 1re année, résumée dans son tableau de cours : division euclidienne, nombres premiers (leur ensemble est infini) et existence de la décomposition, PGCD comme dernier reste non nul de l'algorithme d'Euclide. On utilise aussi (ka)∧(kb)=k (a∧b)(ka)\wedge(kb)=k\,(a\wedge b) pour k∈N∗k\in\mathbb{N}^*, (a∧b)(a∨b)=∣ab∣(a\wedge b)(a\vee b)=|ab|, les congruences modulo nn et leur compatibilité avec ++, ×\times et les puissances, et l'ensemble Z/nZ\mathbb{Z}/n\mathbb{Z}. Tout ce qui suit est nouveau.

Nombres premiers entre eux et théorème de Bézout

Entiers premiers entre eux

Soient aa et bb deux entiers relatifs non tous les deux nuls. Ils sont premiers entre eux si a∧b=1a\wedge b=1, c'est-à-dire si leurs seuls diviseurs communs sont 11 et −1-1. Par exemple 49=7249=7^2 et 30=2×3×530=2\times3\times5 n'ont aucun facteur premier commun : 49∧30=149\wedge30=1. Deux nombres premiers distincts sont toujours premiers entre eux.

Caractérisation du PGCD

Soient a,b∈Z∗a,b\in\mathbb{Z}^* et d∈N∗d\in\mathbb{N}^*. Alors a∧b=da\wedge b=d si et seulement s'il existe α,β∈Z\alpha,\beta\in\mathbb{Z} tels que a=dαa=d\alpha, b=dβb=d\beta et α∧β=1\alpha\wedge\beta=1.

Démonstration : caractérisation du PGCD

Si a∧b=da\wedge b=d, dd divise aa et bb : a=dαa=d\alpha et b=dβb=d\beta. La propriété (ka)∧(kb)=k (a∧b)(ka)\wedge(kb)=k\,(a\wedge b) donne d=(dα)∧(dβ)=d (α∧β)d=(d\alpha)\wedge(d\beta)=d\,(\alpha\wedge\beta), donc α∧β=1\alpha\wedge\beta=1. Réciproquement, si a=dαa=d\alpha, b=dβb=d\beta et α∧β=1\alpha\wedge\beta=1, alors a∧b=d (α∧β)=da\wedge b=d\,(\alpha\wedge\beta)=d.

Identité et théorème de Bézout

  • Identité de Bézout : si aa et bb sont deux entiers non tous les deux nuls, il existe u,v∈Zu,v\in\mathbb{Z} tels que au+bv=a∧bau+bv=a\wedge b.
  • Théorème de Bézout : a∧b=1a\wedge b=1 si et seulement s'il existe u,v∈Zu,v\in\mathbb{Z} tels que au+bv=1au+bv=1.

Démonstration : identité et théorème de Bézout

L'ensemble EE des entiers strictement positifs de la forme au+bvau+bv contient a2+b2a^2+b^2, donc il a un plus petit élément m=au0+bv0m=au_0+bv_0. Divisons aa par mm : a=mq+ra=mq+r avec 0≤r<m0\leq r\lt m. Alors r=a(1−qu0)+b(−qv0)r=a(1-qu_0)+b(-qv_0) est de la même forme ; s'il était strictement positif, il serait dans EE et plus petit que mm. Donc r=0r=0 et m∣am\mid a ; de même m∣bm\mid b, d'où m≤a∧bm\leq a\wedge b. Inversement, a∧ba\wedge b divise aa et bb, donc il divise au0+bv0=mau_0+bv_0=m, et a∧b≤ma\wedge b\leq m. Ainsi m=a∧bm=a\wedge b.

Pour le théorème : si a∧b=1a\wedge b=1, l'identité donne uu et vv. Réciproquement, si au+bv=1au+bv=1, tout diviseur commun de aa et bb divise 1, donc a∧b=1a\wedge b=1.

Méthode : coefficients de Bézout par l’algorithme d’Euclide

On écrit les divisions de l'algorithme d'Euclide, puis on remonte (c'est l'algorithme d'Euclide étendu) : on exprime le dernier reste non nul à partir de l'avant-dernière division, et l'on remplace chaque reste par son expression tirée de la division précédente, jusqu'à ne garder que aa et bb.

Exemple 1 : coefficients de Bézout de 161 et 72

161=72×2+1772=17×4+417=4×4+1\begin{aligned}161&=72\times2+17\\72&=17\times4+4\\17&=4\times4+1\end{aligned}

Le dernier reste non nul est 1 : 161∧72=1161\wedge72=1. On remonte :

1=17−4×4=17−4 (72−4×17)=17×17−4×72=17 (161−2×72)−4×72=161×17−72×38.\begin{aligned}1&=17-4\times4\\&=17-4\,(72-4\times17)\\&=17\times17-4\times72\\&=17\,(161-2\times72)-4\times72\\&=161\times17-72\times38.\end{aligned}

Contrôle : 161×17=2737161\times17=2737 et 72×38=273672\times38=2736. Le couple (u ;v)=(17 ;−38)(u\,;v)=(17\,;-38) convient.

Attention : une égalité au+bv=dau+bv=d avec d≥2d\geq2 ne prouve pas que d=a∧bd=a\wedge b ; elle prouve seulement que a∧ba\wedge b divise dd. Par exemple 6×3−7×2=46\times3-7\times2=4, alors que 6∧7=16\wedge7=1. Seul le cas d=1d=1 conclut.

Théorème de Gauss et décomposition en facteurs premiers

Théorème de Gauss

Soient aa, bb, cc des entiers relatifs, avec a≠0a\neq0. Si aa divise bcbc et si a∧b=1a\wedge b=1, alors aa divise cc.

Démonstration : théorème de Gauss

Comme a∧b=1a\wedge b=1, Bézout donne u,vu,v tels que au+bv=1au+bv=1. En multipliant par cc : c=a(cu)+(bc)vc=a(cu)+(bc)v. Or aa divise a(cu)a(cu) et bcbc, donc il divise la combinaison cc.

Exemple 2 : une équation homogène

Résolvons 21x=16y21x=16y dans Z2\mathbb{Z}^2. Si (x ;y)(x\,;y) est solution, 16 divise 21x21x et 16∧21=116\wedge21=1 (16=2416=2^4, 21=3×721=3\times7) : par Gauss, 16 divise xx, soit x=16kx=16k avec k∈Zk\in\mathbb{Z}. Alors 21×16k=16y21\times16k=16y donne y=21ky=21k. Réciproquement, 21×16k=16×21k21\times16k=16\times21k. Les solutions sont les couples (16k ;21k)(16k\,;21k), k∈Zk\in\mathbb{Z}.

Attention : sans l'hypothèse a∧b=1a\wedge b=1, la conclusion est fausse : 6 divise 4×9=364\times9=36, mais 6 ne divise ni 4 ni 9.

Conséquences : produit de diviseurs et lemme d’Euclide

  • Si a∣ca\mid c, b∣cb\mid c et a∧b=1a\wedge b=1, alors ab∣cab\mid c.
  • Lemme d'Euclide : si un nombre premier pp divise abab, alors p∣ap\mid a ou p∣bp\mid b. En effet, si p∤ap\nmid a, alors p∧a=1p\wedge a=1 (les diviseurs positifs de pp sont 1 et pp), et Gauss donne p∣bp\mid b. En 1re année, ce lemme se déduisait de l'unicité de la décomposition, alors admise ; ici, il découle de Bézout et de Gauss, sans utiliser cette unicité, ce qui permet ensuite de la démontrer.
  • Si a∧b=1a\wedge b=1 et a∧c=1a\wedge c=1, alors a∧bc=1a\wedge bc=1 : en multipliant au+bv=1au+bv=1 par au′+cv′=1au^{\prime}+cv^{\prime}=1, on obtient a (uau′+ucv′+bvu′)+bc (vv′)=1a\,(uau^{\prime}+ucv^{\prime}+bvu^{\prime})+bc\,(vv^{\prime})=1. Par récurrence, a∧b=1⇒am∧bk=1a\wedge b=1\Rightarrow a^m\wedge b^k=1 pour m,k∈N∗m,k\in\mathbb{N}^*.

Démonstration : produit de deux diviseurs premiers entre eux

Écrivons c=akc=ak avec k∈Zk\in\mathbb{Z}. Alors bb divise akak et b∧a=1b\wedge a=1 : par Gauss, b∣kb\mid k, soit k=bk′k=bk^{\prime}. Donc c=ab k′c=ab\,k^{\prime} et ab∣cab\mid c.

Exemple 3 : un produit toujours divisible par 6

Soit n∈Zn\in\mathbb{Z} et A=n(n+1)(2n+1)A=n(n+1)(2n+1). Parmi nn et n+1n+1, l'un est pair : 2∣A2\mid A. Selon le reste de nn par 3 : si n=3qn=3q, 3∣n3\mid n ; si n=3q+1n=3q+1, 2n+1=3(2q+1)2n+1=3(2q+1) ; si n=3q+2n=3q+2, n+1=3(q+1)n+1=3(q+1). Donc 3∣A3\mid A. Comme 2∧3=12\wedge3=1, on conclut 6∣A6\mid A.

Théorème fondamental de l’arithmétique

Tout entier n≥2n\geq2 s'écrit comme un produit de nombres premiers, et cette écriture est unique à l'ordre des facteurs près : c'est le théorème fondamental de l'arithmétique. L'existence a été vue en 1re année ; l'unicité, admise alors, se démontre maintenant avec le lemme d'Euclide.

Démonstration : unicité dans le théorème fondamental de l’arithmétique

Raisonnons par l'absurde : soit nn le plus petit entier ayant deux décompositions différentes n=p1p2⋯pr=q1q2⋯qsn=p_1p_2\cdots p_r=q_1q_2\cdots q_s. Le premier p1p_1 divise q1(q2⋯qs)q_1(q_2\cdots q_s) ; en appliquant le lemme d'Euclide autant de fois que nécessaire, il divise l'un des qjq_j, qui est premier, donc p1=qjp_1=q_j. Si np1=1\frac{n}{p_1}=1, les deux produits restants valent 1, donc sont vides (un produit non vide de nombres premiers vaut au moins 2), et les deux décompositions étaient égales. Sinon 2≤np1<n2\leq\frac{n}{p_1}\lt n, et retirer le facteur commun p1=qjp_1=q_j donne deux décompositions différentes de np1\frac{n}{p_1} : cela contredit le choix de nn.

Équations diophantiennes du premier degré à deux inconnues

Condition d’existence et ensemble des solutions

Soient a,b∈Z∗a,b\in\mathbb{Z}^*, c∈Zc\in\mathbb{Z}, d=a∧bd=a\wedge b, a=dαa=d\alpha et b=dβb=d\beta. On considère (E)(E) : ax+by=cax+by=c, d'inconnue (x ;y)∈Z2(x\,;y)\in\mathbb{Z}^2.

  • (E)(E) a des solutions si et seulement si dd divise cc.
  • Si (x0 ;y0)(x_0\,;y_0) est une solution, les solutions sont les couples (x0+βk ;y0−αk)(x_0+\beta k\,;y_0-\alpha k), k∈Zk\in\mathbb{Z}.

Démonstration : condition d’existence et solutions

Si (E)(E) a une solution, dd divise ax+by=cax+by=c. Réciproquement, si c=dmc=dm, l'identité de Bézout au+bv=dau+bv=d donne la solution (um ;vm)(um\,;vm). Soit ensuite (x0 ;y0)(x_0\,;y_0) une solution. Pour (x ;y)(x\,;y) solution, par différence, a(x−x0)=−b(y−y0)a(x-x_0)=-b(y-y_0), puis, en divisant par dd, α(x−x0)=−β(y−y0)\alpha(x-x_0)=-\beta(y-y_0). Donc β\beta divise α(x−x0)\alpha(x-x_0) ; comme α∧β=1\alpha\wedge\beta=1, Gauss donne x−x0=βkx-x_0=\beta k, puis αβk=−β(y−y0)\alpha\beta k=-\beta(y-y_0) et y=y0−αky=y_0-\alpha k (β≠0\beta\neq0). Réciproquement, a(x0+βk)+b(y0−αk)=c+dαβk−dβαk=ca(x_0+\beta k)+b(y_0-\alpha k)=c+d\alpha\beta k-d\beta\alpha k=c.

Méthode : résoudre une équation diophantienne en trois étapes

  1. Calculer d=a∧bd=a\wedge b : si d∤cd\nmid c, il n'y a aucune solution ; sinon, diviser l'équation par dd.
  2. Trouver une solution particulière (évidente, ou par les coefficients de Bézout multipliés par cd\frac cd).
  3. Soustraire, appliquer Gauss avec les coefficients simplifiés, vérifier la réciproque.

Exemple 4 : une équation à simplifier, puis une équation sans solution

Soit 322x+144y=10322x+144y=10. On a 322∧144=2322\wedge144=2 et 2 divise 10 : on divise par 2, 161x+72y=5161x+72y=5. L'exemple 1 donne 161×17+72×(−38)=1161\times17+72\times(-38)=1, donc (85 ;−190)(85\,;-190) est solution ; on prend plus simplement (85−72 ;−190+161)=(13 ;−29)(85-72\,;-190+161)=(13\,;-29) : 2093−2088=52093-2088=5. Si (x ;y)(x\,;y) est solution, 161(x−13)=−72(y+29)161(x-13)=-72(y+29) ; 72 divise 161(x−13)161(x-13) et 72∧161=172\wedge161=1, donc x=13+72kx=13+72k, puis y=−29−161ky=-29-161k. Les solutions sont les couples (13+72k ;−29−161k)(13+72k\,;-29-161k), k∈Zk\in\mathbb{Z}.

En revanche, 322x+144y=7322x+144y=7 n'a aucune solution : le membre de gauche est toujours pair.

Attention : dans la solution générale, on utilise βk\beta k et −αk-\alpha k, coefficients divisés par dd. Garder 144k144k et −322k-322k ferait perdre une solution sur deux.

Méthode : système de deux congruences

Pour x≡r [m]x\equiv r\ [m] et x≡s [m′]x\equiv s\ [m^{\prime}], on écrit x=r+mk=s+m′k′x=r+mk=s+m^{\prime}k^{\prime} : le couple (k ;k′)(k\,;k^{\prime}) vérifie mk−m′k′=s−rmk-m^{\prime}k^{\prime}=s-r. Si m∧m′=1m\wedge m^{\prime}=1, une solution x1x_1 étant trouvée, xx est solution si et seulement si mm et m′m^{\prime} divisent x−x1x-x_1, c'est-à-dire x≡x1 [mm′]x\equiv x_1\ [mm^{\prime}].

Exemple 5 : un système de deux congruences

Résolvons x≡2 [7]x\equiv2\ [7] et x≡6 [9]x\equiv6\ [9]. On cherche x=2+7kx=2+7k avec 2+7k≡6 [9]2+7k\equiv6\ [9], soit 7k≡4 [9]7k\equiv4\ [9]. Comme 7×4=28≡1 [9]7\times4=28\equiv1\ [9], on multiplie par 4 : k≡16≡7 [9]k\equiv16\equiv7\ [9]. Pour k=7k=7, x1=51x_1=51 : 51=7×7+2=9×5+651=7\times7+2=9\times5+6. Comme 7∧9=17\wedge9=1, les solutions sont les entiers x≡51 [63]x\equiv51\ [63].

Simplification des congruences et ensemble Z/pZ

Simplification d’une congruence

Soient n≥2n\geq2, a,b∈Za,b\in\mathbb{Z}, c∈Z∗c\in\mathbb{Z}^* et δ=c∧n\delta=c\wedge n. Alors ac≡bc [n]ac\equiv bc\ [n] si et seulement si a≡b [nδ]a\equiv b\ \left[\frac n\delta\right]. En particulier, si c∧n=1c\wedge n=1, on peut simplifier par cc sans changer le module. Si δ=n\delta=n, c'est-à-dire si n∣cn\mid c, les deux membres acac et bcbc sont congrus à 0 et la congruence ac≡bc [n]ac\equiv bc\ [n] est vraie pour tous aa et bb.

Démonstration : simplification d’une congruence

Écrivons n=δn′n=\delta n^{\prime} et c=δc′c=\delta c^{\prime}, avec c′∧n′=1c^{\prime}\wedge n^{\prime}=1 par la caractérisation du PGCD. Si n∣c(a−b)n\mid c(a-b), alors δn′k=δc′(a−b)\delta n^{\prime}k=\delta c^{\prime}(a-b), donc n′∣c′(a−b)n^{\prime}\mid c^{\prime}(a-b), et Gauss donne n′∣a−bn^{\prime}\mid a-b. Réciproquement, si a−b=n′ja-b=n^{\prime}j, alors c(a−b)=c′j δn′=c′j nc(a-b)=c^{\prime}j\,\delta n^{\prime}=c^{\prime}j\,n.

Attention : on divise aussi le module. 10×3≡10×7 [8]10\times3\equiv10\times7\ [8], car 70−30=4070-30=40, mais 3≢7 [8]3\not\equiv7\ [8] ; ici 10∧8=210\wedge8=2 et l'on obtient seulement 3≡7 [4]3\equiv7\ [4].

Résoudre une congruence linéaire

Soient n≥2n\geq2, a∈Z∗a\in\mathbb{Z}^*, b∈Zb\in\mathbb{Z} et δ=a∧n\delta=a\wedge n. L'équation ax≡b [n]ax\equiv b\ [n] équivaut à l'existence de y∈Zy\in\mathbb{Z} tel que ax+ny=bax+ny=b : elle a des solutions si et seulement si δ∣b\delta\mid b. On simplifie alors par δ\delta, puis on multiplie par un entier a′a^{\prime} tel que aδ a′≡1 [nδ]\frac a\delta\,a^{\prime}\equiv1\ \left[\frac n\delta\right] : il existe par Bézout, car aδ∧nδ=1\frac a\delta\wedge\frac n\delta=1 (caractérisation du PGCD), et l'on revient en arrière en multipliant par aδ\frac a\delta, donc chaque étape est une équivalence.

Exemple 6 : une congruence linéaire modulo 24

Soit 14x≡10 [24]14x\equiv10\ [24]. Ici 14∧24=214\wedge24=2, qui divise 10 : on simplifie par 2, 7x≡5 [12]7x\equiv5\ [12]. Comme 7×7=49≡1 [12]7\times7=49\equiv1\ [12], on multiplie par 7 : x≡35≡11 [12]x\equiv35\equiv11\ [12]. Contrôle : 14×11=154=6×24+1014\times11=154=6\times24+10. Modulo 24, les solutions sont x≡11x\equiv11 et x≡23x\equiv23.

Classes inversibles de Z/nZ et ensemble Z/pZ

  • Soit n≥2n\geq2. La classe a‾\overline{a} admet un inverse dans Z/nZ\mathbb{Z}/n\mathbb{Z}, c'est-à-dire une classe a′‾\overline{a^{\prime}} telle que a‾×a′‾=1‾\overline{a}\times\overline{a^{\prime}}=\overline{1}, si et seulement si a∧n=1a\wedge n=1.
  • Si pp est premier, toute classe non nulle de Z/pZ\mathbb{Z}/p\mathbb{Z} est inversible ; par suite, x‾×y‾=0‾\overline{x}\times\overline{y}=\overline{0} entraîne x‾=0‾\overline{x}=\overline{0} ou y‾=0‾\overline{y}=\overline{0}.

Démonstration : classes inversibles

a‾×a′‾=1‾\overline{a}\times\overline{a^{\prime}}=\overline{1} signifie aa′≡1 [n]aa^{\prime}\equiv1\ [n], c'est-à-dire aa′+nk=1aa^{\prime}+nk=1 pour un k∈Zk\in\mathbb{Z}. Par le théorème de Bézout, un tel couple (a′ ;k)(a^{\prime}\,;k) existe si et seulement si a∧n=1a\wedge n=1. Si pp est premier et a‾≠0‾\overline{a}\neq\overline{0}, alors p∤ap\nmid a, donc a∧p=1a\wedge p=1. Enfin, si x‾ y‾=0‾\overline{x}\,\overline{y}=\overline{0} avec x‾≠0‾\overline{x}\neq\overline{0}, on multiplie par l'inverse de x‾\overline{x} : y‾=0‾\overline{y}=\overline{0}.

Exemple 7 : inverse de la classe de 7 dans Z/19Z

19 est premier, donc 7‾\overline{7} est inversible. Euclide donne 19=7×2+519=7\times2+5, 7=5×1+27=5\times1+2, 5=2×2+15=2\times2+1, puis 1=5−2×2=3×5−2×7=3×19−8×71=5-2\times2=3\times5-2\times7=3\times19-8\times7. Donc 7×(−8)≡1 [19]7\times(-8)\equiv1\ [19] et l'inverse de 7‾\overline{7} est −8‾=11‾\overline{-8}=\overline{11} (77=4×19+177=4\times19+1). L'équation 7‾x+2‾=6‾\overline{7}x+\overline{2}=\overline{6} équivaut à 7‾x=4‾\overline{7}x=\overline{4}, soit x=11‾×4‾=44‾=6‾x=\overline{11}\times\overline{4}=\overline{44}=\overline{6}.

Petit théorème de Fermat

Énoncé du petit théorème de Fermat

Soit pp un nombre premier.

  • Pour tout entier aa non divisible par pp, ap−1≡1 [p]a^{p-1}\equiv1\ [p].
  • Pour tout entier aa, ap≡a [p]a^p\equiv a\ [p].

Démonstration : petit théorème de Fermat

Soit aa non divisible par pp. Les classes 1‾ a‾\overline{1}\,\overline{a}, 2‾ a‾\overline{2}\,\overline{a}, …, p−1‾ a‾\overline{p-1}\,\overline{a} sont non nulles (produit de deux classes non nulles de Z/pZ\mathbb{Z}/p\mathbb{Z}) et deux à deux distinctes : si i‾ a‾=j‾ a‾\overline{i}\,\overline{a}=\overline{j}\,\overline{a}, on multiplie par l'inverse de a‾\overline{a} et i‾=j‾\overline{i}=\overline{j}. Ce sont donc les p−1p-1 classes non nulles, dans un autre ordre, et leurs produits sont égaux :

(p−1)!×ap−1≡(p−1)! [p].(p-1)!\times a^{p-1}\equiv(p-1)!\ [p].

Aucun des facteurs 1,…,p−11,\dots,p-1 n'est divisible par pp, donc, par le lemme d'Euclide, (p−1)!∧p=1(p-1)!\wedge p=1 : on simplifie, ap−1≡1 [p]a^{p-1}\equiv1\ [p]. En multipliant par aa, ap≡a [p]a^p\equiv a\ [p] ; si p∣ap\mid a, les deux membres sont congrus à 0.

Exemple 8 : reste d’une grande puissance par Fermat

Cherchons le reste de 520265^{2026} par 13. 13 est premier et ne divise pas 5, donc 512≡1 [13]5^{12}\equiv1\ [13]. Comme 2026=12×168+102026=12\times168+10 :

52026=(512)168×510≡510=(52)5 [13].\begin{aligned}5^{2026}&=\left(5^{12}\right)^{168}\times5^{10}\\&\equiv5^{10}=\left(5^2\right)^5\ [13].\end{aligned}

Or 52=25≡−1 [13]5^2=25\equiv-1\ [13], donc 52026≡(−1)5≡12 [13]5^{2026}\equiv(-1)^5\equiv12\ [13] : le reste est 12.

Attention : la réciproque est fausse. 42=16≡1 [15]4^2=16\equiv1\ [15], donc 414=(42)7≡1 [15]4^{14}=\left(4^2\right)^7\equiv1\ [15], alors que 15 n'est pas premier. Et Fermat ne s'applique pas si p∣ap\mid a : 2612≡0 [13]26^{12}\equiv0\ [13].

Systèmes de numération et critères de divisibilité

Écriture d’un entier en base b

Soit b≥2b\geq2 un entier. Tout entier N≥1N\geq1 s'écrit de manière unique N=akbk+ak−1bk−1+⋯+a1b+a0N=a_kb^k+a_{k-1}b^{k-1}+\dots+a_1b+a_0, avec des chiffres ai∈{0 ;1 ;… ;b−1}a_i\in\{0\,;1\,;\dots\,;b-1\} et ak≠0a_k\neq0. On note N=akak−1⋯a0‾(b)N=\overline{a_ka_{k-1}\cdots a_0}_{(b)}. En base 16, les chiffres 10 à 15 s'écrivent A, B, C, D, E, F.

Démonstration : existence et unicité de l’écriture en base b

Existence : on divise NN par bb, N=bq0+a0N=bq_0+a_0, puis q0=bq1+a1q_0=bq_1+a_1, et ainsi de suite. Les quotients sont des entiers naturels strictement décroissants tant qu'ils ne sont pas nuls, donc l'un d'eux est nul ; en remplaçant chaque quotient, on obtient l'écriture. Unicité, par récurrence forte sur NN : dans toute écriture, N=b (akbk−1+⋯+a1)+a0N=b\,(a_kb^{k-1}+\dots+a_1)+a_0 avec 0≤a0<b0\leq a_0\lt b, donc, par unicité de la division euclidienne, a0a_0 est le reste et akbk−1+⋯+a1a_kb^{k-1}+\dots+a_1 le quotient qq de NN par bb. Si q=0q=0, l'écriture se réduit à a0a_0 ; sinon ak⋯a1‾(b)\overline{a_k\cdots a_1}_{(b)} est une écriture de q<Nq\lt N, unique par hypothèse de récurrence.

Exemple 9 : écrire 1517 en base 5 et en base 16

1517=5×303+2303=5×60+360=5×12+012=5×2+22=5×0+2\begin{aligned}1517&=5\times303+2\\303&=5\times60+3\\60&=5\times12+0\\12&=5\times2+2\\2&=5\times0+2\end{aligned}

On lit les restes de bas en haut : 1517=22032‾(5)1517=\overline{22032}_{(5)}. Contrôle : 2×625+2×125+3×5+2=15172\times625+2\times125+3\times5+2=1517. En base 16, 1517=16×94+131517=16\times94+13 et 94=16×5+1494=16\times5+14, donc 1517=5ED‾(16)1517=\overline{5ED}_{(16)}.

Méthode : addition et multiplication en base b

On pose l'opération comme en base 10, colonne par colonne depuis la droite : dès qu'un résultat rr atteint bb, on écrit le reste de rr par bb et l'on retient le quotient. Pour comparer deux entiers écrits en base bb, celui qui a le plus de chiffres est le plus grand ; à nombre égal de chiffres, on compare de gauche à droite.

Exemple 10 : opérations en base 6

2453‾(6)+1354‾(6)\overline{2453}_{(6)}+\overline{1354}_{(6)} : 3+4=7=6+13+4=7=6+1, on écrit 1 et l'on retient 1 ; 5+5+1=11=6+55+5+1=11=6+5, on écrit 5, retenue 1 ; 4+3+1=8=6+24+3+1=8=6+2, on écrit 2, retenue 1 ; 2+1+1=42+1+1=4. Résultat 4251‾(6)\overline{4251}_{(6)}. Contrôle en base 10 : 609+358=967=4×216+2×36+5×6+1609+358=967=4\times216+2\times36+5\times6+1. De même, 45‾(6)×3‾(6)\overline{45}_{(6)}\times\overline{3}_{(6)} : 5×3=15=2×6+35\times3=15=2\times6+3, on écrit 3, retenue 2 ; 4×3+2=14=2×6+24\times3+2=14=2\times6+2. Résultat 223‾(6)\overline{223}_{(6)}, soit 29×3=8729\times3=87.

Critères de divisibilité par les congruences

Soit N=ak⋯a1a0‾(10)N=\overline{a_k\cdots a_1a_0}_{(10)}. Les critères de divisibilité du tronc commun se démontrent par les congruences : comme 10≡1 [9]10\equiv1\ [9], 10≡−1 [11]10\equiv-1\ [11] et 100≡0 [4]100\equiv0\ [4], la compatibilité avec les puissances donne :

N≡ak+⋯+a1+a0 [9],N≡a0−a1+a2−…+(−1)kak [11],N≡a1a0‾(10) [4].\begin{aligned}N&\equiv a_k+\dots+a_1+a_0\ [9],\\N&\equiv a_0-a_1+a_2-\dots\\&\quad+(-1)^ka_k\ [11],\\N&\equiv\overline{a_1a_0}_{(10)}\ [4].\end{aligned}

Comme m∣N  ⟺  N≡0 [m]m\mid N\iff N\equiv0\ [m], NN est divisible par 9 si et seulement si la somme de ses chiffres l'est (de même pour 3, car 10≡1 [3]10\equiv1\ [3]). Il est divisible par 11 si et seulement si sa somme alternée l'est, et par 4 si et seulement si le nombre formé par ses deux derniers chiffres l'est. De même, 100≡0 [25]100\equiv0\ [25] et 10≡0 [5]10\equiv0\ [5].

Exemple 11 : divisibilité de 73 854 par 9 et par 11

Somme des chiffres : 7+3+8+5+4=277+3+8+5+4=27, multiple de 9. Somme alternée depuis les unités : 4−5+8−3+7=114-5+8-3+7=11, multiple de 11. Donc 9 et 11 divisent 73 854 ; comme 9∧11=19\wedge11=1, 99 le divise aussi : 73854=99×74673854=99\times746.

Pages liées