1.3: La divisibilidad y el algoritmo de división
- Page ID
- 115004
Ahora discutimos el concepto de divisibilidad y sus propiedades.
Divisibilidad de enteros
Si\(a\) y\(b\) son enteros tales que\(a\neq 0\), entonces decimos "\(a\)divide\(b\)" si existe un entero\(k\) tal que\(b=ka\).
Si\(a\) divide\(b\), también decimos "\(a\)es un factor de\(b\)" o "\(b\)es un múltiplo de\(a\)" y escribimos\(a\mid b\). Si\(a\) no divide\(b\), escribimos\(a\nmid b\). Por ejemplo\(2\mid 4\) y\(7\mid 63\), mientras\(5\nmid 26\).
- Tenga en cuenta que cualquier entero par tiene la forma\(2k\) para algún entero\(k\), mientras que cualquier entero impar tiene la forma\(2k+1\) para algún entero\(k\). Así\(2|n\) si\(n\) es par, mientras que\(2\nmid n\) si\(n\) es impar.
- \(\forall a\in\mathbb{Z}\)uno tiene eso\(a\mid 0\).
- Si\(b\in\mathbb{Z}\) es tal que\(|b|<a\), y\(b\neq 0\), entonces\(a\nmid b\).
Si\(a\),\(b\) y\(c\) son enteros tales que\(a\mid b\) y\(b\mid c\), entonces\(a\mid c\).
Desde\(a\mid b\) y\(b\mid c\), entonces existen enteros\(k_1\) y\(k_2\) tal que\(b=k_1a\) y\(c=k_2b\). Como resultado, tenemos\(c=k_1k_2a\) y por lo tanto\(a\mid c\).
Desde\(6\mid 18\) y\(18\mid 36\), entonces\(6\mid 36\).
El siguiente teorema establece que si un entero divide otros dos enteros entonces divide cualquier combinación lineal de estos enteros.
[thm4] Si\(a,b,c,m\) y\(n\) son enteros, y si\(c\mid a\) y\(c\mid b\), entonces\(c\mid (ma+nb)\).
Desde\(c\mid a\) y\(c\mid b\), entonces por definición existe\(k_1\) y\(k_2\) tal que\(a=k_1c\) y\(b=k_2c\). Así\[ma+nb=mk_1c+nk_2c=c(mk_1+nk_2),\] y por lo tanto\(c\mid (ma+nb)\).
El teorema [thm4] puede generalizarse a cualquier combinación lineal finita de la siguiente manera. Si
\[a\mid b_1, a\mid b_2,...,a\mid b_n\] entonces\[a\mid \sum_{j=1}^nk_jb_j\] para cualquier conjunto de enteros\(k_1,\cdots,k_n\in\mathbb{Z}\). Sería un buen ejercicio para probar la generalización por inducción.
El siguiente teorema afirma un resultado algo elemental pero muy útil.
[thm5] El Algoritmo de División Si\(a\) y\(b\) son enteros tales que\(b>0\), entonces existen enteros únicos\(q\) y\(r\) tales que\(a=bq+r\) donde\(0\leq r< b\).
Considera el conjunto\(A=\{a-bk\geq 0 \mid k\in \mathbb{Z}\}\). Tenga en cuenta que no\(A\) está vacío ya que para\(k<a/b\),\(a-bk>0\). Por el principio de ordenamiento de pozos,\(A\) tiene un elemento mínimo\(r=a-bq\) para algunos\(q\). Observe que\(r\geq 0\) por construcción. Ahora si\(r\geq b\) entonces (since\(b>0\))\[r>r-b=a-bq-b=a-b(q+1)=\geq 0.\] Esto lleva a una contradicción ya que\(r\) se supone que es el número entero menos positivo de la forma\(r=a-bq\). Como resultado tenemos\(0\leq r <b\).
Eso lo demostraremos\(q\) y\(r\) somos únicos. Supongamos que\(a=bq_1+r_1\) y\(a=bq_2+r_2\) con\(0\leq r_1<b\) y\(0\leq r_2<b\). Entonces tenemos\[b(q_1-q_2)+(r_1-r_2)=0.\] Como resultado tenemos\[b(q_1-q_2)=r_2-r_1.\] Así lo conseguimos\[b\mid (r_2-r_1).\] Y desde\(-\max(r_1,r_2)\leq|r_2-r_1|\leq\max(r_1,r_2)\), y\(b>\max(r_1,r_2)\), entonces\(r_2-r_1\) debe ser\(0\), i.e\(r_2=r_1\). Y ya que\(bq_1+r_1=bq_2+r_2\), también lo conseguimos\(q_1=q_2\). Esto demuestra singularidad.
Si\(a=71\) y\(b=6\), entonces\(71=6\cdot 11+5\). Aquí\(q=11\) y\(r=5\).
Ejercicios
- Demuestre eso\(5\mid 25, 19\mid38\) y\(2\mid 98\).
- Usa el algoritmo de división para encontrar el cociente y el resto cuando 76 se divide por 13.
- Utilice el algoritmo de división para encontrar el cociente y el resto cuando -100 se divide por 13.
- Mostrar que si\(a,b,c\) y\(d\) son enteros con\(a\) y\(c\) distinto de cero, tal que\(a\mid b\) y\(c\mid d\), entonces\(ac\mid bd\).
- Demostrar que si\(a\) y\(b\) son enteros positivos y\(a\mid b\), entonces\(a\leq b\).
- Demostrar que la suma de dos enteros pares es par, la suma de dos enteros impares es par y la suma de un entero par y un entero impar es impar.
- Mostrar que el producto de dos enteros pares es par, el producto de dos enteros impares es impar y el producto de un entero par y un entero impar es par.
- Mostrar que si\(m\) es un entero entonces\(3\) divide\(m^3-m\).
- Mostrar que el cuadrado de cada entero impar es de la forma\(8m+1\).
- Mostrar que el cuadrado de cualquier entero es de la forma\(3m\) o\(3m+1\) pero no de la forma\(3m+2\).
- Demuéstralo si\(ac\mid bc\), entonces\(a\mid b\).
- Demuéstralo si\(a\mid b\) y\(b\mid a\) entonces\(a=\pm b\).