


\chapter{Los Naturales y los Enteros.}


\hrule
\vskip0.5cm
%-----------------------------------------------------------------
\noindent{\sffamily\bfseries Objetivos del capítulo} $\,$
\begin{itemize} \footnotesize
 \item Introducir los Números Naturales y los Números Enteros estudiando sus propiedades respecto de la suma, del producto y del orden. Especialmente el principio de inducción e inducción generalizado.
 \item Estudio y aplicación del algoritmo de la división. Existencia y unicidad del $\mcd$ y $\MCM$. Teorema de Bezout y factorización única en $\ZZ$.
 \item Estudio de los anillos de congruencias módulo $n$.
\end{itemize}
\vskip0.25cm
%-----------------------------------------------------------------
\hrule
\vskip0.3cm
\[\,\]




\section{Los Números Naturales y los Números enteros}

\subsection{Los Números Naturales}

\hypertarget{Apeano}{ } \label{Apeano}
\begin{defi}\rm  Los Números Naturales\index{Número! Natural} aparecen por la necesidad que tiene el hombre (primitivo) tanto de contar como de ordenar una \nomenclature{$\mathbb{N}$}{El conjunto de los números naturales}
cierta cantidad de objetos.
$$\mathbb{N}:=\{1,2,3,\dots\}$$
En los números naturales podemos sumar y multiplicar, pero no podemos, en la mayoría de los casos,  ni restar ni
dividir. Históricamente el cero no es considerado un número natural. Matemáticamente los naturales se definen a partir
 de 5 axiomas, los \textbf{Axiomas de Peano}: \index{Axiomas de Peano}
\begin{enumerate}
\item[1).] El $1$ es un número natural.
\item[2).] Para cada número natural $n$ existe otro número natural $n'$.
\item[3).] Si $n\in \mathbb{N}$, $n'\ne 1$.
\item[4).] Si $n,m\in \mathbb{N}$ y $n'=m'$, entonces $n=m$.
\item[5).] \textbf{Principio de inducción matemática}: Si $S$ es un subconjunto de $\mathbb{N}$ tal que:\index{Principio de Inducción}
\begin{enumerate}
\item $1\in S$ y
\item si $n\in S$, entonces $n'\in S$.
Se tiene que  $S={\mathbb N}$
\end{enumerate}
\end{enumerate}
\textbf{Nota:} Observar que, en la representación usual de los Naturales,  para cada $n\in {\mathbb N}$, $n'$ no es más que $n+1$.
\end{defi}

\retodo{Primera vez que se usa el principio de inducción}

\begin{ejem}\rm
Demuestra que para todo número natural $n$ se verifica que $$1+3+5+\dots+(2n-1)=n^2.$$
\end{ejem}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Debes de poder comprender este ejemplo sin problemas.} \textbf{Demo:} Consideremos el conjunto $S$ de los números naturales para los que la igualdad es cierta. Es
claro que $1\in S$, ya que $1=1^2$. Supongamos que la igualdad es cierta para $n$, es decir que $n\in S$ y veamos que
es cierta para $n+1$. Tenemos, por hipótesis,  que
$$1+3+5+\dots+(2n-1)=n^2$$ Observar que el siguiente impar de $2n-1$ es $2n+1$, por tanto, si sumamos en ambos lados de la igualdad
$2n+1$ obtenemos
$$1+3+5+\dots+(2n-1)+(2n+1)=n^2+2n+1=(n+1)^2$$ es decir, que $n+1\in S$. Por tanto aplicando el principio
de inducción matemática, $S=\mathbb{N}$, lo que demuestra que la igualdad es cierta para todo número natural.\EndProof

\hypertarget{PindGen}{ }\label{PindGen}
\begin{defi}[Principio de inducción generalizado:] \index{Principio de Inducción!Generalizado}\rm Sea $S$ un subconjunto de $\mathbb N$ tal que:
\begin{enumerate}
\item[$\bullet$] $1\in S$ y
\item[$\bullet$] si $1,2,\dots,n\in S$, entonces $n+1\in S$.
\end{enumerate}
 Entonces $S={\mathbb N}$
\end{defi}

En este punto nos separamos de la teoría axiomática de los Números Naturales (tanto la suma, el producto como el buen
orden de $\mathbb{N}$ se pueden definir usando una pequeña cantidad de axiomas; a partir de ellos se pueden demostrar
todas las propiedades que vamos a ver a continuación). Si quieres ver la teoría completa, la puedes encontrar en
\cite{AYJA}.



\hypertarget{Pnat}{ }\label{Pnat}
\begin{defi}[Propiedades de los Números Naturales]\rm\par \

\begin{enumerate}
 \item Propiedades respecto de la suma:
        \begin{enumerate}

        \item Propiedad asociativa: \index{Propiedad!Asociativa}$(x+y)+z=x+(y+z)\quad \forall\ x,y,z\in \mathbb{N}$.

        \item Existencia de elemento neutro: \index{Propiedad!Elemento Neutro}$x+0=0+x=x\quad \forall\ x\in \mathbb{N}$.\quad (si $0\in \NN$)

        \item Propiedad conmutativa: \index{Propiedad!Conmutativa} $x+y=y+x\quad \forall\ x,y\in \mathbb{N}$.
\end{enumerate}

\item Propiedades respecto del producto:
\begin{enumerate}
        \item Propiedad asociativa:\index{Propiedad!Asociativa} $(x\,y)\,z=x\,(y\,z)\quad \forall\ x,y,z\in \mathbb{N}$.

        \item Existencia de elemento neutro:\index{Propiedad!Elemento Neutro} $x\,1=1\,x=x\quad \forall\ x\in \mathbb{N}$.

        \item Propiedad conmutativa:\index{Propiedad!Conmutativa} $x\,y=y\,x\quad \forall\ x,y\in \mathbb{N}$.

        \item Ley de simplificación: \index{Ley!de Simplificación}  $\forall\ x,y,z\in \mathbb{N}$, con $x\ne0$,  si $x\,y=x\,z$, entonces $y=z$.
\end{enumerate}
\item Propiedades respecto del orden: \textbf{Los Naturales poseen un buen orden}, es decir, cualquier subconjunto no vacío de $\mathbb N$ posee elemento mínimo. \index{Ley!del Buen Orden}




\item Propiedades conjuntas: para todo $x,y,z\in \mathbb{N}$
\begin{enumerate}

        \item Propiedad distributiva:\index{Propiedad!Distributiva} $(x+y)\,z=x\,z+y\,z$.
        \item Si $x\le y$, entonces $x+z\le y+z$.
        \item Si $x\le y$, entonces $x z\le y z$.
\end{enumerate}
\end{enumerate}
\end{defi}

\noindent \textbf{Nota:} Dado $(X,\le)$ cualquier conjunto ordenado y dados $x,y\in X$ denotamos por:
\begin{enumerate}
  \item[$\bullet$] $x<y$, \nomenclature{$x<y$}{$x$ menor estricto que $y$}que se leerá $x$ menor estricto que $y$, si $x\le y$ con $x\ne y$.
  \item[$\bullet$] $x\ge y$, \nomenclature{$x\ge y$}{$x$ mayor o igual que $y$}que se leerá $x$ mayor o igual que $y$, si $y\le x$.
  \item[$\bullet$] $x>y$, \nomenclature{$x>y$}{$x$ mayor estricto que $y$}que se leerá $x$ mayor estricto que $y$, si $y\le x$ con $y\ne x$.
\end{enumerate}

En particular, para $(\NN,\le)$ tenemos que, $1\le x$ para todo $x\in \NN$, con lo que $1<x$ siempre que $1\ne x$.

\hypertarget{Enteros}{ }
\subsection{Los Números Enteros}\label{Enteros}

\hypertarget{Dent}{ }\label{Dent}
\begin{defi} \rm
 Los Números Enteros: \index{Número! Entero}aparecen simetrizando  el conjunto de números na\-tu\-rales, y añadiéndoles el cero. Los denotaremos por $\mathbb Z$. \nomenclature{$\mathbb{Z}$}{Los Números Enteros}
Con este nuevo conjunto de números  obtenemos la mejoría de que, ahora sí, la resta de dos números enteros es un número
entero.
$${\mathbb Z}:=\{\dots, -3,-2,-1,0,1,2,3,\dots\}$$
\end{defi}


\begin{defi}[Propiedades de los Números Enteros]\label{propi}\rm\par\

\begin{enumerate}
 \item Propiedades respecto de la suma:
        \begin{enumerate}

        \item Propiedad asociativa: \index{Propiedad!Asociativa}$(x+y)+z=x+(y+z)\quad \forall\ x,y,z\in \mathbb{Z}$.

        \item Existencia de elemento neutro: \index{Propiedad!Elemento Neutro}$x+0=0+x=x\quad \forall\ x\in \mathbb{Z}$.

        \item Existencia de elemento opuesto: \index{Propiedad!Elemento Opuesto}para todo $x\in \mathbb{Z}$ existe $-x\in \mathbb{Z}$ tal que $$x+(-x)=(-x)+x=0.$$

        \item Propiedad conmutativa: \index{Propiedad!Conmutativa}$x+y=y+x\quad \forall\ x,y\in \mathbb{Z}$.
\end{enumerate}

\item Propiedades respecto del producto:
\begin{enumerate}
        \item Propiedad asociativa: \index{Propiedad!Asociativa}$(x\,y)\,z=x\,(y\,z)\quad \forall\ x,y,z\in \mathbb{Z}$.

        \item Existencia de elemento neutro: \index{Propiedad!Elemento Neutro}$x\,1=1\,x=x\quad \forall\ x\in \mathbb{Z}$.

        \item Propiedad conmutativa: \index{Propiedad!Conmutativa}$x\,y=y\,x\quad \forall\ x,y\in \mathbb{Z}$.

         \item Ley de simplificación:\index{Ley!de Simplificación} $\forall\ x,y,z\in \mathbb{Z}$, con $x\ne0$, si $x\,y=x\,z$, entonces $y=z$.
\end{enumerate}


\item Propiedades conjuntas:
\begin{enumerate}

        \item Propiedad distributiva: \index{Propiedad!Distributiva}$(x+y)\,z=x\,z+y\,z\quad \forall\ x,y,z\in \mathbb{Z}$.
\end{enumerate}


\item Propiedades respecto del orden: para todo $x,y,z\in \mathbb{Z}$
\begin{enumerate}
\item Si $x\le y$, entonces $x+z\le y+z$.
\item Si $x\le y$ y $0\le z$, entonces $x\,z\le y\,z$.
\item Si $x\le y$, y $z\le 0$, entonces $y\,z\le x\,z$.
\end{enumerate}
\end{enumerate}
\end{defi}

\noindent \textbf{Nota:} Observar que normalmente los elementos de $\mathbb Z$ no poseen  inverso.


\begin{defi}\rm
Se define el \textbf{valor absoluto}\index{Valor Absoluto} de un número entero $x\in \mathbb{Z}$ y se representa por
$\vert x\vert$ como: \nomenclature{$\vert n\vert$}{Valor absoluto de $n\in \ZZ$}

