#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\use_default_options true
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style swiss
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Section
Aritmética de los enteros
\end_layout

\begin_layout Standard
Propiedades de 
\begin_inset Formula $\mathbb{Z}$
\end_inset

:
\end_layout

\begin_layout Enumerate

\series bold
Unicidad de los neutros:
\series default
 
\begin_inset Formula $\exists!0\in\mathbb{Z}:\forall a\in\mathbb{Z},0+a=a$
\end_inset

; 
\begin_inset Formula $\exists!1\in\mathbb{Z}:\forall a\in\mathbb{Z},1a=a$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Unicidad de los opuestos:
\series default
 
\begin_inset Formula $\forall a\in\mathbb{Z},\exists!(-a)\in\mathbb{Z}:a+(-a)=0$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Cancelación en sumas:
\series default
 
\begin_inset Formula $\forall a,b,c\in\mathbb{Z},(a+b=a+c\implies b=c)$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Multiplicación por cero:
\series default
 
\begin_inset Formula $\forall a\in\mathbb{Z},a0=0$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Reglas de signos:
\series default
 
\begin_inset Formula $\forall a,b\in\mathbb{Z},(-(-a)=a\land a(-b)=(-a)b=-(ab)\land(-a)(-b)=ab)$
\end_inset

.
\end_layout

\begin_layout Enumerate

\series bold
Cancelación en productos:
\series default
 
\begin_inset Formula $\forall a,b,c\in\mathbb{Z},a\neq0,(ab=ac\implies b=c)$
\end_inset

.
\end_layout

\begin_layout Standard

\series bold
Teorema de la división entera:
\series default
 
\begin_inset Formula $\forall a,b\in\mathbb{Z},\exists!q,r\in\mathbb{Z}:(a=bq+r\land0\leq r<|b|)$
\end_inset

.
 Llamamos a 
\begin_inset Formula $q$
\end_inset

 el 
\series bold
cociente
\series default
 de la división y a 
\begin_inset Formula $r$
\end_inset

 el 
\series bold
resto
\series default
\SpecialChar endofsentence
 
\series bold
Demostración:
\series default
 Sean 
\begin_inset Formula $a,b>0$
\end_inset

 y 
\begin_inset Formula $R=\{x\in\mathbb{Z}|x\geq0\land\exists n\in\mathbb{Z}\mid x=a-bn\}\subseteq\mathbb{N}$
\end_inset

.
 Sabemos que 
\begin_inset Formula $R\neq\emptyset$
\end_inset

 porque 
\begin_inset Formula $a=a-b\cdot0\in R$
\end_inset

.
 Por tanto tiene primer elemento 
\begin_inset Formula $r=a-bq\in R$
\end_inset

.
 Si 
\begin_inset Formula $r\geq b$
\end_inset

 entonces 
\begin_inset Formula $0\leq r-b\in R\#$
\end_inset

, luego 
\begin_inset Formula $r<b$
\end_inset

.
 Si 
\begin_inset Formula $a<0$
\end_inset

 y 
\begin_inset Formula $b>0$
\end_inset

 entonces 
\begin_inset Formula $-a>0$
\end_inset

 y 
\begin_inset Formula $-a=bq+r$
\end_inset

 con 
\begin_inset Formula $0\leq r<b$
\end_inset

.
 Si 
\begin_inset Formula $r=0$
\end_inset

, 
\begin_inset Formula $a=b(-q)+0$
\end_inset

, y si 
\begin_inset Formula $r\neq0$
\end_inset

, 
\begin_inset Formula $a=b(-q)-r=b(-q-1)+(b-r)$
\end_inset

.
 Si 
\begin_inset Formula $a\neq0$
\end_inset

 y 
\begin_inset Formula $b<0$
\end_inset

 entonces 
\begin_inset Formula $-b>0$
\end_inset

 y 
\begin_inset Formula $a=(-b)q+r$
\end_inset

 con 
\begin_inset Formula $0\leq r<-b=|b|$
\end_inset

, luego 
\begin_inset Formula $a=b(-q)+r$
\end_inset

 con 
\begin_inset Formula $0\leq r<|b|$
\end_inset

.
 Finalmente, si 
\begin_inset Formula $a=0$
\end_inset

 entonces 
\begin_inset Formula $0=b\cdot0+0$
\end_inset

.
 Para la unicidad de 
\begin_inset Formula $q$
\end_inset

 y 
\begin_inset Formula $r$
\end_inset

, supongamos 
\begin_inset Formula $a=bq+r=bq'+r'$
\end_inset

 con 
\begin_inset Formula $0\leq r,r'<|b|$
\end_inset

.
 Entonces 
\begin_inset Formula $b(q-q')=r-r'$
\end_inset

, con lo que 
\begin_inset Formula $|b||q-q'|=|r-r'|$
\end_inset

, pero como 
\begin_inset Formula $0\leq r,r'<|b|$
\end_inset

, entonces 
\begin_inset Formula $q-q'=0$
\end_inset

 y 
\begin_inset Formula $r-r'=0$
\end_inset

.
\end_layout

\begin_layout Standard
Decimos que 
\series bold

\begin_inset Formula $b$
\end_inset

 divide a 
\begin_inset Formula $a$
\end_inset


\series default
 o que 
\series bold

\begin_inset Formula $a$
\end_inset

 es múltiplo de 
\begin_inset Formula $b$
\end_inset


\series default
 (
\begin_inset Formula $b|a$
\end_inset

) si 
\begin_inset Formula $\exists c\in\mathbb{Z}:a=bc$
\end_inset

.
 Si 
\begin_inset Formula $a\neq0$
\end_inset

, también decimos que 
\series bold

\begin_inset Formula $b$
\end_inset

 es divisor de 
\begin_inset Formula $a$
\end_inset


\series default
.
 Para 
\begin_inset Formula $b\neq0$
\end_inset

, 
\begin_inset Formula $b|a$
\end_inset

 equivale a que la división entera de 
\begin_inset Formula $a$
\end_inset

 entre 
\begin_inset Formula $b$
\end_inset

 dé resto 0.
\end_layout

\begin_layout Enumerate
La divisibilidad es reflexiva y transitiva.
\end_layout

\begin_layout Enumerate
No es antisimétrica, pero 
\begin_inset Formula $a|b\land b|a\implies|a|=|b|$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|b\iff a|-b$
\end_inset

, con lo que si 
\begin_inset Formula $b\neq0$
\end_inset

, 
\begin_inset Formula $b$
\end_inset

 y 
\begin_inset Formula $-b$
\end_inset

 tienen los mismos divisores.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|b\iff-a|b$
\end_inset

, luego 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $-a$
\end_inset

 tienen los mismos múltiplos.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $c|a\land c|b\implies c|ra+sb$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|b\land c|d\implies ac|bd$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|b\implies ca|cb$
\end_inset

.
 El recíproco es cierto si 
\begin_inset Formula $c\neq0$
\end_inset

.
\end_layout

\begin_layout Enumerate
Si 
\begin_inset Formula $b\neq0$
\end_inset

, 
\begin_inset Formula $a|b\implies|a|\leq|b|$
\end_inset

.
\end_layout

\begin_layout Standard
Dados 
\begin_inset Formula $a,b\in\mathbb{Z}$
\end_inset

, su 
\series bold
máximo común divisor
\series default
 es 
\begin_inset Formula $\text{mcd}(a,b)=\max\{d\in\mathbb{Z}\mid d|a\land d|b\}$
\end_inset

 (excepción: 
\begin_inset Formula $\text{mcd}(0,0)=0$
\end_inset

).
 Este existe porque el conjunto de divisores comunes es no vacío (contiene
 al 1) y finito, luego tiene máximo.
 Propiedades:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcd}(a,b)=\text{mcd}(a,|b|)=\text{mcd}(|a|,|b|)$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcd}(a,0)=|a|$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcd}(a,b)=0\iff a=b=0$
