Aller au contenu

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

Type
Cours
Lecture
14 min

Pour deux entiers relatifs aa et bb avec b≠0b\neq0, on dit que bb divise aa, et l'on note b∣ab\mid a, s'il existe k∈Zk\in\mathbb{Z} tel que a=kba=kb. Pour a∈Za\in\mathbb{Z} et b∈N∗b\in\mathbb{N}^*, la division euclidienne de aa par bb donne un unique couple d'entiers (q ;r)(q\,;r) tel que a=bq+ra=bq+r et 0≤r<b0\leq r\lt b. Pour un entier n≥2n\geq2, aa est congru à bb modulo nn, noté a≡b [n]a\equiv b\ [n], si nn divise a−ba-b : aa et bb ont alors le même reste dans la division par nn. Exemple : −47=6×(−8)+1-47=6\times(-8)+1 avec 0≤1<60\leq1\lt6, donc le reste de −47-47 par 6 est 1 et −47≡1 [6]-47\equiv1\ [6].

Chapitre du semestre 2 de la 1re année du baccalauréat sciences mathématiques (option française BIOF) ; les sciences expérimentales ne l'étudient pas. Il étend à Z\mathbb{Z} l'arithmétique dans ℕ du tronc commun et ajoute les congruences et Z/nZ\mathbb{Z}/n\mathbb{Z}. Les entiers premiers entre eux, Bézout, Gauss et Fermat viennent en 2e année du bac SM.

Sommaire8 parties

Résumé de cours : arithmétique dans Z en un tableau

aa, bb, cc, dd sont des entiers relatifs et n≥2n\geq2 un entier naturel.

NotionÀ retenir
Divisibilitépour b≠0b\neq0 : b∣a  ⟺  ∃k∈Z, a=kbb\mid a\iff\exists k\in\mathbb{Z},\ a=kb
a∣ba\mid b et a∣c⇒a∣ub+vca\mid c\Rightarrow a\mid ub+vc pour u,v∈Zu,v\in\mathbb{Z}
Division euclidiennea∈Za\in\mathbb{Z}, b∈N∗b\in\mathbb{N}^* : a=bq+ra=bq+r, 0≤r<b0\leq r\lt b
(q ;r)(q\,;r) unique ; b∣a  ⟺  r=0b\mid a\iff r=0
Nombre premierp≥2p\geq2, diviseurs positifs 1 et pp
test : si aucun premier pp tel que p2≤np^2\leq n ne divise nn, alors nn est premier
Décompositionn=p1α1⋯pkαkn=p_1^{\alpha_1}\cdots p_k^{\alpha_k}, écriture unique
(α1+1)⋯(αk+1)(\alpha_1+1)\cdots(\alpha_k+1) diviseurs positifs
PGCDa∧b=b∧ra\wedge b=b\wedge r : dernier reste non nul
diviseurs communs = diviseurs de a∧ba\wedge b
PPCMmultiples communs = multiples de a∨ba\vee b
(a∧b)(a∨b)=∣ab∣(a\wedge b)(a\vee b)=|ab|
Congruencea≡b [n]  ⟺  n∣a−ba\equiv b\ [n]\iff n\mid a-b
  ⟺  \iff même reste dans la division par nn
Compatibilitéa≡ba\equiv b et c≡d [n]⇒c\equiv d\ [n]\Rightarrow
a+c≡b+da+c\equiv b+d, ac≡bdac\equiv bd, ak≡bk [n]a^k\equiv b^k\ [n]
Ensemble Z/nZZ/nZ={0‾ ;1‾ ;… ;n−1‾}\mathbb{Z}/n\mathbb{Z}=\{\overline{0}\,;\overline{1}\,;\dots\,;\overline{n-1}\}
a‾+b‾=a+b‾\overline{a}+\overline{b}=\overline{a+b}, a‾×b‾=ab‾\overline{a}\times\overline{b}=\overline{ab}
PDF A4 · 1 page · 102 KoTélécharger le résumé (PDF)

Divisibilité dans Z : diviseurs, multiples et propriétés

Diviseur et multiple d’un entier relatif