$$\vert x\vert:=\begin{cases} \ \ x&\quad \hbox{si }x\ge 0 \\ -x&\quad \hbox{si }x<0
\end{cases}$$
\end{defi}

$\bigstar$ Los ejercicios del 1 al 6 te pueden servir para saber si has asimilado los conceptos de esta sección.


\timeclase{Fin de clase 8; 14-10-2011, grupo A y B}


\section{Factorización y Divisibilidad en $\mathbb{Z}$}


\subsection{Algoritmo de la División y Divisibilidad en $\mathbb{Z}$}

\hypertarget{Adiv}{ }\label{Adiv}
\begin{center}
\shadowbox{\parbox{\columnwidth+0\fboxsep+10\fboxrule-\shadowsize}{
\centering
\begin{prop}[Algoritmo de la división.]\rm \index{Algoritmo de la División} Dados dos números enteros $x,y\in \mathbb{Z}$ con $y>0$ existen $c,r\in \mathbb{Z}$
(únicos), tales que  $x=cy+r$ con $0\le r<y$.
\end{prop}
}}
\end{center}

\retodo{Es la primera vez que se usa reducción al absurdo.}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=azul]{Si miras el dibujo, el resto consiste en ir restando a $x$ múltiplos de $y$, -y, -2y,...,-cy hasta justo antes de dar negativo (ese número es el resto y el número de veces que has restado el y,  el cociente. La unicidad por reducción al absurdo} \textbf{Demo:} Consideremos el conjunto $$X:=\{x-ny\ \vert\ x-ny\ge0,\ n\in
\mathbb{Z}\}\subset \mathbb{N}$$

Gráficamente tenemos:

\begin{center}
\begin{tikzpicture}[thick]
\draw[thick] (-1,0) -- (13,0);
\draw[thick] (0,-.3)--(0,.3) node[above]{$0$};
\draw[thick] (0.8,-.3)--(0.8,.3) node[above]{$Y$};
\draw[thick] (12.6,-.3)--(12.6,.3) node[above]{$X$};
\draw[very thin] (12.6-.8,-.2)--(12.6-.8,.2) node[above] {\small $x-y$};
\draw[very thin] (12.6-1.6,-.2) node[below] {\small $x-2y$}--(12.6-1.6,.2);
\draw[very thin] (12.6-2.4,-.2)--(12.6-2.4,.2) node[above] {\small $x-3y$};
\foreach \i in {4,...,15}{
\draw[very thin] (12.6-\i*.8,-.2)--(12.6-\i*.8,.2);}
\draw[very thin] (.6,-.2) node[below] {\small $x-cy$}--(.6,.2);
\end{tikzpicture}
\end{center}

Es claro que $X\ne \emptyset$, ya que:
\begin{enumerate}
\item[--] Si $x\ge 0$,\quad  $x=x-0 y\in X$ y,
\item[--]  Si $x\le 0$,\quad  $0\le x(1-y)=x-(xy)\in X$.
\end{enumerate}


Por tanto, aplicando que $(\mathbb{N},\le)$ es un buen orden, sea $r=\Min(X)$. Así, existe $c\in \mathbb{Z}$ tal
que $r=x-cy$, es decir, $x=cy+r$. Veamos ahora que $r<y$. Por reducción al absurdo, si $y\le r$, tenemos que $0\le r-y=x-(c+1)y\in X$, una contradicción, ya que $r-y<r$ y $r$ era el mínimo en $X$.
Por tanto, hemos encontrado $c,r\in \ZZ$ tales que $x=cy+r$ con $0\le r<y$.

 Veamos, por último, que $c$ y $r$ son únicos: Supongamos $r,r',c,c'$ tales que

\[\begin{split}
x&=cy+r\hskip 1.2truecm 0\le r<y\\
x&=c'y'+r'\hskip 1truecm 0\le r'<y
\end{split}\]

Podemos suponer  $0\le r\le r'<y$. Entonces $cy+r=c'y+r'$ por lo que $$0\le r'-r=(c-c')y.\eqno{(1)}$$

 Por tanto, $r'-r$ es múltiplo de $y$ y  $r'-r\le r'< y$, con lo que la única posibilidad es $r'-r=0$, ver \fullref{el ejercicio}{multmenor}{}. Ahora, por la ley de simplificación $c-c'=0$. \hfill$\blacksquare$

 \begin{prop}[Algoritmo de la división (ejercicio).]\rm \index{Algoritmo de la División} Dados dos números enteros $x,y\in \mathbb{Z}$ con $y\ne0$ existen $c,r\in \mathbb{Z}$
(únicos), tales que  $x=cy+r$ con $0\le r<|y|$.
\end{prop}

\begin{defi}\rm Con la notación del teorema anterior se dice que $x$ es el \textbf{dividendo}, $y$ el \textbf{divisor}, $c$ el \textbf{cociente} y
$r$ el  \textbf{resto}. \index{Algoritmo de la División!Dividendo}\index{Algoritmo de la División!Divisor}\index{Algoritmo de la División!Cociente}\index{Algoritmo de la División!Resto}
\end{defi}

\begin{defi}\rm
 Sean $x,y$ dos números enteros. Se dice que $y$ \textbf{divide} a $x$ y se\index{Divisibilidad}  representa $^y\vert _x$ si existe $c\in \mathbb{Z}$ \nomenclature{$^y\vert _x$}{$y$ divide a $x$}
tal que $x=cy$.
\end{defi}

\begin{coro}[\fullref{Ejercicio}{ejjdos2}{}]\rm
La relación de divisibilidad en $\ZZ$ es reflexiva, transitiva y verifica que para todo $a,b\in \ZZ$, si
$$^a\vert _b \hbox{ y } ^b\vert _a\quad \hbox{entonces } a=\pm b.$$
Por tanto, es una relación de orden en $\NN$.
\end{coro}


\subsection{Máximo Común divisor}
\begin{defi} \hypertarget{mcd}{ }\label{mcd}\rm Sean $x$ e $y$ dos número enteros alguno de ellos no nulo. Se define el \textbf{máximo común divisor}\index{Máximo Común Divisor} de $x$ e $y$, y se representa
por $\mcd(x,y)$ como un número  $d \in \mathbb{Z}$ con las siguientes propiedades: \nomenclature{$\mcd(x,y)$}{Máximo Común Divisor}
\begin{enumerate}
\item $d>0$.
 \item $^d\vert _x$ y $^d\vert_y$.
\item Si $^r\vert _x$ y $^r\vert_y$, entonces $^r\vert_d$.
\end{enumerate}
\end{defi}

\begin{center}
\shadowbox{\parbox{\columnwidth+0\fboxsep+10\fboxrule-\shadowsize}{
\centering
\begin{prop}\rm \label{mcd} Sean $x,y$ dos enteros alguno no nulos. Entonces existen $\mcd(x,y)$ y es único. Es más, existen $r,s\in \mathbb{Z}$ tales que
$rx+sy=m.c.d(x,y)$.
\end{prop}
}}
\end{center}


\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=azul]{Recordar que el máximo común divisor de dos números x,y es el menos natural que se puede escribir de la forma $ax+by$ es decir, el mínimo del conjunto $X$.} \textbf{Demo:} Sea el conjunto $$X=\{ax+by\ \vert\ a,b\in \ZZ, \hbox{ con } ax+by>0\}\subset \NN.$$ Es claro que $X\ne
\emptyset$, ya que $x^2+y^2\in X$. Por tanto, aplicando que $(\NN,\le)$ posee un buen orden, existe $$d=rx+sy=\Min(X)\in \NN.\eqno{(1)}$$
Veamos que $d=\mcd(x,y)$: por definición, $d>0$. demostremos que  $d$ divide a $x$. Aplicando el algoritmo de la división a $x,d$, existen $c,r\in \ZZ$ tal que $x=cd+r$ con $0\le r<d$. Por tanto, $x=c(rx+sy)+r$, luego $r=(1-cr)x+(-cs)y$. Así, si $r\ne 0$, $r\in X$ con $r<d$, que es imposible. Luego $r=0$, o lo que es lo mismo, $d$ divide a $x$. Cambiando los papeles de $x$ e $y$ demostramos que $d$ divide a $y$. Por último, Si $a$ divide a $x$ y divide a $y$, entonces $x=ax'$, $y=ay'$ y por tanto $d=rx+sy=rax'+say'=(rx'+sy')a$ lo que demuestra que $a$ divide a $d$.

Veamos la unicidad: si $d$ y $d'$ verifican las propiedades de $\mcd(x,y)$, entonces $^d\vert _{d'}$ y $^{d'}\vert _d$ por lo que $d=\pm d'$ pero como ambos son números naturales, tenemos que $d=d'$.  \EndProof
\vskip.3truecm





\noindent\textbf{Nota:} Observar que hemos conseguido, a partir de una demostración indirecta, demostrar que existen dos enteros $r,s$ tales que $rx+sy=\mcd(x,y)$. Es más, el máximo común divisor de $x$ e $y$ es el menor natural que puede ser escrito en esta forma. No obstante, en un caso concreto, no sabemos encontrar dichos números. El siguiente teorema, debido a Euclides, nos da un algoritmo para calcularlos.

\noindent\textbf{Nota:} Aunque pueda parecer una demostración extraña, cuando estudiemos la noción de ideal y los ideales de $\ZZ$ veremos que el resultado (y su demostración) son muy obvios.

\noindent \textbf{Nota:} En ningún momento se ha dicho que $r$ y $s$ sean únicos. Así: $\mcd(2,3)=1$ y,
\[\begin{split}
1\ \ \cdot \red3\black+(-1)\cdot \red2\black&=1\\
(-3)\cdot \red3\black+\hskip .35truecm 5 \hskip .3truecm\black\cdot \red2\black&=1.
\end{split}\]

\begin{lema}[\fullref{Ejercicio}{lemasiete7}{}]
  Sean $x,y,a,b\in \ZZ$, Entonces:
  \begin{enumerate}
    \item[(i)] Si $^x\vert_y$, entonces $\mcd(x,y)=\vert x\vert$.
    \item[(ii)] Si $^x\vert_a$ y $^x\vert_b$, entonces $^x\vert_{\alpha a+\beta b}$ para todo $\alpha,\beta\in \ZZ$.
  \end{enumerate}
\end{lema}


\hypertarget{Aeuc}{ }\label{Aeuc}
\begin{theo}[Algoritmo de Euclides]\rm \index{Algoritmo de Euclides}
Sean $x,y$ dos enteros no nulos.  Supongamos que $x=cy+r$ con $r\ne 0$. Entonces
\begin{enumerate}
\item[(i)] $\mcd(x,y)=\mcd(y,r)$.
\item[(ii)] Aplicando el algoritmo de la división a $x$ e $y$: $x=cy+r_1$. Si $r_1\ne 0$ volvemos a aplicar el algoritmo de la división a $y$ y $ r_1$: $y=c_2 r_1+r_2$, y reiterando el proceso:

\[\begin{split}
x=&c_1 y+r_1\quad \hbox{si}\quad r_1\ne0\\
y=&c_2 r_1+r_2\quad \hbox{si}\quad r_2\ne0\\
r_1=&c_3 r_2+r_3\quad \hbox{si}\quad r_3\ne0\\
\ &\qquad \vdots\\
r_{k}=&c_{k+2} r_{k+1}+r_{k+2}\quad \dots
\end{split}\]

$\exists\  n\in \NN$ tal que $r_n=0$, entonces $r_{n-2}=c_{n} r_{n-1}$ y $\mcd(x,y)=r_{n-1}$.


\end{enumerate}
\end{theo}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{El punto (i) es una mera comprobación. El punto dos es sólo un argumento inductivo. Por tanto debes de poder demostrarlo sin problemas} \textbf{Demo:} (1). Sea $d=\mcd(x,y)$ y $d'=\mcd(y,r)$. $$x=cy+r\eqno{(1)}$$ Como $^d\vert _x$, $^d\vert _y$ y $r=x-cy$, $^d\vert_r$. Ahora, aplicando que $d'=\mcd(y,r)$, $^d\vert _{d'}$. Análogamente, como $d'$ divide a $y$ y a $r$, por (1),  $d'$ divide a $x$ y por tanto $^{d'}\vert d$. Así, $d=\pm d'$ y por tanto $d=d'$.

(2). La cadena decreciente de números naturales $r_1>r_2>r_3\cdots>r_k>\cdots$ debe de llega a cero (principio del buen orden). Supongamos que $r_n=0$, entonces $r_{n-2}=c_{n-1} r_{n-1}$. Ahora, aplicando reiteradamente el apartado anterior $$\mcd(x,y)=\mcd(r_{n-2},r_{n-1})=r_{n-1}$$ \hfill$\blacksquare$


\begin{ejem}\rm
Calcula $\mcd(1567, 4763)$.
\begin{eqnarray}
4763=&3\cdot 1567+62\\
1567=&25\cdot 62+17 \\
62=&3\cdot 17+11\\
17=&1\cdot 11+6\\
11=&1\cdot 6+5\\
6=&1\cdot 5+\fbox{1}\\\
5=&5\cdot 1+0
\end{eqnarray}

Luego $\mcd(1567, 4763)=1$. En cualquier caso, observar que rápidamente nos encontramos con números pequeños a los que
les podemos calcular de forma fácil su máximo común divisor, $\mcd(62,17)=1$.

$\star$ Veamos ahora como calcular $r,s\in \ZZ$ tales que $r\cdot 1567+s\cdot 4763=1$. Despejamos el 5 de (2.5) y lo sustituimos en (2.6): $6=1\cdot (11-6)+1$,
$$ 1=(-1)\cdot \red11\black+2\cdot \red6\black\eqno{(\clubsuit)}$$
Despejamos de  (2.4) el  $6$, y lo sustituimos en $(\clubsuit)$, $6=17-11$:
$$ 1=(-1)\cdot \red11\black+2\cdot \red(17-11)\black=(-3)\cdot\red11\black+ 2\cdot\red17\black\eqno{(\blacklozenge)}$$
Despejamos el $11$ de (2.3) y lo sustituimos en $(\blacklozenge)$:
$$1=(-3)\cdot\red(62-3\cdot 17)\black+ 2\cdot\red17\black=(-3)\cdot\red62\black+ 11\cdot\red17\black\eqno{(\spadesuit)}$$
Despejamos el $17$ de (2.2) y lo sustituimos en $(\spadesuit)$:
$$1=(-3)\cdot\red62\black+ 11\cdot\red(1567-25\cdot 62)\black=11\cdot\red1567\black- 278\cdot\red 62\black\eqno{(\blacktriangle)}$$
Por último, despejamos $ 62$ de (2.1) y lo sustituimos en $(\blacktriangle)$:
$$1=11\cdot\red1567\black- 278\cdot\red (4763-3\cdot 1567)\black=-278\cdot \red4763\black+845\cdot \red1567\black\eqno{(\bigstar)}$$
\end{ejem}



\begin{defi}\rm Se dice que un número entero $p$ es \textbf{primo} \index{Número! Primo} si $\vert p\vert\ne 1$ y sólo es divisible por
$\{1,-1,p,-p\}$.
\end{defi}

\timeclase{Fin de clase 9; 18-10-2011, grupo A y B}

\noindent \textbf{Nota:} Como ejemplos de números primos: 2,3,5,7,11,13,17,19,23 o incluso el número  29.996.224.275.833
que es el primo número $10^{12}$.

\begin{defi} \rm Sean $x$ e $y$ dos número enteros no nulos. Se dice que $x$ e $y$ son \textbf{primos relativos}\index{Número!Primos Relativos} si $\mcd(x,y)=1$.
\end{defi}

\begin{coro}[Teorema de Bezout]\rm \index{Bezout}Sean $x,y$ dos enteros no nulos. Las siguientes condiciones son equivalentes:
 \begin{enumerate}
   \item[(i)]   $x,y$ son primos relativos.
   \item[(ii)] existen $r,s\in \mathbb{Z}$ tales que $rx+sy=1$.
 \end{enumerate}
\end{coro}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Cualquier apartado debe de poder demostrarse sin problemas.} \textbf{Demo:}