\end_inset

.
\end_layout

\begin_layout Standard
Dados 
\begin_inset Formula $a,b\in\mathbb{Z}$
\end_inset

 con alguno distinto de 0, 
\begin_inset Formula $\text{mcd}(a,b)=\min\{ra+sb>0|r,s\in\mathbb{Z}\}$
\end_inset

, y todo divisor común de 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $b$
\end_inset

 lo es de 
\begin_inset Formula $\text{mcd}(a,b)$
\end_inset

.
 
\series bold
Demostración:
\series default
 Dado 
\begin_inset Formula $\emptyset\neq D=\{ra+sb>0|r,s\in\mathbb{Z}\}\subseteq\mathbb{Z}^{+}$
\end_inset

, existe 
\begin_inset Formula $\delta=\min D$
\end_inset

.
 Existen entonces 
\begin_inset Formula $\alpha,\beta\in\mathbb{Z}$
\end_inset

 tales que 
\begin_inset Formula $\delta=\alpha a+\beta b$
\end_inset

.
 Por el algoritmo de la división, 
\begin_inset Formula $a=\delta q+r$
\end_inset

 con 
\begin_inset Formula $0\leq r<\delta$
\end_inset

, luego 
\begin_inset Formula $r=(1-\alpha q)a+(-q\beta)b$
\end_inset

, luego 
\begin_inset Formula $r$
\end_inset

 es combinación lineal y entonces 
\begin_inset Formula $r\in D$
\end_inset

 o 
\begin_inset Formula $r=0$
\end_inset

.
 Lo primero es imposible porque 
\begin_inset Formula $r<\delta=\min D$
\end_inset

, luego 
\begin_inset Formula $r=0$
\end_inset

 y 
\begin_inset Formula $\delta|a$
\end_inset

.
 Análogamente 
\begin_inset Formula $\delta|b$
\end_inset

.
 Que sea máximo, y que todo divisor común de 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $b$
\end_inset

 lo sean de 
\begin_inset Formula $\delta$
\end_inset

, se desprende de que 
\begin_inset Formula $c|a\land c|b\implies c|\alpha a+\beta b=\delta$
\end_inset

.
\end_layout

\begin_layout Standard
De aquí que para todo 
\begin_inset Formula $a,b\in\mathbb{Z}$
\end_inset

 existen 
\begin_inset Formula $r,s\in\mathbb{Z}$
\end_inset

 tales que 
\begin_inset Formula $\text{mcd}(a,b)=ra+sb$
\end_inset

.
 Una expresión de la forma 
\begin_inset Formula $d=ra+sb$
\end_inset

 es una 
\series bold
identidad de Bézout
\series default
.
 En particular, si 
\begin_inset Formula $a=da'$
\end_inset

 y 
\begin_inset Formula $b=db'$
\end_inset

 con 
\begin_inset Formula $d=\text{mcd}(a,b)$
\end_inset

, entonces 
\begin_inset Formula $\text{mcd}(a',b')=1$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $d=\text{mcd}(a,b)$
\end_inset

 si y sólo si 
\begin_inset Formula $d|a$
\end_inset

, 
\begin_inset Formula $d|b$
\end_inset

, 
\begin_inset Formula $c|a\land c|b\implies c|d$
\end_inset

 y 
\begin_inset Formula $d\geq0$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies]$
\end_inset


\end_layout

\end_inset

Las propiedades (1) y (3) son por definición, y la (2) la acabamos de demostrar.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Si 
\begin_inset Formula $a\neq0$
\end_inset

 o 
\begin_inset Formula $b\neq0$
\end_inset

, 
\begin_inset Formula $d$
\end_inset

 es el mayor entero que divide a 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $b$
\end_inset

.
 Si 
\begin_inset Formula $a=b=0$
\end_inset

, como 
\begin_inset Formula $0|a,b$
\end_inset

, entonces 
\begin_inset Formula $0|d$
\end_inset

, luego 
\begin_inset Formula $d=0$
\end_inset

.
\end_layout

\begin_layout Standard
El máximo común divisor de 
\begin_inset Formula $a_{1},\dots,a_{n}$
\end_inset

 es 
\begin_inset Formula $\text{mcd}(a_{1},\dots,a_{n})=\max\{d\in\mathbb{Z}\mid \forall i,d|a_{i}\}$
\end_inset

.
 Entonces 
\begin_inset Formula $\text{mcd}(a_{1},\dots,a_{n})=\text{mcd}(\text{mcd}(a_{1},a_{2}),a_{3},\dots,a_{n})$
\end_inset

.
 
\series bold
Demostración:
\series default
 Sea 
\begin_inset Formula $d\coloneqq \text{mcd}(a_{1},\dots,a_{n})$
\end_inset

, como 
\begin_inset Formula $d||a_{1},\dots,a_{n}$
\end_inset

, entonces 
\begin_inset Formula $d|(f\coloneqq \text{mcd}(a_{1},a_{2})),a_{3},\dots,a_{n}|e\coloneqq \text{mcd}(\text{mcd}(a_{1},a_{2}),a_{3},\dots,a_{n})$
\end_inset

 y por tanto 
