1.3: La divisibilidad y el algoritmo de división

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\).

1. 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.
2. \(\forall a\in\mathbb{Z}\)uno tiene eso\(a\mid 0\).
3. 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

1. Demuestre eso\(5\mid 25, 19\mid38\) y\(2\mid 98\).
2. Usa el algoritmo de división para encontrar el cociente y el resto cuando 76 se divide por 13.
3. Utilice el algoritmo de división para encontrar el cociente y el resto cuando -100 se divide por 13.
4. 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\).
5. Demostrar que si\(a\) y\(b\) son enteros positivos y\(a\mid b\), entonces\(a\leq b\).
6. 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.
7. 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.
8. Mostrar que si\(m\) es un entero entonces\(3\) divide\(m^3-m\).
9. Mostrar que el cuadrado de cada entero impar es de la forma\(8m+1\).
10. Mostrar que el cuadrado de cualquier entero es de la forma\(3m\) o\(3m+1\) pero no de la forma\(3m+2\).
11. Demuéstralo si\(ac\mid bc\), entonces\(a\mid b\).
12. Demuéstralo si\(a\mid b\) y\(b\mid a\) entonces\(a=\pm b\).

Colaboradores y Atribuciones

• Template:ContribRaji