Soient a∈Za\in\mathbb{Z} et b∈Z∗b\in\mathbb{Z}^*. On dit que bb divise aa, ou que bb est un diviseur de aa, ou que aa est un multiple de bb, s'il existe k∈Zk\in\mathbb{Z} tel que a=kba=kb. On note b∣ab\mid a, et b∤ab\nmid a sinon. Les multiples de bb forment l'ensemble bZ={kb / k∈Z}b\mathbb{Z}=\{kb\ /\ k\in\mathbb{Z}\}.

Comme a=kb  ⟺  a=(−k)(−b)  ⟺  −a=(−k)ba=kb\iff a=(-k)(-b)\iff-a=(-k)b, on a b∣a  ⟺  −b∣a  ⟺  b∣−ab\mid a\iff-b\mid a\iff b\mid-a : il suffit de chercher les diviseurs positifs, puis d'ajouter leurs opposés. Tout b≠0b\neq0 divise 0.

Propriétés de la divisibilité

Soient aa, bb, cc des entiers relatifs, non nuls lorsqu'ils sont placés à gauche du symbole ∣\mid.

  • Transitivité : si a∣ba\mid b et b∣cb\mid c, alors a∣ca\mid c.
  • Combinaison : si a∣ba\mid b et a∣ca\mid c, alors a∣ub+vca\mid ub+vc pour tous u,v∈Zu,v\in\mathbb{Z}.
  • Si a∣ba\mid b et b≠0b\neq0, alors ∣a∣≤∣b∣|a|\leq|b| : un entier non nul n'a qu'un nombre fini de diviseurs.
  • Si a∣ba\mid b et b∣ab\mid a, alors ∣a∣=∣b∣|a|=|b|, c'est-à-dire a=ba=b ou a=−ba=-b.

Démonstration : transitivité, combinaison et majoration

Si b=kab=ka et c=k′bc=k^{\prime}b avec k,k′∈Zk,k^{\prime}\in\mathbb{Z}, alors c=(k′k)ac=(k^{\prime}k)a. Si b=kab=ka et c=k′ac=k^{\prime}a, alors ub+vc=(uk+vk′)aub+vc=(uk+vk^{\prime})a avec uk+vk′∈Zuk+vk^{\prime}\in\mathbb{Z}. Enfin, si b=kab=ka avec b≠0b\neq0, alors k≠0k\neq0, donc ∣k∣≥1|k|\geq1 et ∣b∣=∣k∣ ∣a∣≥∣a∣|b|=|k|\,|a|\geq|a| ; si de plus b∣ab\mid a, on a aussi ∣b∣≤∣a∣|b|\leq|a|.

Méthode : trouver les entiers n tels qu’une expression en divise une autre

On écrit An+B=A(n+α)+(B−Aα)An+B=A(n+\alpha)+(B-A\alpha). Comme n+αn+\alpha divise A(n+α)A(n+\alpha), la propriété de combinaison donne n+α∣An+B  ⟺  n+α∣B−Aαn+\alpha\mid An+B\iff n+\alpha\mid B-A\alpha : on liste les diviseurs, positifs et négatifs, de cette constante.

Exemple 1 : un diviseur qui dépend de n

Cherchons les entiers n≠−2n\neq-2 tels que n+2∣3n+17n+2\mid3n+17. On écrit 3n+17=3(n+2)+113n+17=3(n+2)+11, donc n+2∣3n+17  ⟺  n+2∣11n+2\mid3n+17\iff n+2\mid11. Les diviseurs de 11, nombre premier, sont −11-11, −1-1, 1 et 11 :

n∈{−13 ;−3 ;−1 ;9}.n\in\{-13\,;-3\,;-1\,;9\}.

Division euclidienne dans Z

Théorème de la division euclidienne dans Z

Soient a∈Za\in\mathbb{Z} et b∈N∗b\in\mathbb{N}^*. Il existe un unique couple (q ;r)∈Z×N(q\,;r)\in\mathbb{Z}\times\mathbb{N} tel que

a=bq+ret0≤r<b.a=bq+r\quad\text{et}\quad0\leq r\lt b.

qq est le quotient et rr le reste de la division euclidienne de aa par bb. De plus, b∣a  ⟺  r=0b\mid a\iff r=0.

Démonstration : existence et unicité du quotient et du reste

