BURHAN.

Arithmétique dans ℤ : Résumé de cours de Mathématiques 2BAC Sciences Mathématiques

Arithmétique dans ℤ : résumé de maths 2BAC SM, avec les points essentiels, les formules et les méthodes à retenir pour réviser avant un contrôle. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).

L'essentiel en une page

Ce chapitre repose sur peu d'outils, mais chacun a ses conditions. Ce sont elles que le correcteur vérifie. On note a∧ba \wedge b le PGCD de aa et bb, et a∨ba \vee b leur PPCM.

Division euclidienne, b entier naturel non nul
a=bq+r,0≤r<ba = bq + r, \quad 0 \leq r < b
Congruence
a≡b [n]⇔n∣a−ba \equiv b \ [n] \Leftrightarrow n \mid a - b
Bézout
a∧b=1⇔∃(u,v)∈Z2, au+bv=1a \wedge b = 1 \Leftrightarrow \exists (u, v) \in \mathbb{Z}^2, \ au + bv = 1
Gauss
a∣bc et a∧b=1⇒a∣ca \mid bc \text{ et } a \wedge b = 1 \Rightarrow a \mid c
Fermat, p premier ne divisant pas a
ap−1≡1 [p]a^{p-1} \equiv 1 \ [p]
Fermat, p premier, tout entier a
ap≡a [p]a^{p} \equiv a \ [p]
Inverse modulo n
a‾ inversible dans Z/nZ⇔a∧n=1\overline{a} \text{ inversible dans } \mathbb{Z}/n\mathbb{Z} \Leftrightarrow a \wedge n = 1
Solutions de ax + by = c, a et b premiers entre eux
(x0+bk, y0−ak), k∈Z(x_0 + bk, \ y_0 - ak), \ k \in \mathbb{Z}
PGCD et PPCM, a et b entiers naturels non nuls
(a∧b)(a∨b)=ab(a \wedge b)(a \vee b) = ab

À retenirLa chaîne à reconnaître

Un premier pp, puis p∤ap \nmid a, puis a∧p=1a \wedge p = 1, puis Fermat, puis une congruence modulo pp, puis la conclusion. Chaque maillon se justifie par un énoncé que tu nommes.

Divisibilité et congruences

En clair : a∣ba \mid b veut dire que b=kab = ka pour un certain entier relatif kk. Par exemple 9∣−639 \mid -63, car −63=(−7)×9-63 = (-7) \times 9. En revanche 9∤489 \nmid 48.

PropriétéPropriétés de la divisibilité

Soient aa, bb et cc des entiers relatifs.

  1. Si a∣ba \mid b et b∣cb \mid c, alors a∣ca \mid c.
  2. Si a∣ba \mid b et a∣ca \mid c, alors a∣bλ+cμa \mid b\lambda + c\mu pour tous entiers relatifs λ\lambda et μ\mu.
  3. Si a∣ba \mid b et b≠0b \neq 0, alors ∣a∣≤∣b∣\lvert a \rvert \leq \lvert b \rvert.
  4. Si a∣ba \mid b et b∣ab \mid a, alors a=ba = b ou a=−ba = -b.

ThéorèmeDivision euclidienne dans ℤ

Soient aa un entier relatif et bb un entier naturel non nul. Il existe un unique couple (q,r)(q, r) d'entiers relatifs tel que a=bq+ret0≤r<b.a = bq + r \quad \text{et} \quad 0 \leq r < b. L'entier qq est le quotient et l'entier rr le reste de la division euclidienne de aa par bb.

ExempleDiviser un entier négatif

On divise −38-38 par 99 : −38=9×(−5)+7-38 = 9 \times (-5) + 7, avec 0≤7<90 \leq 7 < 9. Le quotient vaut −5-5 et le reste vaut 77.

DéfinitionCongruence modulo n

