MATH203 : Introduction à l'algèbre
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
- ,
- 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 , définissons la fonction f(x) = x^2 - y^2 = (x - y)(x + y). On a donc pour tout 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 , 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 , "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 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.
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", "", ... Le sens devrait être clair
- La disjonction : notée "A ou 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", "", ... 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", "", "". "" 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", , ... 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", , ... 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 :
- des connaissances : liste d'objets connus, de théorèmes, d'hypothèses locales au problème
- un but à démontrer
- Pour passer d'une étape à l'autre, on peut :
- chercher à simplifier le but/le diviser
- 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:
- Montrer que : Ajouter A aux hypothèses et montrer B. / Utiliser que : Démontrer A pour pouvoir ajouter B aux connaissances.
- 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.
- 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.
- Montrer que ¬ A : Supposer A et chercher une contradiction / Utiliser que ¬ A : Montrer A et en déduire une contradiction
- 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.
- 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 A
- ¬ (A B) (A et ¬ B)
- ¬ (A et B) (¬ A ou ¬ B) (A B)
(B A)
- ¬ (∀x, A) ∃x, (¬ A)
- ¬ (∃x, A) ∀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 x}. Si A ∈ A alors A A et si A 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 :
- A ∪ B={x / x ∈ A ou x ∈ B} (Ici ce n'est pas le shéma de compréhension, mais une contruction nouvelle)
- A ∩ B={x / x ∈ A et x ∈ B} = {x ∈ A / x ∈ B}
- A-B=A ∩ Bc={x / x ∈ A et x B}
- Ac complémentaire de A : cette notation signifie en général E-A où E est un grand ensemble sans ambiguïté.
- P(A) : ensemble des parties de A; B ∈ P(A) si et seulement si B ⊂ A ⇔ ∀ x (x ∈ B ⇒ x ∈ A)
- 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 BA
- 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, fl`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 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 :
- réflexive : ∀a ∈ A aRa
- antisymétrique : ∀a, a' ∈ A (aRa' et a'Ra) ⇒ a=a'
- 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 :
- réflexive : ∀a ∈ A a R a
- symétrique : ∀a, a' ∈ A a R a' ⇒ a' R a
- 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.
- ∀ x, y ∈ E (x ≡ y ⇔ x=y)
- 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 :
- Tous les sous-ensembles non vides de lN ont un plus petit élément.
- 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).
- 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
Divisibilité
PGCD
- Signification
- Preuve de l'existence
- Algorithme d'Euclide
- Propriétés
- Description
- 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.
- a≡na%n
- Z/nZ={0,1,2,...,n-1} est un ensemble fini à n éléments.
- 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é : si est premier. Ceci peut aussi s'écrire
mais il faut alors que ne divise pas .
- Preuve : Dans (Z/pZ-{0},X) groupe à p-1 éléments, on veut montrer que ap-1=1(mod p).
- ∃ m tel que am=1. {an/n ∈ Z} est un sous groupe de Z/pZ fini, d'où ∃ n' tel que an=an' or p est premier donc an' a un inverse. D'où an-n'=1 ou an'-n=1.
- Montrons que le plus petit n tel que an=1 divise p-1 (théorème de Lagrange). On partitionne Z/pZ en une famille d'ensembles de même cardinal que {an}, 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 : β=β α 0 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,a2,...an-1}=A et b={b,ab,a2b,...an-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.
- La donnée d'une telle partition revient à donner une relation d'équivalence sur Z/pZ : β R γ ⇔ ∃ e ∈ Z tel que β = γ α e.
- n l p-1 ⇒ ∃ q ∈ Z tel que p-1=qn et an=1 ⇒ ap-1=aqn=(an)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 possède au moins un racine dans .
- Preuve :
- Soient un polynôme à coefficients dans . Définissons par . On va montrer que P admet une racine dans .
- Montrons que :
- On a , or , d'où :
- or , d'où :
- Cherchons R tel que si lzl>R alors :
- si ... si c'est à dire si ∀ p ∈ [lO;nl[. Donc si alors .
- D'où si lzl>R, alors , soit
- Cherchons z tel que ∀ M, f(z)>M. Il suffit que lzl>R et lzln>lzl> 2M/lanl. D'où si alors f(z)>M, c'est à dire .
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 z0 ∈ D tel que f atteint son minimum en z0.
- 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.
- Montrons que Inf(f(D)) est atteinte.
- C est compact donc on peut trouver une suite z0, z1... ∈ D telle que f(zn) tend vers Inf(f(D)) quand n tend vers + ∞ .
- f est une fonction continue car P(z) est continue, et z → lzl est continue?
- . Soit m=Inf(f(D)) et soit , f(l)=m et l ∈ D. f atteint son minimum en l ∈ D.
- 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.
- g atteint son minimum en 0. Q(z)=b0+bpzp+...+bnzn où bp est le plus petit coefficient non nul autre que b0 ≠ 0, et lb0l=m.
- On cherche z tel que bpzp=-b0C où C ∈ lR+ ⇔
- lbp+1zp+1+...+bnznl ≤ lzpl(lbp+1zl+lbp+2z2l+...+lbnzn-pl) or lbp+1zl ≤ lbp/(2n)l si lzl ≤ lbp/(2bp+qn)l ... lbp+qzql ≤ lbp/(2n)l si lzl ≤ min(1,lbp/(2nbp+ql), c'est à dire lbp/1zp+1+...+bnznl ≤ lbnzpl/2 si lzl ≤ min(1,lbp/(2nbp+1)l,...lb0/bql)=r.
- Si on prend lzl=r, z=rei θ et bpzp=-b0C où C ∈ lR+. bp(rei θ )p=-b0C, ei θ =-cb0/(rpbp)=Kei ω . Pour que K=1, on prend lCl=lrpbp/b0l. D'où z=rei arg(-b0/bp)/p.
- Q(z)=b0+bpzp+ ε avec ε ≤ lbpzp/2l. D'où bpzp=bprpei arg(-b0/bp)=-lbplrpei arg(b0). D'où Q(z)=(lb0l-lbprpl)ei arg(b0)+ε, soit Q(z) ≤ (lb0l-lbprpl)ei arg(b0)+lεl ≤ lb0l-lbprpl+lεl<lb0l<m
Conclusion : P a une racine z0 telle que lQ(0)l=lP(z0-l)l=m=0, c'est à dire que P a une racine z0=l ∈ D.
Fonctions polynômes/Polynômes
- Un polynôme de degré d est un élément de lRd+1 : P=(a0,a1,...,ad) 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 a0+a1x+...adxd si P=(a0,a1,...,ad)
- 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+X2 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 n'a pas de sens dans Z/pZ.
Si P=(a0,a1,...,ad) (d°=d), alors P'=(a1,2a2,...,dad) (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 :
- Stathme : valeur absolue dans Z, degré d'un polynôme ∈ lN
- 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
- 0 ∧ Q=Q et P ∧ 0=P
- Si d°P+d°Q=0 : les deux polynômes sont constants, P ∧ Q=1=P=Q et donc P ∧ Q existe
- 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
- 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.
- Par récurrence P ∧ Q existe ( puisque d°P+d°Q<d°P+d°P ≤ d°P+d°Q)
- Polynômes de Bezout
- Si P ∧ Q=D alors ∃ U, V deux polynômes tels que UP+VQ=D
- Existence : On remonte l'algorithme (par récurrence sur d°P+d°Q)
- Si P=0 et Q 0 : 0.P+1.Q=Q=P ∧Q
- Si P 0 et Q=0 : 1.P+0.Q=P=P ∧ Q
- Si d°P+d°Q=0 : et : a-1.a+0.b=1=P ∧ Q
- 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
- Remarques :
- Construction de F4 : lK=Z/2Z
- Dans Z/pZ :
- Tous les polynômes de degré 2 sont de la forme X2+aX+b, donc il y a p2 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=ap+bp
- X2, X2+X=X(X+1), et X2+1=(X+1)2 sont réductibles, contrairement à X2+X+1.
- On pose X2+X+1=0, soit X2=X+1
F4={0,1,X,X+1}={0,1,α,β}, donc 0={P(X2+X+1) l P ∈ lK[X]}, 1={P(X2+X+1)+1 l P ∈ lK[X]}, α={P(X2+X+1)+X l P ∈ lK[X]}, et β={P(X2+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 : lK=lR
- P=1+X2 est irréductible : X2=-1 et on pose X=i
Tous les restes de la division par 1+X2 sont de la forme a+bX=a+ib
D'où =P[lR]/1+X2={a+ib l a,b ∈ lR}
- =P[lR]/1+X+X2={a+jb l a,b ∈ lR}
Permutations
Définition
Une permutation est une bijection sur un ensemble fini. On note Sn l'ensemble des permutations de {1,2,...,n}
Notation
. Sur chaque ligne figurent une fois tous les éléments de 1 à n. σ(1)=2 et σ-1(2)=1.
Composition
- Si σ, σ' ∈ Sn alors σ•σ' est aussi une permutation.
idn ∈ Sn :
σ•id=σ (id est neutre pour •), σ•σ-1=id
- {Sn,•} est un groupe non commutatif.
- , où σ•σ=id
Support de σ
Transposition
Signature
Corrections de quelques exercices
Feuille 4 - Exercice 5
et
Après une division, on trouve : avec
On effectue une seconde division :
Donc un pgcd de et est .
On a donc
Feuille 4 - Exercice 6
a pour racine évidente 1 et -1 et on trouve par identification
n'a pas 1 pour racine, mais il admet -1 comme racine et on trouve . lui n'admet ni 1 ni -1 comme racine.
Donc le seul facteur commun entre et est qui est donc un pgcd de et .
Décomposer les polynômes ne permet pas de trouver des "polynômes de Bezout".
On utilise alors l'algorithme d'Euclide:
puis
On retrouve le même pgcd à un facteur multiplicatif près, mais on peut écrire:
et donc au final