\documentclass[12pt,a4paper]{article}
\usepackage{amsfonts,times}
\usepackage{amsmath}
\usepackage{t1enc}
%\usepackage{isolatin1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\font\goth=cmfrak
\def\permutations{\mbox{\goth S}}
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%


\newcommand{\myspace}[1]{}
%\newcommand{\myspace}[1]{#1\baselineskip}
\newcommand{\ko}{\;\;\; , \;\;\;\;}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\K}{\mathbb{K}}

\newcommand{\M}{\mathcal{M}}

\newcommand{\ra}{\rightarrow}

\newcommand{\kernel}{\mathsf{ker}}
\newcommand{\image}{\mathsf{im}}
\newcommand{\rg}{\mathsf{rg}}


%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf %Exercice
    \arabic{exo}) }\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak
%
  }
\def\qu{

  \addtocounter{question}{1}\alph{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}}
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ {\`a} placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}}
\def\refsqu#1{\csname refsqu#1\endcsname}

%%%%%%%%%%fin de macros fiche d'exos
%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.cm}
\addtolength{\leftmargin}{-\elargir}
%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{10\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\vec}[1]{\stackrel{\longrightarrow}{#1}}


\begin{document}
\pagestyle{empty}
% \hrule\null\smallskip
%{\Large \noindent NOM:\hfill Pr{\'e}nom:\hfill\null}\smallskip
%\hrule\null\bigskip
\noindent{\bf  Pr{\'e}paration au
CAPES de math{\'e}matiques \hfill Universit{\'e} de Paris 7\\
\mbox{}\hfill{2004-2005}}
\begin{center}
 \framebox{\Large \bf  \hspace{ 1cm} Avancement du cours d'alg{\`e}bre \hspace{1cm}}
\end{center}

\def\rep{
  \begin{tabular}[c]{|c|c|c|}
    \hline
    Oui&Non&jslp\footnotemark[1]\\
    \hline
  \end{tabular} }
% \footnotetext[1]{Je sais le prouver}

{\it Ceci n'est pas un cours, c'est simplement un plan d{\'e}taill{\'e}
  autant que possible, avec une r{\'e}daction parfois abusive et sans
  aucune d{\'e}monstration}\\

\underline{\bf Cours du 27 septembre 2004}\\

{\bf ARITHMETIQUE}\\

Rappel : d{\'e}finitions d'anneau, anneau commutatif, anneau int{\`e}gre\\

{\bf I L'anneau ${\Bbb Z}$}\\

C'est un anneau (commutatif) int{\`e}gre.\\

{\bf 1) Divisibilit{\'e} dans l'anneau ${\Bbb Z}$}\\

D{\'e}finition: a divise b\\
Exemples\\

- Division euclidienne\\
Th{\'e}or{\`e}me:  Soit $a \in {\Bbb Z}$, $b \in {\Bbb Z} \setminus
\{0\}$. Alors il existe un unique couple $(q,r) \in  {\Bbb Z} \times
{\Bbb N}$ tel que $a=bq+r$ et $r < |b|$.\\
D{\'e}monstration.\\
Exemples\\

- Sous-groupes de ${\Bbb Z}$\\
D{\'e}finition de $n{\Bbb Z}$ pour $n \in {\Bbb Z}$.\\
Th{\'e}or{\`e}me: Les sous-groupes de ${\Bbb Z}$ sont les $n{\Bbb Z}$, $n
\in {\Bbb N}$.\\
D{\'e}monstration.\\
Corollaire: Les id{\'e}aux de ${\Bbb Z}$ sont les $n{\Bbb Z}$, $n \in
{\Bbb N}$. ${\Bbb Z}$ est principal.\\
Rappel: d{\'e}finition d'un id{\'e}al dans un anneau commutatif, une
intersection d'id{\'e}aux est un id{\'e}al (exercice), d{\'e}finition de
l'id{\'e}al engendr{\'e} par une partie, d'un id{\'e}al principal, d'un
anneau principal.\\
Lemme: $n{\Bbb Z}$ est l'id{\'e}al engendr{\'e} par $\{n\}$.\\
D{\'e}monstration.\\

-PGCD/PPCM\\
Soit $n \in {\Bbb N}^*$, $(a_1,\ldots,a_n) \in {\Bbb Z}^n$.\\
i) $a_1{\Bbb Z} \cap \ldots \cap a_n {\Bbb Z}$ est l'ensemble des multiples
communs aux $(a_i)$. C'est une intersection d'id{\'e}aux de ${\Bbb Z}$
donc un un id{\'e}al de $\Z$. Il existe donc un unique $m \in {\Bbb N}$
tel que $a_1{\Bbb Z} \cap \ldots \cap a_n {\Bbb Z}=m{\Bbb Z}$. $m$
s'appelle le PPCM des $(a_i)$, not{\'e} $PPCM(a_1,\ldots,a_n)$. C'est
l'unique {\'e}l{\'e}ment de ${\Bbb N}$ qui v{\'e}rifie:\\
a) pour tout $i$, $m$ est un multiple de $a_i$ et b) $m$ divise tous les multiples communs des $a_i$.\\
Propri{\'e}t{\'e}s: $PPCM(a,b,c)=PPCM(PPCM(a,b),c)$,
$PPCM(ka,kb)=|k|PPCM(a,b)$. (exercice)\\
Notation $a \vee b$.\\
ii) Lemme: $a_1{\Bbb Z} + \ldots + a_n {\Bbb Z}$ est un id{\'e}al de
${\Bbb Z}$. (exercice)\\
Il existe donc un unique $d \in {\Bbb N}$
tel que $a_1{\Bbb Z} + \ldots + a_n {\Bbb Z}=d{\Bbb Z}$. $d$
s'appelle le PGCD des $(a_i)$, not{\'e} $PGCD(a_1,\ldots,a_n)$. C'est
l'unique {\'e}l{\'e}ment de ${\Bbb N}$ qui v{\'e}rifie:\\
a) pour tout $i$, $d$ divise $a_i$ et b) tout diviseur  commun des
$a_i$ divise $d$.\\
Propri{\'e}t{\'e}s: $PGCD(a,b,c)=PGCD(PGCD(a,b),c)$,
$PGCD(ka,kb)=|k|PGCD(a,b)$. (exercice)\\
Notation $a \wedge b$.\\

- Th{\'e}or{\`e}me de B{\'e}zout\\
D{\'e}finition: Les entiers $a_1,\ldots,a_n$ sont premiers entre eux si
$PGCD(a_1,\ldots,a_n)=1$.\\
Th{\'e}or{\`e}me: Les entiers $a_1,\ldots,a_n$ sont premiers entre eux si
et seulement si il existe $(u_1,\ldots,u_n) \in {\Bbb Z}^n$ tel que
$a_1u_1+\ldots a_nu_n=1$.\\
D{\'e}monstration.\\

 \underline{\bf Cours du 4 octobre 2004}\\

- Retour sur le cours pr{\'e}c{\'e}dent\\
$i)$ Mise au point sur les d{\'e}finitions suivantes:\\
anneau int{\`e}gre = anneau non trivial, commutatif et sans diviseur de
0\\
anneau principal = anneau int{\`e}gre tel que tout id{\'e}al est
principal\\
$ii)$ D{\'e}finition d'un {\'e}l{\'e}ment inversible dans un anneau $(A,+,\times)$. On
note $A^*$ l'ensemble des {\'e}l{\'e}ments inversibles de $A$.\\
Lemme: $(A^*, \times)$ est un groupe.\\
D{\'e}monstration.\\
D{\'e}finition: $A$ est un corps si $A^*=A\setminus \{0\}$.\\
Exemples: ${\Bbb Z}^*=\{+1,-1\}$, ${\cal M}_n({\Bbb R})^*=GL_n({\Bbb
  R})=\{M \in {\cal M}_n({\Bbb R}) | \det M \neq  0\}$, ${\cal
  M}_n({\Bbb Z})^*=\{M \in {\cal M}_n({\Bbb Z}) | \det M = \pm 1\}$ (d{\'e}montr{\'e}).\\
D{\'e}finition d'un sous-anneau.\\

- Remarque sur les entiers premiers entre eux: Si $a$, $b$ et $c$ sont
  premiers entre eux deux {\`a} deux, alors $a$, $b$ et $c$ sont
  premiers entre eux.\\
La r{\'e}ciproque est fausse. Par exemple 2, 4 et 5 sont premiers entre
  eux mais pas premiers entre eux deux {\`a} deux.\\
Proposition: Soit $(a,b,c) \in {\Bbb Z}^3$. Si $a \wedge b=1$ et $a \wedge c=1$ alors $a \wedge
  bc=1$. (Exercice. Indication: multiplier les deux relations de
  B{\'e}zout).\\
Lemme de Gauss: Soit $(a,b,c) \in {\Bbb Z}^3$. Si $a \wedge b=1$ et
  $a$ divise $bc$ alors $a$ divise $c$.\\
D{\'e}monstration.\\
Corollaire: $i)$ Soit $(a,b,c) \in {\Bbb Z}^3$. On suppose que $a \wedge
  b=1$, $a$ divise $c$ et $b$ divise $c$. Alors $ab$ divise $c$.\\
$ii)$ Soit $a$ et $b$ des entiers premiers entre eux. Alors
  $PGCD(a,b)=|ab|$.\\
 D{\'e}monstration.\\
Proposition: Soit $(a,b) \in {\Bbb Z}^2$. On a $PGCD(a,b)\times
  PPCM(a,b)=|ab|$.\\
D{\'e}monstration.\\
Exemple.\\

{\bf 2) Nombres premiers}\\

D{\'e}finition: on appelle nombre premier tout {\'e}l{\'e}ment de ${\Bbb N}$
sup{\'e}rieur o{\`u} {\'e}gal {\`a} 2 dont les seuls diviseurs positifs sont 1
et lui-m{\^e}me.\\
Exemples: 2,3,5,7...\\
Th{\'e}or{\`e}me (d{\'e}composition en facteurs premiers): Soit $n \in {\Bbb
  N}^*$. Alors il existe $k \in {\Bbb N}^*$, des nombres premiers
$p_1,\ldots,p_k$ deux {\`a} deux distincts, des entiers
$\alpha_1,\ldots,\alpha_k$ dans ${\Bbb N}^*$ tels que
$n=\prod_{i=1}^{k}p_i^{\alpha_i}.$ Cette d{\'e}composition est
unique. Par convention, 1=1 est la d{\'e}composition en facteurs
premiers de 1.\\
D{\'e}monstration.\\
Application: $i)$ Soit $a=p_1^{\alpha_1}\ldots p_k^{\alpha_k}$ la
d{\'e}composition en facteurs premiers d'un entier $a \in {\Bbb
  N}\setminus\{0,1\}$. Alors les diviseurs positifs de $a$ sont les
$p_1^{\varepsilon_1}\ldots p_k^{\varepsilon_k}$ o{\`u} $0 \leq \varepsilon_i
\leq \alpha_i$ pour tout $i$. Il y a donc
$(\alpha_1+1)\ldots(\alpha_k+1)$ diviseurs positifs distincts de
$a$.\\
$ii)$ Soit $a,b \in {\Bbb N}\setminus\{0,1\}$ et
$a=p_1^{\alpha_1}\ldots p_k^{\alpha_k}$ et $b=q_1^{\beta_1}\ldots
q_l^{\beta_l}$ leurs d{\'e}compositions en facteurs premiers. On
{\'e}crit $a=r_1^{\gamma_1}\ldots r_m^{\gamma_m}$ et
$b=r_1^{\delta_1}\ldots r_m^{\delta_m}$ o{\`u} les $r_i$ sont les $p_i$
et les $q_i$ (sans redite) et o{\`u} $\gamma_i \geq 0$ et $\delta_i \geq
0$ pour tout $i$. Alors $PGCD(a,b)=r_1^{min(\gamma_1,\delta_1)}\ldots
r_m^{min(\gamma_m,\delta_m)}$ et $PPCM(a,b)=r_1^{max(\gamma_1,\delta_1)}\ldots
r_m^{max(\gamma_m,\delta_m)}$. (Exercice)\\
Exercice: Il existe une infinit{\'e} de nombres premiers.\\

{\bf 3) Algorithme d'Euclide}\\

Remarque : D'apr{\`e}s la propri{\'e}t{\'e} d'associativit{\'e} du $PGCD$ il
suffit de savoir calculer le $PGCD$ de deux entiers, et m{\^e}me de deux
entiers positifs (puisque $PGCD(a,b)=PGCD(|a|,|b|)$). C'est ce que
fait l'algorithme d'Euclide.\\
Lemme: Soit $a \in {\Bbb Z}$, $b \in {\Bbb Z}\setminus\{ 0\}$ et $a=bq+r$ la
division euclidienne de $a$ par $b$. Alors $PGCD(a,b)=PGCD(b,r)$.\\
D{\'e}monstration.\\
Description de l'algorithme d'Euclide pour calculer le $PGCD$ de deux
entiers positifs (ou nuls) $a$ et $b$. Exemple. En "remontant"
l'algorithme, on trouve un couple de B{\'e}zout pour $a$ et $b$.\\
Remarque: comme $a{\Bbb Z} +b{\Bbb Z}=PGCD(a,b){\Bbb Z}$, il existe
$(u,v)\in {\Bbb Z}^2$ tel que $au+bv=PGCD(a,b)$. $(u,v)$ s'appelle un
couple de B{\'e}zout pour $a$ et $b$. On a m{\^e}me plus: l'{\'e}quation
$ax+by=c$ (appel{\'e}e {\'e}quation de B{\'e}zout) a des solutions si et
seulement si $PGCD(a,b)$ divise $c$. (d{\'e}montr{\'e}). Pour un exemple
de r{\'e}solution d'une {\'e}quation de B{\'e}zout, voir l'exercice IV du
test.\\
Encore une remarque: si on a une {\'e}galit{\'e} du type $au+bv=1$ cela
prouve bien que $a$ et $b$ sont premiers entre eux. En revanche si on
a une {\'e}galit{\'e} du type $au+bv=c$, cela prouve seulement que le
$PGCD$ de $a$ et $b$ {\it divise} $c$.\\
Version matricielle de l'algorithme d'Euclide: soit $a$ et $b$ deux
entiers positifs ou nuls. Alors l'algorithme d'Euclide nous donne une
matrice $P \in {\cal M}_2({\Bbb Z})$ inversible (dans ${\cal
  M}_2({\Bbb Z})$) telle que $\left(\begin{array}{c} a \\ b \end{array}
\right)=P\left(\begin{array}{c} PGCD(a,b) \\ 0 \end{array}
\right)$. L'{\'e}galit{\'e} $\left(\begin{array}{c} PGCD(a,b) \\ 0 \end{array}
\right)=P^{-1}\left(\begin{array}{c} a \\ b \end{array} \right)$
permet alors de trouver un couple de B{\'e}zout pour $a$ et $b$.\\

\bigskip
\underline{\bf Cours du 11 octobre 2004}
\bigskip

{\bf 4. Congruences et anneaux r{\'e}siduels}
\bigskip

On fixe un entier $n\geq 2$. D{\'e}finition de la relation de
congruence module $n$. C'est une relation d'{\'e}quivalence.
Elle est compatible avec la multiplication et l'addition.
Donc {\'e}galement avec le passage {\`a} l'oppos{\'e} et
aux puissances.

{\em L'anneau $\Z/n\Z$} est l'ensemble des
classes de congruences muni des lois induites par
l'addition et la multiplication des repr{\'e}sentants.
C'est un anneau commutatif.

Un {\'e}l{\'e}ment $\overline{a}$
de cet anneau est inversible ssi il existe $x \in\Z$
tel que $ax$ soit congru {\`a} $1$ modulo $n$ ssi
l'{\'e}quation de Bezout
\[
ax+ny=1
\]
admet une solution $(x,y)\in\Z^2$ ssi $PGCD(a,n)=1$
ssi l'{\'e}l{\'e}ment $\overline{a}$ est un g{\'e}n{\'e}rateur
du groupe additif $\Z/n\Z$.

Par exemple, les {\'e}l{\'e}ments
inversibles de $\Z/30\Z$ sont les classes de
\[
1,7,11,13,17,19,23,29
\]
resp. de
\[
1,7,11,13,-13,-11,-7,-1
\]
et leurs inverses sont respectivement les classes de
\[
1,13,11,7,-7,-11,-13,-1.
\]

Un anneau avec un nombre fini d'{\'e}l{\'e}ments est int{\`e}gre
ssi il est un corps.  L'anneau $\Z/n\Z$ est un corps ssi il est
int{\`e}gre ssi $n$ est premier.



\bigskip
\underline{\bf Cours du 17 octobre 2004}
\bigskip

{\bf 5. Le Th{\'e}or{\`e}me des restes chinois}
\bigskip

Soient $A,B$ deux anneaux. Un {\em homomorphisme d'anneaux} de $A$ dans
$B$ est une application $f: A \to B$ compatble avec l'addition,
la multiplication et qui envoie l'unit{\'e} de $A$ sur celle de $B$.
Un {\em isomorphisme d'anneaux} est un homomorphisme d'anneaux
qui est en outre bijectif.
{\em L'anneau produit $A\times B$} est l'ensemble produit
muni des lois d{\'e}finies composante par composante.

Un homomorphisme d'anneaux est en particulier un homomorphisme
de groupes ab{\'e}liens. Donc il envoie $0_A$ sur $0_B$.
L'application r{\'e}ciproque d'un isomorphisme d'anneaux est
encore un isomorphisme d'anneaux.
Si $A$ et $B$ sont des anneaux, l'anneau produit $A\times B$
est bien un anneau. On a $0_{A\times B} =(0_A,0_B)$ et
$1_{A\times B}= (1_A, 1_B)$. On a des homomorphismes
canoniques $p_1: A \times B \to A$  et $p_2 : A \times B \to B$
donn{\'e}s par les projections. L'application
\[
A \to A\times B \ko a \mapsto (a,0)
\]
est compatible avec l'addition et la multiplication mais
n'est pas un homomorphisme d'anneaux si $B\neq \{0\}$ car
elle n'envoie pas l'unit{\'e} de $A$ sur celle de $A\times B$.

Exemples de morphismes d'anneaux~: l'application canonique
$\Z \to \Z/n\Z$ et les applications canoniques $\Z/(kl\Z) \to \Z/k\Z$.

Si $f:A\to B$ est un homomorphisme d'anneaux, alors
$f(A^*)\subset B^*$ est l'application induite $A^*\to B^*$
est un homomorphisme de groupes. C'est un isomorphisme de
groupes si $f$ est un isomorphisme d'anneaux.
Le groupe des {\'e}l{\'e}ments inversibles de $A\times B$
est {\'e}gal au groupe $A^* \times B^*$.


\noindent
Th{\'e}or{\`e}me des restes chinois~: Soient $l$ et $m$ deux
entiers tels que $PGCD(l,m)=1$. Alors l'application
\[
f: \Z/(lm)\Z \to \Z/l\Z \times \Z/m\Z \ko
\]
qui envoie la classe de $x$ modulo $lm$ sur le couple
form{\'e} des classes de $x$ module $l$ et modulo $m$ est
un isomorphisme d'anneaux.

\noindent
Corollaire~: L'application ci-dessus induit un isomorphisme de
groupes
\[
(\Z/lm\Z)^* \to (\Z/l\Z)^* \times (\Z/m\Z)^*.
\]


\noindent
Corollaire~: Soit $n=p_1^{a_1} \ldots p_k^{a_k}$ la d{\'e}composition
d'un entier $n\geq 2$ en produit de puissances de nombres premiers
distincts deux {\`a} deux. Alors on a un isomorphisme de groupes
\[
(\Z/n\Z)^* \to (\Z/p_1^{a_1})^* \times \cdots \times (\Z/p_k^{a_k})^*.
\]


Pour un entier $n\geq 2$, on pose $\phi(n)$ {\'e}gal
{\`a} l'ordre du groupe $(\Z/n\Z)^*$. On appelle $\phi$
{\em l'indicatrice d'Euler}. On a $\phi(p)=p-1$ lorsque
$p$ est premier,
\[
\phi(p^a)= p^a - p^{a-1}
\]
si $p$ premier et $a\geq 1$ et, si $PGCD(l,m)=1$, on
a $\phi(lm)=\phi(l)\phi(m)$.


\newpage
\bigskip
{\bf 6. Application au calcul de restes de puissances}
\bigskip

Soit $G$ un groupe (dont la loi est not{\'e}e multiplicativement)
et $g$ un {\'e}l{\'e}ment de $G$. {\em L'ordre de $G$} est le nombre
de ses {\'e}l{\'e}ments. {\em L'ordre de $g$} est infini si
$g^n\neq e$ pour tout $n\geq 1$. Sinon, c'est le plus petit
entier $n\geq 1$ tel que $g^n=e$.

L'ordre de $g$ est {\'e}gal {\`a} l'ordre du sous-groupe $H$
de $G$ engendr{\'e} par $g$. Ce sous-groupe est form{\'e} des
puissances $g^n$, $n\in\Z$, de $g$. Si l'ordre de $g$
est infini, nous avons un isomorphisme de groupes
\[
(\Z,+) \to H \ko l \mapsto g^l.
\]
Si l'ordre de $g$ est fini, {\'e}gal {\`a} $n$, nous avons
un isomorphisme de groupes
\[
(\Z/n\Z, +) \to H \ko \overline{l} \mapsto g^l.
\]
En particulier, si l'ordre de $G$ est fini, alors l'ordre de
chaque {\'e}l{\'e}ment de $G$ est fini et divise l'ordre de $G$
(par le th{\'e}or{\`e}me de Lagrange, l'ordre d'un sous-groupe
divise l'ordre du groupe).

Soit $g$ un {\'e}l{\'e}ment d'un groupe fini $G$.  Les deux points {\`a}
retenir sont les suivants~:
\begin{enumerate}
\item la puissance $g^l$ ne d{\'e}pend que de la classe de $l$ modulo
l'ordre de $g$ et
\item  l'ordre de $g$ divise l'ordre de $G$.
\end{enumerate}
Ces deux points impliquent les th{\'e}or{\`e}mes suivants~:

\noindent
Petit th{\'e}or{\`e}me de Fermat~: soit $p$ un nombre premier et
$x$ un entier qui n'est pas divisible par $p$. Alors on a
\[
x^{p-1} = 1 \mod p.
\]

\noindent
Th{\'e}or{\`e}me d'Euler~: soit $n\geq 2$ un entier et $x$ un
entier premier avec $n$. Alors on a
\[
x^{\phi(n)} = 1 \mod n.
\]

\bigskip\noindent
{\bf\underline{Cours du 3 novembre}}
\bigskip

A compl{\'e}ter.

\bigskip\noindent
{\bf\underline{Cours du 8 novembre}}
\bigskip

{\bf ALGEBRE LINEAIRE}

\bigskip
{\bf 0  Matrices}
\bigskip

{\bf 1. Matrices {\'e}chelonn{\'e}es}
\bigskip

Ici, ${\bf k}$ est un corps commutatif (${\bf k}=\R$ ou $\C$ par exemple). Pour des
entiers $n$,$p$ $\geq 1$, on note ${\cal M}_{n,p}$ l'ensemble des
matrices $n \times p$ {\`a} coefficients dans ${\bf k}$. (Remarque:
c'est un ${\bf k}$-espace vectoriel et m\^eme une ${\bf k}$-alg{\`e}bre si
$n=p$.)

Pour $A=(a_{ij}) \in {\cal M}_{n,p}$, on d{\'e}finit la {\em fonction {\'e}chelon}
de $A$, not{\'e}e $e_A$ ; c'est la fonction qui {\`a} tout indice de ligne
$i$ associe le plus petit indice de colonne $j$ tel que $a_{ij}$ est
non nul. Si la ligne $i$ est nulle, on pose $e_A(i)=p+1$.\\
Exemples.

\noindent
D{\'e}finition: On dit que la matrice $A$ est {\em {\'e}chelonn{\'e}e (par
  rapport aux lignes)} si pour tout $i=1,\ldots,n-1$ on a :
(1)  $e_A(i)=p+1 \Rightarrow e_A(i+1)=p+1$ et (2) $e_A(i) \leq p
     \Rightarrow e_A(i+1)>e_A(i)$.\\
On dit que $A$ est {\em {\'e}chelonn{\'e}e r{\'e}duite (par
  rapport aux lignes)} si elle v{\'e}rifie en plus la condition: pour
  tout  $i=1,\ldots,n$, $e_A(i) \leq p$ $\Rightarrow$ ($a_{i,e_A(i)}=1$ et
  pour tout $l \in \{i,\ldots,n\} \setminus \{i\}$, $a_{l,e_A(i)}=0$).

\noindent
Rappel: Les {\em op{\'e}rations {\'e}l{\'e}mentaires sur les lignes} (d'une
matrice ou d'un syst{\`e}me lin{\'e}aire) sont:

(1) {\'e}changer deux lignes

(2) multiplier une ligne par un scalaire non nul

(3) ajouter {\`a} une ligne un multiple d'une autre ligne

\noindent
Th{\'e}or{\`e}me: a) Par un nombre fini d'op{\'e}ration {\'e}l{\'e}mentaires sur
les lignes de $A$, on peut transformer $A$ en une matrice {\'e}chelonn{\'e}e (par
  rapport aux lignes).\\
b) Par un nombre fini d'op{\'e}ration {\'e}l{\'e}mentaires sur
les lignes de $A$, on peut transformer $A$ en une matrice
{\'e}chelonn{\'e}e r{\'e}duite (par rapport aux lignes), et celle-ci est
unique. On la note $EL(A)$.\\
R{\'e}f{\'e}rence pour la d{\'e}monstration: P.Gabriel, Matrices,
g{\'e}om{\'e}trie, alg{\`e}bre lin{\'e}aire (A2.8), F.Liret et D.Martinais,
Maths pour le DEUG.

$EL(A)$ s'appelle la {\em forme {\'e}chelonn{\'e}e r{\'e}duite (par
  rapport aux lignes)} de $A$ ou la {\em r{\'e}duite de Gauss-Jordan} de
  $A$.

Remarque importante: les op{\'e}rations {\'e}l{\'e}mentaires ne modifient
pas le rang. De plus le rang d'une matrice {\'e}chelonn{\'e}e est donn{\'e}
par son nombre de lignes non nulles.

Remarque: Cas des matrices carr{\'e}es\\
Si $A \in {\cal M}_{n}({\bf k})$ est {\'e}chelonn{\'e}e, alors elle est
triangulaire sup{\'e}rieure. De plus $A$ est inversible si et seulement
si $EL(A)$ est la matrice identit{\'e}. (exercice)

Exemples de calculs de formes {\'e}chelonn{\'e}es r{\'e}duites.\\
Utilisation de la calculatrice: fonction rref (row reduced echelon
form) ou GausJord sur les Texas Instrument.

\bigskip
{\bf 2. Application {\`a} la r{\'e}solution des syst{\`e}mes lin{\'e}aires}
\bigskip

On cherche {\`a} r{\'e}soudre le syst{\`e}me
$$(*)\left\{ \begin{array}{c} a_{11}x_1+ \ldots +a_{1p}x_p =b_1\\
a_{21}x_1+ \ldots +a_{2p}x_p =b_2\\
\vdots\\
a_{n1}x_1+ \ldots +a_{np}x_p =b_n
\end{array}
\right.$$
soit sous forme matricielle: $$AX=B$$ avec $A=(a_{ij}) \in {\cal
  M}_{n,p} \ $, $X=\left(\begin{array}{c}x_1\\ \vdots\\x_p
  \end{array}\right) \in {\cal M}_{p,1} \simeq {\bf k}^p$ et $B=\left(\begin{array}{c}b_1\\ \vdots\\b_n
  \end{array}\right) \in {\cal M}_{n,1} \simeq {\bf k}^n$.

Lorsqu'on effectue des op{\'e}rations {\'e}l{\'e}mentaires sur les lignes du
syst{\`e}me $(*)$, on ne change pas l'ensemble des solutions, et cela
revient {\`a} faire les m{\^e}mes op{\'e}rations {\'e}l{\'e}mentaires sur les
lignes de la matrice $(A|B)$ appel{\'e}e {\em matrice augment{\'e}e} du
syst{\`e}me. D'apr{\`e}s le th{\'e}or{\`e}me du paragraphe pr{\'e}c{\'e}dent, on
peut ainsi se ramener {\`a} un syst{\`e}me dont la matrice augment{\'e}e est
{\'e}chelonn{\'e}e r{\'e}duite.

\underline {On se place d{\'e}sormais dans ce cas-l{\`a}.}\\
{\it 1er cas} : il existe $i \in \{i,\ldots,n\}$ tel que
$e_A(i)=p+1$ et $b_i\neq 0$. Alors le syst{\`e}me n'a pas de solution.\\
{\it 2{\`e}me cas} : $\forall i \in \{i,\ldots,n\}, b_i\neq 0
\Rightarrow e_A(i)\leq p$.\\
Alors on appelle {\em variables li{\'e}es} les variables $x_{e_A(i)}$
o{\`u} $i \in \{i,\ldots,n\}$ est tel que $e_A(i)\leq p$. il y en a $r$
o{\`u} $r$ est le rang de $A$. On appelle {\em variables libres} les
autres variables (il y en a $p-r$). On obtient la solution
g{\'e}n{\'e}rale du syst{\`e}me en attribuant des valeurs arbitraires aux
variables libres et en exprimant les variables li{\'e}es en fonction des
variables libres.\\
Exemples  de r{\'e}solutions (de syst{\`e}mes {\'e}chelonn{\'e}s r{\'e}duits).\\

\noindent
Th{\'e}or{\`e}me g{\'e}n{\'e}ral: (Avec le formalisme du d{\'e}but du paragraphe)
Soit l'ensemble des solutions du syst{\`e}me $(*)$ est vide, soit la
solution g{\'e}n{\'e}rale est de la forme $X=X_{part} + X_{hom}$ o{\`u}
$X_{part}$ est une solution particuli{\`e}re de $(*)$ et $X_{hom}$ est
la solution g{\'e}n{\'e}rale du syst{\`e}me homog{\`e}ne $AX=0$. Ainsi
l'ensemble des solutions est un sous-espace affine de ${\bf k}^p$ de
dimension $p-rang(A)$.

\bigskip\noindent
{\bf\underline{Pour le 15 novembre}}
\bigskip

Pr{\'e}parer les exercices II, III et IV de la feuille "Alg{\`e}bre
lin{\'e}aire I" ainsi que l'exercice 6 du test de d{\'e}but d'ann{\'e}e.

\bigskip\noindent
{\bf\underline{Cours du 15 novembre}}
\bigskip

\bigskip
{\bf 3. Application {\`a} la recherche d'\'equations d'un
sous-espace donn\'e par des g\'en\'erateurs}
\bigskip

Une matrice $A$ de format $p\times n$ est \'echelonn\'ee par
rapport aux colonnes si sa transpos\'ee est \'echelonn\'ee par
rapport aux lignes.

\bigskip \noindent Th{\'e}or{\`e}me: a) Par un nombre fini
d'op{\'e}rations {\'e}l{\'e}mentaires sur les colonnes de $A$, on
peut transformer $A$ en une matrice {\'e}chelonn{\'e}e (par
  rapport aux colonnes).\\
b) Par un nombre fini d'op{\'e}rations {\'e}l{\'e}mentaires sur
les colonnes de $A$, on peut transformer $A$ en une matrice
{\'e}chelonn{\'e}e r{\'e}duite (par rapport aux colonnes), et
celle-ci est unique. On la note $EC(A)$.\\

\noindent Ce th\'eor\`eme r\'esulte par transposition du
th\'eor\`eme correspond sur les lignes. On a $EC(A) = \mbox{ }^t
EL(^tA)$.

L'espace engendr\'e par les colonnes reste inchang\'e quand on
effectue des op\'erations \'el\'ementaires sur les colonnes. Donc
cet espace est le m\^eme pour $A$ et $EC(A)$. Ainsi, pour chercher
un syst\`eme d'\'equations dont l'espace des solutions est
engendr\'e par les colonnes de $A$, on peut remplacer $A$ par
$EC(A)$. Alors ce probl\`eme est facile \`a r\'esoudre.

Pour calculer $EC(A)$ sur une TI89, on peut utiliser la commande
$gausJord(a^T)^T$.

La matrice $EC(EL(A))=EL(EC(A))$ comporte un bloc $I_r$ en haut
\`a gauche et des z\'eros ailleurs, o\`u $r$ d\'esigne le rang de
$A$.

Une autre m\'ethode pour trouver un syst\`eme d'\'equations pour
le sous-espace engendr\'e par les colonnes de $A$ consiste \`a
r\'esoudre le syst\`eme $Ax=y$ pour un vecteur d'inconnus $y$.
Plus pr\'ecis\'ement, on met la matrice augment\'ee $[A|y]$ de ce
syst\`eme sous forme \'echelonn\'ee r\'eduite. Alors les lignes
nulles de la partie gauche donnent le syst\`eme recherch\'e. Pour
effectuer cette m\'ethode sur une calculatrice, on utilise la
matrice augment\'ee $[A|I_p]$, dont la partie de droite contiendra
les coefficients des composantes $y_i$.

\bigskip
{\bf 4. Interpr\'etation matricielle des op\'erations
\'el\'ementaires et cons\'equences}
\bigskip

Soient $A$ une matrice $n\times p$, $i_1\neq i_2$ des entiers
entre $1$ et $n$, $\lambda\in k$, $a\in k^*$.

\bigskip
\noindent Lemme : Si $B$ est obtenue \`a partir de $A$

\noindent a) en \'echangeant les lignes $i_1$ et $i_2$, alors
$B=P(i_1, i_2) A$.

\noindent b) en rajoutant $\lambda$ fois la ligne num\'ero $i_1$
\`a la ligne num\'ero $i_2$, alors $B=T_(i_1, i_2)(\lambda) B$.

\noindent c) en multipliant la ligne num\'ero $i_1$ par $a$, alors
$B=D_{i_1}(a)A$.
\bigskip

\noindent On a $P(i,j) P(i,j)=I_n$, $T_{i_1,
i_2}(\lambda)T_{i_1,i_2}(\lambda)= I_n$, $D_{i_1}(a)
D_{i_1}(a^{-1})=I_n$. Donc ces matrices sont inversibles. On les
appelle les matrices \'el\'ementaires.

Le lemme entra\^{\i}ne qu'effectuer des op\'erations
\'el\'ementaires sur les lignes revient \`a multiplier \`a gauche
par des matrices \'el\'ementaires.

Un lemme analogue montre qu'effectuer des op\'erations
\'el\'ementaires sur les colonnes revient \`a multiplier \`a
droite par des matrices \'el\'ementaires.

\bigskip\noindent
Corollaire 1 : Soit $A$ une matrice $n\times p$. Il existe une
matrice inversible produit de matrices \'el\'ementaires $P$ telle
que $PA=EL(A)$ et une matrice inversible produite de matrice
\'el\'ementaires $Q$ telle que $AQ=EC(A)$.


\bigskip\noindent
Corollaire 2 : Si $A$ est inversible, alors $A$ est produit de
matrice \'el\'ementaires. Donc le groupe $GL(n,k)$ des matrices
inversibles est engendr\'e par des matrices \'el\'ementaires.

\bigskip \noindent
Exercice : Montrer que $GL(n,k)$ est en fait engendr\'e par les
matrices \'el\'ementaires autres que les matrices $P(i_1, i_2)$.
Indication : Commencer par le cas $n=2$.

\bigskip\noindent
{\bf\underline{Cours du 22 novembre}}
\bigskip

\bigskip\noindent
Lemme : Soient $V$ un espace vectoriel de dimension finie, $W$ un
espace vectoriel et $f:V\to W$ une application lin\'eaire. Soit
$v_1, \ldots, v_s, v_{s+1}, \ldots, v_p$ une base de $V$
telle que $v_1, \ldots, v_s$ est une base du noyau de $f$.
Alors $f(v_{s+1}), \ldots, f(v_p)$ est une base de
l'image de $f$.

\bigskip\noindent
Remarque : Gr\^ace au th\'eor\`eme de la base incompl\`ete, on
peut toujours trouver une base comme dans le lemme. Ainsi,
on obtient le th\'eor\`eme du rang : $\dim \kernel(f) + 
\dim \image(f) =\dim V$.

\bigskip\noindent
Corollaire 3 : Soient $A$ et $B$ deux matrices $n\times p$. Alors on
a \'equivalence entre
\begin{itemize}
\item[(i)] Il existe $P\in Gl_n(k)$ tel que $PA=B$.
\item[(ii)] On peut transformer $A$ en $B$ par un nombre fini
d'op\'erations \'el\'ementaires sur les lignes.
\item[(iv)] $EL(A)=EL(B)$.
\item[(v)] $\kernel f_A = \kernel f_B$.
\end{itemize}

\bigskip\noindent
{\bf 5. La $\rg$-\'equivalence}
\bigskip

\bigskip\noindent
Th\'eor\`eme : Soiet $A$ et $B$ deux matrices $n\times p$. On a \'equivalence
entre
\begin{itemize}
\item[(i)] Il existe une matrice inversible $P\in Gl(n,k)$ et une
matrice inversible $Q\in Gl(p,k)$ telles que $PAQ=B$.
\item[(ii)] $\rg A=\rg B$.
\item[(iii)] On peu transformer $A$ en $B$ par des op\'erations
\'el\'ementaires sur les lignes et les colonnes.
\item[(iv)] $EC(EL(A))= EC(EL(B))$.
\end{itemize}

\bigskip\noindent
Solution des exercices II et III.

\bigskip\noindent
{\bf\underline{Cours du 29 novembre}}
\bigskip

\bigskip\noindent
Lemme : Soit $f: E \to F$ une application lin\'eaire entre espaces
vectoriels de dimension finie. Alors $E$ et $F$ admettent des
bases dans lesquelles la matrice de $F$ est une matrice $n\times p$
comportant un bloc $I_r$ en haut \`a gauche et des z\'eros ailleurs.
Ici $n=\dim F$, $p=\dim E$, $r = \rg f$.

\bigskip\noindent
Solution des exercices IV, V, VI, VII et VIII.
\end{document}