Soit nn un entier naturel non nul. Deux entiers relatifs aa et bb sont congrus modulo nn si n∣a−bn \mid a - b. On écrit alors a≡b [n]a \equiv b \ [n], et on lit « aa est congru à bb modulo nn ».

PropriétéCongruence et reste

Soient nn un entier naturel non nul et aa, bb deux entiers relatifs.

  1. 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.
  2. Tout entier relatif aa est congru modulo nn à son reste rr, et à aucun autre entier de {0,1,…,n−1}\{0, 1, \dots, n - 1\}.

ExempleUn reste sans gros calcul

Cherchons le reste de 53×71+4653 \times 71 + 46 modulo 88. On a 53≡5 [8]53 \equiv 5 \ [8], 71≡7 [8]71 \equiv 7 \ [8] et 46≡6 [8]46 \equiv 6 \ [8]. Donc 53×71+46≡5×7+6 [8]53 \times 71 + 46 \equiv 5 \times 7 + 6 \ [8], soit 41≡1 [8]41 \equiv 1 \ [8]. Le reste est 11.

PropriétéOpérations sur les congruences

Soit nn un entier naturel non nul.

  1. Pour tous entiers relatifs aa, bb, cc : a≡a [n]a \equiv a \ [n] ; si a≡b [n]a \equiv b \ [n], alors b≡a [n]b \equiv a \ [n] ; si a≡b [n]a \equiv b \ [n] et b≡c [n]b \equiv c \ [n], alors a≡c [n]a \equiv c \ [n].
  2. Pour tous entiers relatifs aa, bb, cc, dd : si a≡b [n]a \equiv b \ [n] et c≡d [n]c \equiv d \ [n], alors a+c≡b+d [n]a + c \equiv b + d \ [n] et ac≡bd [n]ac \equiv bd \ [n].
  3. Pour tous entiers relatifs aa, bb : si a≡b [n]a \equiv b \ [n], alors ak≡bk [n]a^k \equiv b^k \ [n] pour tout entier naturel kk.

MéthodeReste d'une puissance

  1. Repère un petit exposant k≥1k \geq 1 pour lequel ak≡1 [n]a^k \equiv 1 \ [n].
  2. Divise l'exposant NN par kk : N=kq+rN = kq + r, avec 0≤r<k0 \leq r < k.
  3. Rédige : aN=(ak)q×ara^N = (a^k)^q \times a^r, donc aN≡ar [n]a^N \equiv a^r \ [n], d'après les opérations sur les congruences.

ExemplePuissance de 3 modulo 11

35=243=22×11+13^5 = 243 = 22 \times 11 + 1, donc 35≡1 [11]3^5 \equiv 1 \ [11]. Comme 2026=5×405+12026 = 5 \times 405 + 1, on obtient 32026=(35)405×3≡3 [11]3^{2026} = (3^5)^{405} \times 3 \equiv 3 \ [11].

Nombres premiers et décomposition

En clair : un nombre premier pp vérifie p≥2p \geq 2 et n'a que deux diviseurs positifs, 11 et pp. Leur ensemble se note P\mathbb{P}. Le nombre 11 n'est pas premier.

PropriétéPlus petit diviseur premier

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

  1. Le plus petit diviseur pp de nn tel que p≥2p \geq 2 est un nombre premier. En particulier, nn admet au moins un diviseur premier.
  2. Si nn est composé, alors p2≤np^2 \leq n.
  3. Par conséquent, si aucun nombre premier pp tel que p2≤np^2 \leq n ne divise nn, alors nn est premier.

Exemple223 est-il premier ?

On a 142=196≤223<225=15214^2 = 196 \leq 223 < 225 = 15^2. Il suffit donc de tester 22, 33, 55, 77, 1111 et 1313. Aucun d'eux ne divise 223223 : 223223 est premier.

ThéorèmeInfinité des nombres premiers

L'ensemble P\mathbb{P} des nombres premiers est infini.

ThéorèmeThéorème fondamental de l'arithmétique

