\documentclass[french,12pt]{article}


\oddsidemargin=-0.5cm
\evensidemargin=-0.5cm
\topmargin=-1.5cm
\parindent=0pt
\textheight=25 cm
\textwidth=16 cm



\usepackage{amssymb,amsmath,amsthm}
\newtheorem{thm}{Th\'eor\`eme}[section]
\newtheorem{lem}[thm]{Lemme}
\newtheorem{cor}[thm]{Corollaire}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defi}[thm]{D\'efinition}
\newtheorem{td}[thm]{Th\'eor\`eme et D\'efinition}
\def\exe{{\bf Exemples}}
\def\B{{\mathcal B}}
\theoremstyle{definition} \def\Ker{{\rm Ker}}
\def\Im{{\rm Im}}
\newtheorem{ex}[thm]{Exemple}

\theoremstyle{remark}

\newtheorem{rem}[thm]{Remarque}
\newtheorem{preuve}[thm]{Preuve}
\def\resp{(resp. $\C$) }

\numberwithin{equation}{section}
\def\R{\mathbb R}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\Q{\mathbb Q}
\def\Z{\mathbb Z}
\def\rg{{\rm rang}}
\def\ch{\mathrm ch}
\def\sh{\mathrm sh}



\begin{document}













\def\ra{\longrightarrow}

\bigskip

\begin{center}
{\bf {\huge
 Congruences, $\Z/n\Z$}}
\end{center}
\vskip 2cm








\begin{section}{Rappels d'arithm\'etique}
Division euclidienne et formule de Bezout.

Description des id\'eaux de $Z$ : tout id\'eal 

- c'est \`a dire un sous-ensemble non vide $S$ tel que si $x, \in S$ alors $x+y \in S$ et si $\lambda \in \Z$ et $x \in S$ alors $\lambda x \in S$-

est, si il contient un entier non nul,  de la forme $(d)=\{ \mu d | \mu \in \Z \}$, soit l'ensemble des multiples de $
d$, $d$ est le plus petit entier positif non nul contenu dans $S$.

Si $p$ premier divise $ab$, $p$ divise $a$ o\`u $b$,

Si $a$ est premier \`a $b$ et $a$ divise $bc$, $a$ divise $b$.

Il existe une infinit\'e de nombres premiers, nombres premiers de la forme $4k+1$.

\end{section}

\begin{section}{D\'efinition de $\Z/n\Z$}


Soit $n$ un entier. La classe de congruence $\bar k$ d'un entier $k$ modulo $n$ est l'ensemble des entiers $\ell$ tels que $k-\ell$ soit divisible par $n$.

Addition.

\begin{itemize}
\item associativit\'e, commutativit\'e
\item \'el\'ement neutre $\bar 0$, oppos\'e d'un \'el\'ement.
 


\end{itemize}

Multiplication.

\begin{itemize}
\item associativit\'e, commutativit\'e
\item \'el\'ement neutre $\bar 1$, inverse d'un \'el\'ement.

\end{itemize}



\end{section}

\begin{section}{El\'em\'ents inversibles}

Un \'el\'ement $\bar k$ de $\Z/n\Z$ est inversible si et seulement si $k$ et sont premiers entre eux.

$(\Z/n\Z)^*$

Indicatrice d'Euler $\varphi$, $\varphi(n)$ est le cardinal de $(\Z/n\Z)^*$.

$\varphi(p^n)=p^n-p^{n-1}$ si $p$ est premier.


$\varphi(mn)=\varphi(m)\varphi(n)$ si $m$ et $n$ sont premiers entre eux.

Formule

$$
n= \sum_{d|n} \varphi(d)
$$





\end{section}

\begin{section} {Ordre d'un \'el\'ement de $\Z/n\Z$}

D\'efinition : $ord(\bar k)$ est le plus petit entier $u$ strictement positif tel que $u\bar k=0$.

$$
ord(\bar k)=\frac{n}{pgcd(n,k)}
$$








\end{section}

\begin{section} {Lemme chinois}


Si $m$ et $n$ sont premiers entre eux, alors les groupes additifs $\Z/mn\Z$ et  \`a $\Z/n\Z \times\Z/n\Z$ sont isomorphes, {\it via} l'homomorphisme qui envoie
la classe de congruence modulo $mn$ sur les classes modulo $m$ et modulo $n$.

De plus  alors les groupes multiplicatifss $(\Z/mn\Z)^*$ et  \`a $(\Z/n\Z)^* \times(\Z/n\Z)^*$ sont aussi isomorphes, {\it via} la m\^eme application.
 
 \end{section}

\begin{section}{Th\'eor\`emes de Fermat, Wilson et d'Euler}


Th\'eor\`eme de Fermat

Si $p$ est premier et $x \in (\Z/p\Z)^*$ alors $x^{p-1}=1$ ou de mani\` ere \'equivalente $x^p=x$.


Th\'eor\`eme de Wilson


$p$ est premier si et seulement si $(p-1)!+1$ est divisible par $p$.

Th\'eor\`eme d'Euler

Soit $n>1$, et $x \in (\Z/n\Z)^*$ alors $x^{\varphi(n)}=1$.




 
 \end{section}





\end{document}