$(i)\implies (ii)$. Si $x,y$ son primos relativos, por definición, $\mcd(x,y)=1$ luego por \fullref{el teorema}{mcd}{} existen $r,s\in \ZZ$ tal que $rx+sy=1$.

$(ii)\implies (i)$. Supongamos que existen $r,s\in \mathbb{Z}$ tales que $rx+sy=1$ y $d=\mcd(x,y)$. Como $d$ divide a $x$ y $d$ divide a $y$, $x=dx'$, $y=dy'$ y por tanto
$$1=rx+sy=rdx'+sdy'=d(rx'+sy')$$
Por tanto $d$ divide a $1$ lo que implica que $d=1$, ver \fullref{el ejercicio}{unosoloprod}{}. Es decir, $x$ e $y$ son primos relativos. \EndProof



\begin{theo}[Teorema Generalizado de Bezout]\label{genbezout}\rm
Sean $n_1,n_2,\dots, n_r\in \NN$ tales que si $k\in \mathbb{N}$ divide a todo $n_i$,  $k=1$.  Entonces existen $\alpha_1,\alpha_2,\dots,\alpha_r\in \ZZ$ tales que $\alpha_1 n_1+\alpha_2 n_2+\cdots+\alpha_r n_r=1$.
\end{theo}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=rojo]{???} \textbf{Demo:}  Vamos a dar una demostración por inducción a $r$, el número de elementos que tenemos:

(i). Si $r=2$ tenemos que este resultado es el teorema de Bezout, por lo que no tenemos nada que demostrar.

(ii). Supongamos que el resultado es cierto para $r-1$ y consideremos $r$ naturales no nulos $n_1,n_2,\dots, n_r\in \NN$ tales que si $k\in \mathbb{N}$ divide a todo $n_i$,  $k=1$. Sean los naturales $n_1,n_2,\dots, n_{r-1}$ y sea el conjunto
$$\Delta:=\{\lambda\in \NN\ \vert \lambda \text{ divide a todos los $n_i$ } i=1,\dots, r-1\}$$
Es claro que $1\in \Delta$ y que todo elemento de $\Delta$ es menor que cualquiera de los $n_i$, por lo que es un conjunto finito. Sea $\beta$ el mayor elemento de $\Delta$. Tenemos entonces que $n_i=\beta n_i'$ con $n_i'\in \ZZ$ y que el conjunto $\{n_1',n_2',\dots,n_{r-1}'\}$ verifica la hipótesis de inducción (si hubiera un $\gamma$ que dividiera a todos los $n_i'$, $\gamma \beta>\beta$ dividiría a todos los $n_i$, $i=1,\dots, r-1$, una contradicción ya que $\beta$ era el mayor. Por tanto, aplicando la hipótesis de inducción existen $\alpha_i'\in \ZZ$ tal que
$$\alpha'_1 n'_1+\alpha'_2 n'_2+\cdots+\alpha'_{r-1} n'_{r-1}=1.\eqno{(*)}$$
Por otro lado $\mcd(\beta, n_r)=1$ ya que si algún natural dividiera a $\beta$ y a $n_r$ dividiría a todos los $n_i$ (que no puede ser por hipótesis). Luego aplicando el teorema de Bezout existen $a,b\in \ZZ$ tal que
$$a\beta+bn_r=1.\eqno{(**)}$$
Luego por $(**)$, y sustituyendo $(*)$, tenemos:
\begin{align*}
 1&=a\beta+bn_r=a\beta(1)+bn_r=a\beta(\alpha'_1 n'_1+\alpha'_2 n'_2+\cdots+\alpha'_{r-1} n'_{r-1})+bn_r\\
 &=a\alpha'_1 \beta n'_1+a\alpha'_2 \beta n'_2+\cdots+a\alpha'_{r-1}\beta  n'_{r-1}+bn_r\\
 &=a\alpha'_1 n_1+a\alpha'_2 n_2+\cdots+a\alpha'_{r-1}n_{r-1}+bn_r
\end{align*}
que nos demuestra el resultado.\EndProof

\begin{prop} \label{divprodprim}\rm Sean $n_1,n_2,\dots, n_k$  números enteros no nulos y $p\in \mathbb{Z}$ un número primo. Supongamos que  $^p\vert _{n_1 n_2\dots n_k}$
entonces existe $i\in \{1,2,\dots,k\}$ tal que $^p\vert _{n_i}$.
\end{prop}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=rojo]{Es un proceso de inducción en donde el caso 2 es aplicar Bezout. En cuestiones de divisibilidad hay que tener muy en cuenta Bezout.} \textbf{Demo:}  Vamos a dar una demostración por inducción a $k$. Demostremos el caso $k=2$. Supongamos que $p$ no divide a $n_1$. Entonces $m.c.d(p,n_1)=1$ por lo que por el Teorema de Bezout
existen $\alpha, \beta\in \ZZ$ tal que
$$\alpha n_1+\beta p=1\eqno{(1)}$$
Ahora, como  por hipótesis $n_1n_2=cp$, multiplicando en (1) por $n_2$,
$$n_2=n_2(\alpha n_1+\beta p)=\alpha (n_1 n_2)+\beta p n_2=\alpha (cp)+\beta p n_2=(\alpha c+\beta n_2)p\eqno{(2)}$$
Por tanto, $n_2$ es divisible por $p$.

Supongamos que el resultado es cierto para $k-1$, entonces, si  $^p\vert _{n_1 n_2\dots n_k}$, aplicando el caso anterior a los números $(n_1\dots n_{k-1})$ y $n_k$ tenemos que, $^p\vert _{n_1\dots n_{k-1}}$ o $^p\vert n_k$ y por el proceso de inducción,  si $^p\vert _{n_1\dots n_{k-1}}$, existe un $i$ tal que $^p\vert _{n_i}$. Lo que demuestra la proposición. \hfill $\blacksquare$




\subsection{Factorización en $\mathbb{Z}$}