Tout entier naturel n≥2n \geq 2 s'écrit comme un produit de nombres premiers, et cette écriture est unique à l'ordre des facteurs près. En regroupant les facteurs égaux : n=p1α1p2α2⋯pkαk,n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, où l'entier kk, les nombres premiers p1<p2<⋯<pkp_1 < p_2 < \dots < p_k et les entiers naturels non nuls α1,…,αk\alpha_1, \dots, \alpha_k sont uniques.

PropriétéDiviseurs, PGCD et PPCM par la décomposition

Soient p1<p2<⋯<pkp_1 < p_2 < \dots < p_k des nombres premiers.

  1. Si n=p1α1⋯pkαkn = p_1^{\alpha_1} \cdots p_k^{\alpha_k} avec des exposants αi\alpha_i entiers naturels, les diviseurs positifs de nn sont les entiers p1γ1⋯pkγkp_1^{\gamma_1} \cdots p_k^{\gamma_k} avec 0≤γi≤αi0 \leq \gamma_i \leq \alpha_i pour tout ii. Leur nombre est (α1+1)(α2+1)⋯(αk+1)(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1).
  2. Si a=p1α1⋯pkαka = p_1^{\alpha_1} \cdots p_k^{\alpha_k} et b=p1β1⋯pkβkb = p_1^{\beta_1} \cdots p_k^{\beta_k}, avec des exposants entiers naturels éventuellement nuls, alors a∧b=p1min⁡(α1,β1)⋯pkmin⁡(αk,βk)eta∨b=p1max⁡(α1,β1)⋯pkmax⁡(αk,βk).a \wedge b = p_1^{\min(\alpha_1, \beta_1)} \cdots p_k^{\min(\alpha_k, \beta_k)} \quad \text{et} \quad a \vee b = p_1^{\max(\alpha_1, \beta_1)} \cdots p_k^{\max(\alpha_k, \beta_k)}.
  3. Pour tous entiers naturels non nuls aa et bb : (a∧b)(a∨b)=ab(a \wedge b)(a \vee b) = ab.

ExempleLire une décomposition

540=22×33×5540 = 2^2 \times 3^3 \times 5 possède (2+1)(3+1)(1+1)=24(2 + 1)(3 + 1)(1 + 1) = 24 diviseurs positifs. Avec 252=22×32×7252 = 2^2 \times 3^2 \times 7, on lit 540∧252=22×32=36540 \wedge 252 = 2^2 \times 3^2 = 36 et 540∨252=22×33×5×7=3780540 \vee 252 = 2^2 \times 3^3 \times 5 \times 7 = 3780.

PGCD, Euclide, Bézout, Gauss

En clair : a∧ba \wedge b est le plus grand diviseur positif commun à aa et bb. a∨ba \vee b est leur plus petit multiple commun strictement positif. Deux entiers sont premiers entre eux lorsque a∧b=1a \wedge b = 1.

PropriétéAlgorithme d'Euclide

Soient aa et bb deux entiers naturels non nuls. On pose r0=ar_0 = a et r1=br_1 = b, puis, tant que rk≠0r_k \neq 0, on note rk+1r_{k+1} le reste de la division euclidienne de rk−1r_{k-1} par rkr_k. Il existe un rang m≥1m \geq 1 tel que rm≠0r_m \neq 0 et rm+1=0r_{m+1} = 0, et alors a∧b=rm.a \wedge b = r_m. Le PGCD de aa et bb est le dernier reste non nul.

ExempleEuclide sur 611 et 247

Division Reste
611=247×2+117611 = 247 \times 2 + 117 117117
247=117×2+13247 = 117 \times 2 + 13 1313
117=13×9+0117 = 13 \times 9 + 0 00

Le dernier reste non nul est 1313, donc 611∧247=13611 \wedge 247 = 13.

MéthodeRemonter Euclide pour un couple (u, v)

