% $Header: /cvsroot/latex-beamer/latex-beamer/solutions/conference-talks/conference-ornate-20min.en.tex,v 1.6 2004/10/07 20:53:08 tantau Exp $
\documentclass[xcolor={hyperref,dvips,ps2pdf},dvips]{beamer} 



%\documentclass[xcolor=pst]{beamer}
%\documentclass{beamer}
%\usepackage{fancyvrb}
\usepackage[baw]{fvrb-ex}
%\fvset{xrightmargin=0cm,frame=single,framerule=0.5mm,gobble=2,formatcom=\color{blue},fram%esep=5mm}

\fvset{xrightmargin=0cm,gobble=2,formatcom=\color{blue}}
\graphicspath{{/home/moi/Figures/figuresTS/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}}
%\usepackage{lmodern}
\usepackage{BeamerPolymaths}
\renewcommand{\La}{\LaTeX{}}
\renewcommand\FancyVerbFormatLine[1]{\colorbox{green}{#1}}
\renewcommand{\e}{{\rm e}}

\mode<presentation>
{
  \usetheme{Warsaw}
  % or ...

  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\title[ARITHM\'ETIQUE I] % (optional, use only with long paper titles)
{ARITHM\'ETIQUE I \\ Division - Congruences - PGCD}

\subtitle
{}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the \inst{?} command only if the authors have different
%   affiliation.

\institute{Lycée Jean PERRIN}% (optional, but mostly needed)


\date[Septembre 2006] % (optional, should be abbreviation of conference name)
{Septembre 2006}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{}

\AtBeginSubsection[]
{
  \begin{frame}<beamer>
    \frametitle{Sommaire}
     
    \tableofcontents[currentsection,currentsubsection]
       
  \end{frame}
}


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Sommaire}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}


\section{Division euclidienne}

\subsection{Le théorème}

\begin{frame}


\pause

{\scriptsize Le dessin \ref{dem} }

\begin{center}
\includegraphics[height=2cm]{analyse2.8}\label{diveuc}
\end{center}



\pause

\begin{theorem}

\begin{itemize}

\item Soit $a$ un entier relatif et $b$ un entier naturel non
nul.

\item Il existe un unique couple d'entiers $(q,r)$ tels que
\[a=bq+r\quad\text{avec}\quad0\ie r<b\]

\item Déterminer $q$ et $r$, c'est effectuer la division euclidienne de
$a$ par $b$.

\item On appelle $a$ le dividende, $b$ le diviseur, $q$ le quotient et
$r$ le reste.

\end{itemize}

\end{theorem}



\end{frame}


\subsection{La démonstration}

\begin{frame}

\pause

Le dessin est le secret de la démonstration

\pause

Il traduit qu'un entier $a$ est 

\pause


\begin{itemize}
\item soit un multiple de $b$
\item soit est encadré par deux multiples consécutifs de $b$
\end{itemize}

\pause

Il faudra prouver 

\pause

\begin{itemize}

\item qu'un tel couple existe
\item qu'il est unique
\end{itemize}

\end{frame}

\begin{frame}
\frt{Existence}

\pause

Nous traiterons le cas où $a\in\bbn$


\pause

Soit $\MR_i$ l'ensemble des multiples de
 $b$ inférieurs ou égaux à $a$.

\pause

\begin{itemize}
\item $\MR_i$ est non vide
 car ...
\item $\MR_i$ est majoré par ...
\end{itemize}
\pause 

L'ensemble $\MR_i$ est donc une partie de $\bbn$ non vide et
 majorée : conclusion ?

\pause

Appelons $\mu$ ce plus grand  élément.

\pause

Comment peut-on écrire $\mu$ en fonction de $b$ ?
\end{frame}


\begin{frame}
\frt{Unicité : suite}


\pause

C'est un multiple de $b$, donc il existe un entier $q$ tel que $\mu=qb$.

\pause

Que dire du multiple suivant de b~?

\pause

On en déduit que \[bq\ie a<bq+b\]

\pause

Regardons à nouveau le dessin {\scriptsize \ref{diveuc}} : comment introduie le reste ?

\pause

Nous avons donc démontré l'existence de deux entiers $q$ et $r$
 tels que $a=bq+r$ avec $0\ie r<b$


\label{dem}
\end{frame}

\begin{frame}
\frt{Unicité}

\pause

Supposons qu'il existe deux couples et montrons que c'est impossible.

\pause

\begin{itemize}
\item $a=bq+r\quad\text{avec}\quad 0\ie r<b$
\item $a=bq'+r'\quad\text{avec}\quad 0\ie r'<b$
\end{itemize}

\pause

Effectuez la différence membre à membre de ces égalités. 

\pause

Que dire de $r-r'$ ?



\end{frame}


\subsection{Algorithmes XCAS}


\begin{frame}[fragile]
\frt{Calcul du quotient}




\pause 

\begin{Verbatim}
  quotient(a,b):={
\end{Verbatim}

\pause 

\begin{Verbatim}
  local k
\end{Verbatim}

\pause 

\begin{Verbatim}
  while(k*b<=a){k:=k+1;}
\end{Verbatim}


\pause 

\begin{Verbatim}
  k-1;
\end{Verbatim}


\pause 

\begin{Verbatim}
  }
\end{Verbatim}






\end{frame}


\begin{frame}[fragile]
\frt{Calcul du reste}




\pause 

\begin{Verbatim}
  reste(a,b):={
\end{Verbatim}

\pause 

\begin{Verbatim}
  local k
\end{Verbatim}

\pause 

\begin{Verbatim}
  while(k*b<=a){k:=k+1;}
\end{Verbatim}


\pause 

\begin{Verbatim}
 a-b*(k-1);
\end{Verbatim}


\pause 

\begin{Verbatim}
  }
\end{Verbatim}






\end{frame}




\begin{frame}[fragile]

\pause

Sachez tout de même que ces fonctions sont pré-programmées de manière plus efficace sur XCAS 

\pause

\begin{itemize}

\item
\begin{Verbatim}
  iquo(2354,67);
\end{Verbatim}


\pause


\item
\begin{Verbatim}
  irem(2354,67);
\end{Verbatim}

\end{itemize}
\end{frame}

\section{Congruences}

\subsection{Comme au CM1...}

\begin{frame}

Voici un classement des entiers naturels

\pause

\begin{center}
\begin{tabular}{ccccc}

0&1&2&3&4\\
5&6&7&8&9\\
10&11&12&13&14\\
15&16&17&18&19\\
20&...& & &

\end{tabular}
\end{center}

\end{frame}


\begin{frame}

\pause

Vous pouvez aussi enrouler la droite des réels graduée par les entiers sur un cercle de périmètre 5 et retrouver les mêmes sensations qu'avec la congruence modulo $2\pi$ : 

\pause

\begin{center}
\includegraphics{limfonc.56}
\end{center}


\end{frame}

\begin{frame}
\pause

Cela nous permet de classer les entiers par équipes : l'équipe de ceux qui ont pour reste 0 dans la division euclidienne par 5, l'équipe
de ceux qui ont pour reste 1, etc.
\pause

Maintenant, si Roger, Bébert et Josette font partie de la même équipe, on pourra désigner cette équipe par <<~équipe de Roger~>> ou
<<~équipe de Bébert~>> ou bien <<~équipe de Josette~>>.

\pause

Pour nos nombres, l'équipe de ceux qui ont pour reste 3 pourra s'appeler l'équipe de 3 ou l'équipe de 8 ou l'équipe de $32\,318$. 
\end{frame}


\subsection{Définition de la congruence}

\begin{frame}

\pause

Nous venons de dire que nous allons regrouper les nombres
selon leur reste dans la division euclidienne par un entier
naturel $n$ quelconque cette fois-ci. Il faut donc définir un code
pour se reconnaître entre gens du même monde~:

\pause

\begin{definition}

\begin{itemize}
\item Soient $a$ et $b$ deux entiers et $n$ un entier naturel
supérieur à 2.

\item Dire que $a$ est congru à $b$ modulo $n$ signifie que $a$ et $b$
ont le même reste dans la division euclidienne par $n$.

\item On note \[a\equiv b[n]  \]

\end{itemize}

\end{definition}




\end{frame}


\subsection{propriétés de la congruence}

\begin{frame}

\frt{Propriété fondamentale}

\begin{propriete}
Soit $a$ et $b$ deux entiers et $n$ un entier naturel.

$a$ est congru à $b$ modulo $n$ si et seulement si $a-b$ est un
multiple de $n$
\end{propriete}

\end{frame}






\begin{frame}
\frt{Preuve}

\pause

Puisque les congruences sont liés au reste, il faut 
utiliser les divisions euclidiennes par $n$.


\pause

Je pose donc $a=nq+r$ et $b=nq'+r'$ sans oublier que $r$ et $r'$
sont dans $\llbracket 0,n \llbracket$.


\pause

Que peut-on dire de $r$ et $r'$ ?





\end{frame}



\begin{frame}

\pause

{\large \danger} Le
<<~si et seulement si~>> de la propriété signifie que les assertions sont
équivalentes, c'est à dire que

\pause

\begin{itemize}

\item \gros{si} $a\equiv b[n]$, \gros{alors} $a-b$ est un multiple
de $n$

\item \gros{ET réciproquement}

\item \gros{si} $a-b$ est un multiple de $n$, \gros{alors}
$a\equiv b[n]$


\end{itemize}



\end{frame}


\begin{frame}

\pause

Cette fois-ci, nous supposons que $a-b$ est
un multiple de $n$, donc il existe un entier $k$ tel que $a-b=kn$.

\pause

Or $a-b=n(q-q')+r-r'$, donc $r-r'=n(k-q+q')$.

\pause

Que peut-on en déduire sur la différence des restes : $r-r'$ ?




\end{frame}



\begin{frame}
\frt{Conséquence}

\pause

Cette propriété nous permet en fait d'exploiter autrement les
congruences. 

\pause

En effet, si par exemple $x\equiv 5[32]$, cela
signifie qu'il existe un entier $k$ tel que  $x-5=32k$, soit
encore que $x=5+32k$.

\pause

\begin{propriete}
\[a\equiv b[n]\ssi \text{ il existe un entier } k
\text{ tel que } a=b+kn\]
\end{propriete}




\end{frame}


\begin{frame}


\pause

{\large \danger} Ça ressemble à la division euclidienne de $a$ par $n$.

\pause

 Mais ça peut ne pas l'être : n'oubliez pas que le reste doit
obligatoirement être positif et strictement inférieur au diviseur.

\pause

Par exemple on a bien $33\equiv 97[32]$, mais 97 n'est certes pas
le reste de la division de 33 par 32.


\end{frame}




\begin{frame}
\frt{Propriétés calculatoires}

\begin{proprietes}

\begin{itemize}

\item $a\equiv a[n]$
\item Si $a\equiv b[n]$, alors $b\equiv a[n]$
\item Si $a\equiv b[n]$ et $b\equiv c[n]$, alors $a\equiv c[n]$
\item Si $a\equiv b[n]$ et $a'\equiv b'[n]$, alors $$a+a'\equiv
b+b'\ [n]\quad a-a'\equiv b-b'\ [n]\quad aa'\equiv bb'\ [n]$$
\item Si $a\equiv b[n]$, alors, pour tout $p\in\bbn$, $a^p\equiv
b^p[n]$

\end{itemize}

\end{proprietes}

\end{frame}






\end{document}