\hypertarget{Tfac}{ }\label{Tfac}
\begin{center}
\shadowbox{\parbox{\columnwidth+0\fboxsep-10\fboxrule-\shadowsize}{
\centering
\begin{defi}[Teorema de Factorización] \index{Factorización} \rm Dado un número entero $n$ con $\vert n\vert>1$ existen unos únicos
$p_1<\dots<p_k$  primos y $n_1,\dots,n_k\in \mathbb{N}$ tales que $n=\pm p_1^{n_1}\dots p_k^{n_k}.$
\end{defi}
}}
\end{center}


\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=azul]{Es un proceso de inducción.}  \textbf{Demo:} Es claro que podemos suponer $n\in \NN$. Vamos a usar el principio de inducción generalizado:
 si $n=2$, ya está factorizado. Supongamos que todo número natural menor que $n$ esta factorizado como producto de
 primos. Si $n$ es primo, no hay nada que demostrar, caso contrario existen $a,b\in \NN$ mayores que $1$ tales
 que $n=ab$. Entonces $a,b<n$ y por hipótesis de inducción, $a$ y $b$ factoriza como producto de primos.

Veamos la unicidad: El caso $n=2$ es trivial. Por tanto, y aplicando el principio de inducción generalizado
 puedo suponer que tenemos factorización única para todo natural $< n$.
 Supongamos $n=p_1^{n_1}\dots p_k^{n_k}=p_1^{m_1}\dots p_k^{m_k}$ con $n_i, m_i\in \NN$ (puedo suponer que los
 primos que aparecen en la factorización son los mismos al haber permitido el exponente cero). Reordenando  puedo
  suponer $n_1\ne 0$ y por tanto $n$ es divisible por $p_1$. Aplicando el resultado anterior,
   $^{p_1}\vert _{p_1^{m_1}\dots p_k^{m_k}}$ y como $p_1$ no puede dividir a ningún primo que no
    sea el mismo, $m_1\ge1$, Tenemos entonces que $p_1^{n_1-1}\dots p_k^{n_k}=p_1^{m_1-1}\dots p_k^{m_k}<n$,
    aplicando ahora el proceso de inducción $n_i=m_i$ para todo $i$. \hfill $\blacksquare$

\begin{coro}\rm
 Sean $x,y$ dos enteros no nulos. Entonces el máximo común divisor de $x$ e $y$ es el producto de los primos
comunes elevado al menor exponentes (en sus respectivas factorizaciones).
\end{coro}

\hypertarget{Teuc}{ }\label{Teuc}
\begin{coro}[Teorema de Euclides]\rm
 Existen infinitos primos.
\end{coro}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=azul]{si el número de primos fuera finito el producto de ellos más 1 no sería factorizable}  \textbf{Demo:} Vamos a dar una demostración por reducción al absurdo. Supongamos que el número de primos es finito, $p_1,p_2,\dots, p_k$. Sea $n=p_1p_2\cdots p_k+1\in \ZZ$. Tenemos que $n$ se factoriza como producto de primos, sea $p$ uno de estos primos. Entonces $n$ es divisible por $p$, pero $p_1p_2\cdots p_k$ es divisible por $p$, por tanto $1$ es divisible por $p$, una contradicción (si $1=p\alpha$, $p=\pm 1$ y no puede ser primo).   \hfill $\blacksquare$

\timeclase{Fin de clase 10; 20-10-2011, grupo A y B}

\hypertarget{MCM}{ }\label{MCM}
\begin{defi}\rm Sean $x,y$ dos número enteros alguno no nulos. Se define el mínimo común múltiplo \index{Mínimo Común Múltiplo}de $x$ e $y$ y se representa
por $\MCM(x,y)$ como un número   $m \in \mathbb{Z}$ con las siguientes propiedades:\nomenclature{$\MCM(x,y)$}{mínimo común múltiplo}
\begin{enumerate}
\item $m>0$.
\item $^x\vert_m$ e $^y\vert_m$.
\item Si $^x\vert _r$ e $^y\vert _r$, entonces $^m\vert _r$.
\end{enumerate}
\end{defi}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Considerar el conjunto de todos los múltiplos comunes y demostrar que el mínimo en este conjunto (que existe) verifica lo que queremos}  \textbf{Demo:} Hay que demostrar que tal número existe y es único. Una posible demostración consiste en considerar el conjunto $$\Delta:=\{0<a\in \mathbb{N}\ \vert\ ^x\vert_a,\ ^y\vert_a\}$$
Demostrar que es no vacío y que es mínimo de este conjunto, digamos  $m$,  es el $\MCM(x,y)$. Por hipótesis, $m$ verifica $1.$ y $2.$ por último, si $^x\vert _r$ e $^y\vert _r$, por el algoritmo de la división $r=mc+r'$ (demostrar que $r'=0$).\hfill $\blacksquare$



\begin{prop}\rm Sean $x,y$ dos enteros no nulos. Entonces el mínimo común múltiplo de $x$ e $y$ es el
producto de los primos comunes y no comunes  elevado al mayor de los exponentes (en sus respectivas factorizaciones).
\end{prop}

\begin{coro}[\fullref{Ejercicio}{ejjdos2}{}]\rm
Sabemos que la relación de divisibilidad en $\NN$ es  una relación de orden. Además, el ínfimo de dos elementos $a,b\in \NN$ coincide con $\mcd(a,b)$, y el supremo de dos elementos  $a,b\in \NN$ coincide con $\MCM(a,b)$, por lo que $\NN$ con la relación de divisibilidad es un retículo.
\end{coro}


\begin{coro}\rm Sean $x,y$ dos enteros no nulos. Entonces $$\vert xy\vert =m.c.d(x,y).\MCM(x,y).$$\end{coro}

$\bigstar$ Los ejercicios del 7 al 21 de este tema pueden servirte para comprobar si has asimilado las nociones de estas dos secciones.


\hypertarget{Cong}{ }
\section{Congruencias.}\label{Cong}

\subsection{Anillos de congruencias}
En esta sección vamos a trabajar con nuevos conjuntos de números: $\ZZ_n$, los \textbf{anillos de congruencias modulo $n$}.  \nomenclature{$\ZZ_n$}{Anillo de congruencias módulo $n$}

\hypertarget{RCpr}{ }\label{RCpr}
\begin{defi}\rm
Sea $\ZZ$ el conjunto de los  enteros y $n\in \NN$. Dados $a,b\in \ZZ$, diremos que $a$ es congruente con $b$ módulo $n$, y lo representaremos por $a\equiv b\  (\Mod n)$ si $^n\vert _{a-b}$.
\end{defi}


\begin{prop}\rm
Sea $\ZZ$ el conjunto de los enteros y $n\in \NN$. Entonces:
\begin{enumerate}
\item[(i)] Para todo $a,b\in \ZZ$,  $a\equiv b\  (\Mod n)$ si y sólo si el resto de dividir $a$ por $n$ coincide con el resto de dividir $b$ por $n$.
\item[(ii)] La relación de congruencia es una relación de equivalencia,
\item[(iii)] Las clases de equivalencia de la relación de congruencia módulo $n$ son $${\ZZ}_n:=\ZZ/_{(\Mod n)}=
\{\overline 0,\overline 1,\overline 2,\cdots,\overline {n-1}\}.$$
\end{enumerate}
\end{prop}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Es una comprobación, lo deberías de demostrar sin problemas}
 \textbf{Demo:} (i). Aplicando el algoritmo de la división $a=cn+r$, $b=c'n+r'$. Podemos suponer que $r'\le r$
(en caso contrario les cambiamos los nombres). Ahora, $a-b=(c-c')n+r-r'$ con $0\le r-r'\le r< n$, por tanto $a-b$ es
múltiplo de $n$ si y sólo si $r-r'=0$.

(ii). Trivial a partir de (i).

(iii). Dado $a\in\ZZ$, aplicando el algoritmo de la división, $a=cn+r$ con $0\le r<n$. Por tanto $a-r=cn$ y $a\equiv r\
(\Mod n)$ o lo que es lo mismo $\overline a=\overline r$ (hemos demostrado que a lo sumo hay $n$ clases de
equivalencia, $\{\overline 0,\overline 1,\overline 2,\cdots,\overline {n-1}\}$). Veamos ahora que todas son distintas:
sean $0\ne i\le j<n$ y supongamos que $\overline i=\overline j$. Entonces $j\equiv i\ (\Mod n)$ por lo que $j-i=cn$.
Por otro lado, $0\le j-i\le j<n$, con lo que la única posibilidad es $j-i=0n=0$, es decir $i=j$ y hay $n$ clases de
equivalencia. \EndProof

\textbf{Nota:} En el anillo de congruencias módulo $n$, con $n\in \NN$, tenemos que la clase de equivalencia de un elemento $r\in \ZZ$ es:
$$\overline r=\{r+\alpha n\ \vert\ \alpha\in \ZZ\}$$
Es decir, cualquier elemento de este conjunto es un representante para la clase $\overline r\in \ZZ_n$.


\begin{theo}\label{Acong}\rm
Sea $\ZZ$ el conjunto de los enteros y $n\in \NN$. Entonces podemos definir una suma y un producto en el conjunto cociente, ${\ZZ}_n$:
\begin{enumerate}
\item[(i)] $\overline a+\overline b:=\overline{a+b}$ para todo $\overline a,\overline b\in {\ZZ}_n$.
\item[(ii)] $\overline a\cdot \overline b:=\overline{a\cdot b}$ para todo $\overline a,\overline b\in {\ZZ}_n$.
\item[(iii)] Las operaciones anteriores verifican las propiedades 1.(a),(b),(c),(d), 2.(a),(b),(c), 3.(a). de  \fullref{la definición}{propi}{}.
\end{enumerate}

\textbf{Nota:} No hay ninguna relación de orden asociada a este conjunto cociente. A $\ZZ_n$ con las operaciones
anteriores se le denomina el \textbf{anillo de congruencias}\index{Anillo! de Congruencia} módulo $n$. Observar que $\overline 0=\{kn\ \vert\ k\in \ZZ\}$, es decir, los múltiplos de $n$ son el elemento neutro de la suma.
\end{theo}


\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=azul]{Es una comprobación, el color azul (dificultad media) es simplemente porque te tienes que acordar de comprobar que las operaciones están bien definidas, es decir que no depende del representante}
 \textbf{Demo:}  En (i) y en (ii) se ha definido la suma y el producto respecto de representantes de cada clase,
por lo que hay que demostrar que la suma y el producto están bien definidos (no dependen de representantes). Sean
\[\begin{matrix} \begin{matrix}
\overline a=\overline a'\\\overline b=\overline b'
\end{matrix}&
\Longrightarrow &
\begin{matrix}
 a-a'=c n\\ b-b'=c'n
\end{matrix}
\end{matrix}\eqno{(1)}\]