\begin_inset Formula $d|e$
\end_inset

.
 Pero 
\begin_inset Formula $e|f,a_{3},\dots,a_{n}$
\end_inset

, luego 
\begin_inset Formula $e|a_{1},\dots,a_{n}$
\end_inset

 y 
\begin_inset Formula $e|d$
\end_inset

, y como 
\begin_inset Formula $d,e\geq0$
\end_inset

, 
\begin_inset Formula $d=e$
\end_inset

.
\end_layout

\begin_layout Standard

\series bold
Teorema:
\series default
 Dados 
\begin_inset Formula $a_{1},\dots,a_{n}\in\mathbb{Z}^{*}$
\end_inset

, 
\begin_inset Formula $\text{mcd}(a_{1},\dots,a_{n})=\min\left\{ \sum_{i=1}^{n}r_{i}a_{i}>0|r_{i}\in\mathbb{Z}\right\} $
\end_inset

.
 Además, 
\begin_inset Formula $d=\text{mcd}(a_{1},\dots,a_{n})$
\end_inset

 si y sólo si 
\begin_inset Formula $d|a_{1},\dots,a_{n}$
\end_inset

, 
\begin_inset Formula $c|a_{1},\dots,a_{n}\implies c|d$
\end_inset

 y 
\begin_inset Formula $d\geq0$
\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Formula $a,b\in\mathbb{Z}$
\end_inset

 son 
\series bold
coprimos
\series default
 o 
\series bold
primos entre sí
\series default
 si 
\begin_inset Formula $\text{mcd}(a,b)=1$
\end_inset

, es decir, si 
\begin_inset Formula $\exists\alpha,\beta\in\mathbb{Z}:\alpha a+\beta b=1$
\end_inset

.
 Si 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $b$
\end_inset

 son coprimos:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|bc\implies a|c$
\end_inset

.
\begin_inset Newline newline
\end_inset

Sea 
\begin_inset Formula $1=\alpha a+\beta b$
\end_inset

, multiplicando por 
\begin_inset Formula $c$
\end_inset

, 
\begin_inset Formula $c=\alpha ac+\beta bc$
\end_inset

.
 Como 
\begin_inset Formula $a|bc$
\end_inset

, 
\begin_inset Formula $c=\alpha ca+\beta na$
\end_inset

 y 
\begin_inset Formula $a|c$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|c\land b|c\implies ab|c$
\end_inset

.
\begin_inset Formula 
\begin{multline*}
\begin{array}{c}
1=ra+sb\\
\frac{c}{a},\frac{c}{b}\in\mathbb{Z}
\end{array}\implies\frac{c}{a}=\frac{c}{a}ra+\frac{c}{a}sb=\frac{c}{b}rb+\frac{c}{a}sb=b\left(\frac{c}{b}r+\frac{c}{a}s\right)\implies\\
\implies c=ab\left(\frac{c}{b}r+\frac{c}{a}s\right)\implies ab|c
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
Se tiene que 
\begin_inset Formula $\text{mcd}(a,b)=\text{mcd}(a-sb,b)=\text{mcd}(a,b-sa)$
\end_inset

, y en particular, si 
\begin_inset Formula $b\neq0$
\end_inset

 y 
\begin_inset Formula $a=bq+r$
\end_inset

 con 
\begin_inset Formula $0\leq r<b$
\end_inset

, entonces 
\begin_inset Formula $\text{mcd}(a,b)=\text{mcd}(b,r)$
\end_inset

.
 La aplicación repetida de lo anterior se conoce como 
\series bold
algoritmo de Euclides
\series default
.
 También permite obtener identidades de Bézout.
 Si llamamos 
\begin_inset Formula $(a,b)=\text{mcd}(a,b)$
\end_inset

:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{eqnarray*}
a=bq_{1}+r_{1} & (a,b)=(b,r_{1}) & r_{1}<b\\
b=r_{1}q_{2}+r_{2} & (b,r_{1})=(r_{1},r_{2}) & r_{2}<r_{1}\\
 & \vdots\\
r_{n-2}=r_{n-1}q_{n}+0 & (r_{n-2},r_{n-1})=(r_{n-1},0)=r_{n-1} & 0<r_{n-1}
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
Como 
\begin_inset Formula $b>r_{1}>\dots\geq0$
\end_inset

, el algoritmo acaba en un número finito de pasos.
 Además, cada dos pasos del algoritmo, el resto se reduce a la mitad.
 
\series bold
Demostración:
\series default
 Sean 
\begin_inset Formula $a=bq+r$
\end_inset

, 
\begin_inset Formula $b=rq'+s$
\end_inset

 y 
\begin_inset Formula $r=sq''+t$
\end_inset

, si 
\begin_inset Formula $s\leq\frac{1}{2}r$
\end_inset

 entonces 
\begin_inset Formula $t<s\leq\frac{1}{2}r$
\end_inset

 y hemos terminado, y si 
\begin_inset Formula $s>\frac{1}{2}r$
\end_inset

, entonces 
\begin_inset Formula $q''=1$
\end_inset

 y 
\begin_inset Formula $t=r-s<r-\frac{1}{2}r=\frac{1}{2}r$
\end_inset

.
\end_layout

\begin_layout Standard
Dados 
\begin_inset Formula $a,b\in\mathbb{Z}^{*}$
\end_inset

, su 
\series bold
mínimo común múltiplo
\series default
 es 
\begin_inset Formula $\text{mcm}(a,b)=\min\{m\in\mathbb{Z}^{+}\mid a|m\land b|m\}$
\end_inset

.
 Si 
\begin_inset Formula $a$
\end_inset

 o 
\begin_inset Formula $b$
\end_inset

 son 0, entonces 
\begin_inset Formula $\text{mcm}(a,b)=0$
\end_inset

.
 Propiedades:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcm}(a,b)=\text{mcm}(a,|b|)=\text{mcm}(|a|,|b|)$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcm}(a,b)=0\iff a=0\lor b=0$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcm}(a,ab)=|ab|$
\end_inset

.
\end_layout

\begin_layout Standard
Teorema:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\text{mcm}(a,b)\text{mcd}(a,b)=|ab|$
\end_inset

.
\begin_inset Newline newline
\end_inset

Para 
\begin_inset Formula $a,b>0$
\end_inset

, sea 
\begin_inset Formula $d=\text{mcd}(a,b)$
\end_inset

 con 
\begin_inset Formula $a=da'$
\end_inset

 y 