Existence : soit q=E(ab)q=E\left(\frac ab\right), la partie entière de ab\frac ab. Alors q≤ab<q+1q\leq\frac ab\lt q+1 ; en multipliant par b>0b\gt0, bq≤a<bq+bbq\leq a\lt bq+b, donc r=a−bqr=a-bq vérifie 0≤r<b0\leq r\lt b. Unicité : si a=bq+r=bq′+r′a=bq+r=bq^{\prime}+r^{\prime} avec 0≤r<b0\leq r\lt b et 0≤r′<b0\leq r^{\prime}\lt b, alors b ∣q−q′∣=∣r′−r∣<bb\,|q-q^{\prime}|=|r^{\prime}-r|\lt b, donc ∣q−q′∣<1|q-q^{\prime}|\lt1, soit q=q′q=q^{\prime}, puis r=r′r=r^{\prime}. Enfin, si a=kba=kb, l'écriture a=bk+0a=bk+0 est la division euclidienne, donc r=0r=0 ; la réciproque est immédiate.

Pour bb entier négatif non nul, on divise aa par ∣b∣=−b|b|=-b : a=∣b∣q′+ra=|b|q^{\prime}+r avec 0≤r<∣b∣0\leq r\lt|b|, donc a=b×(−q′)+ra=b\times(-q^{\prime})+r. Par exemple 38=5×7+3=(−5)×(−7)+338=5\times7+3=(-5)\times(-7)+3.

Exemple 2 : diviser un entier négatif

Divisons −250-250 par 9. D'abord 250=9×27+7250=9\times27+7, donc −250=9×(−27)−7-250=9\times(-27)-7, qui n'est pas la division euclidienne car −7<0-7\lt0. On retire 9 au produit et on l'ajoute au reste :

−250=9×(−28)+2.-250=9\times(-28)+2.

Comme 0≤2<90\leq2\lt9, le quotient est −28-28 et le reste 2.

Attention : le reste est toujours positif ou nul. Le reste de −250-250 par 9 n'est ni −7-7 ni 7, mais 2. En général, si a=bq+ra=bq+r avec 0<r<b0\lt r\lt b, alors −a=b(−q−1)+(b−r)-a=b(-q-1)+(b-r).

Méthode : raisonner selon le reste de la division par b

Tout entier relatif s'écrit n=bq+rn=bq+r avec r∈{0 ;1 ;… ;b−1}r\in\{0\,;1\,;\dots\,;b-1\}. Pour démontrer une propriété de tous les entiers, on traite chacun des bb restes possibles : c'est un raisonnement par disjonction des cas.

Exemple 3 : un carré augmenté de 2 n’est jamais multiple de 5

Soit n=5q+rn=5q+r avec q∈Zq\in\mathbb{Z} et r∈{0 ;1 ;2 ;3 ;4}r\in\{0\,;1\,;2\,;3\,;4\}. Alors n2=5(5q2+2qr)+r2n^2=5(5q^2+2qr)+r^2 : n2n^2 a le même reste que r2r^2 dans la division par 5. Pour r2=0r^2=0, 1, 4, 9, 16, ce reste vaut 0, 1, 4, 4, 1. Le reste de n2+2n^2+2 vaut donc 2, 3 ou 1, jamais 0 : n2+2n^2+2 n'est multiple de 5 pour aucun entier nn.

Nombres premiers et décomposition en facteurs premiers

Définition d’un nombre premier

Un entier naturel pp est premier s'il a exactement deux diviseurs positifs, 1 et pp. Cela impose p≥2p\geq2 : 1 n'est pas premier. Les premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ; le crible d'Ératosthène les donne jusqu'à une borne fixée.

Plus petit diviseur premier et test de primalité

Soit nn un entier naturel, n≥2n\geq2.

  • Le plus petit diviseur p≥2p\geq2 de nn est premier : tout entier n≥2n\geq2 a un diviseur premier.
  • Si nn n'est pas premier, ce plus petit diviseur vérifie p2≤np^2\leq n.
  • Test : si aucun nombre premier pp tel que p2≤np^2\leq n ne divise nn, alors nn est premier.

Démonstration : le plus petit diviseur supérieur à 1 est premier

Soit pp le plus petit diviseur de nn supérieur ou égal à 2 (il en existe : nn lui-même). Si pp n'était pas premier, il aurait un diviseur dd tel que 1<d<p1\lt d\lt p, qui diviserait nn par transitivité : contradiction. Si nn n'est pas premier, p≠np\neq n et n=pmn=pm avec m≥2m\geq2 diviseur de nn, donc m≥pm\geq p et n=pm≥p2n=pm\geq p^2. Le test est la contraposée de ce second point.

