Mathématiques · Algèbre 1 · chapitre 5 sur 5

Arithmétique

Algèbre 1, semestre 1 — programme commun ENSA, ENSAM, FST, FS, EST, APESA et CPGE

L'arithmétique étudie la divisibilité dans l'ensemble Z des entiers relatifs. Tout part de la division euclidienne : elle fournit l'algorithme d'Euclide, qui calcule le PGCD et une relation de Bézout, puis le lemme de Gauss et la décomposition en facteurs premiers. Les congruences rendent les calculs sur les restes rapides et rigoureux.

Sur MC² : 1 résumé de cours · 1 TD corrigé · 1 devoir maison (DM) corrigé · 1 devoir libre (DL) corrigé

Ce que couvre le chapitre

  • Divisibilité. Pour a,b∈Za,b\in\mathbb{Z}, a∣ba\mid b s'il existe k∈Zk\in\mathbb{Z} tel que b=kab=ka. Si a∣ba\mid b et a∣ca\mid c, alors a∣bu+cva\mid bu+cv pour tous u,v∈Zu,v\in\mathbb{Z} ; tout entier divise 00.

  • Division euclidienne. Pour a∈Za\in\mathbb{Z} et b∈N∗b\in\mathbb{N}^*, il existe un unique couple (q,r)∈Z2(q,r)\in\mathbb{Z}^2 tel que a=bq+ra=bq+r et 0≤r<b0\leq r<b ; bb divise aa si et seulement si r=0r=0.

  • PGCD et algorithme d'Euclide. Pour (a,b)≠(0,0)(a,b)\neq(0,0), pgcd⁡(a,b)\operatorname{pgcd}(a,b), aussi noté a∧ba\wedge b, est le plus grand entier positif qui divise aa et bb ; les diviseurs communs à aa et bb sont exactement les diviseurs de leur PGCD. Si a=bq+ra=bq+r, alors pgcd⁡(a,b)=pgcd⁡(b,r)\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,r) : dans l'algorithme d'Euclide, le dernier reste non nul est le PGCD.

  • Bézout et Gauss. Il existe u,v∈Zu,v\in\mathbb{Z} tels que au+bv=pgcd⁡(a,b)au+bv=\operatorname{pgcd}(a,b) ; aa et bb sont premiers entre eux si et seulement s'il existe u,v∈Zu,v\in\mathbb{Z} tels que au+bv=1au+bv=1. Lemme de Gauss : si a∣bca\mid bc et pgcd⁡(a,b)=1\operatorname{pgcd}(a,b)=1, alors a∣ca\mid c.

  • Nombres premiers. Un entier p≥2p\geq2 est premier si ses seuls diviseurs positifs sont 11 et pp. Il y en a une infinité ; si pp premier divise abab, il divise aa ou bb ; tout entier n≥2n\geq2 est un produit de nombres premiers, de façon unique à l'ordre des facteurs près, et les exposants de ces décompositions donnent le PGCD et le PPCM.

  • Congruences. a≡b(modn)a\equiv b\pmod{n} signifie n∣a−bn\mid a-b. C'est une relation d'équivalence compatible avec l'addition et la multiplication : si a≡ba\equiv b et c≡d(modn)c\equiv d\pmod{n}, alors a+c≡b+da+c\equiv b+d et ac≡bd(modn)ac\equiv bd\pmod{n}, et ak≡bk(modn)a^k\equiv b^k\pmod{n} pour tout k∈Nk\in\mathbb{N}.

  • Petit théorème de Fermat. Si pp est premier et ne divise pas aa, alors ap−1≡1(modp)a^{p-1}\equiv1\pmod{p} ; pour tout a∈Za\in\mathbb{Z}, ap≡a(modp)a^p\equiv a\pmod{p}.

