5.5: Más sobre GCD

Última actualización
Guardar como PDF

Page ID: 112886

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

En esta sección, discutiremos algunos resultados técnicos sobre$\gcd(a,b)$.

Teorema$\PageIndex{1}\label{thm:EA}$

Vamos$d=\gcd(a,b)$, dónde$a,b\in\mathbb{N}$. Entonces\[\{ as+bt \mid s,t\in\mathbb{Z} \} = \{ nd \mid n\in\mathbb{Z} \}. \nonumber\] Por lo tanto, cada combinación lineal de$a$ y$b$ es un múltiplo de$\gcd(a,b)$, y viceversa, cada múltiplo de$\gcd(a,b)$ es expresable como una combinación lineal de$a$ y$b$.

Prueba

Por brevedad,\[S=\{as+bt\mid s,t\in\mathbb{Z}\}, \qquad\mbox{and}\qquad T=\{nd\mid n\in\mathbb{Z}\}. \nonumber\] vamos a demostrarlo$S=T$ demostrando eso$S\subseteq T$ y$T\subseteq S$.

Vamos$x\in S$. Para probarlo$S\subseteq T$, queremos demostrarlo$x\in T$ también. Estar en$S$ medias$x = as+bt$ para algunos enteros$s$ y$t$. Ya que$d=\gcd(a,b)$, sabemos que$d\mid a$ y$d\mid b$. De ahí,$a=da'$ y$b=db'$ para algunos enteros$a'$ y$b'$. Entonces\[x = as+bt = da's+db't = d(a's+b't), \nonumber\] donde$a's+b't$ es un entero. Esto demuestra que$x$ es un múltiplo de$d$. De ahí,$x\in T$.

Para demostrarlo$T\subseteq S$, basta con demostrarlo$d\in S$. La razón es, si$d=as+bt$ para algunos enteros$s$ y$t$, entonces$nd = n(as+bt) = a(ns)+b(nt)$ implica eso$nd\in S$.

Para probarlo$d\in S$, considere$S^+$. Ya que$a=a\cdot1+b\cdot0$, tenemos$a\in S^+$. Por lo tanto,$S^+$ es un conjunto no vacío de enteros positivos. El principio de ordenamiento correcto implica que$S^+$ tiene un elemento más pequeño. Llámenlo$e$. Entonces\[e = as^*+bt^* \nonumber\] para algunos enteros$s^*$ y$t^*$. Eso ya lo sabemos$a\in S^+$. Siendo el elemento más pequeño en$S^+$, debemos tener$e\leq a$. Entonces$a=eq+r$ para algunos enteros$q$ y$r$, donde$0\leq r<e$. Si$r>0$, entonces\[r = a-eq = a-(as^*+bt^*)q = a(1-s^*q)+b(-t^*q). \nonumber\] Esto hace$r$ una combinación lineal de$a$ y$b$. Ya que$r>0$, encontramos$r\in S^+$. Ya que$r<e$ contradiría la minimalidad de$e$, debemos tener$r=0$. En consecuencia,$a=eq$, así$e\mid a$. De igual manera$b = a\cdot0+b\cdot1\in S^+$, ya que, podemos aplicar el mismo argumento para demostrarlo$e\mid b$. Concluimos que$e$ es un divisor común de$a$ y$b$.

Que$f$ sea cualquier divisor común de$a$ y$b$. Entonces$f\mid a$ y$f\mid b$. De ello se deduce que$f\mid (ax+by)$ para cualquier número entero$x$ y$y$. En particular,$f\mid(as^*+bt^*)=e$. De ahí,$f\leq e$. Ya que$e$ es en sí mismo un divisor común de$a$ y$b$, y acabamos de demostrar que$e$ es más grande que cualquier otro divisor común de$a$ y$b$, el entero$e$ mismo debe ser el mayor divisor común. De ello se deduce que$d=\gcd(a,b)=e\in S^+$. La prueba ya está completa.

Corolario$\PageIndex{2}$

El mayor divisor común de dos enteros distintos de cero$a$ y$b$ es el entero positivo más pequeño entre todas sus combinaciones lineales. En otras palabras,$\gcd(a,b)$ es el elemento positivo más pequeño del conjunto$\{as+bt \mid s,t\in\mathbb{Z}\}$.

Corolario$\PageIndex{3}$

Para cualquier número entero distinto de cero$a$ y$b$, existen enteros$s$ y$t$ tal que$\gcd(a,b)=as+bt$.

Prueba: Teorema 5.5.1 sostiene que el conjunto de todas las combinaciones lineales de$a$ y$b$ es igual al conjunto de todos los múltiplos de$\gcd(a,b)$. Dado que$\gcd(a,b)$ es un múltiplo de sí mismo, debe ser igual a una de esas combinaciones lineales. Así,$\gcd(a,b) = sa+tb$ para algunos enteros$s$ y$t$.

Teorema$\PageIndex{4}$

Dos enteros distintos de cero$a$ y$b$ son relativamente primos si y sólo si$as+bt=1$ para algunos enteros$s$ y$t$.