Exemple 4 : tester si 419 et 667 sont premiers

202=400≤419<441=21220^2=400\leq419\lt441=21^2 : on teste les nombres premiers jusqu'à 19. 419 n'est divisible ni par 2, ni par 3 (somme des chiffres 14), ni par 5, et

419=7×59+6=11×38+1=13×32+3=17×24+11=19×22+1.\begin{aligned}419&=7\times59+6\\&=11\times38+1\\&=13\times32+3\\&=17\times24+11\\&=19\times22+1.\end{aligned}

Aucun reste n'est nul : 419 est premier. Pour 667, 252=625≤667<676=26225^2=625\leq667\lt676=26^2 ; aucun nombre premier jusqu'à 19 ne divise 667, mais 667=23×29667=23\times29 : 667 n'est pas premier.

Infinité des nombres premiers

L'ensemble des nombres premiers est infini.

Démonstration : il existe une infinité de nombres premiers

Raisonnons par l'absurde : supposons qu'il n'existe qu'un nombre fini de nombres premiers p1,…,pkp_1,\dots,p_k, et posons N=p1p2⋯pk+1≥3N=p_1p_2\cdots p_k+1\geq3. NN admet un diviseur premier, qui est donc l'un des pip_i. Alors pip_i divise NN et p1p2⋯pkp_1p_2\cdots p_k, donc leur différence 1, ce qui est impossible car pi≥2p_i\geq2.

Décomposition en produit de facteurs premiers

Tout entier naturel n≥2n\geq2 s'écrit n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, où p1<p2<⋯<pkp_1\lt p_2\lt\dots\lt p_k sont des nombres premiers et α1,…,αk\alpha_1,\dots,\alpha_k des entiers naturels non nuls. On l'obtient en divisant par le plus petit diviseur premier, puis en recommençant avec le quotient ; l'unicité est admise. Pour n∈Zn\in\mathbb{Z}, ∣n∣≥2|n|\geq2, on décompose ∣n∣|n|. Conséquences :

  • les diviseurs positifs de nn sont les p1β1⋯pkβkp_1^{\beta_1}\cdots p_k^{\beta_k} avec 0≤βi≤αi0\leq\beta_i\leq\alpha_i. Il y en a (α1+1)(α2+1)⋯(αk+1)(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1), et deux fois plus dans Z\mathbb{Z} ;
  • si un nombre premier pp divise un produit abab de deux entiers non nuls, alors p∣ap\mid a ou p∣bp\mid b. En effet, ∣ab∣=pm|ab|=pm avec m∈N∗m\in\mathbb{N}^* : décomposer mm donne une décomposition de ∣ab∣|ab| qui contient pp, et mettre bout à bout celles de ∣a∣|a| et de ∣b∣|b| en donne une autre. Par l'unicité admise, elles coïncident : pp figure dans celle de ∣a∣|a| ou dans celle de ∣b∣|b|.
Attention : cette dernière propriété est fausse pour un diviseur qui n'est pas premier : 10∣4×1510\mid4\times15, mais 10∤410\nmid4 et 10∤1510\nmid15.

Exemple 5 : décomposer 1188 et compter ses diviseurs

On divise par les nombres premiers dans l'ordre croissant :

1188=2×594=22×297=22×33×11.\begin{aligned}1188&=2\times594=2^2\times297\\&=2^2\times3^3\times11.\end{aligned}

Les exposants sont 2, 3 et 1 : 1 188 a (2+1)(3+1)(1+1)=24(2+1)(3+1)(1+1)=24 diviseurs positifs et 48 diviseurs dans Z\mathbb{Z}.

PGCD, algorithme d’Euclide et PPCM

Plus grand commun diviseur de deux entiers relatifs

Soient aa et bb deux entiers relatifs non tous les deux nuls. L'ensemble de leurs diviseurs communs est fini et contient 1 ; son plus grand élément est le PGCD de aa et bb, noté a∧ba\wedge b ou pgcd(a ;b)\mathrm{pgcd}(a\,;b). On a a∧b≥1a\wedge b\geq1, a∧b=∣a∣∧∣b∣a\wedge b=|a|\wedge|b|, a∧0=∣a∣a\wedge0=|a| si a≠0a\neq0, et a∧b=∣b∣a\wedge b=|b| si b≠0b\neq0 et b∣ab\mid a.