Ce qui est attendu à l'examen

  • Appliquer l'algorithme d'Euclide, puis le remonter pour obtenir une relation de Bézout explicite.

  • Résoudre une équation ax+by=cax+by=c dans Z2\mathbb{Z}^2 : condition d'existence par le PGCD, solution particulière, puis toutes les solutions grâce au lemme de Gauss.

  • Calculer le reste d'une grande puissance par congruences, en cherchant une puissance congrue à 11 ou à −1-1, ou avec le petit théorème de Fermat.

  • Démontrer une divisibilité pour tout entier nn, par congruences, par récurrence ou en examinant les restes possibles de nn.

  • Utiliser la décomposition en facteurs premiers pour compter les diviseurs d'un entier, ou pour calculer un PGCD et un PPCM.

L'erreur classique

Diviser une congruence comme une égalité

De 2x≡2(mod4)2x\equiv2\pmod{4}, on déduit parfois x≡1(mod4)x\equiv1\pmod{4}. C'est faux : x=3x=3 vérifie 2×3=6≡2(mod4)2\times3=6\equiv2\pmod{4}, alors que 3≢1(mod4)3\not\equiv1\pmod{4}. Une congruence se multiplie membre à membre, mais elle ne se simplifie pas comme une égalité.

La simplification par kk est permise quand kk est premier avec le module : si ka≡kb(modn)ka\equiv kb\pmod{n} et pgcd⁡(k,n)=1\operatorname{pgcd}(k,n)=1, alors nn divise k(a−b)k(a-b) en étant premier avec kk, donc n∣a−bn\mid a-b par le lemme de Gauss. Dans le cas général, il faut aussi diviser le module : avec d=pgcd⁡(k,n)d=\operatorname{pgcd}(k,n),

ka≡kb(modn)  ⟺  a≡b(modn/d).ka\equiv kb\pmod{n}\iff a\equiv b\pmod{n/d}.

Ici d=2d=2 : les solutions de 2x≡2(mod4)2x\equiv2\pmod{4} sont les x≡1(mod2)x\equiv1\pmod{2}, c'est-à-dire tous les entiers impairs.

Exemples corrigés

Exemple 1 — Une équation diophantienne

Résoudre dans Z2\mathbb{Z}^2 l'équation 43x+17y=543x+17y=5.

Corrigé

PGCD et Bézout. L'algorithme d'Euclide donne

43=2×17+9,17=1×9+8,9=1×8+1,43=2\times17+9,\qquad17=1\times9+8,\qquad9=1\times8+1,

donc pgcd⁡(43,17)=1\operatorname{pgcd}(43,17)=1. En remontant : 1=9−8=9−(17−9)=2×9−17=2×(43−2×17)−17=2×43−5×171=9-8=9-(17-9)=2\times9-17=2\times(43-2\times17)-17=2\times43-5\times17.

Solution particulière. En multipliant par 55 : 43×10+17×(−25)=543\times10+17\times(-25)=5.

Toutes les solutions. Si 43x+17y=543x+17y=5, alors, par différence, 43(x−10)=−17(y+25)43(x-10)=-17(y+25). Ainsi 1717 divise 43(x−10)43(x-10) en étant premier avec 4343 : par le lemme de Gauss, 17∣x−1017\mid x-10, soit x=10+17kx=10+17k avec k∈Zk\in\mathbb{Z}, puis y=−25−43ky=-25-43k. Réciproquement, 43(10+17k)+17(−25−43k)=5+43×17k−17×43k=543(10+17k)+17(-25-43k)=5+43\times17k-17\times43k=5. Donc

S={(10+17k, −25−43k):k∈Z}.\mathcal{S}=\{(10+17k,\,-25-43k) : k\in\mathbb{Z}\}.

Exemple 2 — Le reste d'une grande puissance

Déterminer le reste de la division euclidienne de 5835^{83} par 1313.

Corrigé

On cherche une petite puissance de 55 simple modulo 1313 : 52=25=2×13−15^2=25=2\times13-1, donc 52≡−1(mod13)5^2\equiv-1\pmod{13}. Comme 83=2×41+183=2\times41+1 :