Isole chaque reste, puis remonte les lignes depuis le dernier reste non nul. Ici 13=247−2×11713 = 247 - 2 \times 117 et 117=611−2×247117 = 611 - 2 \times 247. On remplace : 13=611×(−2)+247×513 = 611 \times (-2) + 247 \times 5. Contrôle toujours ton couple en recalculant au+bvau + bv.

ThéorèmeIdentité de Bézout

Soient aa et bb deux entiers relatifs non tous les deux nuls, et d=a∧bd = a \wedge b.

  1. Il existe deux entiers relatifs uu et vv tels que au+bv=dau + bv = d.
  2. Un entier relatif divise à la fois aa et bb si et seulement s'il divise dd.

ThéorèmeThéorème de Bézout

Deux entiers relatifs aa et bb sont premiers entre eux si et seulement s'il existe deux entiers relatifs uu et vv tels que au+bv=1.au + bv = 1.

En pratique : pour prouver a∧b=1a \wedge b = 1, il suffit d'exhiber un couple. Par exemple 8×(−4)+11×3=18 \times (-4) + 11 \times 3 = 1, donc 8∧11=18 \wedge 11 = 1.

ThéorèmeThéorème de Gauss

Soient aa, bb et cc des entiers relatifs. Si a∣bca \mid bc et si a∧b=1a \wedge b = 1, alors a∣ca \mid c.

PropriétéConséquences du théorème de Gauss

Soient pp un nombre premier et aa, bb, nn des entiers relatifs.

  1. Si p∤ap \nmid a, alors a∧p=1a \wedge p = 1.
  2. Si p∣abp \mid ab, alors p∣ap \mid a ou p∣bp \mid b.
  3. Si a∣na \mid n, b∣nb \mid n et a∧b=1a \wedge b = 1, alors ab∣nab \mid n.
  4. Si pp divise un produit a1a2⋯asa_1 a_2 \cdots a_s d'entiers relatifs (s≥1s \geq 1), alors pp divise l'un des aia_i.

MéthodeRédiger un argument de Gauss

  1. Écris la divisibilité d'un produit : a∣bca \mid bc.
  2. Justifie a∧b=1a \wedge b = 1 : par un couple de Bézout, par les décompositions, ou parce que aa est premier et a∤ba \nmid b.
  3. Conclus en nommant le théorème. Exemple : 15∣4m15 \mid 4m et 15∧4=115 \wedge 4 = 1, donc 15∣m15 \mid m d'après le théorème de Gauss.

ℤ/nℤ et petit théorème de Fermat

En clair : modulo n≥2n \geq 2, la classe a‾\overline{a} réunit tous les entiers qui ont le même reste que aa. Il y a exactement nn classes : 0‾,1‾,…,n−1‾\overline{0}, \overline{1}, \dots, \overline{n-1}. On calcule sur les classes comme sur les restes : a‾+b‾=a+b‾\overline{a} + \overline{b} = \overline{a + b} et a‾×b‾=ab‾\overline{a} \times \overline{b} = \overline{ab}.

PropriétéClasses inversibles de ℤ/nℤ

Soient nn un entier naturel, n≥2n \geq 2, et aa un entier relatif. La classe a‾\overline{a} est inversible dans Z/nZ\mathbb{Z}/n\mathbb{Z}, c'est-à-dire qu'il existe une classe b‾\overline{b} telle que a‾×b‾=1‾\overline{a} \times \overline{b} = \overline{1}, si et seulement si a∧n=1a \wedge n = 1.

MéthodeInverser une classe

Vérifie a∧n=1a \wedge n = 1, trouve uu et vv tels que au+nv=1au + nv = 1, puis conclus : a‾×u‾=1‾\overline{a} \times \overline{u} = \overline{1}. Modulo 2626 : 7×(−11)+26×3=17 \times (-11) + 26 \times 3 = 1, donc l'inverse de 7‾\overline{7} est −11‾=15‾\overline{-11} = \overline{15}.

PropriétéLe cas de ℤ/pℤ, p premier