Algorithme d’Euclide

Soient a∈Za\in\mathbb{Z}, b∈N∗b\in\mathbb{N}^* et rr le reste de la division euclidienne de aa par bb. Alors a∧b=b∧ra\wedge b=b\wedge r. On divise aa par bb, puis bb par rr, et ainsi de suite : les restes sont des entiers naturels strictement décroissants, donc l'un d'eux est nul, et a∧ba\wedge b est le dernier reste non nul.

Démonstration : les deux couples ont les mêmes diviseurs communs

Comme r=a−bqr=a-bq, un diviseur commun de aa et bb divise rr ; comme a=bq+ra=bq+r, un diviseur commun de bb et rr divise aa. Les deux couples ont donc les mêmes diviseurs communs. En notant r0=br_0=b, r1=rr_1=r, …, rkr_k le dernier reste non nul, on obtient

a∧b=r0∧r1=r1∧r2=⋯=rk−1∧rk=rk,\begin{aligned}a\wedge b&=r_0\wedge r_1=r_1\wedge r_2\\&=\dots=r_{k-1}\wedge r_k=r_k,\end{aligned}

car le dernier pas s'écrit rk−1=rkq+0r_{k-1}=r_kq+0.

Diviseurs communs et PGCD de deux multiples

  • Les diviseurs communs de aa et bb sont exactement les diviseurs de a∧ba\wedge b : chaque étape de l'algorithme conserve les diviseurs communs, et ceux du dernier reste non nul et de 0 sont les diviseurs de ce reste.
  • Pour a∈Za\in\mathbb{Z}, b∈N∗b\in\mathbb{N}^* et k∈N∗k\in\mathbb{N}^*, (ka)∧(kb)=k (a∧b)(ka)\wedge(kb)=k\,(a\wedge b) : les divisions ka=(kb)q+krka=(kb)q+kr, avec 0≤kr<kb0\leq kr\lt kb, montrent que l'algorithme appliqué à kaka et kbkb donne les mêmes quotients et des restes multipliés par kk.

Exemple 6 : PGCD de 2717 et 1105 par l’algorithme d’Euclide

2717=1105×2+5071105=507×2+91507=91×5+5291=52×1+3952=39×1+1339=13×3+0\begin{aligned}2717&=1105\times2+507\\1105&=507\times2+91\\507&=91\times5+52\\91&=52\times1+39\\52&=39\times1+13\\39&=13\times3+0\end{aligned}

Le dernier reste non nul est 13 : 2717∧1105=132717\wedge1105=13. Les diviseurs communs de 2 717 et 1 105 sont donc −13-13, −1-1, 1 et 13.

Plus petit commun multiple

Soient a,b∈Z∗a,b\in\mathbb{Z}^*. Le plus petit multiple commun strictement positif de aa et bb est leur PPCM, noté a∨ba\vee b ou ppcm(a ;b)\mathrm{ppcm}(a\,;b). Il existe, car ∣ab∣|ab| est un multiple commun strictement positif, et les multiples communs de aa et bb sont exactement les multiples de a∨ba\vee b.

Démonstration : les multiples communs sont les multiples du PPCM

Soit m=a∨bm=a\vee b. Un multiple de mm est multiple de aa et de bb par transitivité. Réciproquement, soit cc un multiple commun, et c=mq+rc=mq+r avec 0≤r<m0\leq r\lt m. Alors r=c−mqr=c-mq est un multiple commun de aa et bb, positif ou nul et inférieur à mm : par définition de mm, il est nul. Donc m∣cm\mid c.

PGCD et PPCM à partir des décompositions