(i). Veamos que la suma está bien definida: por (1), sumando ambas expresiones, $a-a'+b-b'=(c+c')n,$ o lo que es lo
mismo, $$a+b-(a'+b')=(c+c')n,$$ es decir, $a+b\equiv a'+b'\ (\Mod n)$ y por tanto $\overline {a+b}=\overline {a'+b'}$.



(ii). Veamos que el producto está bien definida: por (1), $a=a'+cn$ y $b=b'+c'n$ por tanto, si multiplicamos ambas
expresiones, $$ab=a'b'+a'c'n+b'cn+cc'n^2=a'b'+(a'c'+b'c+cc'n)n.$$ Por tanto $ab\equiv a'b'\ (\Mod n)$ y por tanto
$\overline {ab}=\overline {a'b'}$.

(iii).  Todas estas propiedades son ahora triviales:



 \begin{itemize}
\item Propiedades de la suma:
\begin{itemize}
\item Asociativa:  $\overline x+(\overline y +\overline z)=\overline x+\overline{y+z}=\overline {x+(y+z)}=\overline{(x+y)+z}=\overline{x+y}+\overline{z}=(\overline x+\overline y)+\overline z$.
\item Conmutativa: $\overline x+\overline y=\overline {x+y}=\overline {y+x}=\overline y+\overline x$.

\item Elemento neutro: $\overline x+\overline 0=\overline {x+0}=\overline x$.

\item  Elemento opuesto: $\overline x+\overline {-x}=\overline 0$.
\end{itemize}

\item Propiedades del producto:
\begin{itemize}
\item Asociativa:
$\overline x\cdot(\overline y \cdot \overline z)=\overline x\cdot \overline{y\cdot z}=\overline {x\cdot(y\cdot z)}=\overline{(x\cdot y)\cdot z}=\overline{x\cdot y}\cdot \overline z=(\overline x\cdot \overline y)\cdot\overline z$
\item Conmutativa: $\overline x\cdot \overline y=\overline {x\cdot y}=\overline {y\cdot x}=\overline y\cdot \overline x$.

\item Elemento Neutro: $\overline x\cdot \overline 1=\overline {x\cdot 1}=\overline x$.
\end{itemize}
\item Propiedades conjuntas (distributiva):
$$\overline x\cdot(\overline y+\overline z)=\overline x\cdot(\overline{y+z})=\overline {x\cdot(y+z)}=\overline{x\cdot y+x\cdot z}=\overline{x}\cdot\overline{y}+\overline{x}\cdot\overline{z}.$$
\end{itemize}
Lo que demuestra la proposición. Se dice que  $(\ZZ_n,+)$ es un grupo abeliano por cumplir las 4 primeras propiedades. Se dice que $(\ZZ_n,+,\cdot)$ es un anillo unitario por cumplir todas las propiedades anteriores. \hfill $\blacksquare$

\timeclase{Fin de clase 11; 21-10-2011, grupo A y B: Ejercicios. Fin de clase 12; 25-10-2011, grupo A y B}

\begin{coro}
  Sea $n\in \NN$ y sean $a,b,c,d,x\in \ZZ$, $y\in \NN$. Supongamos que $a\equiv b\  (\Mod n)$ y $c\equiv d\ (\Mod n)$. Entonces,\vskip.3truecm

  \hskip-.5truecm
  \begin{tabular}{ll}
  $(i)$ $a+c\equiv b+d\  (\Mod n)$\hskip2.5truecm \ & $(ii)$ $a\cdot c\equiv b\cdot d\  (\Mod n)$.\\
  \ &\ \\
   $(iii)$ $x\cdot a\equiv x\cdot b\  (\Mod n)$.& $(iv)$ $a^y\equiv b^y\  (\Mod n)$.
  \end{tabular}
\end{coro}


\noindent{\textbf{Nota:}} Se ha demostrado que si estamos trabajando en el anillo de congruencias modulo $n$ cuando multiplicamos o sumamos número podemos cambiar cualquiera de ellos por un congruente (modulo $n$) suyo. Así, en $\mathbb{Z}_{11}$ tenemos:
$$(213\cdot 543)+1113\equiv (4\cdot 4)+2=18\equiv 7 \ (\Mod 11)$$

En cambio no podemos cambiar por números congruentes las potencias (los exponentes nos dicen cuantas veces hay que multiplicar un elemento): $$2^{12}\not\equiv 2^1 \ (\Mod 11)$$



\begin{ejem}\rm
Veamos las tablas de sumar y multiplicar de $\ZZ_6$:

 \noindent \centerline{\begin{tikzpicture}[thick,scale=.7]
\foreach \i/\j in {0,1,...,5}
\draw (\i,.5) node{\i} (-1,-\i-.5) node{\i};
\draw (-1.5,0)--(5.5,0);
\draw (-.5,1)--(-.5,-6);
\foreach \i in {0,1,...,5}
\draw (\i,-.5) node{\i} (-1,-\i-.5) node{\i};
\foreach \i in {0,1,2,3,4,5}
\foreach \j in {0,...,\i}
\draw (\i-\j,-\j-+.5) node{\i};
\foreach \j in {0,1,2,3,4,5}
\foreach \i in {0,1,...,\j}
\draw (6+\i-\j,-\j-+.5) node{\i};
\filldraw[white] (5.8,0) rectangle (7.2,-6);
\draw (-1,.5) node{$+$};
\end{tikzpicture}
\begin{tikzpicture}[thick,scale=.7]
\foreach \i/\j in {0,1,...,5}
\draw (\i,.5) node{\i} (-1,-\i-.5) node{\i};
\draw (-1.5,0)--(5.5,0);
\draw (-.5,1)--(-.5,-6);
\foreach \i in {0,1,...,5}
\draw (\i,-.5) node{0} (\i,-1.5) node{\i} (0,-\i-.5) node{0} (1,-\i-0.5) node{\i};
\draw (2,-2.5) node{4} (2,-3.5) node{0} (3,-2.5) node{0} (2,-4.5) node{2} (2,-5.5) node{4};
\draw (3,-3.5) node{3} (3,-4.5) node{0} (3,-5.5) node{3};
\draw (4,-2.5) node{2} (4,-3.5) node{0} (4,-4.5) node{4} (4,-5.5) node{2};
\draw (5,-2.5) node{4} (5,-3.5) node{3} (5,-4.5) node{2} (5,-5.5) node{1};
\draw (-1,.5) node{$\bullet$};
\end{tikzpicture}}
\end{ejem}
\textbf{Nota:} En estos conjuntos de números ocurren cosas extrañas: Por ejemplo, en $\ZZ_6$, $\overline 2\ \overline 3=\overline 0$, por lo que el producto de números no nulos puede ser cero.

\hypertarget{Invc}{ }\label{Invc}
\begin{defi}\rm
Sea $\ZZ_n$ el anillo de congruencias módulo $n$ (con $n\in \NN$). Diremos que \textbf{$\overline a\in {\ZZ}_n$ es inversible en $\ZZ_n$} si existe $\overline b\in{\ZZ}_n$ tal que $\overline a\cdot \overline b=\overline 1=\overline b\cdot \overline a$
\end{defi}

\begin{prop}\rm
Sea $\ZZ_n$ el anillo de congruencias módulo $n$ (con $n\in \NN$) y sea  $\overline a\in {\ZZ}_n$. Entonces, $\overline
a$ es inversible en $\ZZ_n$ si y solo si $\mcd(a,n)=1$. Es más, en este caso, existe un único $\overline b\in \ZZ_n$
tal que $\overline a\cdot \overline b=\overline 1=\overline b\cdot \overline a$, llamado \textbf{el inverso de $\overline a$ en
$\ZZ_n$}, que se de\-no\-ta\-rá usualmente por $\overline a^{-1}$. \index{Elemento inverso!en congruencias}
\end{prop}
\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Siempre hay que tener en la cabeza el teorema de Bezout}  \textbf{Demo:}  Supongamos que $\overline a$ es inversible en $\ZZ_n$, entonces existe $\overline b\in \ZZ_n$
tal que $$\overline a\ \overline b=\overline 1,\quad\hbox{ es decir,}\quad  ab\equiv 1\ (\Mod n)$$ o lo que es lo mismo
$ab-1=cn$. Por tanto, $ab+(-c)n=1$, luego $\mcd(a,n)=d$ divide a $1$, lo que implica $\mcd(a,n)=1$. Por otro lado, si
$\mcd(a,n)=1$, aplicando el Teorema de Bezout existen $r,s\in \ZZ$ tales que $ar+cn=1$ o lo que es lo mismo, $ar-1=-sn$,
$(ar\equiv 1\ (\Mod n)$) es decir, $\overline a\ \overline r=\overline {ar}=\overline 1$.

Por último, si $\overline b,\overline b'$ son inversos para $\overline a$, $$\overline b=\overline b\ \overline
1=\overline b(\overline a\ \overline b')=(\overline b\ \overline a)\overline b'=\overline 1\ \overline b'=\overline
b'.$$ Lo que demuestra la unicidad.\hfill $\blacksquare$

\begin{coro}\rm \label{Zncuerpo} Sea $\ZZ_n$ el anillo de congruencias módulo $n$ (con $n\in \NN$). Entonces, las siguientes condiciones son equivalentes:
\begin{enumerate}
\item[(i)] Todo elemento no nulo de $\ZZ_n$ es inversible.
\item[(ii)] $n$ es un número primo.
\item[(iii)] Para todo par de elementos no nulos  $\overline a,\overline b$ de $\ZZ_n$, $\overline a\ \overline b\ne \overline 0$.
\end{enumerate}
\end{coro}
\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Es una comprobación, lo deberías de demostrar sin problemas}
 \textbf{Demo:}  (ii) $\implies$ (i). Por el resultado anterior, si $n$ es primo, para todo $0<k<n$,
$\mcd(n,k)=1$ y por tanto
 $\overline k$ es inversible en $\ZZ_n$.

 (i)\ $\implies$ (ii). Supongamos que todo elemento no nulo de $\ZZ_n$ es inversible. Entonces,
  para todo $k\in \NN$, $0<k<n$, se tiene que $\mcd(k,n)=1$. Por tanto $n$ no es divisible por ningún $k$ tal que $0<k<n$. Así, $n$ es primo.

(i)\ \ \,$\implies$ (iii). Sean $\overline a,\overline b\in \ZZ_n$ tales que $\overline a\ \overline b=\overline 0$. Si
 $\overline a= \overline 0$ no hay nada que demostrar, por tanto supongamos  $\overline a\ne \overline 0$. Entonces,  $\overline a$
  es inversible en $\ZZ_n$, sea
 $\overline a^{-1}\in \ZZ_n$ y por tanto, $$\overline 0=\overline a^{-1}\cdot \overline 0=\overline a^{-1} (\overline a\ \overline b)=
 (\overline a^{-1} \ \overline a) \overline b=\overline 1 \overline b$$

(iii) $\implies$ (ii). Por reducción al absurdo, supongamos que $n$ no es primo. Entonces existen $a,b\in \ZZ$,
$1<a,b<n$ tales que $n=ab$. Pero entonces $\overline a, \overline b$ son no nulos y $\overline a\  \overline
b=\overline n=\overline 0$, una contradicción. \hfill $\blacksquare$


\hypertarget{Tfer}{ }\label{Tfer}
\begin{theo}[Teorema de Fermat(chico)]
Sea $p,x\in \NN$ con $p$ un número primo y $\mcd(p,x)=1$. Entonces $x^{p-1}\equiv 1\ (\Mod p)$.
\end{theo}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=azul]{Plantea tu lo que te hace falta recordar}
 \textbf{Demo:}  Sea $\overline x\in \ZZ_p$. Como $\mcd(p,x)=1$, $\overline x$ es inversible en $\ZZ_p$, sea