Soit pp un nombre premier.

  1. Toute classe non nulle de Z/pZ\mathbb{Z}/p\mathbb{Z} est inversible.
  2. Pour toutes classes a‾\overline{a} et b‾\overline{b} de Z/pZ\mathbb{Z}/p\mathbb{Z} : si a‾×b‾=0‾\overline{a} \times \overline{b} = \overline{0}, alors a‾=0‾\overline{a} = \overline{0} ou b‾=0‾\overline{b} = \overline{0}.

ExempleLes inverses dans ℤ/11ℤ

1111 est premier : chaque classe non nulle a un inverse.

a‾\overline{a} 1‾\overline{1} 2‾\overline{2} 3‾\overline{3} 4‾\overline{4} 5‾\overline{5} 6‾\overline{6} 7‾\overline{7} 8‾\overline{8} 9‾\overline{9} 10‾\overline{10}
inverse 1‾\overline{1} 6‾\overline{6} 4‾\overline{4} 3‾\overline{3} 9‾\overline{9} 2‾\overline{2} 8‾\overline{8} 7‾\overline{7} 5‾\overline{5} 10‾\overline{10}

Le petit théorème de Fermat est utilisé dans 11 des 13 exercices d'arithmétique consultés.

ThéorèmePetit théorème de Fermat

Soit pp un nombre premier.

  1. Pour tout entier relatif aa tel que p∤ap \nmid a : ap−1≡1 [p]a^{p-1} \equiv 1 \ [p].
  2. Pour tout entier relatif aa : ap≡a [p]a^p \equiv a \ [p].

MéthodeFermat puis réduction de l'exposant modulo p − 1

  1. Écris les deux hypothèses : pp est premier et p∤ap \nmid a.
  2. Déduis-en ap−1≡1 [p]a^{p-1} \equiv 1 \ [p].
  3. Divise l'exposant NN par p−1p - 1 : N=(p−1)q+rN = (p - 1)q + r, avec 0≤r<p−10 \leq r < p - 1.
  4. Conclus : aN≡ar [p]a^N \equiv a^r \ [p].

ExempleReste de 6 puissance 1000 modulo 17

1717 est premier et 17∤617 \nmid 6, donc 616≡1 [17]6^{16} \equiv 1 \ [17]. Or 1000=16×62+81000 = 16 \times 62 + 8, donc 61000≡68 [17]6^{1000} \equiv 6^8 \ [17]. Puis 62=36≡2 [17]6^2 = 36 \equiv 2 \ [17], d'où 68≡24=16 [17]6^8 \equiv 2^4 = 16 \ [17]. Le reste est 1616.

Équation ax + by = c

ThéorèmeExistence de solutions de ax + by = c

Soient aa et bb deux entiers relatifs non nuls, cc un entier relatif et d=a∧bd = a \wedge b. L'équation ax+by=cax + by = c, d'inconnue (x,y)∈Z2(x, y) \in \mathbb{Z}^2, admet au moins une solution si et seulement si d∣cd \mid c.

ThéorèmeSolutions de ax + by = c

Soient aa et bb deux entiers relatifs non nuls et premiers entre eux, cc un entier relatif, et (x0,y0)(x_0, y_0) une solution de l'équation ax+by=cax + by = c dans Z2\mathbb{Z}^2. Les solutions de cette équation dans Z2\mathbb{Z}^2 sont exactement les couples (x0+bk, y0−ak),k∈Z.(x_0 + bk, \ y_0 - ak), \quad k \in \mathbb{Z}.

MéthodeRésoudre ax + by = c : Bézout puis Gauss

  1. Calcule d=a∧bd = a \wedge b. Si d∤cd \nmid c, il n'y a aucune solution.
  2. Sinon, divise l'équation par dd : les nouveaux coefficients sont premiers entre eux.
  3. Trouve une solution particulière (x0,y0)(x_0, y_0), par exemple à partir d'un couple de Bézout.
  4. Écris toutes les solutions avec les coefficients simplifiés, puis vérifie-les dans l'équation.