\begin_inset Formula $b=db'$
\end_inset

, sea 
\begin_inset Formula $m=a'b'd$
\end_inset

.
 Entonces 
\begin_inset Formula $a|m$
\end_inset

 y 
\begin_inset Formula $b|m$
\end_inset

.
 Sea 
\begin_inset Formula $c=\alpha a=\beta b$
\end_inset

 con 
\begin_inset Formula $\alpha,\beta\in\mathbb{Z}$
\end_inset

, entonces 
\begin_inset Formula $\alpha da'=\beta db'$
\end_inset

, luego 
\begin_inset Formula $\alpha a'=\beta b'$
\end_inset

, y como 
\begin_inset Formula $a'$
\end_inset

 y 
\begin_inset Formula $b'$
\end_inset

 son coprimos, 
\begin_inset Formula $a'|\beta$
\end_inset

 y 
\begin_inset Formula $\beta=\gamma a'$
\end_inset

 con 
\begin_inset Formula $\gamma\in\mathbb{Z}$
\end_inset

.
 Sustituyendo, 
\begin_inset Formula $c=\gamma a'b=\gamma a'db'=\gamma m\geq m$
\end_inset

, luego 
\begin_inset Formula $m=\text{mcm}(a,b)$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a|c\land b|c\implies\text{mcm}(a,b)|c$
\end_inset

.
\end_layout

\begin_layout Standard
El mínimo común múltiplo de 
\begin_inset Formula $a_{1},\dots,a_{n}$
\end_inset

 es 
\begin_inset Formula $\text{mcm}(a_{1},\dots,a_{n})=\min\{m\in\mathbb{Z}^{+}\mid \forall i,a_{i}|m\}$
\end_inset

.
 Así, 
\begin_inset Formula $m=\text{mcm}(a_{1},\dots,a_{n})$
\end_inset

 si y sólo si 
\begin_inset Formula $a_{1},\dots,a_{n}|m$
\end_inset

, 
\begin_inset Formula $a_{1},\dots,a_{n}|c\implies m|c$
\end_inset

 y 
\begin_inset Formula $m\geq0$
\end_inset

.
\end_layout

\begin_layout Standard
Una ecuación del tipo 
\begin_inset Formula $ax+by=c$
\end_inset

 en la que se buscan soluciones enteras es una 
\series bold
ecuación diofántica lineal
\series default
, en este caso de dos variables.
 Tiene solución si y sólo si 
\begin_inset Formula $d=\text{mcd}(a,b)|c$
\end_inset

, y entonces estas son de la forma
\begin_inset Formula 
\[
\left\{ \begin{array}{ccc}
x & = & x_{0}+x'\\
y & = & y_{0}+y'
\end{array}\right.
\]

\end_inset

donde 
\begin_inset Formula $x_{0},y_{0}$
\end_inset

 es una solución particular y 
\begin_inset Formula $x',y'$
\end_inset

 es una solución de la 
\series bold
ecuación homogénea asociada
\series default
, 
\begin_inset Formula $ax+by=0$
\end_inset

.
 En particular, si 
\begin_inset Formula $\alpha a+\beta b=d$
\end_inset

 y 
\begin_inset Formula $c=c'd$
\end_inset

, entonces 
\begin_inset Formula $x_{0}=c'\alpha$
\end_inset

 e 
\begin_inset Formula $y_{0}=c'\beta$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies]$
\end_inset


\end_layout

\end_inset

Sean 
\begin_inset Formula $x,y\in\mathbb{Z}$
\end_inset

 con 
\begin_inset Formula $ax+by=c$
\end_inset

.
 Entonces 
\begin_inset Formula $d|ax+by=c$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Multiplicando la identidad de Bézout, 
\begin_inset Formula $(c'\alpha)a+(c'\beta)b=c'd=c$
\end_inset

.
\end_layout

\begin_layout Standard
Si 
\begin_inset Formula $d=\text{mcd}(a,b)$
\end_inset

, 
\begin_inset Formula $a=a'd$
\end_inset

 y 
\begin_inset Formula $b=b'd$
\end_inset

, las soluciones de 
\begin_inset Formula $ax+by=0$
\end_inset

 son
\begin_inset Formula 
\[
\left\{ \begin{array}{ccc}
x & = & -b't\\
y & = & a't
\end{array}\right.
\]

\end_inset

para cualquier 
\begin_inset Formula $t\in\mathbb{Z}$
\end_inset

.
 
\series bold
Demostración:
\series default
 
\begin_inset Formula $ax=-by$
\end_inset

, luego 
\begin_inset Formula $a'x=-b'y$
\end_inset

.
 Como 
\begin_inset Formula $a'$
\end_inset

 y 
\begin_inset Formula $b'$
\end_inset

 son coprimos y 
\begin_inset Formula $a'|-b'y$
\end_inset

, entonces 
\begin_inset Formula $a'|y$
\end_inset

, luego existe 
\begin_inset Formula $t\in\mathbb{Z}$
\end_inset

 con 
\begin_inset Formula $y=a't$
\end_inset

, con lo que 
\begin_inset Formula $a'x=-b'a't$
\end_inset

 y 
\begin_inset Formula $x=-b't$
\end_inset

.
 Multiplicando, todos los enteros de esta forma son solución.
\end_layout

\begin_layout Standard
Un entero 
\begin_inset Formula $p\neq1,-1$
\end_inset

 es 
\series bold
primo
\series default
 si sus únicos divisores son 1, 
\begin_inset Formula $-1$
\end_inset

, 
\begin_inset Formula $p$
\end_inset

 y 
\begin_inset Formula $-p$
\end_inset

.
 Así,
\begin_inset Formula 
\[
p\text{ es primo}\iff(p|ab\implies p|a\lor p|b)\iff(p|a_{1}\cdots a_{n}\implies\exists i:p|a_{i})
\]

\end_inset


\end_layout

\begin_layout Description
\begin_inset Formula $1\implies2]$
\end_inset

 Si 
\begin_inset Formula $p|a$
\end_inset

 ya está.
 Si no, 
\begin_inset Formula $\text{mcd}(p,a)=1$
\end_inset

 y 
\begin_inset Formula $p|b$
\end_inset

.
\end_layout

\begin_layout Description
\begin_inset Formula $2\implies3]$
\end_inset

 Por inducción con 
\begin_inset Formula $a_{1}\cdots a_{n}=a_{1}(a_{2}\cdots a_{n})$
\end_inset

.
\end_layout