$\overline y$ su inverso. En estas condiciones tenemos que la aplicación  $\Psi_x:\ZZ_p\to \ZZ_p$ definida por
$\Psi_x(\overline a)=\overline x\ \overline a$ es inversible con inversa $\Psi_y$. Por tanto, \hfill

$${\ZZ_p}=\im \Psi_x=\{\overline x\  \overline 1,\overline x\  \overline 2,\dots, \overline x\  \overline {p-1}\}$$

Luego $\prod_{k=1}^{p-1}\overline k=\prod_{k=1}^{p-1}\overline x\ \overline k=\overline x^{p-1}\
\prod_{k=1}^{p-1}\overline k$. Por último, como $\prod_{k=1}^{p-1} \overline k$ es un elemento no nulo de $\ZZ_p$, multiplicando
por su inverso, $\overline x^{p-1}=\overline 1$ es decir, $x^{p-1}\equiv 1\ (\Mod p)$. \hfill
$\blacksquare$

Podemos encontrar una generalización de este teorema para cualquier número Natural, es el llamado Teorema de Euler:

\begin{defi}\rm
Se define la \textbf{función de Euler}\index{Función de Euler}\nomenclature{$\varphi(n)$}{Función de Euler} como  $\varphi:\NN\to \NN$ definida por:
$$\varphi(n)=\#\{a\in \NN\ \vert\ 1\le a\le n,\ \mcd(a,n)=1\}$$
Por ejemplo, $\varphi(10)=4$ o si $p$ es un número primo, $\varphi(p)=p-1$.
\end{defi}

\begin{prop}\rm
 $\varphi(n)$ coincide con el número de elementos inversibles en $\ZZ_n$
\end{prop}

\begin{prop}[Ejercicio]\rm
Sea $\varphi:\NN\to \NN$ la función de Euler. Entonces
 \begin{enumerate}
   \item[(i)] Si $p$ es un número primo y $r\in \NN$, entonces $\varphi(p^r)=p^r(1-\frac1p)=p^r-p^{r-1}$.
   \item[(ii)] Si $n,m\in \ZZ$ con $\mcd(n,m)=1$, entonces $\varphi(nm)=\varphi(n)\varphi(m)$.
   \item[(iii)] Si $n\in \ZZ$, ($n\ne 0,1,-1$) se factoriza como producto de primos $n=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k}$, entonces
$$\varphi(n)=n(1-\frac1{p_1})(1-\frac1{p_2})\cdots (1-\frac1{p_k})$$
 \end{enumerate}
\end{prop}



\begin{theo}[Teorema de Euler]
Sean $n,x\in \NN$ con  $\mcd(n,x)=1$. Entonces $x^{\varphi(n)}\equiv 1\ (\Mod n)$.
\end{theo}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{La demostración es casi idéntica a la del teorema de Fermat}
 \textbf{Demo:} La demostración es muy similar a la demostración del teorema de Fermat. Consideremos $\Delta$ el conjunto de los elementos inversibles de $\ZZ_n$. Sea $\overline x\in \ZZ_n$. Como $\mcd(n,x)=1$, $\overline x$ es inversible en $\ZZ_p$, sea
$\overline y$ su inverso. En estas condiciones tenemos que la aplicación  $\Psi_x: \Delta\to \Delta$ definida por
$\Psi_x(\overline a)=\overline x\ \overline a$, está bien definida, y es inversible con inversa $\Psi_y$. Por tanto,
$$\Delta=\im \Psi_x=\{\overline x\  \overline a\ \vert \ \overline a\in  \Delta\}$$



Luego $\prod_{a\in \Delta}\overline a=\prod_{a\in \Delta}\overline x\ \overline a=\overline x^{\varphi(n)}\
\prod_{a\in \Delta}\overline a$. Por último, como $\prod_{a\in \Delta} \overline a$ es un elemento inversible de $\ZZ_p$, multiplicando
por su inverso, $\overline x^{\varphi(n)}=\overline 1$ o lo que es lo mismo, $x^{\varphi(n)}\equiv 1\ (\Mod n)$. \hfill
$\blacksquare$

\timeclase{Fin de clase 13; 28-10-2011, grupo A y B (clase día 27 se recuperará. Martes 1 Fiesta. Jueves y viernes en congreso en Zaragoza. Recuperar 3 dias)}

\subsection{Sistemas de ecuaciones en congruencias}

\hypertarget{Econg}{ }\label{Econg}
\begin{ejem} \rm Estudiemos ahora ecuaciones en los anillos de congruencias $\ZZ_n$. Supon\-ga\-mos que queremos encontrar las
soluciones de la ecuación $$\overline 3 \overline x=\overline 5\quad \hbox{en }\ZZ_6.\eqno{(1)}$$ o  lo que es lo
mismo, $3x\equiv 5\ (\Mod 6)$. En estos momentos la única posibilidad que tenemos es comprobar, sustituyendo, si tiene
o no tiene soluciones:
\[\begin{split}
3\cdot 0\equiv 0\ (\Mod 6),&\quad 3\cdot 1\equiv 3\ (\Mod 6),\quad 3\cdot 2\equiv 0\ (\Mod 6),\\\quad 3\cdot 3\equiv 3\
(\Mod 6),&\quad  3\cdot 4\equiv 0\ (\Mod 6),\quad 3\cdot 5\equiv 3\ (\Mod 6)
\end{split}\]
luego no tiene soluciones. Sin embargo, la ecuación  $$\overline 6 x=\overline 4\quad\hbox{en } \ZZ_8.\eqno{(2)}$$
tiene por soluciones $x=2$ y $x=6$:
\[\begin{split}
6\cdot 0\equiv 0\ (\Mod 8),&\quad 6\cdot 1\equiv 6\ (\Mod 8),\quad 6\cdot 2\equiv 4\ (\Mod 8),\\
6\cdot 3\equiv 2\ (\Mod 8),&\quad 6\cdot 4\equiv 0\ (\Mod 8),\quad 6\cdot 5\equiv 6\ (\Mod 8),\\
\quad 6\cdot 6\equiv 4\ (\Mod 8),&\quad  6\cdot 7\equiv 2\ (\Mod 8),
\end{split}\]

\textbf{Nota:} Observar que, ``simplificando" \  la ecuación anterior por $2$,  $\overline  3x=\overline 2$, tiene una
única solución $x=6$ (luego $x=2$ ha dejado de ser solución!!).
\end{ejem}


\begin{prop}\rm
Sean $n_1,n_2,\dots, n_k,r,s,u,v,n,m\in \ZZ$ elementos no nulos.
\begin{enumerate}
 \item[(i)] Supongamos que para cada $i\in \{1,2,\dots,k\}$, $\mcd(s,
n_i)=1$ y sea $m=\prod_{i=1}^k n_i$.  Entonces $\mcd(s, m)=1$.
\item[(ii)] Si $s$ divide a $uv$, y $\mcd(s,u)=1$, entonces $s$ divide a $v$.
\item[(iii)] Si $^n\vert_s$ y $^m\vert_s$ con $\mcd(n,m)=1$, entonces $^{nm}\vert s$
\item[(iv)] Si $\mcd(n,m)=d$, y sean $n'$ y $m'$ tales que  $n=n' d$ y $m=m'd$. Entonces $\mcd(n',m')=1$.
\end{enumerate}
\end{prop}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Lo debes de demostrar sin problemas. Recuerda Bezout}
 \textbf{Demo:} (i) Sea $d=\mcd(s, m)$. Por reducción al absurdo, supongamos que $d>1$. Entonces podemos factorizar $d$ como producto de primos. Sea $p$ uno de los primos que aparece en la factorización de $d$.  Tenemos entonces que $d$ divide a $s$ y de divide a $m=\prod_{i=1}^k n_i$. Luego por la \fullref{proposición}{divprodprim}{} existe un $k$ tal que $p$ divide a $n_k$ (si un primo $p$ divide a un producto de números, entonces divide a alguno de ellos). Pero entonces ($^p\vert_s$ y $^p\vert_{n_k}$), $p$ divide a $\mcd(s,n_k)=1$, una contradicción. Por tanto $d=1$.

 (ii) Si $\mcd(s,u)=1$ y $vu=\gamma s$, por Bezout existen $\alpha, \beta\in\ZZ$ tales que $\alpha s+\beta u=1$. Si multiplicamos ahora por $v$,
$$v=\alpha s v+\beta u v=\alpha s v+\gamma s=(\alpha  v+\gamma) s$$
Lo que demuestra que $s$ divide a $v$.

(iii) Por hipótesis $s=\alpha m$ y $s=\beta n$. Aplicando el Teorema de Bezout, existen $x,y\in \ZZ$ tales que $xn+ym=1$. Por tanto, multiplicando esta igualdad por $s$ obtenemos
$$s=sxn+sym=\alpha mxn+\beta n ym=(\alpha x+\beta y)nm$$
Por tanto $s$ es divisible por $nm$.

(iv)  Por el teorema de existencia del máximo común divisor, existen $r,s\in\ZZ$ tales que $$d=rn+sm=rn'd+sm'd=(rn'+sm')d.$$ Aplicando ahora la ley de simplificación en $\ZZ$ tenemos que $rn'+sm'=1$, por lo que por el Teorema de Bezout, $\mcd(n'.m')=1$.\hfill $\blacksquare$

\textbf{Nota:} Podemos pensar en una ecuación $\overline a \cdot x=\overline b$ en $\ZZ_n$, el anillo de congruencias módulo $n$, con $n\in \NN$, o podemos pensar en la ecuación en congruencias $ax\equiv b\ (\Mod n)$. En ambos casos se trata del mismo problema, en el primero las soluciones serán elementos de $\ZZ_n$ ( con lo que con dar un representante de cada solución es suficiente. En el segundo tenemos que dar todos los elementos de $\ZZ$ que verifican la ecuación, que no es más que cualquier representante de las soluciones en $\ZZ_n$: Así,

$\bullet$ La ecuación $\overline 3\cdot x=\overline 4$ en $\ZZ_5$ tiene por solución $x=\overline 3\in \ZZ_5$.

$\bullet$ La ecuación $3x\equiv 4\ (\Mod 5)$ tiene por solución el conjunto $$S=\{\cdots,-12,-7,-2,3,8,13,\cdots\}.$$
Que no es más que el conjunto definido por $\overline 3$.

Trabajaremos indistintamente con una ecuación que con otra. Cuando se hable sobre el numeró de soluciones de alguna de estas ecuaciones nos estaremos refiriendo al número de soluciones en $\ZZ_n$ (ya que en $\ZZ$ o no tiene soluciones o son infinitas)



\begin{theo}\rm
Sean $n\in \NN$ y $a,b\in \ZZ$. Entonces las siguientes condiciones son equivalentes:
\begin{enumerate}
\item[(i)] La ecuación $ax\equiv b\ (\Mod n)$ tiene solución.
\item[(ii)] El máximo común divisor de $a$ y $n$ divide a $b$.
\end{enumerate}
Es más, el número de soluciones de la ecuación (en $\ZZ_n$) es exactamente el $\mcd(a,n)$.
\end{theo}

\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Recuerda Bezout}
 \textbf{Demo:} Denotemos por $d=\mcd(a,n)$. Supongamos que $s\in \ZZ$ es solución de la ecuación $$ax\equiv b\ (\Mod n).$$
