MATH203 : Introduction à l'algèbre

Feuilles de TD : 1 2

Que sont les mathématiques

En mathématique on étudie les propriétés d'objets tels que les nombres, les droites, ... Ces objets sont dénotés par des "expressions" comme

• x^2 - 1,
• Le milieu du segment [A,B],
• f est continue.

Chaque domaine des mathématiques possède son propre "voacabulaire" pour écrire des expressions et ce vocabulaire est introduit dans chacun de vos cours.

L'égalité joue un rôle particulier en mathématique car elle est "subtitutive" : si deux expressions a et b sont égales, on peut remplacer a par b dans toute expression sans en changer la valeur. Il faut tout de même faire attention aux variables liées. Considérons l'exemple suivant:

 Soit y un réel et  x = y + 2, on a donc x - y = 2. 
 Pour $x\in \mathbb {R}$, définissons la fonction f(x) = x^2 - y^2 = (x - y)(x + y). 
 On a donc pour tout $x\in \mathbb {R}$ f(x) = 2(x + y) (pour un x particulier). 

On a commis une erreur car x est une variable liée dans la seconde phrase. On peut toujours changer le nom des variables liées et écrire

 Soit y un réel et  x = y + 2, on a donc x - y = 2. 
 Pour $z\in \mathbb {R}$, définissons la fonction f(z) = z^2 - y^2 = (z - y)(z + y).
 On a donc f(x) = 2(x + y). 

Parmis les expressions certaines sont des "énoncés", c'est à dire des expressions dont la valeur est vraie ou fausse comme

