Résumé de cours MPSI : raisonnement, relations et arithmétique

↩ Chapitre : Raisonnement, ensembles et arithmétique (MPSI)

L’essentiel des chapitres Raisonnement et vocabulaire ensembliste et Arithmétique dans ℤ du programme officiel de MPSI (premier semestre).

1. Logique, ensembles, applications

  • Contraposée, absurde, disjonction des cas, analyse-synthèse ; récurrence simple, double, forte (liée au fait que toute partie non vide de \mathbb N a un plus petit élément).
  • Image directe, image réciproque f^{-1}(B) ; injections, surjections, bijections ; (g\circ f)^{-1}=f^{-1}\circ g^{-1}.
  • Relation d’équivalence (réflexive, symétrique, transitive) : ses classes forment une partition. Exemples : congruences dans \mathbb R et \mathbb Z.
  • Relation d’ordre (réflexive, antisymétrique, transitive), ordre partiel ou total (la divisibilité sur \mathbb N est un ordre partiel).

2. Divisibilité, PGCD, Bézout

Théorèmes

  • Division euclidienne : a=bq+r, 0\leqslant r<|b|. a\mid b et b\mid a \iff a=\pm b.
  • Euclide : a\wedge b=b\wedge r ; les diviseurs communs de a et b sont les diviseurs de a\wedge b ; (ka)\wedge(kb)=k(a\wedge b).
  • Bézout : il existe u,v avec au+bv=a\wedge b (algorithme d’Euclide étendu) ; a\wedge b=1\iff\exists u,v,\ au+bv=1.
  • Gauss : a\mid bc et a\wedge b=1\Rightarrow a\mid c. Si a\wedge b=1, a\mid n et b\mid n \Rightarrow ab\mid n.
  • ab=(a\wedge b)(a\vee b) pour a,b\geqslant0 ; forme irréductible d’un rationnel. PGCD d’un nombre fini d’entiers ; premiers entre eux dans leur ensemble \neq deux à deux.

3. Nombres premiers et congruences

  • Infinité des nombres premiers ; crible d’Ératosthène ; décomposition unique n=\prod p^{v_p(n)}.
  • Valuation p-adique : v_p(ab)=v_p(a)+v_p(b) ; a\mid b\iff v_p(a)\leqslant v_p(b) pour tout p ; v_p(a\wedge b)=\min, v_p(a\vee b)=\max.
  • Congruences : compatibles avec + et \times ; si a\wedge n=1, a a un inverse modulo n (par Bézout), d’où la résolution de ax\equiv b\ [n].

Petit théorème de Fermat

Si p est premier : a^p\equiv a\ [p] pour tout a\in\mathbb Z, et a^{p-1}\equiv1\ [p] si p\nmid a.

À savoir sur le programme

Les anneaux \mathbb Z/n\mathbb Z et la notion d’ensemble quotient sont hors programme en MPSI ; l’approche reste élémentaire.

4. Pièges classiques

  • a\mid bc n’implique pas a\mid b ou a\mid c (sauf si a est premier).
  • On ne simplifie une congruence par a que si a\wedge n=1 : 2x\equiv2\ [4] n’entraîne pas x\equiv1\ [4].

Publications similaires