Entonces existe $ \alpha\in\ZZ$ tal que $as-b=\alpha n$. Por tanto $b=as-\alpha n$. Ahora, como $a$ y $n$ son
divisibles por $d$ (esto es por definición), $b$ es divisible por $d$.

Supongamos ahora que $b$ es divisible por $d$, $b=\beta d$. Por \fullref{el Teorema}{mcd}{} existen $r,s\in \ZZ$ tales que $d=ra+sn$. Si multiplicamos por $\beta $ en esta igualdad obtenemos que  $b=\beta d=\beta (ra+sn)$, lo que implica que  $\beta r a-b=\beta sn$, o lo que es lo mismo,  $a(\beta r)\equiv b\ (\Mod n)$, es decir, $\beta r$
es solución de la ecuación.

Demostremos ahora el además: Supongamos que la ecuación  $ax\equiv b\ (\Mod n)$ tiene solución, sea $s$ una solución de la ecuación. Por lo anterior sabemos que  $d=\mcd(a,n)$ divide a $b$. Sean $\alpha, \gamma\in \ZZ$ tales que $n=\gamma d$, $a=\alpha d$. Veamos que $s+\gamma$ es también solución de la ecuación.
$$a(s+\gamma)=as+a\gamma\equiv b+a\gamma=b+\alpha d \gamma=b+\alpha n\equiv b\ (\Mod n)$$

Luego para todo $k\in \mathbb{N}$, $s+k\gamma$ es solución. Como nos estamos preocupando de las soluciones módulo $n$, la solución $s+d\gamma=s+n\equiv s\ (\Mod n)$ por lo que $k$ toma los valores $0\le k\le d-1$. Por tanto, como mucho tenemos las siguientes $d$ soluciones  $$\{s,s+\gamma,s+2\gamma,\dots,s+(d-1)\gamma\}$$
Observar que todas son distintas, módulo $n$, ya que si $$0\le t_1<t_2\le d-1\hbox{ y }s+t_1\gamma\equiv s+t_2\gamma\ (\Mod N),$$ entonces $0\le (t_2-t_1)\gamma\le t_2\gamma<d\gamma=n$ y por tanto como $(t_2-t_1)\gamma=\dot n$ (es múltiplo de $n$) éste tiene que ser cero, una contradicción, $t_1=t_2$.

Por último, si $s'$ es solución del sistema, $a(s'-s)\equiv 0\ (\Mod n)$ y por tanto $a(s'-s)=\tau n$ dividiendo en esta igualdad por $d$ obtenemos $$d\alpha(s'-s)=a(s'-s)=\tau n=\tau \gamma d$$ por lo que $\alpha(s'-s)=\tau \gamma$ y como $\mcd(\alpha,\gamma)=1$, por la proposición anterior,  $\gamma$ divide a $s'-s$ por lo que $ s'-s=\xi \gamma$ y por tanto $s'=s+\xi \gamma$ es una de las soluciones anteriores.
\hfill $\blacksquare$

El siguiente resultado nos va a permitir calcular más fácilmente las soluciones de una ecuación en congruencias cuando el número de soluciones (En $\ZZ_n$) es mayor que 1:

\begin{prop}[Ejercicio]
  Sean $a,b\in \ZZ$ y $n\in \NN$. Supongamos que $1<\mcd(a,n)=d$ y que $d$ divide a $b$. Tenemos entonces que $a=da'$, $n=dn'$ y $b=db'$. Entonces el conjunto de soluciones en $\ZZ$ de las siguientes  ecuaciones coincide  $$ax\equiv b\ (\Mod n)\qquad a'x\equiv b'\ (\Mod n')$$
