 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%          Teor'ia de N'umeros                 %%% 
%%%                                              %%%         
%%%   Notas para un curso para alumnos de prepas %%%         
%%%    de Viba en el CIMAT, nov-dic 1997        %%% 
%%%                                              %%%        
%%%              escrito en latex                %%%        
%%%                                              %%%        
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentstyle[12pt,spaccent]{article}
\newtheorem{thm}{Teorema}
\newcommand{\n}{\noindent}
\newcommand{\p}{\mbox{'}}
\newcommand{\bs}{\bigskip}
\newcommand{\ms}{\medskip}
\newcommand{\dem}{\n{\bf Demostraci\'on. }}
\newcommand{\qed}{\hfill\mbox{$\Box$}\bigskip}
\def\mod#1{ \,\,\,(\hbox{mod }{#1})}


\begin{document}
\specialaccent

%%%%%%%%%%%%%%%%   titulo  
\rightline{Taller de Matem'aticas, Viba}
\rightline{CIMAT, 1997}
\bs\bs\bs
\centerline{\Huge Teor'ia de N'umeros}
\bs\bs\bs\bs\bs\bs

\n{\bf Plan general:}
\begin{enumerate}


\item Introducci'on y conceptos b'asicos\

\begin{itemize}

\item Divisibilidad de enteros 

\item N'umeros primos

\item El Teorema Fundamental de la Aritm'etica

\item La sucesi'on de los primos

\item Algunas preguntas acerca de los primos 

\item La demostraci'on del Teorema Fundamental de la Aritm'etica

\end{itemize}

\item Congruencias

\begin{itemize}

\item Definici'on de congruencias

\item Propiedades elementales de congruencias

\item El ``peque\~no'' teorema de Fermat



\end{itemize}
\end{enumerate}

\newpage



\section{Introducci\'on y conceptos b\'asicos}

\subsection{Divisibilidad de enteros}

 Los n'umeros
$$\ldots, -3,-2,-1,\,\,0,\,\,1,\,\,2,\ldots$$
se llaman los {\em enteros}; los n'umeros

 $$0,1,2,3,\ldots$$ 
los {\em enteros no-negativos}; y los n'umeros 
 $$1,2,3\ldots$$ 
 los {\em enteros positivos}. Los enteros positivos forman la materia prima
de la aritm'etica, pero a veces es esencial considerarlos como una
sub-clase de una clase m'as amplia de n'umeros como los enteros.

Se dice que un entero $ n$ es {\em divisible} por otro entero $ d$,
distinto de cero, si existe un entero, digamos $ m$, tal que $ n = d \cdot
m$.

Si $ n$  y $ d$  son positivos, $ m$  tambi\'en es necesariamente
positivo. Expresamos el hecho que $ n $ es divisible por $d$, o que $d$ es
un {\em divisor} de $n$, por
$$d|n.$$
As'i tenemos que

$$1|n\,\,\,\,\, \mbox{y}\,\,\,\,\, n|n,$$
para todo $n$, y $d|0$ para todo $d \ne 0$.

Es bastante f'acil demostrar que
\begin{eqnarray}
a|b, b|c &\Longrightarrow& a|c,\\
a|b  &\Longrightarrow&ac|bc,\\
a|b, a|c &\Longrightarrow& a|\,(bm + cn)
\end{eqnarray}
para todo $m,n$ enteros. (La notaci'on ``A $\Longrightarrow$ B'' significa
``el hecho A implica el hecho B'').


 

Demostramos (1): Si $a|b$ entonces existe un entero $m_1$ tal que $b =
am_1$; y si $b|c$ existe un entero $m_2$ tal que $c = bm_2$. Llamamos $m$
al producto $m_1m_2$; entonces tenemos que $c = bm_2 = (am_1)m_2 =
a(m_1m_2) = am$, as'i que $a|c$, seg\'un la definici'on. 
\bs
Dejamos la demostraci'on de (2) y (3) como un ejercicio.

\subsection{N\'umeros primos}\label{sec:primos}

Entre los enteros positivos hay una sub-clase de importancia particular, la
clase de los primos. Un n'umero entero positivo $p$ se llama {\em primo}
si

\medskip
(i) $p >1$,

 (ii) $p$ no tiene divisores positivos adem'as de $1$ y $p$.  

\medskip\n Por ejemplo, $37$ es un primo. Es importante notar que 1 no se
considera primo. Normalmente reservamos la letra $p$ para los primos.

Un n'umero entero positivo mayor que $1$ y no primo se llama {\em
compuesto}. 
\medskip
Aqu'i est'a nuestro primer teorema:

\begin{thm}
Todo entero positivo, con excepci'on del 1, es un producto de primos. 
\end{thm}

\dem Sea $n$ un entero positivo mayor que 1. Si $n$ es primo, no hay
nada que probar. Si $n$ no es primo, o sea compuesto, entonces tiene
divisores entre 1 y $n$. Si $m$ es el m'as peque\~no entre estos
divisores, $m$ debe ser primo; porque si no, entonces $m$ tendr'ia un
divisor $l$, $1 < l < m$, que necesariamente ser'ia tambi'en un
divisor de $n$. Esto contradice la elecci'on de $m$ como el divisor
m'as peque\~no; as'i que $m$ debe ser primo.

Concluimos entonces que si $n$ no es primo es divisible por un primo,
digamos $p_1$, o sea 
$$n = p_1n_1,$$
donde $n_1$ es un entero positivo, $1<n_1 <n$. Si
$n_1$ es primo la demostraci'on est'a terminada, y si no, continuamos
como antes: $n_1$ es divisible por un primo $p_2$ menor que $n_1$,
as'i que

$$n = p_1n_1 = p_1p_2n_2,$$
 donde $n_2$ es un entero positivo, $1 <n_2 < n_1 < n$.

As'i seguimos y obtenemos una suceci'on decreciente de enteros positivos $n
> n_1 >
 n_2 >n_3>\ldots>1$. Tarde o temprano este proceso tiene que parar, o sea
obtenemos un $ n_k = p_k$ primo, y 
\begin{equation}\
n = p_1p_2p_3 \ldots p_{k-1} p_k.\label{eqn:fact}
\end{equation}
Esto completa la demostraci'on. \qed


Por ejemplo, si empezamos con 666, obtenemos
$$666 = 2 \cdot 3 \cdot  3 \cdot 37.$$

\bs 

Ahora una observaci'on que nos ayuda a averiguar si un entero
$n$ es compuesto o primo: si $n = a \cdot b$, entonces $a$ y $b$ no pueden
ser ambos mayores que $\sqrt{n}$, as'i que si $n$ es compuesto, 
es divisible por un primo no mayor que $\sqrt{n}$. Por ejemplo, para
averiguar si 79 es un primo, es suficiente verificar si tiene un divisor primo
menor que 9 (notando que $8<\sqrt{79}<9$). Como 2,3,5 y 7 no dividen a 79
concluimos que 79 es un primo.

Los primos en la factorizaci'on (\ref{eqn:fact}) no son necesariamente
distintos, o arreglados en un orden particular. Si los arreglamos en orden
creciente, agrupando conjuntos de primos id'enticos en un 'unico factor, y
cambiamos la notaci'on un poco, obtenemos
\begin{equation}\label{eqn:formaestandar} n = p_1^{a_1} p_2^{a_2} p_3^{a_3}
\ldots p_k^{a_k}, \end{equation} donde $a_1, a_2,\ldots$ son enteros
positivos.  Decimos entonces que $n$ est'a expresado en {\em forma
estandar}. Por ejemplo,
$$169400 = 2^3 \cdot 5^2 \cdot 11^2$$
es una expresi'on de $169400$ en
forma estandar.

\subsection{El Teorema Fundamental de la Aritm'etica}

 No hay nada en la demostraci'on del Teorema 1 que nos asegure que la
expresi'on de $n$ como un producto de primos es 'unica, salvo orden de
los factores, o dicho de otra manera, que $n$ tiene una sola forma
estandar. Pero si consideramos algunos casos particulares sospechamos que
esto es cierto.

\begin{thm}[``El Teorema Fundamental de la aritm'etica''] La forma estandar de
  un entero positivo $n$ es 'unica; en otras palabras, se puede
  expresar $n$ como un producto de primos en solo una manera, salvo por
  el orden de los factores.
\end{thm}

El teorema 2, como su nombre implica, es muy b'asico, e indispensable
para el estudio sistem'atico de los n'umeros enteros. Al parecer, el
teorema fue anunciado explicitamente por primera vez por el
matem'atico alem'an Carl Friedrich Gauss (1777-1855) en su libro {\it
  Disquisitiones arithmeticae} (1801), aunque sin duda el resultado ya
era conocido antes de Gauss. La demostraci'on del teorema no es muy
dif'icil, pero s'i un poco larga. Por el momento la posponemos.

Ahora, debe ser obvio porque insistimos que 1 no sea primo. Si lo fuera,
tendr'iamos que corregir el Teorema 2, pues siempre podr'ia uno a\~nadir
cualquier n'umero de 1's en la forma estandar.

\bs

Damos ahora algunas ilustraciones de la utilidad de nuestro Teorema
Fundamental. 

\ms
Un entero positivo $d$ que divide a dos enteros $a$ y $b$ simult'aneamente, 
$d|a$ y $d|b$, se llama un {\em divisor com'un} de $a$ y $b$. Obviamente,
$d\leq \min\{a,b\}$ (el m'inimo entre $a$ y $b$). Denotamos el 
{\em divisor
com'un m'aximo} de $a$ y $b$ por $(a,b)$. Por ejemplo, $(4,6)=2$, y si $a>0$
entonces $(a,0)=(-a,0)=a$. 

Si $(a,b)=1$ decimos que $a$ y $b$ son {\em primos
relativos}, o {\em coprimos}. Por ejemplo, $9$ y $14$ son primos relativos.
Usando el Teorema Fundamental obtenemos una f'ormula sencilla para $(a,b)$.
\begin{thm}\label{thm:gcd}
Si 
$$a=\Pi_p p^\alpha\qquad (\alpha\geq 0)$$
y

$$b=\Pi_p p^\beta\qquad (\beta\geq 0),$$

entonces 
$$(a,b)=\Pi_p p^{\min\{\alpha,\beta\}}.$$

\end{thm}

La notaci'on $a=\Pi_p p^\alpha$ es una notaci'on breve para la
factorizaci'on de $a$ en primos, y significa que estamos considerando
un producto de t'erminos de la forma $p^\alpha$, para todo los primos
$p$, donde la potencia $\alpha$ depende de $p$. Por su puesto, los
$\alpha$'s son todos ceros excepto para un n'umero finito de primos,
as'i que el producto es realmente finito.

\ms 
El teorema es una consecuencia inmediata del Teorema
Fundamental y  dejamos la demostraci'on como un ejercicio. 

Por ejemplo, para obetener  el divisor com'un maximal de 79380 y 2142, 
calculamos primero sus formas estandar,
$$79380=2^2\cdot 3^4\cdot5\cdot 7^2, \qquad 2142=2\cdot 3^2\cdot 7\cdot
17,$$
y obtenemos inmediatamente que su divisor com'un m'aximo es 
$$2\cdot 3^2 \cdot 7=126.$$ 

\bs
El {\em m'inimo com'un m'ultiple} de dos n'umeros $a$ y $b$ es el positivo
m'inimo divisible por ambos $a$ y $b$, y est'a denotado por $\{a,b\}$.
Tenemos entonces que $a|\{a,b\}$, $b|\{a,b\}$. 
\begin{thm}
En la notaci'on del Teorema \ref{thm:gcd},
$$\{a,b\}=\Pi_p p^{\max \{\alpha,\beta\}}.$$
\end{thm}
Por ejemplo, el  m'inimo com'un m'ultiple de $79380=2^2\cdot 3^4\cdot5\cdot
7^2$ y $2142=2\cdot 3^2\cdot 7\cdot
17$ es 
$$2^2\cdot 3^4 \cdot 5\cdot7^2\cdot 17=1,349,460.$$ 

Dejamos la demostraci'on de este teorema tambi'en como un ejercicio.



\begin{thm}
$$\{a,b\}={ab \over (a,b)}.$$
\end{thm}

\dem Es una consecuencia de los dos teoremas anteriores
y la identidad obvia
$$\min\{\alpha,\beta\}+\max\{\alpha,\beta\}=\alpha+\beta.$$
\qed

\bs
Otro resultado b'asico que derivamos del Teorema Fundamental es
\begin{thm}\label{thm:euc1}
Si $p$ es un primo, y $p|ab$, entonces $p|a$ 'o $p|b$.
\end{thm}

La condici'on de ser primo es claramente esencial; por ejemplo,
$6|3\cdot 4$, pero $6$ no divide a $3$ ni a $4$.

\bs
\dem Escribimos $a$ y $b$ como productos de primos, $a=p_1p_2\ldots$,
$b=q_1q_2\ldots$, as'i que $ab=p_1p_2\ldots q_1q_2\ldots$.
Segun el Teorema Fundamental, si $p|ab$ entonces $p$
debe ser uno de los primos en la expresion de $ab$ como producto de primos;
o sea $p$ es uno de los $p_i$'s o uno los $q_j$'s. En el primer caso $p|a$,
y en el segundo caso $p|b$. \qed

Presentamos una aplicaci'on interesante de este 'ultimo teorema. Primero
una definici'on: un n'umero, no necesariamente entero, es {\em racional},
si se puede expresar como la raz'on de dos enteros $m/n$. Un n'umero no
racional se llama {\em irracional}. 

Si construimos un tri'angulo rect'angulo con dos lados de longitud 1,
la longitud $l$ del tercer lado, la {\em hipotenusa}, satisface, seg'un
el teorema de Pit'agoras,
$$l^2=2,$$
o sea $l=\sqrt{2}$.  

\vspace{5cm}

\begin{thm}
$\sqrt{2}$  es irracional. 
\end{thm}
\bs
\dem Si lo fuera, entonces podr'iamos escribir $\sqrt{2}=m/n$, con $m$ y $n$
enteros positivos, y suponer tambi'en que son primos relativos, $(m,n)=1$. 
As'i que $2n^2=m^2$ y $2|m^2$. Como 2 es un
primo, el
teorema anterior implica que $2|m$, as'i que $m=2k$, donde $k$ es un entero
positivo. Obtenemos entonces 
\begin{eqnarray*}
2n^2=(2k)^2=4k^2&\Longrightarrow& n^2=2k^2.
\end{eqnarray*}
Ahora tenemos $2|n^2\Longrightarrow 2|n$, as'i que 2 es un divisor com'un de $m$
y $n$, contradiciendo la suposici'on original. \qed

\bs

\subsection{La sucesi'on de los primos}

Los primeros primos son

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,\ldots$$
Es f'acil construir una tabla de primos, hasta un l'imite $N$ no muy
grande, por una t'ecnica conocida como la "criba de Eratostenes". Ya
hemos visto que si $n\leq N$, y $n$ no es primo, o sea $n$ es
compuesto, entonces $n$ debe ser divisible por un primo no m'as grande
que $\sqrt{N}$ . Ahora escribimos una lista de los n'umeros
$$2, 3, 4, 5, \ldots, N$$
y eliminamos sucesivamente

\begin{quote}
(i) $4, 6, 8, 10, \ldots,\,\,\,\,\,\,\,\,\,$ 
o sea $2^2$ y luego cada n'umero par,
\end{quote}\begin{quote}
(ii) $9, 15, 21, 27, \ldots,\,\,\,\,\,\,\,\,\,$ o sea $3^2$,
 y luego todos
los m'ultiplos de 3 no eliminados todav'ia,
\end{quote}\begin{quote}
(iii) $25, 35, 55, 65, \ldots,\,\,\,\,\,\,\,\,\,$ o sea $5^2$, el cuadrado del
siguiente n'umero que queda, y luego todos los m'ultiplos de 5 no eliminados
todavia,...
\end{quote}
As'i continuamos el proceso hasta que el siguiente n'umero que queda,
despues del 'ultimo n'umero cuyos m'ultiplos fueron eliminados, es mayor que
$\sqrt{N}$. Los n'umeros que quedaron, los que no fueron eliminados por la
criba, son todos los primos entre $1$ y $N$. Pr'acticamente todas las tablas
de primos est'an construidas por este m'etodo.  

\bs Las tablas indican que la sucesi'on de los primos es infinita. El
n'umero total de primos menores que 10 millones es 664,579, y el
n'umero de primos que hay
entre 9,900,000 y 10,000,000 es 6,134. El n'umero total de primos menores
que 1,000,000,000 es 50,847,478. Se conocen tambi'en unos primos muy grandes,
la mayor'ia de la forma $2^m -1$. Los m'as grandes conocidos tienen miles
de d'igitos y se siguen encontrando m'as y m'as grandes todo el tiempo.

Todo esto sugiere el siguiente teorema de Euclides.

\begin{thm}\label{thm:inf}
El n'umero de primos es infinito.
\end{thm}


\dem
Existen varias demostraciones del teorema. Presentamos la demostraci'on
original de Euclides.

Sean $2, 3, 5, \ldots, p $ todos los primos entre 2 y un primo $p$, y vamos
a demostrar la existencia de un primo nuevo, mayor que $p$. Sea

$$N = (2 \cdot 3 \cdot 5 \cdot \ldots \cdot p) + 1.$$
Si $N$ no es
primo es divisible por un primo. Pero $N$ no es divisible por ninguno
de los primos $2, 3, 5, \ldots, p$ (dividiendo a $N$ por cualquiera de
estos n'umeros da residuo 1), as'i que si $N$ no es primo es divisible
por un primo entre $p$ y $N$. De cualquier modo obtenemos un primo
mayor que $p$. \qed

Por ejemplo, empezando con el primo 2, obtenemos por el m'etodo de esta
demostraci'on una suceci'on de primos $$2, 3,
7, 43, 1907, \ldots$$ 
Este m'etodo no es muy efectivo -- hay maneras mucho
mejores de encontrar primos -- pero tiene la virtud de convertir a la
demostraci'on de Euclides en una demostraci'on {\em constructiva}: el
argumento de Euclides no solo muestra que el n'umero de primos es
infinito, sino tambi'en nos construye, paso por paso, una
sucesi'on infinita de primos. 

\subsection{Algunas preguntas acerca de los primos}

La distribuci'on de los primos entre los enteros positivos, en
``promedio'', es muy regular; su densidad muestra una disminuci'on continua
pero lenta. El n'umero de primos en los primeros 5 ``bloques''
de 1000 es
$$168,135,127,120,119,
$$
y los de los 'ultimos 5 bloques menores que 10,000,000 son
$$62,58,67,64,53.
$$
Estos 'ultimos 53 primos estan divididos en grupos de 
$$5,4,7,4,6,3,6,4,5,9
$$
entre los 10 ``bloquecitos'' de 100 del 'ultimo millar.

\bs
Por otro lado, la distribuci'on {\em detallada} de los primos es
extremadamente irregular. En  primer lugar, las tablas muestran bloques grandes de n'umeros
compuestos. Despu'es del primo 370,261 hay un bloque de 111 n'umeros
compuestos. Es bastante f'acil ver que estos bloques grandes de compuestos 
deben ocurrir: tomamos todos los primos 
$$2,3,5, \ldots ,p$$
hasta un primo $p$. Si definimos 
$$N=2\cdot 3 \cdot 5 \cdot\ldots\cdot p,$$
tenemos que todos los $p-1$ n'umeros 
$$N+2,N+3,N+4,\ldots,N+p$$
son compuestos. Esto es cierto porque si tomamos uno de estos n'umeros,
diagamos $N+m$, $2\leq m\leq p$, $m$ es divisible por uno de los primos,
digamos $q$,  $2\leq q\leq p$, y este $q$ divide tambi'en a $N$, as'i que 
$q$ divide a $N+m$. 
Seg'un el Teorema \ref{thm:inf} hay primos arbitrariamente grandes, as'i que
obtenemos 

\begin{thm}
Existen bloques arbitrariamente largos de compuestos consecutivos. 
\end{thm}

Examinamos ahora otro fen'omeno, la ocurrencia de bloques de primos.
Las tablas de primos indican la persistencia indefinida de {\em pares
  primos}, como $3,5$ o $101,103$, cuya diferencia es 2. Hay 1224
tales pares $(p,p+2)$ antes de $100,000$, y 8169 antes de 1,000,000.
Esto sugiere la
\begin{quote}
{\em conjetura: hay un n'umero infinito de pares primos $(p,p+2)$.}
\end{quote}
De hecho, es razonable conjeturar m'as. Si tomamos los tres n'umeros
$p,p+2,p+4$, los tres no pueden ser primos, porque uno de ellos es divisible
entre 3 (ejercicio), pero no hay una raz'on obvia para no tener ternas de
primos de la forma $p,p+2,p+6$, o $p,p+4,p+6$, y la evidencia de las tablas
sugiere que estas ternas tambi'en persisten indefinitivamente. Llegamos
entonces a otra 
\begin{quote}
{\em conjetura: hay un n'umero infinito de ternas de primos de la forma 
$(p,p+2,p+6)$ y 
$(p,p+4,p+6).$}
\end{quote}
Estas conjeturas, y otras similares, acerca de bloques m'as grandes de
primos, no tienen hasta la fecha demostraciones ni contraejemplos.

\bs ?`Que otras preguntas naturales se puede hacer acerca de una sucesi'on
de n'umeros como los primos? Aqu'i consideramos algunas.
\begin{quote}
  {\em (i) ?`Existe una f'ormula sencilla general que produce la
    sucesi'on de todos los primos?}
\end{quote}

\n No se conoce una f'ormula tal, y es probable que no exista, porque
la distribuci'on de los primos es distinta de la que esperar'iamos de
la existencia de esa f'ormula. A'un as'i, no podemos excluir la
posibilidad de que tal f'ormula exista.

\bs
Una pregunta similar, con comentarios semajantes, es
\begin{quote}
{\em (ii)
?`existe una f'ormula general que produce a partir de un primo, el
primo que le
sigue (o sea una f'ormula tipo $p_{n+1}=p_n^2+1$)?}
\end{quote}

\bs
O una pregunta a'un m'as modesta como
\begin{quote}
{\em (iii)
?`existe una regla sencilla que produce, dado un primo $p$, otro primo
m'as grande?}
\end{quote}

\n Como hemos visto antes, la demostraci'on del Teorema \ref{thm:inf}
nos sugiere una regla de este tipo, pero esta regla est'a muy lejos de ser
sencilla o efectiva, si la examinamos de cerca. El 'unico intento
razonable en la direcci'on de estas preguntas fue una conjetura del
matem'atico franc'es Pierre de Fermat (1601-1665).  Los llamados
``n'umeros de Fermat'' son los n'umeros definidos por la f'ormula
$$F_n=2^{2^n}+1,$$
as'i que
$$F_0=3,\,\,\,\, F_1=5,\,\,\,\, F_2=17,\,\,\,\, F_3=257,\,\,\,\,
F_4=65,537.$$ Estos 5 n'umeros son primos y Fermat conjetur'o que todos son
primos.  Desafortunadamente, no es cierto. En 1732, el matem\'atico suizo
Leonhard Euler (1707-1783) descubri'o que 641 es un divisor de
$F_5=2^{32}+1$, as'i que no es primo. Hoy en d'ia conocemos muchos otros
n'umeros de Fermat compuestos y de hecho no se ha encontrado ning'un otro
n'umero de Fermat primo, m'as que los 5 mencionados arriba, as'i que m'as
razonable ser'a conjeturar que el n'umero de primos entre los $F_n$ es {\em
finito}. Pero los n'umeros de Fermat tienen mucho inter'es en la teor'ia de
n'umeros; por ejemplo, Gauss demostr'o que si $F_n$ es un primo $p$,
entonces es posible construir con comp'as y regla un pol'igono regular con
$p$ lados. La construcci'on para el caso de $p=3$ es muy f'acil, la de
$p=5$ un poco menos f'acil pero todav'ia ``cl'asica'' (conocida por los griegos
antiguos),
pero la construcci'on para el caso de $p=17$ ya es muy dif'icil y se
necesitaba de alguien como Gauss para encontrarla. 

\bs

Otra pregunta interesante es 
\begin{quote}
{\em (iv) ?`cuantos primos hay menores que un n'umero dado $x$?}
\end{quote}

\n Esta pregunta es mucho m'as productiva, pero necesita una
interpretaci'on cuidadosa. Denotamos por $\pi(x)$ el n'umero de primos
menores o iguales a $x$, as'i que $\pi(1)=0$, $\pi(2)=1$, $\pi(20)=8$.
De hecho, si tuvi'esemos una f'ormula exacta para $\pi(x)$, podr'iamos
usarla para producir una lista de todos los n'umeros primos; si
denotamos por $p_n$ el $n$-'esimo primo ($p_1=2$, $p_2=3$, $p_3=5,
\ldots$), es claro que $\pi(p_n)=n$, as'i que la f'ormula deseada para
$p_n$ se obtiene al invertir (o resolver) la 'ultima ecuaci'on,
expresando $p_n$ en t'erminos de $n$. En consecuencia, pedir una
f'ormula sencilla para $\pi(x)$ es pr'acticamente repetir la pregunta
(i).  Tenemos entonces que reinterpretar la pregunta de otra manera, y
preguntar
\begin{quote}
{\em `` ?`Cuantos primos {\em aproximadamente} hay\ldots?''
?`ser'a cierto que la ``mayor'ia'' de los n'umeros son primos, o solo
una peque\~na fracci'on? ?`existe una  expresi'on  sencilla, $f(x)$, que sea una
``buena aproximaci'on'' a $\pi(x)$? }
\end{quote}
La pregunta, en esta forma modificada, fue respondida por varios
matem'aticos,
empezando por el matem'atico ruso Pafnuty Lvovich Chebyshev (1821-1894)
alrededor de 1850. 
\ms
Para anunciar la respuesta tenemos que usar la funci'on logar'itmica $\log x$. 


\begin{thm}[``El teorema de los n'umeros primos'']\label{thm:pnt}

Una ``buena aproximaci'on'', para $x$ grande, de la funci'on $\pi(x)$ es
$$\pi(x)\sim{x\over {\log x}};$$ 
y m'as precisamente, si llamamos $f(x)$ al lado derecho de esta
aproximaci'on, entonces tenemos que la raz'on $\pi(x)/f(x)$ tiende a 1
cuando $x$ tiende a infinito.
\end{thm}

Para tener idea de lo que dice el teorema notamos 
que la funci'on $x/\log x$ es una funci'on que tiende a infinito m'as lento 
que $x$, pero m'as r'apido que cualquier ra'iz $\sqrt[a](x)$, $a>1$, 
y que es la funci'on m'as sencilla con esta propiedad. 

\ms
Es interesante comparar el Teorema \ref{thm:pnt} con la evidencia de las
tablas. Los valores de $\pi(x)$ para $x=10^3$, $x=10^6$, $x=10^9$,
son
$$168,\,\,\,\,78,\!498, \,\,\,\,50,\!847,\!478;
$$
mientras los valores de la aproximaci'on $x/\log x$, al entero m'as
cercano, son
$$ 145,\,\,\,\,72,\!382,\,\,\,\,48,\!254,\!942.$$
Las razones de de estos n'umeros son
$$1.159\ldots,\,\,\,\, 1.084\ldots,\,\,\,\, 1.053\ldots,$$
e indica una convergencia, bastante lenta, a 1.
\bs\bs

Existen muchas m'as conjeturas y preguntas no contestadas acerca de los
primos. Aqu'i est'an otras.
\begin{itemize}
\item ?`Hay un n'umero infinito de primos de la forma $n^2+1$ (como
$5,17,37,\ldots$)?

\item ?`Es cierto que cada n'umero par, mayor que 4, es la suma de dos
  primos impares (como $ 6=3+3$ , $ 8=5+3$ , $ 78=59+19,\ldots$)? Esto
  se conoce como {\em la conjetura de Goldbach}.

\item ?`Es cierto que cada n'umero impar, mayor que 7, se puede expresar
como la suma de 3 primos impares (como $23=5+5+13,\ldots$)?
\end{itemize}


\subsection{La demostraci'on del Teorema Fundamental de la Aritm'etica}

Si el Teorema no fuera cierto, existir'an n'umeros que son
productos de primos de  m'as de una manera. Llamemos temporalmente a 
tales n'umeros {\em raros}, y sea $n$ el m'inimo n'umero raro.
Tenemos entonces dos factorizaciones distintas de $n$ en primos, 
$$n=p_1p_2p_3\ldots=q_1q_2q_3\ldots,$$ con $p_1\leq p_2\leq\ldots$,
$q_1\leq q_2\leq\ldots$. De hecho, ninguno de los $p$'s puede ser igual a
ninguno de los $q$'s, pues si $P$ es un primo que aparece en las dos
factorizaciones entonces $n/P$ ser'a un n'umero raro menor que $n$,
contradiciendo el hecho de que $n$ fue escogido como el raro {\em m'inimo}.

Ahora, como $p_1$ es el primo m'inimo en la primera factorizaci'on, tenemos
que $p_1^2\leq n$ (ver la observaci'on al final de la secci'on
\ref{sec:primos}), y an'alogamente $q_1^2\leq n$. Adem'as, $p_1\neq q_1$,
as'i
que 
$p_1 q_1<n$, por lo que $N=n-p_1q_1$ satisface $0<N<n$, as'i que $N$ no es
raro. 

Como $p_1|n$ y $q_1|n$, tenemos tambi'en que  $p_1|N$ y $q_1|N$,
as'i que ambos $p_1$ y $q_1$ aparecen en la factorizaci'on 'unica de 
$N$, por lo que $p_1q_1|N$. De $n=N+p_1q_1$ tenemos que $p_1q_1|n$, as'i
que $q_1|(n/p_1)$. Pero $n/p_1<n$, as'i que su factorizaci'on
$p_2p_3\ldots$ es 'unica y $q_1$ no aparece como ninguno de los factores,
contradiciendo al hecho de que $q_1|(n/p_1)$.\qed





\newpage




\section{Congruencias}
\subsection{Definici'on de congruencias}

Si un entero positivo $m$ divide a la diferencia $a-b$ de dos n'umeros,
decimos que ``$a$ es {\em congruente} a $b$ modulo $m$'', y lo escribimos 
$$a\equiv b \mod m.$$ 

Por ejemplo, 
$$5\equiv 9 \mod 4,\,\,\,\,\, -8\equiv 1 \mod 9,\,\,\,\,\,
1997\equiv 7 \mod {10}.$$




Esta definici'on no introduce nada nuevo, porque
``$a\equiv b \mod m$'' y ``$m|(a-b)$'' tienen exactamente el mismo
significado; pero cada notaci'on tiene su ventaja.

%Si $a$ no es congruente a $b$ modulo $m$ escribimos $a\not{\equiv} b \mod m$. 

Notamos que en esta definici'on $a$ y $b$ no tienen que ser n'umeros
positivos, y de hecho ni enteros, aunque nosotros no lo vamos a usar m'as
que para n'umeros enteros. 



Si $x\equiv a \mod m$ decimos tambien que ``$a$ es un {\em residuo} de 
$x$''$\mod m$. Si $0\leq a\leq\, m-1$, llamamos a $a$ el residuo {\em m'inimo}
(no-negativo) de $x$, m'odulo $m$. As'i que dos n'umeros $a$ y $b$ son
congruentes$\mod m$ si tienen los mismos residuos$\mod m$.

El residuo m'inimo $\mod m$ de un entero no-negativo $x$ se puede determinar
as'i: se divide $x$ entre $m$, y lo que {\em sobra} es el residuo m'inimo. 
Por ejemplo, el residuo m'inimo de $100 \mod 7$ es 2, porque al dividir 100
entre 7 el resultado es 14 (esto no importa) y sobran 2 (esto s'i importa). 
El residuo m'inimo  de $-100 \mod 7$ es $7-2=5$. (?`Por qu'e?)

Una {\em clase de residuos}$\mod m$ es la clase de todos los n'umeros
congruentes a un n'umero dado$\mod m$. Por ejemplo, la clase de residuos 
de $3\mod 5$ consiste de los n'umeros
$$\ldots -12,-7,-2,\,\,3,\,\,8,\,\,13,\,\,18,\ldots,$$
y la clase de residuos de $0\mod m$ consiste de todos los m'ultiplos de $m$
$$\ldots, -3m, -2m, -m, \,\,0, \,\,m, \,\,2m, \,\,3m,\ldots .$$

Cada miembro de una clase de residuos$\mod m$ se llama un {\em
representante} de la clase. Obviamente hay $m$ clases de residuos$\mod m$,
representados por los residuos m'inimos
$$0,1,2,3,\ldots, m-1.$$

\bs

Las congruencias son de gran importancia pr'actica en la vida cotidiana. 
Por ejemplo, ``hoy me levant'e a las 6 de la ma\~nana'' es una afirmaci'on
acerca del n'umero de horas que han pasado, m'odulo 24, desde alg'un tiempo
fijo. La clase de residuos de este n'umero de horas, o sea la hora del
d'ia, es normalmente mucho m'as importante que el n'umero real de horas que han pasado
desde, digamos, la creaci'on del universo. Calendarios y horarios de
cami'on o clases, son tablas de congruencias, m'odulo 7, 365 y 24. 

\subsection{Propiedades elementales de congruencias}

Es f'acil demostrar que congruencias m'odulo un entero positivo fijo $m$  satisfacen
las siguientes propiedades:
$$\begin{array}{llcl}
(i)& a\equiv b&\Longrightarrow &b\equiv a,\\
 (ii)& a\equiv b, b\equiv c&\Longrightarrow & a\equiv c,\\
(iii)& a\equiv b&\Longrightarrow& ka \equiv kb,\mbox{ para cualquier $k$,}\\
(iv)& a\equiv a\p ,b\equiv b\p &\Longrightarrow& a+b\equiv a\p +
 b\p\quad\mbox{y}\quad ab\equiv a\p b\p .
\end{array}
$$
\medskip\n Demostramos por ejemplo (iii). Si $a\equiv b$ entonces $m|(a-b)$
as'i que existe un $l$ tal que $a-b=ml$. As'i que $k(a-b)=ka-kb=mlk$, as'i
que $m|ka-kb$, y obtenemos que $ka\equiv kb \mod m$. Dejamos la
demostraci'on de las otras propiedades como un ejercicio.

\bs
Las propiedades (i) -- (iv) son muy parecidas a las propiedades
conocidas de las
ecuaciones del 'algebra ordinaria, pero de pronto encontramos una
diferencia importante. En 'algebra, tenemos tambi'en un converso a
(iii). Es decir,
\begin{eqnarray}\label{eqn:alg}
ka=kb&\Longrightarrow &a=b,\quad \mbox{si }k\neq 0.
\end{eqnarray}
Pero con congruencias no es cierto. Por ejemplo 
\begin{equation}\label{eqn:ej}
4\cdot 5\equiv 4\cdot 3  \,\,\mbox{y}\,\, 4\not\equiv 0 \mod 8,
\end{equation}
pero
$$5\not\equiv 3\mod 8.$$

Para entender lo que s'i es cierto en esta direcci'on, revisamos primero la
justificaci'on usual de (\ref{eqn:alg}).

En 'algebra ordinaria de n'umeros, si $k\ne 0$, entoces $k$ tiene un {\em
inverso},
o sea,  existe un n'umero, denotado por $1/k$, tal que $k\cdot (1/k)=1$.
Multiplicando los dos lados de la ecuaci'on $ka=kb$ por $1/k$ (usando una regla
tipo (iii)), obtenemos $(1/k)\cdot k \cdot a= (1/k)\cdot k \cdot b$, y por la
propiedad del inverso,  $k\cdot (1/k)=1$, obtenemos $a=b$. De este
argumento, aplicado a congruencias, obtenemos entonces el siguiente
converso a 
(iii):
\begin{thm}\label{thm:inv1}
Si $k$ es invertible$\mod m$, entonces $ka\equiv kb\mod m$ implica
$a\equiv b$.
\end{thm}

Ahora podemos entender mejor el problema con el ejemplo de
(\ref{eqn:ej}). 
El problema
surgi'o del
hecho que 4 no tiene inverso modulo 8; o sea, no existe un n'umero $x$ que
satisface $4x\equiv 1 \mod 8$. 

La siguiente pregunta, entonces, es fundamental para trabajar  con
congruencias:
\begin{quote}
{\em ?`Que residuos, modulo $m$, tienen inverso?} 
\end{quote}
o dicho de
otra manera, ?`para cu'ales $k$ la congruencia $kx\equiv 1 \mod m$ tiene
una soluci'on $x$?

La respuesta esta dada por 
\begin{thm}\label{thm:inv2} Los residuos invertibles$\mod m$ son los
residuos que son primos relativos a $m$; o sea los residuos que no tienen un
divisor com'un con $m$ mayor que 1. 
\end{thm}

Por ejemplo, segun el teorema, de los 8 residuos m'inimos $\mod 8$,
hay 4 que son invertibles (los impares), y 4 que no son invertibles (los
pares). En particular, 4 no es invertible, como ya  vimos. 

\bs \dem Suponemos que $k$ es invertible$\mod m$ y $d$ es un divisor com'un
de $m$ y $k$. Entonces $k=da$ y $m=db$ para algunos enteros $a$ y $b$, donde
$1\leq b \leq m$. Ahora $kb=dab=ma\equiv 0\mod m$, as'i que si $k$ es
invertible, obtenemos, segun el Teorema \ref{thm:inv1}, que $b\equiv 0$; pero
esto es posible, por la condici'on $1\leq b \leq m$, solamente si $b=m$,
as'i que $d=1$. 

Para el converso, suponemos que $k$ y $m$ no tienen un divisor com'un
mayor que 1, y
consideramos los   $m-1$ n'umeros
$$k, 2k,3k, \ldots,(m-1)k.$$ 

Demostramos que alguno de estos n\'umeros es congruente a $1\mod m$. Para
eso, es  suficiente ver que estos $m-1$ n'umeros representan
$m-1$ clases de congruencias {\em distintas}. Si dos de estos n'umeros son
congruentes, digamos $ka\equiv kb \mod m$, $1\leq a<b\leq m-1$, tenemos que
$m$ divide a la diferencia $kb-ka=k(b-a)$. Ahora como $m$ no tiene factor
com'un con $k$, $m|k(b-a)\Longrightarrow m|(b-a)$ (usando el Teorema
Fundamental). Pero esto es imposible porque $1\leq b-a\leq m-1$. \qed

Un caso particular, pero importante, del 'ultimo teorema es
\begin{thm}\label{thm:inv3} Si $p$ es un primo, entonces $a$ es 
invertible$\mod p$ para todo $a\not\equiv 0$. 
\end{thm}
Por este Teorema, y la discuci'on al principio de esta secci'on,
tenemos que la 'algebra m'odulo un primo $p$ se parece, en sus aspectos
formal,
a la 'algebra ordinaria. En la siguiente  secci'on ilustramos el uso 
de este ``principio'', en la demostraci'on de un teorema de la m'as famosos de la teor'ia de n'umeros.
\subsection{El ``peque\~no'' teorema de Fermat}
\begin{thm}
Si $p$ es un primo, entonces $a^p\equiv a\mod p$, para todo entero $a$.
\end{thm}

Este teorema fue anunciado por Fermat en 1640 y demostrado por primera
vez por Euler en 1736. El ``gran'' teorema de Fermat (o ``'ultimo'' teorema) afirma que la
ecuaci'on $x^n+y^n=z^n$
 no tiene soluciones enteras para $n>2$. Su demostraci'on se llev'o acabo,
despues de grandes esfuerzos de muchos matem'aticos, por el matem'atico
ingl'es  Andrew Wiles (1954-- ) hace 3 a\~nos. 

\bs
\dem Para $a\equiv 0\mod p$ el teorema es obvio. Suponemos entonces que
$a\not\equiv 0$. En este caso, usando que $p$ es primo, sabemos que $a$ es invertible $\mod
p$, as'i que los residuos m'inimos de sus $p-1$ m'ultiplos
$$a, 2a, 3a, \ldots,(p-1)a$$ son todos distintos, y distintos de cero, as'i
que deben constituir a {\em todos} los $p-1$ residuos m'inimos
$1,2,\ldots,p-1$. As'i obtenemos
$$a\cdot 2a \cdot\ldots \cdot(p-1)a\equiv 1\cdot 2\cdot\ldots  \cdot (p-1)\mod p,$$
as'i que
$$a^{p-1}\cdot 1\cdot 2\cdot\ldots \cdot (p-1)\equiv 1\cdot 2\cdot\ldots \cdot (p-1)\mod p;$$
pero $1\cdot 2\cdot\ldots \cdot (p-1)\not\equiv 0\mod p$, as'i que 
$$a^{p-1}\equiv 1\mod p.
$$
\qed

El principio combinatorio usado en la 'ultima demostraci'on se llama
el ``principio de la palomera'': si $N$ palomas se instalan en una palomera
con $N$ sitios, y en cada sitio no cabe m'as que una paloma, entonces todos
los sitios tienen que estar ocupados (a veces se afirma esto en una forma
equivalente: si $N$ palomas se instalan en una palomera con $n$ sitios, y
$n<N$, entonces hay por lo menos un sitio ocupado por m'as de una paloma). 
Este principio, tan  ``obvio'' al  parecer, es de gran utilidad en 
nuestra teor'ia. En la 'ultima demostraci'on las ``palomas'' eran
los n'umeros $a, 2a, 3a, \ldots,(p-1)a$ y la ``palomera'' el sistema de
residuos m'inimos distintos de cero $\mod p$. Otro lugar en donde hemos usado este principio 
fue en la demostraci'on  del Teorema \ref{thm:inv2}.



%\section{Criptolog'ia}
\end{document}
