Divisibilidad
El concepto de divisibilidad es uno de los más importantes que veremos en Teoría de números. Con él pretendemos dar una sustitución de la división que no siempre es posible en el conjunto de los números enteros.
Decimos que un número entero \(b\) es divisible entre un entero \(a\) (distinto de cero) si existe un entero \(c\) tal que: \(b = a · c.\); es decir, dados \(a,b\in\mathbb{Z}\), \[a|b\Leftrightarrow \exists c\in\mathbb{Z};\ b = ac.\]
Se suele expresar de la forma \(a|b\), que se lee: \(a\) divide a \(b\), o \(a\) es un divisor de \(b\), o, también \(b\) es múltiplo de \(a\) (\(b=\dot{a}\)).
Sean \(a, b, c \in \mathbb{Z}\), es decir \(a\), \(b\) y \(c\) son números enteros. Se dan las propiedades básicas:
- Si \(a\neq 0\) entonces \(a\mid a\) [Propiedad reflexiva]
- si \(a\mid b\) y \(b\mid a\) entonces \(|a|= |b|\). [Son iguales o bien uno es el opuesto del otro]
- Cuando \(a\mid b\) y \(b\mid c\), entonces \(a\mid c\) [Propiedad transitiva].
- Si \(a\mid b\) y \(b \neq 0\), entonces \(|a|\leq |b|\).
- \(a\mid b\) y \(a\mid c\), implica \(a\mid (\beta b+ \gamma c)\ \ \forall \ \beta, \gamma \in \mathbb{Z}\). [Divisor de la combinación lineal]
- \(a\mid b\) y \(a\mid c\), implica \(a\mid (\theta b^k+ \kappa c^j)\ \ \forall \ \theta, \kappa, k, j \in \mathbb{Z}\). [Divisor de la combinación lineal de potencias]
- Si \(a\mid b\) y \(a\mid (b \pm\ c)\), entonces \(a\mid c\).
- De \(a\mid b\) y \(a\neq 0\), se deduce \(\frac{b}{a}\mid b\). [Divisores conjugados]
- Para \(c\neq 0\), \(a\mid b\) si y solo si \(ac\mid bc\).
Ejercicio: Probar que si \(a,b,d\in\mathbb{Z}^+\), \(a\) es impar y si \(d|a\) y \(d|(ab+2)\), entonces \(d=1\).
Ejercicio: ¿Es \(\sqrt{2}\) racional?
Ejercicio: Sea \(a\) y \(b\) dos números irracionales, ¿es \(a^b\) irracional?
Os enlazo unos polimedias interesantes:
- Divisibilidad –> http://youtu.be/FVTzu5p5mWY
- Divisibilidad Ejemplo 1 –> http://youtu.be/4BmqFuebG9A
- Divisibilidad Ejemplo 2 –> http://youtu.be/GXvUP-dUjww
- Divisibilidad Ejemplo 3 –> https://youtu.be/5H8hirvHQKI
- Divisibilidad Ejemplo 3b –> https://youtu.be/lHA6c0d-jCc
- Divisibilidad Ejemplo 4 –> https://youtu.be/w3ZmXWswCM8
- Divisibilidad Ejemplo 5 –> https://youtu.be/gtpXda-tPL0
- Divisibilidad Ejemplo 6 –> https://youtu.be/QZiFMtV9x_s
Algoritmo de la división
Comenzamos explicando El algoritmo de la división, que intenta dar consistencia al procedimiento habitual de división entre números enteros, recordando que esta no existe como tal, ya que la división no siempre existe. Sin embargo, podemos dar un resultado que nos ayuda a comprender que entendemos por división en los números enteros.
Teorema: Dados dos números enteros \(a\) y \(b\), con \(a\) no nulo, la división euclídea asocia un cociente \(q\in\mathbb{Z}\) y un resto \(r\in\mathbb{Z}\), únicos, que verifican: \[b=q\,a+r,\quad 0\leq r<|a|\]
Colorario:[Propiedad arquimediana] Dados dos números enteros \(a\) y \(b\), con \(b>a>0\), entonces existe un \(q\in\mathbb{Z}\) talque \[a(q-1)< b < aq\]
Veamos una algoritmo para obtener el cociente y el resto de la división entera: Sean \(a,b\in\mathbb{Z}\), con \(b>a>0\) y sea \(q_0\in\mathbb{Z}\) talque \(r_0=b-aq_0>a\), calculamos
| \(b\) | \(a\) |
| \(r_0=b-aq_0\) | \(q_0\) |
| \(r_1=r_0-aq_1\) | \(q_1\) |
| \(r_2=r_1-aq_2\) | \(q_2\) |
| \(\vdots\) | \(\vdots\) |
| \(r_n=r_{n-1}-aq_n\) | \(q_n\) |
mientras \(r_n>a\). Entonces, \(b=a\left(\sum_{i=0}^nq_i\right)+r_n\).
Si quisiéramos realizar un programa que lo calcule sobraría con asignar \(q_i=1\forall i\) y obtendríamos lo que buscamos:
\[\begin{array}{l}i=1;\\ r[i]=b-a; \\ while(r[i]>a) \\ \qquad r[i++]=r[i]-a; \\ endwhile \\ print({}’Cociente =\%d’,i-\,-))\\ print({}’resto =\%d’,r[i-\,-]))\\ \end{array} \]
Sabemos que en el conjunto de los número enteros no existe la división como tal. Sin embargo, en algunos casos podemos utilizar las siguientes aplicaciones que nos ayudan a trabajar con números reales tratándolos como enteros:
Definición: Sea \(\lfloor \cdot \rfloor:\mathbb{R}\to\mathbb{Z}\), definida por,
\[\forall x\in\mathbb{R},\ \lfloor x\rfloor=\{n\in\mathbb{Z}:n\leq x<n+1\}\]
Del mismo modo,
Definición: Sea \(\lceil \cdot \rceil:\mathbb{R}\to\mathbb{Z}\), definida por,
\[\forall x\in\mathbb{R},\ \lceil x\rceil=\{n\in\mathbb{Z}:n-1\leq x<n\}\]
Ejemplo: ¿Cuál es el resto de la división de \(F_5=2^{2^5}+1\) por 13?
Con estas definiciones podemos reformular el algoritmo de la división de la siguiente forma:
Teorema: Sean dos números enteros \(a\) y \(b\), con \(a\) no nulo. Existe un único \(r\in\mathbb{Z}\) tal que \[\text{Si } a>0,\ b=\left\lfloor\frac{b}{a}\right\rfloor\cdot a+r,\text{ con } 0\leq r<a,\] \[\text{Si } a<0,\ b=\left\lceil\frac{b}{a}\right\rceil\cdot a+r,\text{ con } 0\leq r<|a|.\]
Ejemplo: Sean \(n,p\in\mathbb{N}\), con \(0<p\leq n\). ¿Cuántos números divisibles por \(p\) hay en el conjunto \(\{1,2,\ldots,n\}\)
Veamos una curiosidad. Para conocer el número de cifras que tiene un entero positivo cualquiera basta con calcular :\[\# n=\text{Nº cifras de }n=\lfloor\log(n)\rfloor+1\] donde \(\log(n)\) es el logaritmo decimal.
Ejemplo: ¿Cuántas cifras tiene \(F_{7}\)?
Bases
En un sistema de numeración posicional, se le llama base al número que define el orden de magnitud en que se ve incrementada cada una de las cifras sucesivas que componen el número. Es también la cantidad de símbolos presentes en dicho sistema. Por ejemplo, el sistema de numeración decimal (el más utilizado en la actualidad) utiliza como base el número 10 (diez): hay 10 símbolos o dígitos, y cada uno de ellos se incrementa en un orden de magnitud de 10 por cada posición consecutiva.
En cualquier sistema de numeración, el número \({\displaystyle x}\) y su base \({\displaystyle y}\) se denotan convencionalmente como \((x)_y\), esto se cumple para todos los sistemas salvo el decimal, por ser la manera más habitual de expresar valores, donde se omite la base. Así, por ejemplo, \({\displaystyle (100)_{10}}\) (o sin la base) es el número 100 en el sistema decimal; y \({\displaystyle (100)_{2}}\) es el número 4 en el sistema binario.
Base 2
La base habitual de trabajo es la base 10, el sistema decimal. En informática se trabaja a partir de la base 2, sistema binario. Para pasar del sistema decimal al binario operamos así: dado \(n\) en decimal,
\[\begin{split}
n&=q_02+r_0\\ q_0&=q_12+r_1\\ &\vdots \\ q_{i-1}&=q_i2+r_i
\end{split}\]
hasta que \(q_i=0\). De este modo, \[n=(r_{i-1}r_{i-2}\ldots r_0)_2\]
Observemos que, en este caso, \[n=\sum_{k=0}^{i-1}r_k\ 2^k\]
Base \(m\)
En general, un entero en base \(m\) lo escribimos \[(d_{i-1}\ldots d_0)_m,\] donde \(d_k\) son los \(i\) dígitos del número tales que \(0\leq d_k<m\ \forall k=\{0,\ldots,i-1\},\) verificando
\[(n)_{10}=\sum_{k=0}^{i-1}d_k\ m^k=d_{i-1}m^{i-1}+d_{i-2}m^{i-2}+\ldots d_1m+d_0\]
Los dígitos \(d_k\) son los obtenidos mediante el algoritmo de la división:
\[\begin{split}
n&=q_0m+d_0\\ q_0&=q_1m+d_1\\ &\vdots \\ q_{i-1}&=q_im+d_i
\end{split}\]
hasta que \(q_i=0\).
Ejemplo: ¿Cuánto suman los dígitos de \(F_{4}\) en base 7?
Ejemplo: ¿Cuánto suman los dígitos de \((6789)_{10}\) en base 7?
División con resto con la calculadora
Terminamos introduciendo un anillo que trabajaremos constantemente: (\(\mathbb{Z}_n\), +, •). Recordemos que \(\mathbb{Z}_n\) es el conjunto de las clases residuales, \(\mathbb{Z}_n=\{\bar{i};\ i\in\{1,\ldots,n-1\}\}\), donde \[\bar{i}=\{a\in\mathbb{Z};\ a-i=\dot{n}\}.\]
|
Ejercicio: ¿Qué afirmación no es cierta? |