\documentclass[12pt]{book} \usepackage{mvmaths_perso} \begin{document} \setcounter{chapter}{4} \newcommand{\pgcd}{\mbox{P.G.C.D}} \newcommand{\ppcm}{\mbox{P.P.C.M}} \chapitre{4}{Applications} \section{Résolution de l'équation $ax\equiv b\ [n]$} \prop{Soient $n$ un entier naturel, $a$, $b$ et $c$ trois entiers tels que $ac\equiv bc \ [n]$. Si $c$ est premier avec $n$ alors cette égalité implique $a\equiv b \ [n]$. Ce n'est pas forcément vrai sinon.} \dem{$ac\equiv bc \ [n]$ donc $ac-bc\equiv 0 \ [n]$ . Ceci prouve que $n$ divise $(a-b)c$. Si $n$ est premier avec $c$, alors d'après le théorème de Gauss $n$ divise $(a-b)$, ce qui prouve que $a\equiv b \ [n]$.\par Par contre, on peut constater que $14\equiv 6\ [8]$, alors que $7\not\equiv 3\ [8]$. } \prop{Soient $a$ et $n$ deux entiers naturels, $b$ un entier relatif. Il existe un entier relatif $x$ tel que $ax\equiv b\ [n]$ si et seulement si le PGCD de $a$ et $n$ divise $b$. (C'est en particulier le cas si $a$ et $n$ sont premiers entre eux).} \dem{ \begin{description} \item[($\Rightarrow$)] Supposons qu'il existe un tel $x$. Alors $ax-b \equiv 0[n]$ donc $n$ divise $ax-b$. Le PGCD de $a$ et $n$ divise $n$, donc, par transitivité divise $ax-b$. Comme il divise $a$ et $ax-b$, il divise, par linéarité, $b=ax-(ax-b)$. \item[($\Leftarrow$)] Réciproquement, si $\left\{\begin{array}{l} p=\pgcd(a;n).\\ p \textrm{ divise } b \end{array}\right. $ alors $\left\{\begin{array}{l} \exists (u;v)\in\Z^2, p=au+nv\\ \exists k\in\Z, b=pk \end{array}\right.$\\ On en déduit que $b=auk+nvk$, d'où en raisonnant modulo $n$, $b\equiv auk\ [n]$ et donc $uk$ est une solution. \end{description} } \prop{Soient $a$ et $n$ deux entiers naturels. L'entier $a$ possède un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux.} \dem{Dire qu'un entier $x$ est un inverse de $a$ modulo $n$ signifie que $ax\equiv 1[n]$. Or d'après le théorème précédent, il existe un tel $x$ si et seulement si le PGCD de $a$ et $n$ divise $1$, c'est à dire si et seulement si $a$ et $n$ sont premiers entre eux.} \section{Le petit théorème de Fermat} \theo{Soient $p$ un nombre premier et $a$ un entier. Alors soit $p$ divise $a$, soit $p$ divise $a^{p-1}-1$. Autrement dit, soit $a\equiv 0\ [p]$, soit $a^{p-1}\equiv 1\ [p]$.} \dem{Supposons que $p$ ne divise pas $a$ et prouvons la seconde partie de l'affirmation du théorème. \\ Considérons les multiples de $a$ strictement inférieurs à $pa$ : $a, 2a, 3a,\ldots,(p-1)a$. On note $r_k$ le reste de la division du multiple $ka$ par $p$ pour $1\leq k