• x^2 - 1 = (x - 1)(x + 1)
• Les trois droites sont concourantes
• Toute fonction continue est dérivable (cet énoncé est faux, mais on peut l'écrire !)

Les mathématiques ont pour objet de découvrir quels énoncés sont vrais en partant uniquement "d'axiomes" qui sont des énoncés que l'on adment comme vrais dans un domaine donné des mathématiques.

Tous les énoncés mathématiques peuvent être ecrit en utilisant les "briques" de construction suivantes :

• Des énoncés atomiques propre à chaque domaine des mathématique comme $x\in E$, "f est continue", ... Attention: certains énoncés atomiques peuvent être transformés en énoncés plus complexe en faisant appel à une définition (c'est le cas de "f est continue").
• l'implication : notée $A\Rightarrow B$, $A\rightarrow B$, A implique B, A est une condition suffisante pour B, B est une condition nécessaire pour A, si A alors B, ...

Attention, l'implication mathématique est très différente de l'implication en langage courant qui contient souvent une relation de cause à effet voire qui exprime une équivalence : "si tu ne mange pas ta soupe tu n'aura pas de déssert" est une équivalence en langue naturelle.

$A\Rightarrow B$ est faux uniquement si A est vrai et B est faux. Dans les trois autres cas, l'implication mathématique est vraie. Pour ce persuader que c'est cela qu'il faut faire, considérer l'énoncé suivant (qui est bien vrai ?) :

 Si n est divisible par 4 alors n est pair

• Pour n = 2 on obtient "Faux implique Vrai"
• Pour n = 3 on obtient "Faux implique Faux"
• Pour n = 4 on obitent "Vrai implique Vrai"

• La conjonction : notée "A et B", "$A\land B$", ... Le sens devrait être clair
• La disjonction : notée "A ou B", "$A\lor B$", ... C'est le ou usuel. A ou B est vrai si l'un des deux enoncés au moins est vrai. Il ne faut pas le confondre avec le "ou exclusif", utilisé en informatique, et qui est faux lorsque les deux énoncés sont vrais en même temps.
• La négation : notée "non A", "A est faux", "il est faux que A", "$\lnot A$", ... On a non A est vrai si et seulement si A est faux et donc aussi non A est faux si et seulement si A est vrai.
• L'équivalence : notée "A équivalent à B", "A si et seulement si B", "A est une condition nécessaire et suffisante pour B", "$A\Leftrightarrow B$", "$A\leftrightarrow B$". "$A\Leftrightarrow B$" peut être défini comme "(A implique B) et (B implique A)".
• La quantification universelle : notée "pour tout x A", "on a A pour tout x", "quelque soit x A", $\forall xA$, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.
• La quantification existentielle : notée "il existe x tel que A", "on a A pour au moins un x", "on peut trouver un x tel que A", $\exists xA$, ... Le sens devrait être clair, mais attention la manipulation des quantificateurs est difficile en pratique.

Qu'est-ce qu'une preuve

• Définitions  :
  • Une preuve est un texte pour convaincre constitué d'une suite d'étapes telles qu'à chacune d'elles, on a :

1. des connaissances : liste d'objets connus, de théorèmes, d'hypothèses locales au problème
2. un but à démontrer

• • Pour passe d'une étape à l'autre, on peut :

1. chercher à simplifier le but/le diviser
2. utiliser des connaissances pour progresser (montrer le but, obtenir de nouvelles connaissances, faire un lemme...)

• 6X2+2+... briques de bases  :
  • Si le but est dans la liste des connaissances ou si A et ¬ A sont dans les connaissances, alors la preuve est finie.
  • 6X2 briques de bases:

1. Montrer que A=>B : Ajouter A aux hypothèses et montrer B / Utiliser que A=B : Démontrer A pour pouvoir ajouter B aux connaissances
2. Montrer que A et B  : Deux preuves dont l'ordre n'a pas d'importance / Utiliser que A et B  : Rajouter A et B aux connaissances, et utiliser l'une et/ou l'autre
3. Montrer que A ou B  : On montre A ou B, au choix / Utiliser que A ou B  : Raisonner par disjonction de cas, on a alors deux preuves; rajouter A aux connaissances et montrer le but et rajouter B dans les connaissances et montrer le but
4. Montrer que ¬ A  : Supposer A et chercher une contradiction / Utiliser que ¬ A  : Montrer A et en déduire une contradiction
5. Montrer que ∀ x, A  : Montrer A pour un x quelconque / Utiliser que ∀ x, A  : Prendre le x qui nous intéresse et supposer A(x).
6. Montrer que ∃ x, A  : Montrer A pour un x bien choisi / Utiliser que ∃ x, A : Prendre un nouveau x et supposer A(x)

• • Démonstration par l'absurde  : Si le but est A, alors on suppose ¬ A et on cherche une contradiction (particulièrement fréquent pour montrer un ou , ∃ , ou un énoncé atomique .
  • Il existe d'autres briques propres au domaine dans lequel on se place ( exemple  : preuve par récurrence en arithmétique)

Ensembles, Fonctions, Relations

• Théorie des ensembles
  • Schéma de compréhension  : {x ∈ A / P(x)} est l'ensemble des x de A qui ont la propriété P
  • Paradoxe de Russel  : Soit A={x / x $\notin$ x}. Si A ∈ A alors A $\notin$ A et si A $\notin$ A alors A ∈ A. D'où une contradiction qui aboutit au théorème de Zermels et Frankel, modifiant le schéma de compréhension : {x ∈ A / ...}
  • Construction des ensembles  :

1. A ∪ B={x / x ∈ A ou x ∈ B}
2. A ∩ B={x / x ∈ A et x ∈ B}
3. A^c={x $\notin$ A}
4. A-B=A ∩ B^c={x / x ∈ A et x $\notin$ B}
5. P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
6. AXB où X est appelé produit cartésien : ensemble de couples; {(a,b) P(P(A ∪ B)) / a ∈ A b ∈ B}

• • Inverse d'une relation R  : Soit R ⊂ P(AXB), on peut toujours définir R^-1. R^-1={(b,a) / b ∈ B, a ∈ A, et (a,b) ∈ R}
• Fonction de A dans B  :
  • notée A → B, F(A,B)
  • F(A,B)=_déf{R ⊂ (AXB) / ∀ a ∈ A ∀ b, b' ∈ B, ((aRb) et (aRb')) ⇒ (b=b')}
  • Si f ∈ F(A,B), on écrit b=f(a).
• Application de A dans B  :
  • notée A'A,B) ou B^A
  • A(A,B)={f ∈ F(A,B) / ∀ a ∈ A ∃ b ∈ B tel que b=f(a)}
• Restriction  : Soient f ∈ F(A,B) et A' ⊂ A, f_l`A' ∈ F(A',B)={(a,b) / a ∈ A' et b=f(a)}
• Image directe  : Soient f ∈ F(A,B) et A' ⊂ A, f(A')={b ∈ B / ∃ a ∈ A' b=f(a)}
• Image réciproque  : Soient f ∈ F(A,B) et B' ⊂ B f^-1(B')={a ∈ A / f(a) ∈ B' }
• Inclusion  : A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B)
• Injection  :
  • notée parfois A $\hookrightarrow$ B
  • Soit f une application de A dans B, ∀ a, a' ∈ A (f(a)=f(a') ⇒ a=a') ⇔ f est injective.
