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 "vocabulaire" pour écrire des expressions et ce vocabulaire est introduit dans chacun de vos cours.

L'égalité

L'égalité joue un rôle particulier en mathématique car elle est "substitutive" : 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). 

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) seulement pour un x particulier.

Les énoncés

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 ecrits 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 le lecteur de la vérité d'un énoncé. Une preuve est constituée 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 passer 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\Rightarrow B$ : Ajouter A aux hypothèses et montrer B. / Utiliser que $A\Rightarrow 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 : on montre A puis B. Attentions, les connaissances ou objets introduits lors d'une des deux preuves ne sont plus valables lors de l'autre preuve. / 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.

Attention, là encore, les connaissances ou objets introduits lors d'une des deux preuves ne sont plus valables lors de l'autre preuve.

1. Montrer que ¬ A  : Supposer A et chercher une contradiction / Utiliser que ¬ A  : Montrer A et en déduire une contradiction
2. Montrer que ∀ x, A  : Montrer A pour un x quelconque . En fait un x quelconque est just eune nouvelle variable que l'on a pas utilisée avant et donc on ne sait rien, c'est à dire qu'elel n'apparaît pas dans la liste des connaissances à cet instant. / Utiliser que ∀ x, A  : Prendre le x qui nous intéresse et ajouter A(x) aux connaissances courantes.
3. Montrer que ∃ x, A  : Montrer A pour un x bien choisi / Utiliser que ∃ x, A : Prendre un queslconque (comme pour montrer ∀ x, A) 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)

Loi de Demorgan

On les utilise souvent avec la négation pour simplifier les énoncés:

• ¬ ¬ A $\Leftrightarrow$ A
• ¬ (A $\Rightarrow$ B) $\Leftrightarrow$ (A et ¬ B)
• ¬ (A et B) $\Leftrightarrow$ (¬ A ou ¬ B) $\Leftrightarrow$ (A $\Rightarrow$ B)

$\Leftrightarrow$ (B $\Rightarrow$ A)

• ¬ (∀x, A) $\Leftrightarrow$ ∃x, (¬ A)
• ¬ (∃x, A) $\Leftrightarrow$ ∀x, (¬ A)

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 à la formulation de l'axiome de compréhension de Zermelo, modifiant le schéma de compréhension : {x ∈ A / ...} : on ne peut construire que des sous-ensembles d'ensemble déjà existant.
• Construction des ensembles  :

