\documentstyle{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed\newline}


\newcommand{\catedra}[4]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
                        \hfill Semestre Oto\~no, 1998}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}

% LISTA DE MACROS PERSONALES COMIENZA AQUI

\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}

\newcommand{\modulo}{{\cal Z}}
\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}	
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}

\newcommand{\chapref}[1]{\mbox{Capitulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}

% FIN LISTA DE MACROS PERSONALES

\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%	primer parametro: No. de catedra transcrita
%	segundo parametro: fecha de catedra transcrita
%	tercer parametro: Nombre del transcriptor
\catedra{10}{14 de Abril}{Miguel Barrera M.\footnotemark}

\footnotetext{\ Basada en una
  transcripci\'on anterior de Jens Hardings}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Criptograf\'{\i}a Moderna o de Clave P\'ublica}
%
En los criptosistemas vistos hasta ahora, Alicia
y Roberto eligen la clave $K$ en secreto, comunic\'andola a trav\'es de
un canal seguro. Esta clave permite generar una regla de encripci\'on
$e_{K}$ y una regla de decripci\'on $d_{K}$. En los criptosistemas que
hemos estudiado, $d_{K}$ es f\'acilmente derivable al conocer $e_{K}$.
Los criptosistemas de este tipo se conocen con el nombre de criptosistemas de
clave privada.

Evidentemente, al usar este tipo de sistemas se depende de la existencia previa
(aunque sea temporal) de un canal seguro, en el cual Alicia y Roberto se
comunican la clave, para luego poder mandar informaci\'on a trav\'es de otro
canal inseguro.

En cambio, la criptograf\'{\i}a de clave p\'ublica se basa en la idea que
quiz\'as es posible encontrar un criptosistema en que es computacionalmente
infactible determinar $d_{K}$ dado $e_{K}$. En ese caso, $e_{K}$
puede ser publicada por Roberto, y Alicia o cualquier otro individuo puede
enviar mensajes encriptados a Roberto usando $e_{K}$ y este \'ultimo ser\'a
la \'unica persona capaz de decriptar el texto cifrado usando su regla de
decripci\'on secreta $d_{K}$.

La idea de la criptograf\'{\i}a p\'ublica se debe a Diffie y Hellman [1976],
los cuales no dieron un ejemplo de criptosistema de este tipo. Ellos
propusieron que pod\'{\i}a construirse un criptosistema de este tipo si era
posible encontrar una funci\'on ``f\'acil'' de calcular, pero ``dif\'{\i}cil''
de invertir. La primera realizaci\'on de un criptosistema p\'ublico se debe a
Rivest, Shamir y Adleman
[1977].

El hecho de que no se requiera un canal seguro para la comunicaci\'on de una 
clave secreta supone una ventaja con respecto a la criptograf\'{\i}a de clave 
privada, y esta raz\'on ha facilitado la propagaci\'on de la Criptograf\'{\i}a 
de clave p\'ublica en medios masivos, como por ejemplo Internet o los mismos
tel\'efonos port\'atiles. 

Sin embargo es importante notar que un criptosistema de clave p\'ublica no podr\'a jam\'as
ser un criptosistema perfectamente secreto. En efecto, conocido el texto
cifrado, un adversario puede encriptar todos los textos planos y determinar
cual es el \'unico tal que $y=e_{K}(x)$, dado que el adversario conoce $e_{K}$.
Luego, el texto cifrado enviado permite identificar completamente el texto
plano. Por lo tanto, la discusi\'on de la seguridad de los criptosistemas de
clave p\'ublica necesariamente debe hacerse en el \'ambito de la seguridad
computacional, i.e. la dificultad computacional de calcular $d_{K}$ conociendo
$e_{K}$.

\section{Definici\'on de criptosistema de clave p\'ublica}

El escenario que consideraremos es uno en que hay $(U_{1}$...$U_{n})$ usuarios 
con pares de claves $<P_{n},S_{n}>$ donde $P_{n}$ es p\'ublico 
(conocido por los $U_{n}$ usuarios) y $S_{n}$ es secreto.

\begin{definition} 
un criptosistema de clave p\'ublica es un tripleta $(G,E,D)$ 
de algoritmos probabilistas a tiempo polinomial esperado tal que.



\renewcommand{\labelenumi}{\roman{enumi}.}
\begin{itemize}

\item $G$ es el algoritmo generador de claves:

Toma desde la entrada $1^k$  y produce 
un par $(e,d)$ donde $e$ es denominada clave publica y $d$ es denominada 
clave secreta (notaci\'on $(e,d)$ $\varepsilon$ $G(1^k)$).

Tambi\'en nos referiremos a $(e,d)$ como par de claves de 
encripci\'on/decripci\'on.

\item $E$ es el algoritmo de encripci\'on:

Este algoritmo toma como entrada $1^k$, una clave p\'ublica $e$, 
un mensaje $m$ $\varepsilon$ $\{0,1\}^k$ y produce
como salida $c$ $\varepsilon$ $\{0,1\}^*$ llamado texto cifrado.

Notaci\'on:

$c$ $\varepsilon$ $E(1^k,e,m)$ o
$c$ $\varepsilon$ $E(e,m)$ o
$c$ $\varepsilon$ $E(m)$

nota: se usaran estas dos \'ultimas, cuando sea claro por contexto.

\item $D$ Algoritmo de decripci\'on :

El algoritmo toma $1^k$ una clave publica $e$ , una clave privada $d$ y
$c$ $\varepsilon$ $E(1^k,e,m)$ y produce
como salida $m$ $\varepsilon$ $\{0,1\}^*$ tal que
$\forall$ $(e,d)$ $\varepsilon$ $G(1^k),$ $\forall$ $c$ $\varepsilon$ 
$E(1^k,e,m)$ 
Pr$[D(1^k,e,d,c)$ $\neq$ $m]$ es despreciable.

Es decir, se acepta que la decripci\'on no sea \'unica.


\end{itemize}
\renewcommand{\labelenumi}{\arabic{enumi}.}

\end{definition} 


\textbf{Convenci\'on }

{\em Extendemos la notaci\'on de forma que}
$E(\alpha_{1}...\alpha_{l+1})$=$E(\alpha_{1})...E(\alpha_{l})
E(\alpha_{l+1}$ $P)$.

{\em Donde P hace padding para completar el bloque y donde}
$\alpha_{1}...\alpha_{l},\alpha_{l+1}P$ $\varepsilon$ $\{0,1\}^k$



\section{RSA}

\emph{RSA} es el criptosistema de clave p\'ublica ideado por Rivest, Shamir
y Adleman. En este sistema, el conjunto de claves

$\key =
\set{(n,e,d)}{n=p \cdot q$ ($p,q$ primos) 
y $e,d$ $\varepsilon$ $\modulo_{\varphi (n)}$ 
son tales que $e \cdot d \equiv 1(\bmod \varphi (n))}$,

donde $\varphi (n)$ es la funci\'on phi de Euler, y
si K = $(n,e,d)$ $\varepsilon$ $\key$
\begin{eqnarray*}
e_{K} & = & x^{e} \bmod n\\
d_{K} & = & y^{d} \bmod n.
\end{eqnarray*}
La clave p\'ublica es $(n,e)$ y la clave privada es $d$.

Observar que para que $d_{K}(e_{K}(x)) = x$, se debe tener que
$x = x^{e \cdot d} \bmod n, \forall x \in \modulo_{n}$ si $e \cdot d \equiv 1 ( \bmod
\varphi(n))$. No estamos en condiciones de probar esto \'ultimo. Para ello
requerimos ahondar en teor\'{\i}a de n\'umeros (ver la secci\'on 4).


\textbf{Ejemplo 1}

Ahora vamos a dar un ejemplo de uso de un criptosistema RSA:

Supongamos que Roberto elige $p$ = 101 y $q$ = 113. Entonces $n$ = 11413 y \\
$\varphi(n)$ = 100 $\cdot$ 112 = 11200. 

Como 11200 = $2^{6}5^{2}7$ cualquier entero $e$ puede ser usado como un 
exponente de encripci\'on, si y solo si $e$ no fuera divisible por 2, 5 o 7.
(No se debe factorizar $\varphi(n)$ , solo hay que verificar que 
mcd($\varphi(n),e$)=1 usando el algoritmo del Euclides).

Supongamos que roberto elige e=3533. Entonces del algoritmo de Euclides resulta:

\begin{displaymath}
e^{-1} = 6597 \bmod 11200
\end{displaymath}

Luego, la clave secreta de roberto es $d$=6597


Roberto publica $n$= 11413 y $e$=3533. Ahora supongamos que Alicia quiere 
enviar a Roberto el texto 9726. Ella calcular\'a:

\begin{displaymath}
9726^{3533} \bmod 11413 = 5761
\end{displaymath}

y enviar\'a el texto cifrado 5761 por cualquier canal hasta Roberto.
Cuando Roberto reciba el mensaje, el usar\'a su clave secreta y calcular\'a:

\begin{displaymath}
5761^{6597} \bmod 11413 = 9726
\end{displaymath}

Esta instancia de RSA es f\'acil de atacar porque $p$ y $q$ son n\'umeros 
peque\~nos, 
entonces la factorizacion de $\varphi(n)$ es posible.

Hay algoritmos computacionales que factorizan hasta un n\'umero de 130 
cifras en un tiempo corto (horas en m\'aquinas modernas), 
por lo cual se recomienda que la 
elecci\'on de los $p$ y $q$, tenga cada uno 100 cifras, 
con lo que $n$ tendr\'{\i}a unas 200 cifras, n\'umero cuya 
factorizaci\'on no es computacionalmente factible (en el sentido del tiempo 
empleado, en estos algoritmos el tiempo de espera crece muy r\'apido).

  
\newpage

\section{M\'as de teor\'{\i}a de n\'umeros}



\textbf{Congruencias}

En esta secci\'on repasaremos algunos resultados b\'asicos que conciernen
a las congruencias.

Dados tres enteros $a,b,m$ decimos que \emph{$a$ es congruente a $b$
  m\'odulo $m$}
si 
$m|(a-b)$ y lo denotamos $a$ $\equiv$ $b$ (mod $m$) o $a$ $\equiv_{m}$ $b$\\

Sea $\modulo_{m}$ el conjunto $\{0,\ldots,m-1\}$ dotado de dos 
leyes de composici\'on interna: suma ($+$) y 
multiplicaci\'on ($\cdot$), donde la suma y multiplicaci\'on son 
exactamente iguales a la suma y multiplicaci\'on de enteros pero
donde los resultados son reducidos m\'odulo $m$.
Se verifica que $\modulo_{m}$ as\'{\i} definido forma un anillo conmutativo
con unidad.\footnotemark


\footnotetext{Recordemos que una estructura $\left(A,+,*\right)$ es una estructura de
anillo conmutativo con unidad, si se cumplen las propiedades siguientes:\\
$\left(A,+\right)$ es una estructura de grupo abeliano\\
$\left(x \cdot y\right)\cdot$ $z$= $x$ $\cdot$ $\left(y \cdot z\right)$,
$\forall$  $x, y, z$ $\in$ $A$ (Asociativa). \\
$x \cdot \left(y + z\right)$ = $x \cdot y + x \cdot z$;
$\left ( x + y \right) \cdot z$ = $x \cdot z + y \cdot z$
$\forall x,y,z$ $\in$ $A$ (Distributiva). \\
$\exists$ 1 $\in$ $A |$  $x$ $\cdot$ 1 = 1 $\cdot$ $x$ = $x$, $x$
$\in$ $A$ (Existencia de elemento unidad) \\
$x$ $\cdot$ $y$ = $y$ $\cdot$ $x$, $\forall$  $x,y$ $\in$ $A$ 
(Conmutativa)}


A continuaci\'on enumeramos algunas propiedades de las congruencias.

\renewcommand{\labelenumi}{\roman{enumi}.}
\begin{itemize}

\item Si $a$ $\equiv_{m}$ $b$ y $c$ $\equiv_{m}$ $d$ $\Rightarrow$
$a$ $\pm$ $c$ $\equiv_{m}$ $b$ $\pm$ $d$ y $a\cdot c$ $\equiv_{m}$ $b\cdot d$

\item Si $a$ $\equiv_{m}$ $b$ y $d|m$ $\Rightarrow$ $a$ $\equiv_{d}$ $b$

\item Si $a$ $\equiv_{m}$ $b$ y $a$ $\equiv_{n}$ $b$ y 
$mcd(n,m)=1$ $\Rightarrow$ $a$ $\equiv_{n \cdot m}$ $b$

\end{itemize}

\renewcommand{\labelenumi}{\arabic{enumi}.}

\begin{proposition}\label{prop:inversos}
Los elementos de $\modulo_{m}$ que tienen inversos multiplicativos son
  a\-que\-llos que son relativamente primos a $m$. 
De hecho, de existir el inverso de $a\in \modulo_{m}$ este se puede
  calcular en el tiempo que toma el algoritmo de Euclides en
  determinar $\mcd{a}{m}$.
\end{proposition}

\begin{proof}
Si $a\in \modulo_{m}$ no es relativamente primo a $m$ entonces 
  $d=\mcd{a}{m}>1$. 
Supongamos que existe un $b\in \modulo_{m}$ 
  tal que $ab\equiv$ 1 (mod $m$).
Luego $ab-1$ es divisible por $d$, pero $d|a$, 
  por lo tanto concluimos que $1$ es divisible por $d$, contradicci\'on.

Si $a\in \modulo_{m}$ es relativamente primo a $m$ entonces 
  por un corolario anterior que dec\'{\i}a que si $a$ y $m$ eran primos relativos,
entonces existen enteros $u$ y $v$ tales que 
  $1=au+mv$.
Eligiendo $b=u$, sigue que $m|(1-ab)$,
i.e. $ab \equiv$ 1 (mod $m$).
Luego, $b \bmod m\in\modulo_{m}$ es inverso multiplicativo de $a$.
\end{proof}

\begin{corollary}
La ecuaci\'on $ax\equiv$ b (mod $m$) en la indeterminada $x$
  tiene soluci\'on en $\modulo_{m}$ si $a$ y $m$ son primos relativos y
  el tiempo que toma calcular sus soluciones esta dominado por el
  tiempo que toma encontrar inversos en $\modulo_{m}$.
Si $d=\mcd{a}{m}>1$  entonces $ax\equiv$ b (mod $m$) tiene soluci\'on 
  en $\modulo_{m}$ ssi $d|b$ y sus soluciones son las mismas que las
  de la ecuaci\'on $a^{\prime}x\equiv b^{\prime}$ (mod $m^{\prime}$) donde
  $a^{\prime}=a/d$, $b^{\prime}=b/d$ y $m^{\prime}=m/d$.
\end{corollary}
\begin{proof}
Claramente la soluci\'on en $\modulo_{m}$ de la ecuaci\'on  
  $ax\equiv$ b (mod $m$) es $x=a^{-1}b \bmod m$ donde $a$ es el
  inverso multiplicativo de $a\in\modulo_{m}$ que existe puesto
  que $a$ y $m$ son primos relativos y por la \propref{prop:inversos}.

Si $x$ es soluci\'on de $ax\equiv$ b (mod $m$) y $d=\mcd{a}{b}$ entonces
  $ax\equiv$ b (mod $d$).
Luego $d|(ax-b)$.
Pero como adem\'as $d|a$ se concluye que $d|b$.
Por otro lado, $ax\equiv$ b (mod $m$) implica que $ax=b+km$ para alg\'n entero
  $k$.
Luego, $a^\prime x = b^\prime - km^\prime$, i.e. 
  
$a^\prime x\equiv b^\prime$ (mod $m^\prime$).
En el sentido inverso, tenemos que si $d|b$ entonces $b^\prime$ es un entero
  y como $a^\prime$ y $m^\prime$ son primos relativos existe
  un $x$ soluci\'on de 
  $a^\prime x\equiv b^\prime$ (mod $m^\prime$).
Luego, $a^\prime x = b^\prime - km^\prime$ para alg\'un entero $k$.
Sigue que $ax=b-km$, i.e. $ax\equiv$ b (mod $m$).
\end{proof}

\begin{definition}
Dado $G$ grupo, llamamos orden de $G$ a la cantidad de elementos en $G$ 
y se denota $|G|$.
\end{definition}


\begin{definition}
Se define $\modulo_{n}^{*}$ como el conjunto de n\'umeros que 
pertencen a  $\modulo_{n}$
y que son primos relativos con $n$, por lo tanto

\begin{displaymath}
\modulo_{n}^{*} = \{m  \varepsilon  \{1,...,n-1\}/mcd(n,m)=1\}
\end{displaymath}
\end{definition}

\newpage

\begin{proposition}
$\modulo_{n}^{*}$ es un grupo abeliano.
\end{proposition}

\begin{proof}

\underline{Cerradura:} 
Es f\'acil ver que $xy$ es primo relativo con $n$ 
siempre que $x$ e $y$ sean primos relativos con $n$ 
(no comparten factores y al multiplicarlos tampoco).

\underline{Asociatividad:}
Se hereda de la asociatividad en $\modulo_{n}$.

\underline{Conmutatividad:}
Se hereda de la conmutatividad en $\modulo_{n}$.

\underline{Elemento neutro:}
El 1, heredado tambi\'en del neutro multiplicativo en $\modulo_{n}$.

\underline{Elemento inverso:}
Por demostrar que $a$ $\varepsilon$ $\modulo_{n}^{*}$ $\Rightarrow$
$a^{-1}$ $\varepsilon$ $\modulo_{n}^{*}$.

Podemos observar que si $a$ $\varepsilon$ $\modulo_{n}^{*}$ entonces
es invertible en $\modulo_{n}$, luego $\exists$ $a^{-1}$ $\varepsilon$ 
$\modulo_{n}$.

Debemos probar que $a^{-1}$ $\varepsilon$ $\modulo_{n}^{*}$, i.e.
mcd($a^{-1}$,$n$)=1

En efecto, si $a \cdot a^{-1}$ $\equiv$ 1(mod $n$) entonces  
$n|(aa^{-1}-1)$ 

Supongamos ahora que $\exists$ $d$ $|$ 1 $<d<n$ y que $d|a^{-1}$ y $d|n$

pero $aa^{-1}-1$ = $kn$ $\Rightarrow$ $aa^{-1}-kn$ = 1
como $d|(aa^{-1}-kn)$ $\Rightarrow$ $d|$1 $\Rightarrow$ $d$ = 1

esto \'ultimo est\'a en contradicci\'on con el hecho de que $d>$1

entonces tenemos que mcd($a^{-1}$,$n$)=1

y por lo tanto $a^{-1}$ $\varepsilon$ $\modulo_{n}^{*}$.

\end{proof}

\begin{theorem}{El peque\~no teorema de Fermat}

Sea $p$ un primo. Entonces, para todo entero $a$, $a^{p} \equiv a (\bmod p)$
y si $a$ no es divisible por $p$, entonces $a^{p-1} \equiv 1 (\bmod p)$.
\end{theorem}

\begin{proof}
Sea $a$ divisible por $p$. Entonces $a \equiv 0 (\bmod p)$ y $a^{p} \equiv
0(\bmod p)$ por lo que $a^{p} \equiv a(\bmod p)$.

Si $p$ no divide a  $a$ tenemos que $|\set{ia \bmod p}{i \in \{1,...,p-1\}}|
= p-1$. En efecto, si $i$ es distinto de $j$ y $ia \equiv ja (\bmod p)$,
entonces $p$ divide a $a(i-j)$.
Como $p$ es primo, $p$ no divide a $a$, y $p$ es primo relativo con $a$,
tenemos que $p \mid (i-j)$, lo cual contradice el supuesto anterior.

Luego, el conjunto $\set{ia \bmod p}{i \in \{1,...,p-1\}} = \modulo_{p}^{*}$
\begin{eqnarray*}
 \prod_{i=1}^{p-1} i & \equiv & \prod_{i=1}^{p-1}
 (ia)(\bmod p)\\
 a^{p-1} \prod_{i=1}^{p-1} i & \equiv & \prod_{i=1}^{p-1} i
\end{eqnarray*}
Como $\prod_{i=1}^{p-1} i$ es primo relativo con $p$, se puede cancelar en
ambos lados y obtenemos $a^{p-1} \equiv 1 (\bmod p)$

Inmediatamente se ve que $a^{p} \equiv a (\bmod p)$
\end{proof}

\begin{corollary}
Si $a$ no es divisible por $p$ y $n \equiv m(\bmod (p-1))$, entonces\\
$a^{n} \equiv a^{m}(\bmod p)$.
\end{corollary}

\begin{proof}
Si $n \equiv m (\bmod p-1)$, entonces se cumple que existe un entero $b$ tal
que $n = m + b(p-1)$. Por lo tanto, $a^{n} = a^{m+b(p-1)} = a^{m} \cdot
a^{b(p-1)}$ y del teorema anterior se tiene que $a^{b(p-1)} \equiv
{(a^{p-1})}^{b} \equiv 1(\bmod p)$, y entonces $a^{n} \equiv a^{m}(\bmod p)$.
\end{proof}

\begin{theorem}{Euler}

Si $a$ es primo relativo con $n$, entonces $a^{\varphi(n)} \equiv 1(\bmod n)$.
\end{theorem}

\begin{proof}

si mcd($a,n$)=1, entonces la funci\'on definida desde $\modulo_{m}^{*}$ a 
$\modulo_{m}^{*}$ tal que a $i$ le asigna la imagen $i \cdot a$ es invertible, 
en particular es biyectiva.

Debido a esto podemos establecer las siguientes igualdades

\begin{displaymath}
\large{
\prod_{i \varepsilon \modulo_{m}^{*}}i \,  \equiv_{m}
\prod_{i \varepsilon \modulo_{m}^{*}}(i \cdot a) \, \equiv_{m}
a^{\varphi(n)} \cdot  \prod_{i \varepsilon \modulo_{m}^{*}}i 
}
\end{displaymath}

Luego se pueden cancelar las pitatorias del primer y tercer t\'ermino, debido
a que estamos en un grupo abeliano.

De esto \'ultimo resulta $a^{\varphi(n)}$ $\equiv_{m}$ 1

\end{proof}

\textbf{Dem. alternativa:}
Primero se demostrar\'a el teorema en el caso de que $n$ es una potencia de
un primo $p$, o sea que $n = p^{\alpha}$. Para ello usaremos inducci\'on
sobre $\alpha$.
El caso $\alpha = 1$ ya se demostr\'o anteriormente (peque\~no Teorema de
Fermat). Suponiendo que $\alpha \ge 2$, y que se cumple el teorema para
$n = p^{\alpha-1}$, entonces $a^{p^{\alpha - 1}-p^{\alpha - 2}} = 1 + p^{\alpha
- 1}b$ para alg\'un entero $b$. Usando el hecho de que los coeficientes
binomiales de $(1+x)^{p}$ son divisibles por $p$, exceptuando $1$ y $x$ en
los extremos\footnote{Al expandir, se ve que los t\'erminos son de la forma
$\big(\stackrel{p}{i}\big)x^{i}$, con $1 < i < p$, los cuales son claramente
divisibles por $p$.}, se puede elevar a $p$ a ambos lados y se llega a
$a^{p^{\alpha}-p^{\alpha - 1}} = 1 + S$, donde $S$ es una suma de t\'erminos
todos divisibles por $p$. Entonces se tiene que $a^{\varphi(p^{\alpha})} - 1$
es divisible por $p$, dado que como hemos visto anteriormente,
$\varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha - 1}$.

Finalmente, como $\varphi$ es multiplicativa, es claro que $a^{\varphi(n)}
\equiv 1 (\bmod p^{\alpha})$.

En el caso general, existen $m$ distintos $p_{i}$ (todos primos) y $e_{i}$,
$m$ un natural, tales que
\begin{eqnarray*}
n & = & \prod_{i = 1}^{m}p_{i}^{e_{i}} \\
\varphi(n) & = & \prod_{i = 1}^{m}\varphi(p_{i}^{e_{i}})
\end{eqnarray*}
Definamos
\[ b_{j} = \prod_{i = 1}^{j}p_{i}^{e_{i}} \ , con \ j = 1,...,m .\]
Como $b_{j-1}$ es primo relativo con $p_{j}^{e_{j}}$, se puede ocupar la parte
anterior de la demostraci\'on para cada $b_{j}$, entonces:
\begin{eqnarray*}
a^{\varphi(b_{1})} = & a^{\varphi(p_{1}^{e_{1}})} & \equiv 1 (\bmod p_{1}^{e_{1}})\\
& \vdots &\\
a^{\varphi(b_{j})} = & (a^{\varphi(b_{j-1})})^{\varphi(p_{j}^{e_{j}})} & \equiv 1 (\bmod p_{j}^{e_{j}}),
\end{eqnarray*}
o sea que $a^{\varphi(n)} \equiv 1 (\bmod p_{j}^{e_{j}})$ para $j = 1,...,m$.
Entonces, podemos afirmar que
\[ a^{\varphi(n)} \equiv 1 (\bmod \prod_{i = 1}^{n} p_{i}^{e_{i}}) \]
y se concluye que $a^{\varphi(n)} \equiv 1 (\bmod n)$.

\qed


\begin{corollary}
Si $a$ es primo relativo con $n$, y $m \equiv m'(\bmod \varphi(n))$, entonces\\
$a^{m} \equiv a^{n}(\bmod n)$.
\end{corollary}

\begin{proof}
Del teorema anterior tenemos que $ a^{\varphi(n)} \equiv 1(\bmod n)$.
Adem\'as, $m \equiv n(\bmod \varphi(n))$, o sea que $m = t\varphi(n)+n$,
para alg\'un entero $t$.
Entonces, $a^{m} \equiv a^{t\varphi(n)+n} \equiv (a^{\varphi(n)})^{t}\cdot
a^{n}\equiv a^{n} (\bmod n)$.
\end{proof}

\end{document}