• Surjection  : Soit f une application de A dans B. ∀ b ∈ B ∃ a ∈ A tel que b=f(a) ⇔ f est surjective.
• Bijection  : (∀ a ∈ A ∃! b ∈ B tel que b=f(a) et ∀ b ∈ B ∃! a ∈ A tel que b=f(a)) ⇔ f est bijective (f est alors injective et surjective).
• Composition  :
  • Soient f ∈ F(A,B) et g ∈ F(B,C). gof(x) ∈ F(A,C) est définie par gof(x)=g(f(x)).
  • fog injective, g surjective ⇒ f injective

fog surjective, f injective ⇒ g surjective

fog injective ⇒ g injective

fog surjective ⇒ f surjective

• Relation d'ordre large  : ≤ ≥ ⊂ divise dans lN

R ⊂ (AXA) est d'ordre large si et seulement si elle est :

1. réflexive  : ∀ a ∈ A aRa
2. antisymétrique  : ∀ a, a' ∈ A (aRa' et a'Ra) ⇒ a=a'
3. transitive  : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc

• Relation d'équivalence  : =, ⇔, avoir même reste dans la division par n

R ⊂ (AXA) est d'équivalence si et seulement si elle est :

1. réflexive  : ∀ a ∈ A aRa
2. symétrique  : ∀ a, a' ∈ A aRa' ⇒ a'Ra
3. transitive  : ∀ a, b, c ∈ A (aRb et bRc) ⇒ aRc

• Quotients
  • Définition  : On a un ensemble E et ≡ une relation d'équivalence sur E. Le quotient de E par ≡ noté E/≡ est l'ensemble des classes d'équivalence de ≡.
  • Classe d'équivalence  : La classe d'équivalence de x est x={y ∈ E / x ≡ y} ⇔ ∀ a ∈ E (a ∈ x ⇔ a ≡ x)
  • Propriétés  : Soient E un ensemble et ≡ une relation d'équivalence sur E.

1. ∀ x, y ∈ E (x ≡ y ⇔ x=y)
2. L'ensemble des classes d'équivalence est une partition de E

• • Construction de l'ensemble des rationnels par quotient  : Q={(n,d) l n∈Z, d∈lN*}, soit ≡ / ((n,d) ≡ (n',d') ⇔ nd'=n'd). ≡ est une relation d'équivalence, et l'ensemble des rationnels est le quotient de Q par ≡.
  • Relever une opération sur le quotient
  • Loi interne  : f:EXE → E telle que si x ≡ x' et y ≡ y' alors f(x,y) ≡ f(x',y').

Arithmétique

• Récurrence
  • Principe
  • Récurrence généralisée
• Division euclidienne
  • Définition
  • Preuve de l'existence et de l'unicité par récurrence sur p ≥ 0
• Divisibilité
• PGCD
  • Signification
  • Preuve de l'existence
  • Algorithme d'Euclide

1. Propriétés
2. Description
3. Autre algorithme

• Théorème de Bezout
  • Enoncé
  • Preuve
  • Corollaire
  • Réciproque
• Théorème de Gauss
  • Enoncé
  • Preuve
• Nombres premiers et décomposition
  • Définition
  • Corollaire du théorème de Gauss
  • Théorème de décomposition

Arithmétique modulaire

• Définition de la congruence modulo n
  • Congruence  : relation d'équivalence
  • Notation  : a≡_nb a≡b(mod n) a=b(mod n)
  • a≡_nb ⇔ b-a est un multiple de n
  • a≡_nb ⇔ a%n=b%n
  • Z/nZ est le quotient de Z par la relation d'équivalence modulo n.

1. a≡_na%n
2. Z/nZ={0,1,2,...,n-1} est un ensemble fini à n éléments.
3. Z/nZ est un anneau commutatif non intègre. Tout élément non nul de Z/nZ est inversible si et seulement si n est premier. On note alors Z/nZ=Z/pZ.

• Petit théorème de Fermat
  • Enoncé : $a^{p}=a{\pmod {p}}$ si $p\in \mathbb {N}$ est premier. Ceci peut aussi s'écrire

$a^{p-1}=1{\pmod {p}}$ mais il faut alors que $p$ ne divise pas $a$.

• • Preuve  : Dans (Z/pZ-{0},X) groupe à p-1 éléments, on veut montrer que a^p-1=1(mod p).

∃ m tel que a^m=1. {aⁿ/n ∈ Z} est un sous groupe de Z/pZ fini, d'où ∃ n' tel que aⁿ=a^n' or p est premier donc a^n' a un inverse. D'où a^n-n'=1 ou a^n'-n=1.