\begin_layout Description
\begin_inset Formula $3\implies1]$
\end_inset

 Si 
\begin_inset Formula $a|p$
\end_inset

 entonces 
\begin_inset Formula $p=ab$
\end_inset

 para cierto 
\begin_inset Formula $b$
\end_inset

, y bien 
\begin_inset Formula $p|a$
\end_inset

 (con lo que 
\begin_inset Formula $a=p$
\end_inset

 o 
\begin_inset Formula $a=-p$
\end_inset

) o 
\begin_inset Formula $p|b$
\end_inset

 (con lo que 
\begin_inset Formula $a=1$
\end_inset

 o 
\begin_inset Formula $a=-1$
\end_inset

).
\end_layout

\begin_layout Standard

\series bold
Teorema Fundamental de la Aritmética:
\series default
 Todo entero distinto de 
\begin_inset Formula $0$
\end_inset

 y 
\begin_inset Formula $\pm1$
\end_inset

 puede escribirse como producto de primos, y la factorización es única salvo
 signo y orden.
 
\series bold
Demostración:
\series default
 Consideremos el conjunto de todos los positivos distintos de 1 que no se
 factorizan en primos y, si este no es vacío, sea 
\begin_inset Formula $a\in\mathbb{Z}$
\end_inset

 su mínimo.
 
\begin_inset Formula $a$
\end_inset

 no es primo, luego 
\begin_inset Formula $a=bc$
\end_inset

 con 
\begin_inset Formula $b,c\in\mathbb{Z}^{+}\backslash\{1\}$
\end_inset

.
 Pero como 
\begin_inset Formula $a$
\end_inset

 es mínimo, entonces 
\begin_inset Formula $b$
\end_inset

 y 
\begin_inset Formula $c$
\end_inset

 sí se factorizan en primos, luego 
\begin_inset Formula $a$
\end_inset

 también.
\begin_inset Formula $\#$
\end_inset

 Ahora sea 
\begin_inset Formula $a=p_{1}\cdots p_{n}=q_{1}\cdots q_{m}$
\end_inset

 con 
\begin_inset Formula $p_{1}\cdots p_{n},q_{1}\cdots q_{m}$
\end_inset

 primos y supongamos 
\begin_inset Formula $n\leq m$
\end_inset

.
 Procedemos por inducción sobre 
\begin_inset Formula $n$
\end_inset

.
 Si 
\begin_inset Formula $n=1$
\end_inset

, 
\begin_inset Formula $a=p_{1}=q_{1}\cdots q_{m}$
\end_inset

, y como 
\begin_inset Formula $p_{1}$
\end_inset

 no tiene más divisores primos que 
\begin_inset Formula $-p_{1}$
\end_inset

 y 
\begin_inset Formula $p_{1}$
\end_inset

, debe ser 
\begin_inset Formula $m=1$
\end_inset

 y 
\begin_inset Formula $q_{1}=p_{1}$
\end_inset

.
 Si suponemos el resultado válido para 
\begin_inset Formula $n-1$
\end_inset

, entonces 
\begin_inset Formula $p_{n}$
\end_inset

 divide a 
\begin_inset Formula $a=q_{1}\cdots q_{n}$
\end_inset

 y por tanto divide a algún 
\begin_inset Formula $i\in\{1,\dots,m\}$
\end_inset

.
 Reordenamos los factores para obtener 
\begin_inset Formula $i=m$
\end_inset

, es decir 
\begin_inset Formula $p_{n}|q_{m}$
\end_inset

, con lo que 
\begin_inset Formula $q_{m}=\pm p_{n}$
\end_inset

.
 Entonces 
\begin_inset Formula $p_{1}\cdots p_{n-1}p_{n}=q_{1}\cdots q_{m-1}(\pm p_{n})$
\end_inset

, con lo que 
\begin_inset Formula $p_{1}\cdots p_{n-1}=\pm q_{1}\cdots q_{m-1}$
\end_inset

 y 
\begin_inset Formula $n-1=m-1$
\end_inset

, luego 
\begin_inset Formula $n=m$
\end_inset

 y además, después de ordenar si hiciera falta, 
\begin_inset Formula $q_{i}=\pm p_{i}$
\end_inset

.
\end_layout

\begin_layout Standard
Así, para 
\begin_inset Formula $a\in\mathbb{Z},a\neq0,\pm1$
\end_inset

, 
\begin_inset Formula $a=\pm p_{1}^{n_{1}}\cdots p_{s}^{n_{s}}$
\end_inset

 y estos primos y sus exponentes son únicos (salvo orden).
 Entonces podemos calcular el 
\begin_inset Formula $\text{mcd}(a,b)$
\end_inset

 tomando el producto de primos comunes a 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $b$
\end_inset

 elevados a la mínima potencia y el 
\begin_inset Formula $\text{mcm}(a,b)$
\end_inset

 tomando el producto de primos entre ambos elevados a la máxima potencia.
\end_layout

\begin_layout Standard
Como 
\series bold
teorema
\series default
, el conjunto de los números primos es infinito.
 Si no lo fuera, y fuera 
\begin_inset Formula $\{p_{1},\dots,p_{n}\}$
\end_inset

, el número 
\begin_inset Formula $N\coloneqq p_{1}\cdots p_{n}+1$
\end_inset

 también lo es.
\begin_inset Formula $\#$
\end_inset


\end_layout

\begin_layout Section
Congruencias
\end_layout

\begin_layout Standard
Dados 
\begin_inset Formula $x,y\in\mathbb{Z},m\in\mathbb{Z}^{+}$
\end_inset

, 
\begin_inset Formula $x$
\end_inset

 e 
\begin_inset Formula $y$
\end_inset

 son 
\series bold
congruentes módulo 
\begin_inset Formula $m$
\end_inset


\series default
, 
\begin_inset Formula $x\equiv y\mod m$
\end_inset

 ó 
\begin_inset Formula $x\equiv y\,(m)$
\end_inset

, si 
\begin_inset Formula $m|x-y$
\end_inset

.
 Esta relación es de equivalencia.
 Propiedades:
\end_layout

\begin_layout Enumerate
Si 
\begin_inset Formula $r$
\end_inset

 es el resto de 
\begin_inset Formula $a/m$
\end_inset

 entonces 
\begin_inset Formula $a\equiv r\,(m)$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a\equiv b\,(m)\land0\leq a,b<m\implies a=b$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a\equiv b\,(m)$
\end_inset

 si y sólo si 
\begin_inset Formula $a$
\end_inset

 y 