ExempleRésoudre 18x + 42y = 30

Ici d=18∧42=6d = 18 \wedge 42 = 6 et 6∣306 \mid 30. On simplifie : 3x+7y=53x + 7y = 5, avec 3∧7=13 \wedge 7 = 1. Comme 3×(−2)+7×1=13 \times (-2) + 7 \times 1 = 1, le couple (−10,5)(-10, 5) est solution. Les solutions sont les couples (−10+7k, 5−3k)(-10 + 7k, \ 5 - 3k), k∈Zk \in \mathbb{Z}. En revanche, 18x+42y=2518x + 42y = 25 n'a aucune solution, car 6∤256 \nmid 25.

Écriture en base b

ThéorèmeÉcriture en base b

Soit bb un entier naturel, b≥2b \geq 2. Tout entier naturel non nul nn s'écrit de manière unique sous la forme n=akbk+ak−1bk−1+⋯+a1b+a0,n = a_k b^k + a_{k-1} b^{k-1} + \dots + a_1 b + a_0, où kk est un entier naturel et où les chiffres a0,a1,…,aka_0, a_1, \dots, a_k sont des entiers tels que 0≤ai≤b−10 \leq a_i \leq b - 1 et ak≠0a_k \neq 0. On note n=akak−1…a1a0‾(b)n = \overline{a_k a_{k-1} \dots a_1 a_0}^{(b)}.

Exemple2026 en base 7

Division par 77 Reste
2026=7×289+32026 = 7 \times 289 + 3 33
289=7×41+2289 = 7 \times 41 + 2 22
41=7×5+641 = 7 \times 5 + 6 66
5=7×0+55 = 7 \times 0 + 5 55

On lit les restes du dernier au premier : 2026=5623‾(7)2026 = \overline{5623}^{(7)}.

ExempleRetour en base dix

On développe selon les puissances de la base : 10110‾(2)=24+22+2=22\overline{10110}^{(2)} = 2^4 + 2^2 + 2 = 22. Chaque chiffre en base bb reste compris entre 00 et b−1b - 1.

Méthodes d'examen

Tu dois Outil À écrire d'abord
trouver le reste d'une puissance cycle des restes ou Fermat le module ; pour Fermat, pp premier et p∤ap \nmid a
montrer a∧b=1a \wedge b = 1 Bézout un couple (u,v)(u, v) et le calcul au+bv=1au + bv = 1
passer de a∣bca \mid bc à a∣ca \mid c Gauss a∧b=1a \wedge b = 1
inverser a‾\overline{a} modulo nn Bézout a∧n=1a \wedge n = 1
résoudre ax+by=cax + by = c Bézout puis Gauss d∣cd \mid c et une solution particulière
décider si nn est premier premiers pp tels que p2≤np^2 \leq n la liste des premiers testés