Montrons que le plus petit n tel que aⁿ=1 divise p-1 (théorème de Lagrange). On partitionne Z/pZ en une famille d'ensembles de même cardinal que {aⁿ}, tout élément de Z/pZ peut s'écrire sous la forme α a ^θ .

La donnée d'une telle partition revient à donner une relation d'équivalence sur Z/pZ : β R γ ⇔ ∃ e ∈ Z tel que β = γ α ^e.

R est réflexive : β=β α ⁰ d'où β R β

R est symétrique : ∃ e tel que β = γ α ^e donc γ=βα^-e car α est inversible, d'où si β R γ alors γ R β

R est transitive : ∃ e,f tels que β = γ α ^e et γ=δ α^f implique β = δ α ^e+f, donc si β R γ et γ R δ alors β R δ

1={1,a,a²,...a^n-1}=A et b={b,ab,a²b,...a^n-1b}=B. Soit f:A→B telle que f(x)=xb, f^-1(x)=xb^-1. fof^-1=id et f^-1of=id donc f est bijective. Il en résulte que chaque classe est de taille n, d'où n l p-1.

n l p-1 ⇒ ∃ q ∈ Z tel que p-1=qn et aⁿ=1 ⇒ a^p-1=a^qn=(aⁿ)^q=1

Compléments sur les polynômes

• FTA ou théorème de d'Alembert  :
  • Enoncé : Tout polynôme de degré supérieur ou égal à 1 à coefficients dans C a au moins un racine dans C.
  • Preuve  :

Soient $(z)=a_{0}+a_{1}z+\dots +a_{n}z^{n}$ un polynôme à coefficients dans C[z] et f:C → lR telle que f(z)=lP(z)l

Montrons que P admet une racine dans C.

• • • Montrons que $\lim _{\mid z\mid \longmapsto \infty }f(z)=\infty$ :

On a $f(z)=\mid z^{n}({\frac {a_{0}}{z^{n}}}+{\frac {a_{1}}{z^{n-1}}}+\dots +{\frac {a_{n-1}}{z}}+a_{n})\mid$, or labl=lallbl, d'où :

$f(z)=\mid z^{n}\mid \mid a_{n}+({\frac {a_{0}}{z^{n}}}+{\frac {a_{1}}{z^{n-1}}}+\dots +{\frac {a_{n-1}}{z}})\mid$ or la+bl ≥ llal-lbll, d'où :

$f(z)\geq \mid z^{n}\mid \mid \mid a_{n}\mid -\mid {\frac {a_{0}}{z^{n}}}+{\frac {a_{1}}{z^{n-1}}}+\dots +{\frac {a_{n-1}}{z}}\mid \mid$

Cherchons R tel que si lzl>R alors $\mid {\frac {a_{0}}{z^{n}}}+{\frac {a_{1}}{z^{n-1}}}+\dots +{\frac {a_{n-1}}{z}}\mid <\mid {\frac {a_{n}}{2}}\mid$ :

$\mid {\frac {a_{0}}{z^{n}}}+{\frac {a_{1}}{z^{n-1}}}+\dots +{\frac {a_{n-1}}{z}}\mid \geq \mid {\frac {a_{0}}{z^{n}}}\mid +\mid {\frac {a_{1}}{z^{n-1}}}\mid +\dots +\mid {\frac {a_{n-1}}{z}}\mid$

$\mid {\frac {a_{n-1}}{z}}\mid <\mid {\frac {a_{n}}{2n}}\mid$si $\mid z\mid >\mid 2n{\frac {a_{n-1}}{a_{n}}}\mid$ ... $\mid {\frac {a_{0}}{z^{n}}}\mid <\mid {\frac {a_{0}}{z}}\mid <\mid {\frac {a_{n}}{2n}}\mid$ si $\mid z\mid <max(1,\mid 2n{\frac {a_{0}}{a_{n}}}\mid )$ c'est à dire $\mid {\frac {a_{p}}{z^{n-p}}}\mid <\mid {\frac {a_{p}}{z}}\mid <\mid {\frac {a_{n}}{2n}}\mid$ si $\mid z\mid >max(1,\mid 2n{\frac {a_{p}}{a_{n}}}\mid )$ ∀ p ∈ [lO;nl[. Donc si $\mid z\mid >max(1,\mid 2n{\frac {a_{0}}{a_{n}}}\mid ,\dots ,\mid 2n{\frac {a_{n-1}}{a_{n}}}\mid =R)$ alors $\mid {\frac {a_{0}}{z^{n}}}+{\frac {a_{1}}{z^{n-1}}}+\dots +{\frac {a_{n-1}}{z}}\mid <\mid {\frac {a_{n}}{2}}\mid$.