1. A ∪ B={x / x ∈ A ou x ∈ B} (Ici ce n'est pas le shéma de compréhension, mais une contruction nouvelle)
2. A ∩ B={x / x ∈ A et x ∈ B} = {x ∈ A / x ∈ B}
3. A-B=A ∩ B^c={x / x ∈ A et x $\notin$ B}
4. A^c complémentaire de A : cette notation signifie en général E-A où E est un grand ensemble sans ambiguïté.
5. P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
6. A × B est le produit cartésien : l'ensemble des couples; {(a,b) / a ∈ A b ∈ B}.

• On appelle relation entre A et B un sous ensemble de A × B (on dit aussi correspondance).
• Inverse d'une relation R  : Soit R ⊂ P(A × B), 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) est l'ensemble des relations de A dans B qui associe au plus un élément de B à chaque élément de A.
• F(A,B)=_déf{R ⊂ (A × B) / ∀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
• Il s'agit des fonctions de A dans B définie partout. C'est à dire qui associe exactement un élément de B à chaque élément de A.
• A(A,B)={f ∈ F(A,B) / ∀a ∈ A ∃!b ∈ B tel que b=f(a)} (∃! signifie il existe un unique).

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 (x ∈ A ⇒ x ∈ B)

Injection

• notée parfois A $\hookrightarrow$ B
• Une injection est une application telle que chaque élément de l'ensemble d'arrivée possède au plus un antécédent.
• Soit f une application de A dans B, ∀ a, a' ∈ A (f(a)=f(a') ⇒ a=a') ⇔ f est injective.

Surjection

• Une surjection est une application telle que chaque élément de l'ensemble d'arrivée possède au moins un antécédent.
• Soit f une application de A dans B. ∀ b ∈ B ∃ a ∈ A tel que b=f(a) ⇔ f est surjective.

Bijection

• Une bijection est une application qui est à la fois surjective et injective.
• (∀ a ∈ A ∃! b ∈ B tel que b=f(a) et ∀ b ∈ B ∃! a ∈ A tel que b=f(a)) ⇔ f est bijective.

Composition

• Soient f ∈ F(A,B) et g ∈ F(B,C). (g ο f)(x) ∈ F(A,C) est définie par (g ο f)(x)=g(f(x)).
• f ο g injective, g surjective ⇒ f injective

f ο g surjective, f injective ⇒ g surjective

f ο g injective ⇒ g injective

f ο g surjective ⇒ f surjective

Relation d'ordre large

exemples: ≤ ≥ sur IR, ⊂ sur les ensembles, divise dans lN

R ⊂ (A × A) 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 ⊂ (A × A) est d'équivalence si et seulement si elle est :

1. réflexive  : ∀a ∈ A a R a
2. symétrique  : ∀a, a' ∈ A a R a' ⇒ a' R a
3. transitive  : ∀a, b, c ∈ A (a R b et b R c) ⇒ a R c

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

• Proposition : les trois propriétés suivantes sont équivalentes :

1. Tous les sous-ensembles non vides de lN ont un plus petit élément.
2. Si P est une propriété sur lN, si P(0) est vrai, si ∀n ∈ lN (P(n)⇒P(n+1)), alors ∀n∈lN P(n).
3. Si P est une propriété sur lN, si ∀n∈lN, si ((∀k<n P(k))⇒P(n)), alors ∀n∈lN P(n).

• Preuve
• 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

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 $\mathbb {C}$ possède au moins un racine dans $\mathbb {C}$.
• Preuve  :

Soient $z=a_{0}+a_{1}z+\dots +a_{n}z^{n}\,$ un polynôme à coefficients dans $\mathbb {C} [z]$. Définissons $f:\mathbb {C} \rightarrow \mathbb {R}$ par $f(z)=|P(z)|\,$. On va montrer que P admet une racine dans $\mathbb {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 $|ab|=|a||b|\,$, 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 $|a+b|\geq ||a|-|b||\,$, 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.

Fonctions polynômes/Polynômes

• Un polynôme de degré d est un élément de lR^d+1 : P=(a₀,a₁,...,a_d) est un vecteur .

Il est néanmoins possible de faire quelques opérations supplémentaires sur les polynômes :

• + sur des vecteurs de taille différente
• division euclidienne
• produit
• dérivation

• Fonction polynôme  :

Soit P un polynôme à coefficients dans lK=C, lR, Q, Z/pZ P(x) est une foction de lK → lK qui a x associe a₀+a₁x+...a_dx^d si P=(a₀,a₁,...,a_d)

• Egalité de deux polynômes  :

Dans lR, C et Q, deux polynômes sont égaux si et seulement si les fonctions associées sont égales. Ce n'est pas le cas dans Z/pZ.

Exemple : dans Z/2Z, P=1+X+X² et Q=1, x ∈ {0;1}. P(0)=Q(1)=1 et P(0)=P(1)=1 donc les fonctions sont égales bien que les polynômes soient différents.

Remarque  : Il existe 4 polynômes de degré 2 dans Z/2Z.

• Dérivation  :

P' est une opération formelle sur les coefficients car $\lim _{h\longmapsto 0}{\frac {P(x+h)-P(x)}{h}}$ n'a pas de sens dans Z/pZ.

Si P=(a₀,a₁,...,a_d) (d°=d), alors P'=(a₁,2a₂,...,da_d) (d°=d-1)

• PGCD et polynômes de Bezout  :

• Plus grand diviseur commun : celui qui a le plus grand degré (donc plus grand à une constante multiplicative près)
• Remarques  :

1. Stathme : valeur absolue dans Z, degré d'un polynôme ∈ lN
2. Pour les polynômes, l'algorithme d'Euclide st la preuve de l'existence du PGCD

• Algorithme d'Euclide : preuve par récurrence sur d°P+d°Q

1. 0 ∧ Q=Q et P ∧ 0=P
2. Si d°P+d°Q=0 : les deux polynômes sont constants, P ∧ Q=1=P=Q et donc P ∧ Q existe
3. Hypothèse de récurrence : On suppose que P' ∧ Q' existe pour tout P' et pour tout Q' tels que d°P'+d°Q' ≤ d°P+d°Q. On a d°P+d°Q>0
   1. Supposons d°Q ≥ d°P (sinon on échange P et Q). On effectue la division puissance croissante de Q par P : Q=SP+R où d°R<d°P. Soit D un polynôme : si D l P et D l Q alors D l SP-Q=R; si D l P et D l R alors D l SP+R=Q. Ainsi l'ensemble des diviseurs communs de P et Q est celui des diviseurs de P et R.
   2. Par récurrence P ∧ Q existe ( puisque d°P+d°Q<d°P+d°P ≤ d°P+d°Q)

• Polynômes de Bezout

1. Si P ∧ Q=D alors ∃ U, V deux polynômes tels que UP+VQ=D
2. Existence  : On remonte l'algorithme (par récurrence sur d°P+d°Q)
   1. Si P=0 et Q $\neq$ 0 : 0.P+1.Q=Q=P ∧Q
   2. Si P $\neq$0 et Q=0 : 1.P+0.Q=P=P ∧ Q
   3. Si d°P+d°Q=0 : $P=a\neq 0$ et $Q=b\neq 0$ : a^-1.a+0.b=1=P ∧ Q
   4. Si d°P+d°Q>0 avec d°P ≤ d°Q : Q=SP+R. Par récurrence, on a trouvé U et V tels que UP+VR=P ∧ Q= P ∧ R soit (U-VS)P+VQ=P ∧ Q

Construction d'un nouveau corps

• Soit P un polynôme d'un corps lK. On peut quotienter lK[X] par P, c'est à dire poser P=0. On quotiente par la relation d'équivalence avoir même reste dans la division par P (même preuves que dans Z/nZ).

On obtient un corps si et seulement si P est irréductible, c'est à dire que P ne peut pas s'écrire P=QR avec d°Q>0 et d°R>0.

Remarques :

En d°2 et 3 : P est irréductible si et seulement si P n'a pas de racine

a racine de P si et seulement si (X-a) l P

• Construction de F₄  : lK=Z/2Z

• Dans Z/pZ :

Tous les polynômes de degré 2 sont de la forme X²+aX+b, donc il y a p² polynômes.

Tous les polynômes réductibles de degré 2 sont de la forme (X-a)(X-b), donc il y a p(p+1)/2 polynômes.

(a+b)^p=a^p+b^p

• X², X²+X=X(X+1), et X²+1=(X+1)² sont réductibles, contrairement à X²+X+1.
• On pose X²+X+1=0, soit X²=X+1

F₄={0,1,X,X+1}={0,1,α,β}, donc 0={P(X²+X+1) l P ∈ lK[X]}, 1={P(X²+X+1)+1 l P ∈ lK[X]}, α={P(X²+X+1)+X l P ∈ lK[X]}, et β={P(X²+X+1)+X+1 l P ∈ lK[X]}.

+	0	1	α	β
0	0	1	α	β
1	1	0	β	α
α	α	β	0	1
β	β	α	1	0

×	0	1	α	β
0	0	0	0	0
1	0	1	α	β
α	0	α	β	1
β	0	β	1	α

• Construction de $\mathbb {C}$  : lK=lR

• P=1+X² est irréductible : X²=-1 et on pose X=i

Tous les restes de la division par 1+X² sont de la forme a+bX=a+ib

D'où $\mathbb {C}$=P[lR]/1+X²={a+ib l a,b ∈ lR}

• $\mathbb {C}$=P[lR]/1+X+X²={a+jb l a,b ∈ lR}

Permutations

Définition

Une permutation est une bijection sur un ensemble fini. On note S_n l'ensemble des permutations de {1,2,...,n}

Notation

$\sigma ={\begin{pmatrix}1&3&4&5&2\\2&4&1&3&5\end{pmatrix}}$. Sur chaque ligne figurent une fois tous les éléments de 1 à n. σ(1)=2 et σ^-1(2)=1.

Composition

• Si σ, σ' ∈ S_n alors σ•σ' est aussi une permutation.

id_n ∈ S_n : $id_{n}={\begin{pmatrix}1&2&3&\dots &n\\1&2&3&\dots &n\end{pmatrix}}$

σ•id=σ (id est neutre pour •), σ•σ^-1=id

• {S_n,•} est un groupe non commutatif.

• $S_{2}=\{{\begin{pmatrix}1&2\\1&2\end{pmatrix}},{\begin{pmatrix}1&2\\2&1\end{pmatrix}}\}=\{id_{2},\sigma \}$, où σ•σ=id
• $S_{3}=\{(132),(213),(321),(123),(231),(312)\}$

Corrections de quelques exercices

Feuille 4 - Exercice 5

$P(X)=X^{5}+3X^{4}+X^{3}+X^{2}+3X+1$ et $Q(X)=X^{4}+2X^{3}+X+2$

Après une division, on trouve : $P(X)=Q(X)(X+1)+R(X)$ avec $R(X)=-X^{3}-1$

On effectue une seconde division : $Q(X)=R(X)(-X-2)+0$

Donc un pgcd de $P(X)$ et $Q(X)$ est $X^{3}+1$.

On a donc $-P(X)+(X+1)Q(X)=X^{3}+1$

Feuille 4 - Exercice 6

$P(X)=X^{3}+X^{2}-X-1$ a pour racine évidente 1 et -1 et on trouve par identification $P(X)=(X^{2}-1)(X+1)=(X-1)(X+1)^{2}$

$Q(X)=X^{4}+X^{3}-3X^{2}-4X-1$ n'a pas 1 pour racine, mais il admet -1 comme racine et on trouve $Q(X)=(X+1)(X^{3}-3X-1)$. $X^{3}-3X-1$ lui n'admet ni 1 ni -1 comme racine.

Donc le seul facteur commun entre $P(X)$ et $Q(X)$ est $X+1$ qui est donc un pgcd de $P(X)$ et $Q(X)$.

Décomposer les polynômes ne permet pas de trouver des "polynômes de Bezout".

On utilise alors l'algorithme d'Euclide:

$Q(X)=P(X)X-2X^{2}-3X-1$ puis

${P(X)=(2X^{2}+3X+1)((1/2)X-1/4)-(3/4)X-3/4}$

On retrouve le même pgcd à un facteur multiplicatif près, mais on peut écrire:

$3X+3=(2X^{2}+3X+1)(2X-1)-4P(X)$

$3X+3=(XP(X)-Q(X))(2X-1)-4P(X)$

$3X+3=(-2X+1)Q(X)+(2X^{2}-X-4)P(X)$

et donc au final

$X+1=(1/3)(-2X+1)Q(X)+(1/3)(2X^{2}-X-4)P(X)$