MéthodeLa chaîne « un premier p »

  1. Un premier : introduis pp et dis pourquoi il est premier (hypothèse, ou plus petit diviseur premier d'un entier).
  2. Premiers entre eux : montre que p∤ap \nmid a, puis déduis a∧p=1a \wedge p = 1.
  3. Fermat : les deux hypothèses écrites, pose ap−1≡1 [p]a^{p-1} \equiv 1 \ [p].
  4. Congruence : combine avec la donnée de l'énoncé, module toujours écrit.
  5. Conclusion : par exemple une division de l'exposant par p−1p - 1, ou une contradiction.

ExempleLa chaîne sur un exemple

Soit pp un nombre premier différent de 55. Ses seuls diviseurs positifs sont 11 et pp, donc 5∤p5 \nmid p. Comme 55 est premier, Fermat donne p4≡1 [5]p^4 \equiv 1 \ [5]. Puis 42=4×10+242 = 4 \times 10 + 2, donc p42=(p4)10×p2≡p2 [5]p^{42} = (p^4)^{10} \times p^2 \equiv p^2 \ [5].

MéthodeRaisonner sur le plus petit diviseur premier

  1. Pose pp le plus petit diviseur premier de nn : il existe dès que n≥2n \geq 2.
  2. Traduis l'hypothèse de l'énoncé en congruence modulo pp.
  3. Exploite la minimalité : aucun entier compris entre 22 et p−1p - 1 ne divise nn.

ExemplePremiers entre eux pour tout k

Pour tout entier kk : (3k+2)×2+(2k+1)×(−3)=1(3k + 2) \times 2 + (2k + 1) \times (-3) = 1. D'après le théorème de Bézout, (3k+2)∧(2k+1)=1(3k + 2) \wedge (2k + 1) = 1.

Point important : savoir écrire une identité au+bv=1au + bv = 1, puis la vérifier par le calcul.

Pièges classiques

AttentionSimplifier une congruence

4×5≡4×2 [12]4 \times 5 \equiv 4 \times 2 \ [12], et pourtant 5≢2 [12]5 \not\equiv 2 \ [12]. Ici 4∧12=44 \wedge 12 = 4. En revanche, si cx≡cy [n]cx \equiv cy \ [n] et c∧n=1c \wedge n = 1, on peut simplifier : n∣c(x−y)n \mid c(x - y) et le théorème de Gauss donnent n∣x−yn \mid x - y.

AttentionLes hypothèses de Fermat

La forme ap−1≡1 [p]a^{p-1} \equiv 1 \ [p] exige p∤ap \nmid a : avec p=11p = 11 et a=22a = 22, on a 2210≡0 [11]22^{10} \equiv 0 \ [11]. Elle exige aussi un module premier : avec 99, qui n'est pas premier, 28=256≡4 [9]2^8 = 256 \equiv 4 \ [9].

AttentionGauss sans primalité relative

10∣4×1510 \mid 4 \times 15, mais 10∤410 \nmid 4 et 10∤1510 \nmid 15. Gauss exige a∧b=1a \wedge b = 1, or 10∧4=210 \wedge 4 = 2.

AttentionLire une égalité de Bézout

9×1+15×1=249 \times 1 + 15 \times 1 = 24, et pourtant 9∧15=39 \wedge 15 = 3. Une égalité au+bv=kau + bv = k ne donne pas le PGCD en général : elle dit seulement que a∧ba \wedge b divise kk. Avec k=1k = 1, en revanche, on conclut a∧b=1a \wedge b = 1 par le théorème de Bézout.

AttentionUn reste négatif

−50=7×(−7)−1-50 = 7 \times (-7) - 1 n'est pas une division euclidienne. On écrit −50=7×(−8)+6-50 = 7 \times (-8) + 6, avec 0≤6<70 \leq 6 < 7.

AttentionProduit nul modulo n

Dans Z/10Z\mathbb{Z}/10\mathbb{Z}, 4‾×5‾=0‾\overline{4} \times \overline{5} = \overline{0}, alors qu'aucune des deux classes n'est nulle. Cette règle ne vaut que modulo un nombre premier.

AttentionDeux barres différentes

12‾(5)\overline{12}^{(5)} désigne le nombre 77 écrit en base 55. Sans l'exposant, 12‾\overline{12} est une classe de Z/nZ\mathbb{Z}/n\mathbb{Z}.

Checklist avant l'examen

  • Chaque division euclidienne porte son encadrement 0≤r<b0 \leq r < b.
  • Chaque congruence porte son module.
  • Avant Gauss, la primalité relative est écrite et justifiée.
  • Avant Fermat, « pp est premier » et « p∤ap \nmid a » sont écrits.
  • Chaque couple de Bézout est vérifié par le calcul.
  • Les solutions de ax+by=cax + by = c sont remplacées dans l'équation.
  • Avec Fermat, l'exposant se réduit modulo p−1p - 1, jamais modulo pp.