D'où si lzl>R, alors $f(z)>\mid z^{n}\mid \mid \mid a_{n}\mid -\mid \mid {\frac {a_{n}}{2}}\mid \mid$, soit $f(z)>\mid z^{n}\mid \mid {\frac {a_{n}}{2}}\mid$

Cherchons z tel que ∀ M, f(z)>M. Il suffit que lzl>R et lzlⁿ>lzl> 2M/la_nl. D'où si $\mid z\mid >max(1,{\frac {2M}{\mid a_{n}\mid }},{\frac {2na_{0}}{a_{n}}},\dots ,{\frac {2na_{n-1}}{a_{n}}})=r$ alors f(z)>M, c'est à dire $\lim _{\mid z\mid \longmapsto \infty }f(z)=\infty$.

Graphiquement : Soit D={z/ lzl<r}, pour tout z n'appartenant pas à D f(z)>M. En particulier, il n'existe pas z n'appartenant pas à D tel que f(z)=0; z ≥ r n'est pas une racine.

• • • Montrons qu'il existe z₀ ∈ D tel que f atteint son minimum en z₀.

1. f(D) ⊂ lR₊ donc f(D) est une partie de lR minorée par 0. Par l'axiome de la borne inférieure, f(D) admet une borne inférieure.
2. Montrons que Inf(f(D)) est atteinte.
   1. C est compact donc on peut trouver une suite z₀, z₁... ∈ D telle que f(z_n) tend vers Inf(f(D)) quand n tend vers + ∞ .
   2. f est une fonction continue car P(z) est continue, et z → lzl est continue?
   3. $f(\lim _{n\rightarrow \infty }z_{n})=\lim _{n\rightarrow \infty }(f(z_{n}))=Inf(f(D))$. Soit m=Inf(f(D)) et soit $l=\lim _{n\rightarrow \infty }z_{n}$, f(l)=m et l ∈ D. f atteint son minimum en l ∈ D.
3. Montrons par l'absurde que m=Inf(f(D))=f(l)=0, c'est à dire trouvons z tel que lP(z)l<m alors que par hypothèse c'est impossible. Supposons que P n'a pas de racine. Posons Q(z)=P(z-l) et g(z)=f(z-l)=lQ(z)l.
   1. g atteint son minimum en 0. Q(z)=b₀+b_pz^p+...+b_nzⁿ où b_p est le plus petit coefficient non nul autre que b₀ ≠ 0, et lb₀l=m.
   2. On cherche z tel que b_pz^p=-b₀C où C ∈ lR₊ ⇔ $z^{p}=-C{\frac {b_{0}}{b_{p}}}=\lambda e^{i\theta }\Leftrightarrow z=\lambda ^{1/p}e^{i\theta /p}$
   3. lb_p+1z^p+1+...+b_nzⁿl ≤ lz^pl(lb_p+1zl+lb_p+2z²l+...+lb_nz^n-pl) or lb_p+1zl ≤ lb_p/(2n)l si lzl ≤ lb_p/(2b_p+qn)l ... lb_p+qz^ql ≤ lb_p/(2n)l si lzl ≤ min(1,lb_p/(2nb^p+ql), c'est à dire lb_p/1z^p+1+...+b_nzⁿl ≤ lb_nz^pl/2 si lzl ≤ min(1,lb_p/(2nb^p+1)l,...lb₀/b_ql)=r.
   4. Si on prend lzl=r, z=re^{i θ} et b_pz^p=-b₀C où C ∈ lR₊. b_p(re^{i θ} )^p=-b₀C, e^{i θ} =-cb₀/(r^pb_p)=Ke^{i ω} . Pour que K=1, on prend lCl=lr^pb_p/b₀l. D'où z=re^{i arg(-b₀/b_p)/p}.
   5. Q(z)=b₀+b_pz^p+ ε avec ε ≤ lb_pz^p/2l. D'où b_pz^p=b_pr^pe^{i arg(-b₀/b_p)}=-lb_plr^pe^{i arg(b₀)}. D'où Q(z)=(lb₀l-lb_pr^pl)e^{i arg(b₀)}+ε, soit Q(z) ≤ (lb₀l-lb_pr^pl)e^{i arg(b₀)}+lεl ≤ lb₀l-lb_pr^pl+lεl<lb₀l<m

Conclusion : P a une racine z₀ telle que lQ(0)l=lP(z₀-l)l=m=0, c'est à dire que P a une racine z₀=l ∈ D.