Soient a,b∈Z∗a,b\in\mathbb{Z}^*. On écrit ∣a∣|a| et ∣b∣|b| avec les mêmes nombres premiers pip_i, quitte à mettre des exposants nuls : pip_i a l'exposant αi\alpha_i dans ∣a∣|a| et βi\beta_i dans ∣b∣|b|.

  • Dans a∧ba\wedge b, chaque pip_i a l'exposant min⁡(αi,βi)\min(\alpha_i,\beta_i) : un diviseur commun a des exposants au plus égaux à αi\alpha_i et à βi\beta_i.
  • Dans a∨ba\vee b, chaque pip_i a l'exposant max⁡(αi,βi)\max(\alpha_i,\beta_i) : un multiple commun a des exposants au moins égaux à αi\alpha_i et à βi\beta_i.
  • Comme min⁡(α,β)+max⁡(α,β)=α+β\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta, on obtient (a∧b)(a∨b)=∣ab∣(a\wedge b)(a\vee b)=|ab|.

Exemple 7 : PGCD et PPCM de 440 et 396 par leurs décompositions

440=23×5×11440=2^3\times5\times11 et 396=22×32×11396=2^2\times3^2\times11. On prend, pour chaque nombre premier, le plus petit exposant, puis le plus grand :

440∧396=22×11=44,440∨396=23×32×5×11=3960.\begin{aligned}440\wedge396&=2^2\times11=44,\\440\vee396&=2^3\times3^2\times5\times11\\&=3960.\end{aligned}
Attention : le PPCM n'est pas le produit en général ; ici, il est 44 fois plus petit que 440×396440\times396.

Congruence modulo n

Définition de la congruence modulo n

Soit nn un entier naturel, n≥2n\geq2. Deux entiers relatifs aa et bb sont congrus modulo nn, noté a≡b [n]a\equiv b\ [n], si n∣a−bn\mid a-b. Elle est réflexive, symétrique et transitive : c'est une relation d'équivalence. En particulier, n∣a  ⟺  a≡0 [n]n\mid a\iff a\equiv0\ [n], et le chiffre des unités d'un entier naturel est son reste modulo 10.

Congruence et reste de la division euclidienne

Soit n≥2n\geq2. Alors a≡b [n]a\equiv b\ [n] si et seulement si aa et bb ont le même reste dans la division euclidienne par nn. Le reste de aa par nn est l'unique entier rr tel que a≡r [n]a\equiv r\ [n] et 0≤r≤n−10\leq r\leq n-1.

Démonstration : deux entiers congrus ont le même reste

Écrivons a=nq+ra=nq+r et b=nq′+r′b=nq^{\prime}+r^{\prime}, avec rr et r′r^{\prime} dans {0 ;… ;n−1}\{0\,;\dots\,;n-1\}. Alors a−b=n(q−q′)+(r−r′)a-b=n(q-q^{\prime})+(r-r^{\prime}), donc n∣a−b  ⟺  n∣r−r′n\mid a-b\iff n\mid r-r^{\prime}. Or −n<r−r′<n-n\lt r-r^{\prime}\lt n, et le seul multiple de nn dans cet intervalle est 0 : n∣a−b  ⟺  r=r′n\mid a-b\iff r=r^{\prime}. Enfin, si a≡r0 [n]a\equiv r_0\ [n] avec 0≤r0≤n−10\leq r_0\leq n-1, r0r_0 est son propre reste, donc celui de aa.

Compatibilité avec l’addition, la multiplication et les puissances

Soient n≥2n\geq2 et a,b,c,d∈Za,b,c,d\in\mathbb{Z} tels que a≡b [n]a\equiv b\ [n] et c≡d [n]c\equiv d\ [n]. Alors

a+c≡b+d [n],a−c≡b−d [n],ac≡bd [n],ak≡bk [n]  (k∈N).\begin{aligned}&a+c\equiv b+d\ [n],\\&a-c\equiv b-d\ [n],\\&ac\equiv bd\ [n],\\&a^k\equiv b^k\ [n]\ \ (k\in\mathbb{N}).\end{aligned}

Démonstration : produit et puissances

(a+c)−(b+d)=(a−b)+(c−d)(a+c)-(b+d)=(a-b)+(c-d) est un multiple de nn, de même pour la différence, et ac−bd=a(c−d)+d(a−b)ac-bd=a(c-d)+d(a-b) aussi. Pour les puissances, on raisonne par récurrence sur kk : notons P(k)P(k) la proposition « ak≡bk [n]a^k\equiv b^k\ [n] ».

Initialisation. a0=b0=1a^0=b^0=1, donc P(0)P(0) est vraie.