\begin_inset Formula $b$
\end_inset

 dan el mismo resto entre 
\begin_inset Formula $m$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $a\equiv a'\,(m)\land b\equiv b'\,(m)\implies a+b\equiv a'+b'\,(m)$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Formula $a-a'=\lambda m$
\end_inset

 y 
\begin_inset Formula $b-b'=\mu m$
\end_inset

 para ciertos 
\begin_inset Formula $\lambda,\mu\in\mathbb{Z}$
\end_inset

, luego 
\begin_inset Formula $(a+b)-(a'+b')=(\lambda+\mu)m$
\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $a\equiv a'\,(m)\land b\equiv b'\,(m)\implies ab\equiv a'b'\,(m)$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Formula 
\[
ab-a'b'=(a'+\lambda m)(b'+\mu m)-a'b'=a'b'+(a'\mu+b'\lambda+\lambda\mu m)m-a'b'\equiv0\,(m)
\]

\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset Formula $a\equiv b\,(m)\implies ac\equiv bc\,(m)$
\end_inset

.
 El recíproco es cierto si 
\begin_inset Formula $c$
\end_inset

 y 
\begin_inset Formula $m$
\end_inset

 son coprimos.
\begin_inset Newline newline
\end_inset

La primera parte se sigue de lo anterior.
 Para la segunda, 
\begin_inset Formula $m|ac-bc=(a-b)c\implies m|a-b\implies a\equiv b\,(m)$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $c\neq0\implies(a\equiv b\,(m)\iff ac\equiv bc\,(mc))$
\end_inset

.
\begin_inset Newline newline
\end_inset


\begin_inset Formula $a-b=\lambda m\iff ac-bc=\lambda mc$
\end_inset


\end_layout

\begin_layout Standard
Denotamos la clase de equivalencia (llamada 
\series bold
clase de congruencia módulo 
\begin_inset Formula $m$
\end_inset


\series default
) de 
\begin_inset Formula $a\in\mathbb{Z}$
\end_inset

 por 
\begin_inset Formula $\overline{a}$
\end_inset

, y su 
\series bold
representante canónico
\series default
 es el resto de 
\begin_inset Formula $a/m$
\end_inset

.
 Llamamos entonces 
\begin_inset Formula $\mathbb{Z}/(m)$
\end_inset

 o 
\begin_inset Formula $\mathbb{Z}_{m}$
\end_inset

 al conjunto cociente, que tiene exactamente 
\begin_inset Formula $m$
\end_inset

 elementos.
 Así, para 
\begin_inset Formula $\overline{a},\overline{b}\in\mathbb{Z}_{m}$
\end_inset

, definimos 
\begin_inset Formula $\overline{a}+\overline{b}=\overline{a+b}$
\end_inset

 y 
\begin_inset Formula $\overline{a}\cdot\overline{b}=\overline{a\cdot b}$
\end_inset

, y vemos que están bien definidas y que 
\begin_inset Formula $\mathbb{Z}_{m}$
\end_inset

 es un anillo conmutativo.
 Dado 
\begin_inset Formula $\overline{a}\in\mathbb{Z}_{m}$
\end_inset

:
\begin_inset Formula 
\begin{multline*}
\overline{a}\text{ tiene inverso (}\exists\overline{b}\in\mathbb{Z}_{m}:\overline{a}\cdot\overline{b}=1\text{)}\iff\overline{a}\text{ es cancelable (}\overline{a}\cdot\overline{x}=\overline{a}\cdot\overline{y}\implies\overline{x}=\overline{y}\text{)}\iff\\
\iff\text{mcd}(a,m)=1
\end{multline*}

\end_inset


\end_layout

\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $1\implies2]$
\end_inset

 Multiplicando por 
\begin_inset Formula $\overline{a}^{-1}$
\end_inset

 en ambos lados de 
\begin_inset Formula $\overline{a}\cdot\overline{x}=\overline{a}\cdot\overline{y}$
\end_inset

.
\end_layout

\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $2\implies3]$
\end_inset

 Si 
\begin_inset Formula $\text{mcd}(a,m)=d>1$
\end_inset

, sean 
\begin_inset Formula $a=a'd$
\end_inset

 y 
\begin_inset Formula $m=m'd$
\end_inset

, entonces 
\begin_inset Formula $\overline{a}\cdot\overline{m'}=\overline{a'}\cdot\overline{d}\cdot\overline{m'}=\overline{a'}\cdot\overline{m}=\overline{0}=\overline{a}\cdot\overline{0}$
\end_inset

, pero 
\begin_inset Formula $\overline{m'}\neq\overline{0}$
\end_inset

.
\end_layout

\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $3\implies1]$
\end_inset

 Existen 
\begin_inset Formula $r,s\in\mathbb{Z}$
\end_inset

 con 
\begin_inset Formula $ra+sm=1$
\end_inset

, luego 
\begin_inset Formula $\overline{r}\cdot\overline{a}=1$
\end_inset

.
\end_layout

\begin_layout Standard
Así, 
\begin_inset Formula $\mathbb{Z}_{m}$
\end_inset

 es un cuerpo si y sólo si 
\begin_inset Formula $m$
\end_inset

 es primo, pues entonces todos los elementos tienen inverso.
\end_layout

\begin_layout Standard
Un entero es divisible por 3 si y sólo si la suma de sus cifras lo es.
 
\series bold
Demostración:
\series default
 
\begin_inset Formula $3|m\iff m\equiv0\,(3)$
\end_inset

.
 
\begin_inset Formula $10\equiv1\,(3)$
\end_inset

, luego 
\begin_inset Formula $10^{s}\equiv1\,(3)$
\end_inset

 para todo 
\begin_inset Formula $s$
\end_inset

 y si 
\begin_inset Formula $m$
\end_inset

 se escribe como 
\begin_inset Formula $a_{n}\cdots a_{0}$
\end_inset

, entonces 
\begin_inset Formula $m=a_{n}10^{n}+\dots+a_{0}\equiv a_{n}+\dots+a_{0}\,(3)$
\end_inset

.
 De forma parecida se pueden sacar reglas para el 9 y el 11.
\end_layout

\begin_layout Standard
Dados 
\begin_inset Formula $a,b,t\in\mathbb{Z}$
\end_inset

:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\overline{t}\text{ es sol. de }\overline{a}x=\overline{b}\in\mathbb{Z}_{m}\iff t\text{ es sol. de }ax\equiv b\,(m)\iff\exists s\in\mathbb{Z}:(t,s)\text{ es sol. de }ax-my=b
\]