583=(52)41×5≡(−1)41×5=−5(mod13).5^{83}=\left(5^2\right)^{41}\times5\equiv(-1)^{41}\times5=-5\pmod{13}.

Or −5≡8(mod13)-5\equiv8\pmod{13} et 0≤8<130\leq8<13 : le reste vaut 88. Le petit théorème de Fermat, qui donne 512≡1(mod13)5^{12}\equiv1\pmod{13}, conduit au même résultat avec un peu plus de calcul.

Exemple 3 — Une divisibilité par le petit théorème de Fermat

Montrer que, pour tout entier nn, l'entier n11−nn^{11}-n est divisible par 6666.

Corrigé

On a 66=2×3×1166=2\times3\times11, produit de trois nombres premiers distincts. Posons N=n11−nN=n^{11}-n.

  • Facteur 11. Le petit théorème de Fermat donne n11≡n(mod11)n^{11}\equiv n\pmod{11}, donc 11∣N11\mid N.
  • Facteur 3. Si 3∣n3\mid n, alors 3∣N3\mid N. Sinon, Fermat donne n2≡1(mod3)n^2\equiv1\pmod{3}, d'où n10=(n2)5≡1n^{10}=\left(n^2\right)^5\equiv1 et n11≡n(mod3)n^{11}\equiv n\pmod{3}.
  • Facteur 2. Les entiers n11n^{11} et nn ont la même parité, donc NN est pair.

Enfin, 22 et 33 divisent NN et sont premiers entre eux, donc 6∣N6\mid N : en écrivant N=2mN=2m, le lemme de Gauss appliqué à 3∣2m3\mid2m donne 3∣m3\mid m. De même, 66 et 1111 sont premiers entre eux, donc 66∣N66\mid N.

Andek chi soual ?

Questions fréquentes sur ce chapitre

À quoi sert la relation de Bézout ?

Elle écrit le PGCD de a et b sous la forme au + bv, avec u et v entiers. On s'en sert pour prouver que deux entiers sont premiers entre eux, en trouvant u et v tels que au + bv = 1, pour démontrer le lemme de Gauss, et pour obtenir une solution particulière d'une équation ax + by = c. Les coefficients u et v s'obtiennent en remontant l'algorithme d'Euclide.

Quelle différence entre le lemme d'Euclide et le lemme de Gauss ?

Le lemme d'Euclide dit qu'un nombre premier qui divise un produit divise l'un des facteurs. Le lemme de Gauss le généralise : si a divise bc et si a est premier avec b, alors a divise c. L'hypothèse ne peut pas être retirée : 6 divise 4 × 3 = 12 sans diviser ni 4 ni 3.

Que représente Z/nZ ?

C'est l'ensemble des classes de congruence modulo n : il y en a n, celles de 0, 1, ..., n - 1. On peut y additionner et y multiplier, car la congruence est compatible avec ces opérations. Pour n au moins égal à 2, la classe d'un entier a y est inversible exactement quand a est premier avec n ; toutes les classes non nulles le sont donc quand n est premier.

Y a-t-il un cours en vidéo sur « Arithmétique » (Algèbre 1) ?

Oui. Sur MC² Academy, le chapitre « Arithmétique » du module Algèbre 1 compte 1 résumé et 3 séries d'exercices corrigés. L'inscription est gratuite.

À revoir, pour aller plus loin

Algèbre 1Relations binairesRelations binaires en Algèbre 1 : équivalence, classes et ensemble quotient, ordre total ou partiel, majorant et plus grand élément, avec des exemples corrigés.Algèbre 2PolynômesPolynômes en Algèbre 2 : degré, division euclidienne, racines et multiplicité, relations coefficients-racines, factorisation dans C[X] et R[X], avec exemples.

Travaille « Arithmétique » avec MC²

Ton compte est gratuit, sans carte bancaire : tu retrouves le module Algèbre 1 et tout ton programme.

Yallah, bda dabaLeçon gratuite, sans compte