Hérédité. Soit k∈Nk\in\mathbb{N} tel que P(k)P(k) soit vraie. En multipliant membre à membre ak≡bk [n]a^k\equiv b^k\ [n] et a≡b [n]a\equiv b\ [n], ce que permet la règle du produit, on obtient ak+1≡bk+1 [n]a^{k+1}\equiv b^{k+1}\ [n] : c'est P(k+1)P(k+1).

Conclusion. Par récurrence, ak≡bk [n]a^k\equiv b^k\ [n] pour tout k∈Nk\in\mathbb{N}.

Attention : on remplace la base par un entier congru, jamais l'exposant. 12≡1 [11]12\equiv1\ [11], mais 212=4096=11×372+42^{12}=4096=11\times372+4, donc 212≡4 [11]2^{12}\equiv4\ [11], alors que 21=22^1=2. On ne simplifie pas non plus : 3×7≡3×2 [15]3\times7\equiv3\times2\ [15], car 21−6=1521-6=15, mais 7≢2 [15]7\not\equiv2\ [15] ; la simplification d'une congruence est étudiée en 2e année.

Méthode : reste d’une grande puissance

  1. Remplacer la base par son reste modulo nn.
  2. Calculer les puissances successives jusqu'à un exposant k≥1k\geq1 tel que ak≡1 [n]a^k\equiv1\ [n] ou ak≡−1 [n]a^k\equiv-1\ [n]. Sinon, on repère directement le cycle des restes (exemple : 2k≡4 [6]2^k\equiv4\ [6] pour tout kk pair non nul).
  3. Diviser l'exposant par kk : si N=kq+sN=kq+s avec 0≤s<k0\leq s\lt k, alors aN=(ak)q×as≡as [n]a^N=\left(a^k\right)^q\times a^s\equiv a^s\ [n] si ak≡1 [n]a^k\equiv1\ [n], et aN≡(−1)q as [n]a^N\equiv(-1)^q\,a^s\ [n] si ak≡−1 [n]a^k\equiv-1\ [n].

Exemple 8 : reste d’une grande puissance dans la division par 11

Cherchons le reste de 168316^{83} par 11. Comme 16≡5 [11]16\equiv5\ [11], 1683≡583 [11]16^{83}\equiv5^{83}\ [11]. Les puissances de 5 donnent 52=25≡35^2=25\equiv3, 53≡3×5≡45^3\equiv3\times5\equiv4, 54≡4×5≡95^4\equiv4\times5\equiv9 et 55≡9×5=45≡1 [11]5^5\equiv9\times5=45\equiv1\ [11]. Comme 83=5×16+383=5\times16+3 :

1683≡(55)16×53≡1×125≡4 [11].\begin{aligned}16^{83}&\equiv\left(5^5\right)^{16}\times5^3\\&\equiv1\times125\equiv4\ [11].\end{aligned}

Le reste est 4, car 125=11×11+4125=11\times11+4.

Méthode : démontrer une divisibilité pour tout entier naturel

Pour montrer que m∣Anm\mid A_n pour tout n∈Nn\in\mathbb{N}, on montre que An≡0 [m]A_n\equiv0\ [m] en remplaçant chaque base par une puissance congrue à un entier simple (1 ou −1-1 souvent).

Exemple 9 : une divisibilité par 17 vraie pour tout n

Soit n∈Nn\in\mathbb{N}. On a 34=81=68+13≡−4 [17]3^4=81=68+13\equiv-4\ [17], donc 38≡16≡−1 [17]3^8\equiv16\equiv-1\ [17], et 24=16≡−1 [17]2^4=16\equiv-1\ [17]. Donc

38n+2=9×(38)n≡9 (−1)n [17],24n+3=8×(24)n≡8 (−1)n [17].\begin{aligned}3^{8n+2}&=9\times\left(3^8\right)^n\\&\equiv9\,(-1)^n\ [17],\\2^{4n+3}&=8\times\left(2^4\right)^n\\&\equiv8\,(-1)^n\ [17].\end{aligned}

En additionnant, 38n+2+24n+3≡17 (−1)n≡0 [17]3^{8n+2}+2^{4n+3}\equiv17\,(-1)^n\equiv0\ [17] : 17 divise 38n+2+24n+33^{8n+2}+2^{4n+3} pour tout n∈Nn\in\mathbb{N}.

L’ensemble Z/nZ et ses opérations