\end_inset


\end_layout

\begin_layout Standard
La ecuación 
\begin_inset Formula $ax\equiv b\,(m)$
\end_inset

 tiene solución si y sólo si 
\begin_inset Formula $d\coloneqq \text{mcd}(a,m)|b$
\end_inset

, y las soluciones son todos los enteros 
\begin_inset Formula $x=x_{0}+\lambda\frac{m}{d}$
\end_inset

 con 
\begin_inset Formula $\lambda\in\mathbb{Z}$
\end_inset

, donde 
\begin_inset Formula $x_{0}$
\end_inset

 es una solución particular, de modo que la ecuación tiene 
\begin_inset Formula $d$
\end_inset

 soluciones distintas módulo 
\begin_inset Formula $m$
\end_inset

.
 
\series bold
Demostración:
\series default
 
\begin_inset Formula $ax\equiv b$
\end_inset

 equivale a la ecuación diofántica 
\begin_inset Formula $ax-my=b$
\end_inset

, que tiene solución si y sólo si 
\begin_inset Formula $d|b$
\end_inset

.
 Sean pues 
\begin_inset Formula $b=db'$
\end_inset

, 
\begin_inset Formula $a=da'$
\end_inset

 y 
\begin_inset Formula $m=dm'$
\end_inset

, entonces 
\begin_inset Formula $ax-my=b$
\end_inset

 equivale a 
\begin_inset Formula $a'x-m'y=b'$
\end_inset

 y las soluciones son