\end{prop}
\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Trivial.}
 \textbf{Demo:} Sea $s\in \ZZ$ una solución de $ax\equiv b\ (\Mod n)$. Entonces $as-b=\dot n$, por lo que existe $\alpha\in\ZZ$ tal que $as-b=\alpha n$. Es decir, $a'dx-db'=\alpha dn'$. Si simplificamos ahora por $d$ tenemos que $a'x-b'=\alpha n'$, lo que demuestra que $s$ es solución de la ecuación $a'x\equiv b'\ (\Mod n')$.

  Sea $s\in \ZZ$ una solución de $a'x\equiv b'\ (\Mod n')$. Entonces  existe $\beta\in\ZZ$ tal que $a's-b'=\beta n'$. Si multiplicamos ahora esta igualdad por $d$ tenemos, $a'dx-db'=\alpha dn'$. Es decir, $as-b=\beta n$, lo que demuestra que $s$ es solución de la ecuación $ax\equiv b\ (\Mod n)$. \hfill $\blacksquare$

\textbf{Nota:} La proposición anterior es muy útil a la hora de resolver ecuaciones en congruencias: Resuelve la ecuación en congruencias $$4x\equiv 4 \ (\Mod 8)$$
Como $\mcd(4,8)=4$ y $4$ divide a $4$, esta ecuación tiene solución, es más, modulo $8$ el número de soluciones es $4$. Por la proposición anterior,
esta ecuación tiene las mismas soluciones en $\ZZ$ que la ecuación $$x\equiv 1\  (\Mod 2)$$ que claramente es el conjunto $$\{1+2k,\quad k\in \ZZ\}.$$
Por tanto las soluciones distintas en $\ZZ_8$ son $\{\overline 1,\overline 3,\overline 5,\overline 7\}$ ($\overline 9$ ya coincide con $\overline 1$ en $\ZZ_8$).

\timeclase{Fin de clase 14; 8-11-2011, grupo A y B}


\begin{theo}\rm
Sean $n_1,n_2,\dots, n_k\in \NN$ y $a_1,a_2,\dots, a_k\in \ZZ$. Supongamos que $\mcd(n_i,n_j)=1$ para todo $i,j\in
\{1,2,\dots, k\}$, $i\ne j$. Entonces el sistema de ecuaciones:
\[\begin{split}
x\equiv& a_1\ (\Mod n_1)\\
x\equiv& a_2\ (\Mod n_2)\\
\qquad \vdots\\
x\equiv& a_k\ (\Mod n_k)\\
\end{split}\]
Tiene solución. Es más,  ésta es única modulo $m=\prod_{i=1}^k n_i$.
\end{theo}
\noindent \pdfcomment[icon=Check,hspace=0.5 truecm,author={Puntos clave},markup=Underline,color=verde]{Es una demostración constructiva, con lo que simplemente tienes que acordarte del algoritmo para resolver casos concretos}
 \textbf{Demo:} Vamos a dar una demostración constructiva, lo que nos servirá para resolver casos concretos.
Construimos $k$ y resolvemos $k$ ecuaciones en congruencias independientes: sean $m_i=m/n_i$ y consideremos las
ecuaciones (independientes)
$$m_ix\equiv a_i\ (\Mod n_i)\qquad \hbox{para, }\ i=\{1,2,\dots, k\}$$

Sea $s_r$ solución de la ecuación $r$-esima ecuación, $m_rx\equiv a_r\ (\Mod n_r)$. Veamos que $s=\sum_{i=1}^k m_i s_i$
es solución de nuestro sistema.

$$s= \sum_{i=1}^k m_i s_i\equiv m_r s_r\equiv a_r\ (\Mod n_r)\quad \hbox{para todo $r\in \{1,2,\dots, k\}$}$$

Supongamos ahora que $s$ y $s'$ son soluciones del sistema. Entonces como $s\equiv a_i\ (\Mod n_i)$ y $s'\equiv a_i\
(\Mod n_i)$, $$s-s'\equiv 0 \ (\Mod n_i).\eqno{(1)}$$

Por último, veamos, aplicando un proceso de inducción, que $s-s'$ es divisible por $m$: si $k=1$ no tenemos nada que
demostrar, por (1),  $s-s'$ es divisible por $n_1$. Supongamos que el resultado es cierto para $k-1$ y demostrémoslo
para $k$: por hipótesis  $s-s'$ es divisible por $\prod_{1=1}^{k-1}n_i$ y por (1) $s-s'$ es divisible por $n_k$. Luego
como $\mcd(\prod_{1=1}^{k-1}n_i,n_k)=1$, por la proposición anterior, $s-s'$ es divisible por
$(\prod_{1=1}^{k-1}n_i)n_k=m$, lo que demuestra el teorema. \hfill $\blacksquare$



$\bigstar$ Los ejercicios del 22 al 39 de este tema pueden servirte para comprobar si has asimilado las nociones de esta sección.

\vfill\eject
\hypertarget{Ejjuno}{ }
\section{Ejercicios de Tema}\label{Ejjuno}
\setcounter{ejj}{0}

\begin{ejj}\rm
Demuestra que para todo $n\in \NN$, $1+2+\cdots+n=\frac{n(n+1)}{2}$
\end{ejj}

\begin{ejj}\rm
Encuentra un modelo que verifique los 4 primeros axiomas de Peano pero no el principio de inducción matemática.\hfill \fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Encuentra un modelo que verifique los  axiomas 1,2,4,5 de Peano. \hfill \fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Encuentra un modelo que verifique los  axiomas 1,2,3,5 de Peano. \hfill \fbox{$*$}
\end{ejj}

\begin{ejj}\label{multmenor}\rm
Sean $x,y\in \mathbb{N}\cup \{0\}$. Demuestra que si $x$ es múltiplo de $y$ y $x<y$, entonces $x=0$
\end{ejj}

\begin{ejj}\label{unosoloprod}\rm
Demuestra que $1$ solo es divisible por $1$ y $-1$.
\end{ejj}

\begin{ejj}\label{lemasiete7}
  Sean $x,y,a,b\in \ZZ$, Entonces:
  \begin{enumerate}
    \item[(i)] Si $^x\vert_y$, entonces $\mcd(x,y)=|x|$.
    \item[(ii)] Si $^x\vert_a$ y $^x\vert_b$, entonces $^x\vert_{\alpha a+\beta b}$ para todo $\alpha,\beta\in \ZZ$.
  \end{enumerate}
\end{ejj}

\begin{ejj}\label{ejjdos2}\rm
Demuestra que la relación de divisibilidad es reflexiva, transitiva y verifica que para todo $a,b\in \ZZ$,
$$^a\vert _b \hbox{ y } ^b\vert _a\quad \hbox{entonces } a=\pm b.$$
Por tanto es una relación de orden en $\NN$. ¿Quien es el supremo y el ínfimo de dos elementos $a,b\in \NN$?
\end{ejj}

\begin{ejj}\rm
Demuestra que el máximo común divisor de dos enteros no nulos $x,y\in \ZZ$. coincide con el producto de los primos
comunes elevados al menor exponente.
\end{ejj}

\begin{ejj}\rm
Sean $p_1,p_2,\cdots, p_k$ números primos. Demuestra que en la factorización de $p_1\cdots p_k+1$ no aparece ninguno de los primos anteriores.
\end{ejj}

\begin{ejj}\rm
Sean $0\ne a,b\in \ZZ$  tales que $3a+8b=2$. Entonces $\mcd(b,3)=1$.
\end{ejj}

\begin{ejj}\rm  Demuestra los siguientes criterios de divisibilidad:
\item{\quad $\bullet$} $x$ es divisible por $2$ si y sólo si su última cifra es divisible por $2$.
\item{\quad $\bullet$} $x$ es divisible por $8$ si y sólo si sus tres últimas cifras son divisibles por $8$.
\item{\quad $\bullet$} $x$ es divisible por $3$ si y sólo si la suma de sus cifras es divisible por $3$.
\item{\quad $\bullet$} $x$ es divisible por $11$ si y sólo si la suma de sus cifras en posición par  menos la suma de sus cifras en posición impar es divisible por $11$.
\end{ejj}

\begin{ejj}\rm
  El algoritmo de la división dice que dados $x,y\in \ZZ$ con $y>0$ existen unos únicos $c,r\in \ZZ$ con $0\le r<y$ tales que $x=cy+r$. Demuestra que el resultado también es cierto si $y<0$, es decir: Demuestra que dados $x,y\in \ZZ$ con $y\ne 0$ existen unos únicos $c,r\in \ZZ$ con $0\le r<\vert y\vert$ tales que $x=cy+r$.
\end{ejj}

\begin{ejj}\rm
Sean $a,b$ dos elementos no nulos de $\ZZ$ y sean $s,r\in \ZZ$ tales que $sa+rb=\mcd(a,b)$. Demuestra que $r$ y $s$ son primos relativos. \hfill \fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Sean $x,y,r,s\in \ZZ$ no nulos tales que $rx+sy=1$. Demuestra que $$\mcd(x,y)=\mcd(x,s)=\mcd(r,y)=\mcd(r,s)=1.$$
¿Que se puede decir del $\mcd(r,x)$?
\end{ejj}

\begin{ejj}\rm
Sean $n,m,s\in \ZZ$ no nulos tales que $\mcd(n,s)=1$. Supongamos que $s$ divide al producto $n\cdot m$. Demuestra
entonces que $s$ divide a $m$. ¿Es cierto el resultado si $s$ y $n$ no son primos relativos?
\end{ejj}

\begin{ejj}[Teorema Generalizado de Bezout]\rm
Sean $n_1,n_2,\dots, n_k\in \NN$ tales que si $k\in \mathbb{N}$ divide a todo $n_i$, entonces $k=1$.  Demuestra que existen $\alpha_1,\alpha_2,\dots,\alpha_k\in \ZZ$ tales que $\alpha_1 n_1+\alpha_2 n_2+\cdots+\alpha_k n_k=1$.\hfill \fbox{$**$}
\end{ejj}


\begin{ejj}\rm
Sean $n_1,n_2,\dots, n_k,s\in \ZZ$ elementos no nulos. Supongamos que para cada $i\in \{1,\dots,k\}$, $\mcd(s,
n_i)=1$. Demuestra $\mcd(s, \prod_{i=1}^k n_i)=1$.
\end{ejj}

\begin{ejj}\rm
Demuestra que existe el mínimo común múltiplo de dos elementos no nulos $x,y\in \ZZ$ y que éste es único.\hfill \fbox{$*$}
\end{ejj}




\begin{ejj}\rm
Sean $n,m$ dos elementos no nulos de $\ZZ$. Demuestra que $$\mcd(n,m).\MCM(n,m)=\vert n\cdot m\vert.$$
\end{ejj}

\begin{ejj}\rm
Sean $a,b\in \ZZ$. Demuestra que nunca puede suceder que $6a+21b=\mcd(a,b)$.\hfill \fbox{$*$}
\end{ejj}


\begin{ejj}\rm
Sea $n\in \NN$ y $a,b\in \ZZ$. Demuestra que la ecuación $ax\equiv b\ (\Mod n)$ tiene una única solución si y sólo si
$\mcd(a,n)=1$.\hfill \fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Calcula el resto de dividir $11^{1151}$ entre $7$ y de dividir $13^{1111}$ entre 15.
\end{ejj}


\begin{ejj}\rm
Si es martes y trece y la luna está llena, ¿Cuantos dias habrá que esperar para que sea
viernes con luna nueva? (ciclo lunar 30 dias)\hfill \fbox{$*$}
\end{ejj}
% El sistema de congruencias es $2+k\equiv 5 (mod 7)$ y $13+k\equiv 28 (mod 30)$ Solución 45 dias.



\begin{ejj}\rm
Demuestra que en $\ZZ_n$ no de da la ley de simplificación: Existen $a,b,c$ elementos no nulos de $\ZZ_n$ (para algún $n$) tal que  $$\overline a\ \overline b=\overline a\ \overline c\quad \hbox{ y } \quad \overline b\ne \overline c$$
\end{ejj}

\begin{ejj}\rm
Sea $\varphi:\NN\to \NN$ la función de Euler. Entonces \hfill \fbox{$***$}
 \begin{enumerate}
   \item[(i)] Si $p$ es un número primo y $r\in \NN$, entonces $\varphi(p^r)=p^r(1-\frac1p)=p^r-p^{r-1}$.
   \item[(ii)] Si $n,m\in \ZZ$ con $\mcd(n,m)=1$, entonces $\varphi(nm)=\varphi(n)\varphi(m)$.
   \item[(iii)] Si $n\in \ZZ$, ($n\ne 0,1,-1$) se factoriza como producto de primos $n=p_1^{n_1}p_2^{n_2}\cdots p_k^{n_k}$, entonces
$$\varphi(n)=n(1-\frac1{p_1})(1-\frac1{p_2})\cdots (1-\frac1{p_k})$$
 \end{enumerate}
\end{ejj}

\begin{ejj}\rm
Resuelve el siguiente sistema de ecuaciones en congruencias:
\[\left\{\begin{split}
4x\equiv& 5\ (\Mod 9)\\
5x\equiv& 2\ (\Mod 24)
\end{split}\right.\]
\end{ejj}

\begin{ejj}\rm
Resuelve el siguiente sistema de ecuaciones en congruencias:
\[\left\{\begin{split}
2x\equiv& 3\ (\Mod 5)\\
3x\equiv& 5\ (\Mod 13)
\end{split}\right.\]
\end{ejj}

\begin{ejj}\rm
Calcula las dos últimas cifras del número $21^{3553}$.
\end{ejj}

\begin{ejj}\rm
Calcula las soluciones de los siguientes sistemas (caso de que tengan):
\vskip.5truecm
\begin{tabular}{lll}
  (a). $2x\equiv 3\ (\Mod 5)$&  (b). $15x\equiv 3\ (\Mod 6)$ &  (c). $21x\equiv 14\ (\Mod 35)$ \\
   (d). $4x\equiv 10\ (\Mod 8)$ &  (e). $6x\equiv 6\ (\Mod 12)$ &  (f). $x^2\equiv 3\ (\Mod 7)$ \\
\end{tabular}
\end{ejj}

\begin{ejj}\rm
¿Las ecuaciones $\overline 9\cdot x=\overline{15}$, $\overline 3\cdot x=\overline{5}$ y $\overline 6\cdot x=\overline{10}$ tienen las mismas soluciones en $\ZZ_{12}$? ¿Explica la razón?
\end{ejj}

\begin{ejj}\rm
Sea $n\in \NN$ y sea $\overline z\in \ZZ_n$ con $\mcd(z,n)=1$. Demuestra que las ecuaciones $$a\cdot X\equiv b\ (\Mod n)\quad \text{ y }\quad za\cdot X\equiv zb\ (\Mod n)$$ tienen las mismas soluciones.
\end{ejj}

\begin{ejj}\rm
Sea $n\in \NN$ sea $\overline a\in \ZZ_n$. Se dice que un elemento $0\ne \overline b\in \ZZ_n$ es un divisor de cero de $\overline a$ si $\overline a\cdot \overline b=\overline 0$. Demuestra que el número de divisores de cero de $\overline a$ en $\ZZ_n$ coincide con $\mcd(a,n)-1$.\hfill \fbox{$*$}
\end{ejj}

\begin{ejj}\rm
Resuelve los siguientes sistemas de ecuaciones en congruencias:
\[\left\{\begin{split}
2x\equiv& 3\ (\Mod 6)\\
3x\equiv& 5\ (\Mod 9)
\end{split}\right. \qquad
\left\{\begin{split}
2x\equiv& 2\ (\Mod 6)\\
3x\equiv& 6\ (\Mod 9)
\end{split}\right.\qquad
\left\{\begin{split}
x\equiv& 2\ (\Mod 5)\\
x\equiv& 6\ (\Mod 7)
\end{split}\right.\]
\end{ejj}

\begin{ejj}\rm
Resuelve los siguientes sistemas de ecuaciones en congruencias:
\[\left\{\begin{split}
x\equiv& 1\ (\Mod 2)\\
x\equiv& 2\ (\Mod 3)\\
x\equiv& 3\ (\Mod 5)\\
x\equiv& 4\ (\Mod 7)
\end{split}\right.\]
\end{ejj}

\begin{ejj}\rm
  Calcula todas las soluciones de la ecuación $x^6\equiv 1\ (\Mod 7)$. Explica el resultado.
\end{ejj}

\begin{ejj}\rm
  Sean $a,b\in \ZZ$ y $n\in \NN$. Supongamos que $1<\mcd(a,n)=d$ y que $d$ divide a $b$. Tenemos entonces que $a=da'$, $n=dn'$ y $b=db'$. Entonces el conjunto de soluciones en $\ZZ$ de las siguientes  ecuaciones coincide  $$ax\equiv b\ (\Mod n)\qquad a'x\equiv b'\ (\Mod n')$$
\end{ejj}

\begin{ejj}\rm
Una pecera es limpiada cada 29 dias y a los peces se les dá de comer cada 4. Si hace 3 dias que han comido y 15 que se les ha limpiado la pecera, ¿Cuantos días tienen que esperar los peces para que se les limpie y coman el mismo día?
\end{ejj}

\begin{ejj}\rm Sabemos que $\overline{40}=\overline{74}=-\overline{45}$ en $\ZZ_n$ ¿Quien puede ser $n$?\end{ejj}

\begin{ejj}\rm \label{ejjcuatro}
¿Es un  conjunto la colección de los números naturales que se pueden describir con menos de 15 palabras en castellano?\hfill  \fbox{$***$}
\end{ejj} 