Classes modulo n et ensemble Z/nZ

Soit n≥2n\geq2. La classe de a∈Za\in\mathbb{Z} modulo nn est l'ensemble défini en compréhension a‾={b∈Z / b≡a [n]}={a+kn / k∈Z}\overline{a}=\{b\in\mathbb{Z}\ /\ b\equiv a\ [n]\}=\{a+kn\ /\ k\in\mathbb{Z}\}, et a‾=b‾  ⟺  a≡b [n]\overline{a}=\overline{b}\iff a\equiv b\ [n]. D'après la division euclidienne, chaque entier est congru à un seul des restes 0,1,…,n−10,1,\dots,n-1 : l'ensemble des classes modulo nn est

Z/nZ={0‾ ;1‾ ;… ;n−1‾},\mathbb{Z}/n\mathbb{Z}=\left\{\overline{0}\,;\overline{1}\,;\dots\,;\overline{n-1}\right\},

qui a exactement nn éléments. Par exemple, dans Z/6Z\mathbb{Z}/6\mathbb{Z}, −47‾=1‾\overline{-47}=\overline{1} et 20‾=2‾\overline{20}=\overline{2}.

Addition et multiplication dans Z/nZ

On pose a‾+b‾=a+b‾\overline{a}+\overline{b}=\overline{a+b} et a‾×b‾=ab‾\overline{a}\times\overline{b}=\overline{ab}. Le résultat ne dépend pas des représentants choisis : si a‾=a′‾\overline{a}=\overline{a^{\prime}} et b‾=b′‾\overline{b}=\overline{b^{\prime}}, la compatibilité donne a+b≡a′+b′ [n]a+b\equiv a^{\prime}+b^{\prime}\ [n] et ab≡a′b′ [n]ab\equiv a^{\prime}b^{\prime}\ [n]. Elles sont commutatives et associatives, ×\times est distributive sur ++, et 0‾\overline{0}, 1‾\overline{1} sont les éléments neutres.

Exemple 10 : table de multiplication de Z/6Z et équations

Par exemple, 4‾×5‾=20‾=2‾\overline{4}\times\overline{5}=\overline{20}=\overline{2}. Pour résoudre une équation dans Z/nZ\mathbb{Z}/n\mathbb{Z}, on teste les nn classes sur la table.

×\times0‾\overline{0}1‾\overline{1}2‾\overline{2}3‾\overline{3}4‾\overline{4}5‾\overline{5}
0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}0‾\overline{0}
1‾\overline{1}0‾\overline{0}1‾\overline{1}2‾\overline{2}3‾\overline{3}4‾\overline{4}5‾\overline{5}
2‾\overline{2}0‾\overline{0}2‾\overline{2}4‾\overline{4}0‾\overline{0}2‾\overline{2}4‾\overline{4}
3‾\overline{3}0‾\overline{0}3‾\overline{3}0‾\overline{0}3‾\overline{3}0‾\overline{0}3‾\overline{3}
4‾\overline{4}0‾\overline{0}4‾\overline{4}2‾\overline{2}0‾\overline{0}4‾\overline{4}2‾\overline{2}
5‾\overline{5}0‾\overline{0}5‾\overline{5}4‾\overline{4}3‾\overline{3}2‾\overline{2}1‾\overline{1}

L'équation 4‾x=2‾\overline{4}x=\overline{2} : sur la ligne de 4‾\overline{4}, la valeur 2‾\overline{2} apparaît dans les colonnes 2‾\overline{2} et 5‾\overline{5}, donc x=2‾x=\overline{2} ou x=5‾x=\overline{5}. L'équation 4‾x=1‾\overline{4}x=\overline{1} n'a aucune solution, car 1‾\overline{1} n'apparaît pas sur cette ligne. Retour dans Z\mathbb{Z} : 4x≡2 [6]  ⟺  x≡2 [6]4x\equiv2\ [6]\iff x\equiv2\ [6] ou x≡5 [6]x\equiv5\ [6].

Attention : dans Z/6Z\mathbb{Z}/6\mathbb{Z}, 2‾×3‾=0‾\overline{2}\times\overline{3}=\overline{0} alors qu'aucun des deux facteurs n'est nul : une équation produit ne s'y résout pas comme dans R\mathbb{R}.

Pages liées