\begin_inset Formula 
\[
\left\{ \begin{array}{ccc}
x & = & x_{0}+m'\lambda\\
y & = & y_{0}+a'\lambda
\end{array}\right.
\]

\end_inset

Entonces 
\begin_inset Formula $x_{0}+\lambda m'\equiv x_{0}+\mu m'\,(m)\iff\lambda m'\equiv\mu m'\,(dm')\iff\lambda\equiv\mu\,(d)$
\end_inset

.
\end_layout

\begin_layout Section
Teorema Chino de los Restos
\end_layout

\begin_layout Standard
Sean 
\begin_inset Formula $b_{1},\dots,b_{k}\in\mathbb{Z}$
\end_inset

 arbitrarios y 
\begin_inset Formula $m_{1},\dots,m_{k}\in\mathbb{Z}^{+}$
\end_inset

 coprimos dos a dos, el sistema de congruencias
\begin_inset Formula 
\[
\left\{ \begin{array}{cc}
x\equiv b_{1} & (m_{1})\\
\vdots\\
x\equiv b_{k} & (m_{k})
\end{array}\right.
\]

\end_inset

tiene solución única módulo 
\begin_inset Formula $M\coloneqq m_{1}\cdots m_{k}$
\end_inset

.
 En particular, esta es 
\begin_inset Formula $b_{1}M_{1}N_{1}+\dots+b_{k}M_{k}N_{k}$
\end_inset

, donde 
\begin_inset Formula $M_{i}=\frac{M}{M_{i}}$
\end_inset

 y 
\begin_inset Formula $N_{i}$
\end_inset

 es tal que 
\begin_inset Formula $M_{i}N_{i}\equiv1\,(m_{i})$
\end_inset

.
\end_layout

\begin_layout Standard

\series bold
Demostración:
\series default
 Si 
\begin_inset Formula $p$
\end_inset

 es un número primo que divide a 
\begin_inset Formula $M_{i}$
\end_inset

 y 
\begin_inset Formula $m_{i}$
\end_inset

, entonces divide a algún 
\begin_inset Formula $m_{j}$
\end_inset

 con 
\begin_inset Formula $j\neq i$
\end_inset

, lo cual contradice que 
\begin_inset Formula $\text{mcd}(m_{i},m_{j})=1$
\end_inset

, luego 
\begin_inset Formula $M_{i}$
\end_inset

 y 
\begin_inset Formula $m_{i}$
\end_inset

 son coprimos y 
\begin_inset Formula $M_{i}$
\end_inset

 tiene inverso 
\begin_inset Formula $N_{i}$
\end_inset

 módulo 
\begin_inset Formula $m_{i}$
\end_inset

, teniendo en cuenta que 
\begin_inset Formula $M_{i}N_{i}\equiv0\,(m_{j})$
\end_inset

 para 
\begin_inset Formula $j\neq i$
\end_inset

.
 Entonces 
\begin_inset Formula $x_{0}=b_{1}M_{1}N_{1}+\dots+b_{k}M_{k}N_{k}$
\end_inset

 es solución del sistema.
 Ahora bien, si 
\begin_inset Formula $x$
\end_inset

 e 
\begin_inset Formula $y$
\end_inset

 son soluciones del sistema, 
\begin_inset Formula $x,y\equiv b_{i}\,(m_{i})$
\end_inset

, luego 
\begin_inset Formula $x\equiv y\,(m_{i})$
\end_inset

, con lo que 
\begin_inset Formula $x-y$
\end_inset

 es múltiplo de todos los 
\begin_inset Formula $m_{i}$
\end_inset

 y por tanto 
\begin_inset Formula $x\equiv y\,(M)$
\end_inset

.
\end_layout

\begin_layout Standard
Si los módulos no son coprimos, intentamos simplificar cada ecuación dividiéndol
a entre un número, pues 
\begin_inset Formula $a'dx\equiv b'd\,(m'd)\iff a'x\equiv b'\,(m')$
\end_inset

.
 Si esto no es posible, resolvemos una ecuación y sustituimos en el resto.
\end_layout

\begin_layout Section
Teoremas de Euler y Fermat
\end_layout

\begin_layout Standard
Denotamos 
\begin_inset Formula $\mathbb{Z}_{m}^{*}=\{x\in\mathbb{Z}_{m}|x\text{ es invertible}\}$
\end_inset

, y definimos la 
\series bold
función 
\begin_inset Formula $\phi$
\end_inset

 de Euler
\series default
 como 
\begin_inset Formula $\phi:\mathbb{N}\rightarrow\mathbb{N}$
\end_inset

 tal que 
\begin_inset Formula $\phi(m)=|\{x\in\mathbb{N}|1\leq x\leq m\land\text{mcd}(x,m)=1\}|=|\mathbb{Z}_{m}^{*}|$
\end_inset

.
 Así:
\end_layout

\begin_layout Enumerate
Si 
\begin_inset Formula $p$
\end_inset

 es primo, 
\begin_inset Formula $\phi(p)=p-1$
\end_inset

.
\end_layout

\begin_layout Enumerate
Si 
\begin_inset Formula $p$
\end_inset

 es primo, 
\begin_inset Formula $\phi(p^{n})=p^{n-1}(p-1)$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard
Los no-coprimos con 
\begin_inset Formula $p^{n}$
\end_inset

 son precisamente los múltiplos de 
\begin_inset Formula $p$
\end_inset

, por lo que estos son 
\begin_inset Formula $\frac{p^{n}}{p}=p^{n-1}$
\end_inset

 y 
\begin_inset Formula $\phi(p^{n})=p^{n}-p^{n-1}=p^{n}(p-1)$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Si 
\begin_inset Formula $\text{mcd}(n,m)=1$
\end_inset

, entonces 
\begin_inset Formula $\phi(nm)=\phi(n)\phi(m)$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard
Definimos 
\begin_inset Formula $f:\mathbb{Z}_{nm}^{*}\rightarrow\mathbb{Z}_{n}^{*}\times\mathbb{Z}_{m}^{*}$
\end_inset

 tal que 
\begin_inset Formula $f(x)=(x_{n},x_{m})$
\end_inset

, donde 
\begin_inset Formula $x_{n}$
\end_inset

 y 
\begin_inset Formula $x_{m}$
\end_inset

 son los restos de dividir 
\begin_inset Formula $x$
\end_inset

 entre 
\begin_inset Formula $n$
\end_inset

 y 
\begin_inset Formula $m$
\end_inset

, respectivamente.
 Para abreviar asumimos que está bien definida, y pasamos a ver que es biyectiva.
 Si 
\begin_inset Formula $f(x)=(x_{n},x_{m})=f(y)$
\end_inset

 entonces 
\begin_inset Formula $x\equiv y\,(m)$
\end_inset

 y 
\begin_inset Formula $x\equiv y\,(n)$
\end_inset

, luego 
\begin_inset Formula $nm|(x-y)$
\end_inset

 y en 
\begin_inset Formula $\mathbb{Z}_{nm}^{*}$
\end_inset

 es inyectiva.
 Para ver que es suprayectiva, consideramos 
\begin_inset Formula $(a,b)\in\mathbb{Z}_{n}^{*}\times\mathbb{Z}_{m}^{*}$
\end_inset

.
 Al existir una identidad de Bézout 
\begin_inset Formula $1=rn+sm$
\end_inset

, podemos hacer 
\begin_inset Formula $x=brn+asm$
\end_inset

, con lo que 
\begin_inset Formula $x\equiv a\,(n)$
\end_inset

 y 
\begin_inset Formula $x\equiv b\,(m)$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Si 
\begin_inset Formula $m=p_{1}^{n_{1}}\cdots p_{s}^{n_{s}}$
\end_inset

 es la descomposición de 
\begin_inset Formula $m$
\end_inset

 en factores primos, entonces
\begin_inset Formula 
\[
\phi(m)=\prod_{i=1}^{s}p_{i}^{n_{i}-1}(p_{i}-1)=m\left(1-\frac{1}{p_{1}}\right)\cdots\left(1-\frac{1}{p_{s}}\right)
\]

\end_inset


\end_layout

\begin_layout Standard

\series bold
Teorema de Euler:
\series default
 Sea 
\begin_inset Formula $1<m\in\mathbb{Z}$
\end_inset

.
 Si 
\begin_inset Formula $a$
\end_inset

 es coprimo con 
\begin_inset Formula $m$
\end_inset

 entonces 
\begin_inset Formula $a^{\phi(m)}\equiv1\,(m)$
\end_inset

.
 
\series bold
Demostración:
\series default
 Esto equivale a que 
\begin_inset Formula $\overline{a}^{\phi(m)}=\overline{1}\in\mathbb{Z}_{m}$
\end_inset

.
 Sea 
\begin_inset Formula $\mathbb{Z}_{m}^{*}=\{\overline{x_{1}},\dots,\overline{x_{\phi(m)}}\}$
\end_inset

 y 
\begin_inset Formula $\overline{a}\cdot\mathbb{Z}_{m}^{*}=\{\overline{a}\overline{x}|\overline{x}\in\mathbb{Z}_{m}^{*}\}$
\end_inset

.
 Demostramos que 
\begin_inset Formula $\overline{a}\cdot\mathbb{Z}_{m}^{*}=\mathbb{Z}_{m}^{*}$
\end_inset

:
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\subseteq]$
\end_inset


\end_layout

\end_inset


\begin_inset Formula $x=\overline{ax_{i}}\in\overline{a}\cdot\mathbb{Z}_{m}^{*}\implies x\overline{a}^{-1}\overline{x_{i}}^{-1}=\overline{1}\implies x\in\mathbb{Z}_{m}^{*}$
\end_inset

.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\supseteq]$
\end_inset


\end_layout

\end_inset


\begin_inset Formula $\overline{x_{i}}\in\mathbb{Z}_{m}^{*}\implies\overline{x_{i}}=\overline{a}\,\overline{a}^{-1}\overline{x_{i}}\in\overline{a}\cdot\mathbb{Z}_{m}^{*}$
\end_inset

.
\end_layout

\begin_layout Standard
Entonces 
\begin_inset Formula $\prod_{i=1}^{\phi(m)}\overline{x}_{i}=\prod_{i=1}^{\phi(m)}\overline{ax_{i}}=\overline{a}^{\phi(m)}\prod_{i=1}^{\phi(m)}\overline{x_{i}}$
\end_inset

, y dividiendo entre 
\begin_inset Formula $\prod_{i=1}^{\phi(m)}\overline{x_{i}}$
\end_inset

, porque es invertible, se obtiene el resultado.
\end_layout

\begin_layout Standard

\series bold
Teorema Pequeño de Fermat:
\series default
 Si 
\begin_inset Formula $a\in\mathbb{Z}$
\end_inset

 y 
\begin_inset Formula $p$
\end_inset

 es un número primo que no divide a 
\begin_inset Formula $a$
\end_inset

, entonces 
\begin_inset Formula $a^{p-1}\equiv1\,(p)$
\end_inset

, y para todo 
\begin_inset Formula $x\in\mathbb{Z}$
\end_inset

, 
\begin_inset Formula $x^{p}\equiv x\,(p)$
\end_inset

.
 Esto se deriva del teorema de Euler y de que 
\begin_inset Formula $\phi(p)=p-1$
\end_inset

.
\end_layout

\end_body
\end_document