Prueba: El resultado es una consecuencia directa de la definición que$a$ y$b$ se dice que son relativamente primos si$\gcd(a,b)=1$.

Ejemplo$\PageIndex{1}\label{eg:moregcd-01}$

Es claro que 5 y 7 son relativamente primos, así lo son 14 y 27. Encuentra la combinación lineal de estos dos pares de números que es igual a 1.

Solución: Por inspección, o usando el algoritmo euclidiano extendido, encontramos$3\cdot5-2\cdot7=1$, y$2\cdot14-1\cdot27=1$.

Ejercicio práctico$\PageIndex{1}\label{he:moregcd-01}$

Demuéstralo$\gcd(133,143)=1$ encontrando una combinación lineal apropiada.

Ejercicio práctico$\PageIndex{2}\label{he:moregcd-02}$

Demostrar que 757 y 1215 son relativamente primos al encontrar una combinación lineal apropiada.

Ejemplo$\PageIndex{2}\label{eg:moregcd-02}$

De ello se\[(-1)\cdot n+1\cdot(n+1) = 1 \nonumber\] desprende$\gcd(n,n+1)=1$. Por lo tanto, cualquier par de enteros positivos consecutivos es relativamente primo.

Teorema$\PageIndex{5}$ (Euclid's Lemma)

Vamos$a,b,c\in\mathbb{Z}$. Si$\gcd(a,c)=1$ y$c\mid ab$, entonces$c\mid b$.

Discusión

Anote lo que sabemos y lo que queremos mostrar (WTS):\[\begin{array}{ll} \mbox{Know}: & as+ct=1 \mbox{ for some integers $s$ and $t$}, \\ & ab = cx \mbox{ for some integer $x$}, \\ \mbox{WTS}: & b = cq \mbox{ for some integer $q$}. \end{array} \nonumber\] Para poder mostrar eso$b=cq$ para algún entero$q$, tenemos que llegar a alguna información sobre$b$. Esta información debe provenir de las dos ecuaciones$as+ct=1$ y$ab=cx$. Ya que$b=b\cdot1$, podemos multiplicar$b$ a ambos lados de$as+ct=1$. Por convención, no podemos escribir

$(as+ct=1) \cdot b$.

¡Esta notación es inaceptable! La razón es: no podemos multiplicar una ecuación por un número. Más bien, tenemos que multiplicar ambos lados de una ecuación por el número:\[b = 1\cdot b = (as+ct)\cdot b = asb + ctb. \nonumber\] Obviamente,$ctb$ es un múltiplo de$c$; estamos un paso más cerca de nuestro objetivo. Ya que$asb = ab\cdot s$, y sí sabemos que de hecho$ab$ es un múltiplo de$c$, por lo que la prueba se puede completar. Ya estamos listos para amarrar los cabos sueltos, y pulir la prueba.

Prueba: Asumir$\gcd(a,c)=1$, y$c\mid ab$. Existen enteros$s$ y$t$ tal que\[as + ct = 1. \nonumber\] Esto lleva a\[b = 1\cdot b = (as+ct)\cdot b = asb + ctb. \nonumber\] Desde$c\mid ab$, existe un entero$x$ tal que$ab=cx$. Entonces\[b = ab\cdot s + ctb = cx\cdot s + ctb = c(xs+tb), \nonumber\] donde$xc+tb\in\mathbb{Z}$. Por lo tanto,$c\mid b$.

Corolario$\PageIndex{6}$

Si$a,b\in\mathbb{Z}$ y$p$ es un primo tal que$p\mid ab$, entonces cualquiera$p\mid a$ o$p\mid b$.

Prueba: Si$p\mid a$, terminamos con la prueba. Si$p\nmid a$, entonces$\gcd(p,a)=1$, y el lema de Euclides implica eso$p\mid b$.

No podemos aplicar el corolario si$p$ es compuesto. Por ejemplo,$6\mid 4\cdot15$, pero$6\nmid 4$ y$6\nmid 15$. Por otro lado, cuando$p\mid ab$, donde$p$ es un prime, es posible tener ambos$p\mid a$ y$p\mid b$. Por ejemplo,$5\mid 15\cdot 25$, sin embargo tenemos ambos$5\mid 15$ y$5\mid 25$.

Corolario$\PageIndex{7}$

Si$a_1,a_2,\ldots,a_n\in\mathbb{Z}$ y$p$ es un prime tal que$p\mid a_1 a_2 \cdots a_n$, entonces$p\mid a_i$ para algunos$i$, donde$1\leq i\leq n$. En consecuencia, si un primo$p$ divide un producto de$n$ factores, entonces$p$ debe dividir al menos uno de estos$n$ factores.

Prueba: Te dejamos la prueba como ejercicio.

Ejemplo$\PageIndex{3}\label{eg:moregcd-03}$

Demostrar que$\sqrt{2}$ es irracional.

Comentario

Anteriormente demostramos que$\sqrt{2}$ es irracional en un ejercicio práctico. La solución que presentamos tiene un defecto menor. Un paso clave en esa prueba afirma que\[\mbox{The integer 2 divides $m^2$, therefore 2 divides $m$}. \nonumber\] Esta afirmación es falsa en general. Por ejemplo, 4 divide$6^2$, pero 4 no divide 6. Por lo tanto, tenemos que justificar por qué esta pretensión es válida para 2.

Solución: Supongamos que$\sqrt{2}$ es racional, entonces podemos escribir\[\sqrt{2} = \frac{m}{n} \nonumber\] para algunos enteros positivos$m$ y$n$ que no comparten ningún divisor común excepto 1. Al cuadrar ambos lados y multiplicar en cruz da\[2n^2 = m^2. \nonumber\] Así 2 divide$m^2$. Dado que 2 es primo, el lema de Euclides implica que 2 también debe dividirse$m$. Entonces podemos escribir$m=2s$ para algún entero$s$. La ecuación anterior se convierte en\[2n^2 = m^2 = (2s)^2 = 4s^2. \nonumber\] De ahí, lo\[n^2 = 2s^2, \nonumber\] que implica que 2 divide$n^2$. Nuevamente, dado que 2 es primo, el lema de Euclides implica que 2 también divide$n$. Hemos demostrado que ambos$m$ y$n$ son divisibles por 2. Esto contradice la suposición de que$m$ y$n$ no comparten ningún divisor común. De ahí,$\sqrt{2}$ debe ser irracional.

Ejercicio práctico$\PageIndex{3}\label{he:moregcd-03}$

Demostrar que$\sqrt{7}$ es irracional.

Cerramos esta sección con un resultado realmente fascinante.

Teorema$\PageIndex{8}$

Para cualquier número entero positivo$m$ y$n$,$\gcd(F_m,F_n)=F_{\gcd(m,n)}$.

Corolario$\PageIndex{9}$

Para cualquier entero positivo$n$,$3\mid F_n \Leftrightarrow 4\mid n$.

Prueba

($\Rightarrow$) Si$3\mid F_n$, entonces, porque$F_3=4$, tenemos De\[3 = \gcd(3,F_n) = \gcd(F_4,F_n) = F_{\gcd(4,n)}. \nonumber\] ello se deduce eso$\gcd(4,n)=4$, lo que a su vez implica eso$4\mid n$.

($\Leftarrow$) Si$4\mid n$, entonces$\gcd(4,n)=4$, y\[\gcd(3,F_n) = \gcd(F_4,F_n) = F_{\gcd(4,n)} = F_4 = 3; \nonumber\] por lo tanto,$3\mid F_n$.

Resumen y revisión

Dados dos enteros distintos de cero, solo hay una combinación lineal especial que equivaldría a su divisor común más grande.
Todas las demás combinaciones lineales son solo múltiplos de su divisor más común.
Si$a$ y$c$ son relativamente primos, entonces el lema de$c$ Euclides afirma que si divide$ab$, entonces$c$ debe dividir$b$.
En particular, si$p$ es primo, y si$p\mid ab$, entonces cualquiera$p\mid a$ o$p\mid b$.

Ejercicio$\PageIndex{1}\label{ex:moregcd-01}$

Dado cualquier entero positivo arbitrario$n$, probarlo$2n+1$ y$3n+2$ son relativamente primos.

Ejercicio$\PageIndex{2}\label{ex:moregcd-02}$

Usa la inducción para demostrar que para cualquier entero$n\geq2$, si$a_1,a_2,\ldots,a_n\in\mathbb{Z}$ y$p$ es un primo tal que$p\mid a_1 a_2 \cdots a_n$, entonces$p\mid a_i$ para algunos$i$, donde$1\leq i\leq n$.

Ejercicio$\PageIndex{3}\label{ex:moregcd-03}$

Demostrar que$\sqrt{p}$ es irracional para cualquier número primo$p$.

Ejercicio$\PageIndex{4}\label{ex:moregcd-04}$

Demostrar que$\sqrt[3]{2}$ es irracional.

Ejercicio$\PageIndex{5}\label{ex:moregcd-05}$

Dado cualquier número entero positivo arbitrario$a$$b$,, y$c$, mostrar que si$a\mid c$,$b\mid c$, y$\gcd(a,b)=1$, entonces$ab\mid c$.

OBSERVACIÓN. Este resultado es muy importante. ¡Recuérdalo!

Ejercicio$\PageIndex{6}\label{ex:moregcd-06}$

Dado cualquier número entero positivo arbitrario$a$$b$,, y$c$, mostrar que si$a\mid c$, y$b\mid c$, entonces$ab\mid cd$, dónde$d=\gcd(a,b)$.

Ejercicio$\PageIndex{7}\label{ex:moregcd-07}$

Usa la inducción para demostrarlo$3\mid(2^{4n}-1)$ y$5\mid(2^{4n}-1)$ para cualquier entero$n\geq1$. Usa estos resultados para demostrarlo$15\mid (2^{4n}-1)$ para cualquier entero$n\geq1$.

Ejercicio$\PageIndex{8}\label{ex:moregcd-08}$

Demuéstralo$2\mid F_n \Leftrightarrow 3\mid n$ para cualquier entero positivo$n$.