% $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[secheader]{Madrid}
  % or ...Warsaw

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


\title[ARITHM\'ETIQUE I] % (optional, use only with long paper titles)
{ARITHM\'ETIQUE II\\ Nombres Premiers}

\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{Nombres premiers}

\subsection{Nombres premiers - Nombres composés}

\begin{frame}
  Quoi de plus simple qu'un nombre premier :

\begin{Definition}
  Un entier naturel est dit premier s'il est supérieur ( i.e. supérieur ou égal ) à  2 et n'est 
divisible que par 1 et lui-même.
\end{Definition}
\end{frame}


\begin{frame}
  
\begin{propriete}\label{infinite}
  Tout entier naturel admet au moins un diviseur premier.
\end{propriete}
\end{frame}




\begin{frame}
  \begin{theorem}
  Il y a une infinité de nombres premiers.
\end{theorem}
\end{frame}



\begin{frame}
  
\frt{Comment vérifier qu'un nombre est premier~?} 

 Sortons nos machines et
observons les diviseurs de 1321 par exemple : si aucune des 1319 divisions ne 
<<~tombe juste~>>, alors on pourra dire que 1321 premier.
Et puis d'abord, il est impair, il ne semble pas être divisible par 3, alors 
pourquoi pas...
\end{frame}


\begin{frame}
  \begin{center}
\tiny{ {\setlength{\tabcolsep}{0.1cm}
\begin{tabular}{|c|cccccccccccc|}
\hline
 diviseur& 2& 3& 4& 5& 6&  7&8&9&10&11&12&13\\ \hline
  quotient&660,5&440,3&330,3&264,2
&220,2&188,7&165,1&146,8&132,1& 120,1& 110,1&101,6\\ \hline
 diviseur &14&15&16&17&18&19&20&21&22&23&24&25\\ \hline
quotient &94,36&88,07&82,56&77,71&73,39&69,53 &66,05&62,90&60,05&57,43
&55,04&52,84\\ \hline diviseur&26&27&28&29&30&31&32&33&34&35&36&37 \\ \hline
  quotient&50,81&48,93&47,18& 45,55& 44,03&42,61&41,28&40,03&38,85&37,74 &36,69& 
35,70\\ \hline

\end{tabular}}
}
\end{center}
\end{frame}


\begin{frame}
  
\begin{definition}
  Un entier naturel \emph{autre que 1} qui n'est pas premier est dit 
\textbf{composé}.
\end{definition}
\end{frame}





\subsection{Tests et cribles}

\begin{frame}[fragile]
  \frt{Premier or not premier~?}
{\tiny
\begin{Verbatim}
    test1(n):={
    local k;
    L:=[]; //on crée une liste vide au départ pour y placer les diviseurs de n
    for(k:=2;k*k<=n;k++){ //pour travailler sans approximation
    if (n mod k==0) {return n+'' n'est pas premier''//si k divise n, n n'est pas premier
    }
    return n+" est premier."// sinon n est premier
    }:;
\end{Verbatim}

\end{frame}
}

\begin{frame}[fragile]
  \frt{Crible d'Ératosthène}
{\tiny
\begin{Verbatim}
   Erato(n):={
   local x,j,k,m,q,P;
   x:=[seq(1,j=1..n+1)] // on crée une liste de n+1 nombres valant tous 1 au départ
   x[1]:=0; // 0 et 1 ne sont pas premiers donc on les "raye" en leur associant 0
   for(k:=2;k*k<=n;k++){ // on teste les entiers de 2 à racine carrée de n
   if (x[k]==1) { // si le keme nombre n'est pas barré
   for(m:=2;m<=floor(n/k);m++){
   x[k*m]:=0; // on barre tous ses multiples
   }}}
   P:=[]; // on crée une liste vide
   for(q:=2;q<=n;q++){
   if (x[q]==1) { // si q n'est pas barré
   P:=append(P,q); // on ajoute q à la liste des premiers
   }
   }
   return P
   }:;
\end{Verbatim}}
\end{frame}





\subsection{Décomposition des entiers en produit de nombres premiers}


\begin{frame}
  \begin{propriete}
  Tout entier $n$ supérieur à  2 se décompose en produit fini de nombres 
premiers.
\end{propriete}


\pause

La démonstration la plus simple (mais pas la plus intéressante) consiste à  
raisonner par récurrence sur $n$.

\end{frame}



\begin{frame}
  \begin{theorem}
  Tout entier $n$ supérieur à  2 admet une et une seule (à  l'ordre près 
des termes) décomposition en produit fini de nombres
premiers
\end{theorem}
\end{frame}


\begin{frame}[fragile]
  \frt{Décomposition informatique}
{\tiny
\begin{Verbatim}
  decompo(n):={
  local L,D,N,k;
  D:=[]; //liste des diviseurs premiers, vide au départ
  L:=Erato(n); // on utilise la procédure précédente
  N:=n; // N est l'entier mobile dont on cherche les diviseurs
  while (contains(L,N)==0){ // tant que N n'est pas premier
  for(k:=0;k<length(L);k++){// length(L)=nombre d'éléments de L
  if (N mod L[k]==0){ D:=append(D,L[k]); // si le keme premier divise N, on le rajoute à D
  N:=iquo(N,L[k]); // on divise N par ce nombre premier
  break; // on recommence la boucle au cas où le keme premier divise encore n
  }
  }
  }
  D:=append(D,N); // on n'oublie pas n au cas où il est premier
  }:;
\end{Verbatim}
}

\end{frame}



\begin{frame}[fragile]


Pour être honnête, il existe la fonction \textsf{ifactor} qui donne directement la décomposition en produit de facteurs premiers.


\begin{Verbatim}
  ifactor(500) ;
\end{Verbatim}



  

\end{frame}




\section{Exercices}

{\footnotesize

\begin{frame}

  \begin{exobeam}
    \begin{enumerate} \item \textbf{Démonstration de cours.}

Démontrer qu'il existe une infinité de nombres premiers.

\item Soit $p$ un nombre premier strictement plus grand que 2. Démontrer
que $p$ est congru à 1 ou à $-1$ modulo 4. Donner deux exemples de chacun de ces cas.


 \textsl{Le but de ce qui suit est de répondre à la question suivante :} « \textsl{Les nombres premiers} $p$ \textsl{congrus à} $-1$
\textsl{modulo} 4 \textsl{sont-ils en nombre fini ?} »

Supposons que ce soit le cas : soit $n$ le nombre des nombres premiers congrus à $-1$ modulo 4 ; notons $A = p_{1}p_{2}\cdots p_{n}$ le
produit de ces nombres et $B = 4A - 1$.

\item Montrer que $B$ est congru à $-1$ modulo 4.

\item Soit $q$ un diviseur premier de $B$. Montrer que $q$ est distinct de
chacun des nombres $p_{1},~p_{2},~\cdots,~ p_{n}$ précédents.

Montrer que parmi les diviseurs premiers de $B$, l'un au moins est congru à $-1$ modulo 4.

\item Quelle réponse apporter à la question posée ?

\end{enumerate}


   \end{exobeam}
  
\end{frame}

}




{\tiny

\begin{frame}
  \begin{exobeam}
   


Les nombres 1; 11; 111; 1111 etc. sont des nombres que l'on appelle rep-units (répétition de l'unité). Ils ne s'écrivent qu'avec des
chiffres 1. Ces nombres possèdent de nombreuses propriétés : nous allons en découvrir quelques-unes.


Pour $k$ un entier strictement positif, on note $N_k$ le rep-unit qui s'écrit avec $k$ chiffres 1.

\begin{enumerate}
\item Citez deux nombres premiers inférieurs à 10 n'apparaissant jamais dans la décomposition d'un rep-unit. Justifiez rapidement votre
réponse.

\item À quelle condition sur $k$ le nombre 3 apparaît-il dans la décomposition du rep-unit $N_k$~? Justifiez brièvement votre réponse.

\item Pour $k\se1$, $N_k=\ds\sum_{i=0}^{k-1}10^i=1+10^1+10^2+\cdots+10^{k-1}$ Justifiez l'égalité suivante pour tout $k\se1$ $$9N_k=10^k-1$$

\item Le tableau ci-dessous donne les restes de la division par 7 de $10^k$, pour $k\in[\![1,8]\!]$

\sm

\begin{tabular}{|c|c|c|c|c|c|c|c|c|}

\hline
k&1&2&3&4&5&6&7&8\\
\hline Reste de la division de $10^k$ par 7&3&2&6&4&5&1&3&2\\
\hline

\end{tabular}

\sm

Soit $k$ un entier strictement positif. Démontrez que

$$10^k\equiv 1[7]\ssi k \text{ est un multiple de } 6$$

Déduisez-en que 7 divise $N_k$ si et seulement si 6 divise $k$.

\end{enumerate}




 \end{exobeam}
    
  
\end{frame}

}








\end{document}