Autor Tema: Aritmética de módulos y aplicación a criterios de divisibilidad

0 Usuarios y 1 Visitante están viendo este tema.

05 Junio, 2010, 07:06 pm
Leído 37465 veces

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
En vistas de que este tema se hace cada vez más común, y de lo básico que resulta, parece conveniente fijar un thread con los resultados básicos pertinentes.
Lo que expongo aquí es un primer intento. Si ustedes consideran que hay que completar la información o cambiar algo, indíquenlo.

También se puede ir agregando en el futuro más propiedades relacionadas con congruencias, que sean aplicables a distintas áreas de la Teoría de Números.
Sugieran ustedes qué agregar.

Sección 1. Números enteros. Generalidades.

Sin entrar en muchas definiciones complicadas, vamos a aceptar que todos sabemos o entendemos qué clase de números son los enteros.
Designaremos con \( \mathbb{Z} \) al conjunto de los números enteros, e indiquemos intuitivamente su "definición":

\( \mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\} \)

Como puede verse, los enteros negativos vienen desde el infinito negativo, pasan por 0, y siguen siempre de 1 en 1 yendo hacia el infinito positivo.

Denotamos \( \mathbb{Z}_+ \) al subconjunto de enteros positivos y \( \mathbb{Z}_- \) al subconjunto de enteros negativos:

\( \mathbb{Z}_+=\{n\in\mathbb Z|n>0\} \)
\( \mathbb{Z}_-=\{n\in\mathbb Z|n<0\} \)

Asumimos que en \( \mathbb{Z} \) tenemos definidas dos operaciones binarias, suma y producto, que son conmutativas, asociativas, y cumplen la ley distributiva.
Además, el 0 es neutro para la suma, el 1 es identidad para el producto, y la suma es invertible, vale decir, todo entero \( m \) tiene un opuesto \( -m \) tal que \( m+(-m)=0 \).

Sin embargo, no todo número entero tiene inverso multiplicativo.
De hecho, los únicos enteros invertibles son el 1 y el -1, y cada uno de ellos es su propio inverso.

Se cumplen también las reglas de los signos, entre muchas otras propiedades conocidas por todos nosotros.

En todo nuestro trabajo posterior asumiremos que nuestro campo de trabajo será el conjunto \( \mathbb Z \) de números enteros con las operaciones de suma y producto.

Una propiedad muy importante, que asumiremos sin demostración, es el Principio de Inducción:

Todo subconjunto inductivo de \( \mathbb{Z}_+ \) es igual a \( \mathbb{Z}_+ \)

y está también su propiedad equivalente: el Principio de Buena Ordenación, el cual enunciaremos en un formato aplicable a todos los enteros:

Todo subconjunto no vacío de \( \mathbb{Z} \) acotado inferiormente, tiene un elemento mínimo.
Igualmente:
Todo subconjunto no vacío de \( \mathbb{Z} \) acotado superiormente, tiene un elemento máximo.

Finalmente convengamos en denotar \( |m| \) al valor absoluto de un número entero \( m \).


05 Junio, 2010, 07:09 pm
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Sección 2. Divisibilidad.

\( \bullet \) Definición (Divisibilidad). Dados dos números enteros \( m,n \), se dice que \( m \) es divisor de \( n \) si, y sólo si, existe un número entero \( k \) tal que \( mk=n \). También se suele decir que \( m \) divide a \( n \), o que \( n \) es múltiplo de \( m \). La notación que se usa para indicar esta relación es: \( m|n \).
En símbolos, tendríamos pues que:

\( m\mid n \) si, y sólo si \( \exists{k\in \mathbb{Z}}:mk=n \)


En el siguiente Teorema hacemos un sumario de los resultados básicos de divisibilidad, y la demostración la dejamos como ejercicio.

Teorema 1 (propiedades varias de la divisibilidad) Sean \( m,n,a \) números enteros.

  • \( 1 \mid m \), \( -1\mid m \).
  • \( m\mid m \), \( m\mid -m \).
  • \( m\mid 0 \).
  • Si \( m\neq0 \) entonces \( 0\not\mid m \) (o sea, \( 0 \) no divide a \( m \)).
  • Si \( m\mid n \) entonces \( am\mid an \).
  • Si \( m\mid n \) y \( n\neq 0 \) entonces \( 1\leq |m|\leq |n|. \)

Observemos cómo la última propiedad nos indica que el "tamaño" de un divisor necesariamente es menor que el de su múltiplo.
La excepción a esta regla es el número 0.

En cuanto a la divisibilidad como relación de orden, podemos decir lo siguiente:

Teorema 2 (cuasi-orden de la relación de divisibilidad). La relación de divisibilidad es un cuasi-orden parcial en \( \mathbb{Z}_+ \).

Esto quiere decir que:

  • Reflexividad: Si \( a\in\mathbb{Z} \) entonces \( a\mid a \).
  • Cuasi-Antisimetría: Si \( a,b\in\mathbb{Z} \), \( a\mid b \) y \( b\mid a \), entonces \( |a|=|b| \).
  • Transitividad: Si \( a,b,c\in\mathbb{Z} \),  \( a\mid b \) y \( b\mid c \), entonces \( a\mid c \).

La demostración la dejamos como ejercicio.

El término cuasi-orden parcial me lo acabo de inventar, y tan sólo pone de manifiesto que la antisimetría se cumple con una versión con signos. Si \( a\mid b \) y \( b\mid a \) no podemos asegurar que \( a=b \), como en un orden parcial ocurriría, pero sin embargo eso es casi cierto, porque en realidad se obtiene que los valores absolutos de \( a \) y \( b \) coinciden.

Si restringimos la divisivilidad al conjunto de enteros positivos, se obtiene un orden parcial.

Sin embargo, aún en ese caso el orden obtenido no es total, porque hay al menos un par de enteros positivos que no pueden compararse entre sí.
Por ejemplo, el 2 y el 3 no son el uno divisor del otro.


\( \bullet \) Definición (Primos, compuestos, coprimos). Sea \( m \) un número entero distinto de \( 1,-1,0 \). Se dice que \( m \) es primo si sus únicos divisores son \( 1,-1,m,-m \). Se dice que \( m \) es compuesto si no es primo.
Dados dos enteros \( m,n \), se dice que son coprimos si los únicos números enteros \( d \) que son divisores, tanto de \( m \) como de \( n \) al mismo tiempo, son \( 1 \) y \( -1 \).

Nótese que hemos podido dar la noción de coprimalidad sin apelar al clásico uso del máximo común divisor.

Obsérvese también que \( p \) es primo si, y sólo si \( -p \) es primo.
Ídem con compuestos.
Los numeros 1, 0, no son primos ni compuestos.

Teorema 3 (Algoritmo de División). Sean \( m \) entero y \( d \) entero positivo. Entonces existen únicos enteros \( q,r \) tales que
  • \( m=qd+r \)
  • \( 0\leq r < d \)

Al número \( q \) se le llama cociente, y al número \( r \) se le llama resto.

Si el resto es 0, se escribe \( m/d=q \).
En ese caso se puede comprobar que \( d,q \) son ambos divisores de \( m \) y además \( dq=m \).
Más aún, podemos definir en este caso también \( m/(-d)=-q \).

La operación \( m/d \) para enteros \( m,d \) con \( d\neq \) distinto de 0, se llama división, y claramente está definida sólo cuando \( d \) es divisor de \( m \).
De lo contrario, la división no está definida.

La división puede definirse usando otros métodos, pero siguiendo el "tren" de lo que vengo escribiendo, lo más simple que me quedó fue lo que está escrito ahí arriba.

\( \bullet \) Lema Fundamental de la Aritmética. Todo entero distinto de 1, -1 o 0 es divisible por algun número primo.
Demostración:

Sea \( m \) entero positivo mayor que 1. Supongamos que no es primo. En ese caso, existe un entero \( d \) que es divisor de \( m \) y tal que es distinto de \( 1, -1, m, -m \). Tanto \( d \) como \( -d \) son divisores de \( m \), así que podemos suponer que \( d \) es entero positivo, sin pérdida de generalidad.
Tenemos que \( 1< d<m \). Puede que \( d \) sea primo o compuesto.
Si fuera primo, habríamos terminado. Así que supongamos que es compuesto.
Denotemos \( d_1=d \). Aplicando a \( d_1 \) el mismo procedimiento que aplicamos a \( m \), podemos hallar un número entero positivo \( d_2 \) tal que \( d_2\mid d_1 \) y \( 1< d_2< d_1 \).
Supongamos que tras un número finito de pasos, con este mismo procedimiento, hemos hallado números enteros positivos \( d_1,d_2,...,d_k \) tales que:

* \( d_k< ... <d_2<d_1<m. \)
* \( d_k\mid d_{k-1},...,d_2\mid d_1, d_1\mid m. \)

De nuevo, puede que d_k sea primo o compuesto. Si es compuesto, se puede seguir con el procedimiento para hallar un nuevo entero positivo \( d_{k+1} \) que divide a \( d_k \) y tal que \( 1<d_{k+1}<d_k \).
Sin entrar en demasiados formalismos, digamos que este procedimiento no puede seguir indefinidamente, porque en tal caso tendríamos una sucesión infinita y decreciente de números enteros positivos. Esto no puede ser, porque se contradice el Principio del Descenso Infinito.

Así que hay algún \( d_k \) en el que el proceso termina, y ese número \( d_k \) es primo.

\( \bullet \) Teorema 4 (Infinidad de primos). Los números primos son infinitos.

La demostracion queda como ejercicio, y sigue el clasico argumento de Euclides de razonar por el absurdo, o sea, suponer que hay una cantidad finita de primos positivos \( p_1,...,p_k \) y definir \( p=1+p_1...p_n \). Este valor \( p \) es mayor que todos los primos de la lista, y a su vez resulta indivisible por los otros primos. Y sabemos también que todo número entero que no es primo, es divisible por algún primo. Contradicción.

La lista de números primos positivos forma un conjunto infinito \( \mathbb{P}=\{2, 3, 5, 7, 11, 13, ...\} \).
Se suele denotar a esta lista con una sucesión subindicada, la cual adoptaremos de aquí en adelante: \( \mathbb{P}=\{p_1,p_2,p_3,...\} \).
Así, tenemos \( p_1=2, p_2 = 3, p_3 = 5, p_4 = 7 \), etc.
Procuraremos no usar la letra \( p \) para otra cosa que primos positivos.

\( \bullet \) Teorema Fundamental de la Aritmética. Dado un número entero \( m \), existen únicos enteros positivos primos \( q_1,q_2,...,q_k \) tales que \( q_1<q_2<...<q_k \), únicos exponentes enteros positivos \( c_1,...,c_k \), y un valor \( s=0 \) ó \( 1 \), de tal manera que:

\( m=(-1)^s \;q_1^{c_1}q_2^{c_2}...q_k^{c_k}. \)

Lo anterior puede escribirse en la siguiente forma alternativa:

\( m=(-1)^s \;\prod_{i=1}^\infty p_i^{e_i}, \)

donde los exponentes \( e_i \) son números enteros positivos o bien 0, y sólo una cantidad finita de ellos es no nula, de manera que el producto infinito en realidad es siempre finito y tiene pleno sentido (no hace falta plantearse cuestiones de convergencia o problemas con el infinito).


\( \bullet \) Definición (Máximo Común Divisor) Dados dos números enteros \( m, n \) cualesquiera, tales que al menos uno de ellos (digamos \( m \)) es distinto de 0, se llama máximo común divisor al máximo número entero positivo \( d \) que es divisor de \( m \) y \( n \) al mismo tiempo.
Se usan las notaciones \( (m,n)=d \) y también \( mcd(m,n)=d \).

En realidad primero habría que probar que tal máximo, existe. Que m, n tienen al menos un divisor positivo común, es obvio porque el 1 divide siempre a ambos.
Si formamos la lista de divisores comunes enteros positivos, dicha lista tendrá un máximo porque sabemos que todo divisor es menor que el valor absoluto de \( m \).

Se puede demostrar fácilmente que dos enteros \( m, n \) son coprimos si y sólo si \( mcd(m,n)=1 \). 

\( \bullet \) Identidad de Bezout. Sean \( m,n \) números enteros con \( mcd(m,n) = d \). En tal caso, existen enteros \( u, v \), tales que \( um+vn=d \).

\( \bullet \) Teorema 5 (coprimalidad y combinaciones lineales). Dados dos enteros \( m,n \), resulta que ellos son coprimos entre sí si, y sólo si, existen enteros \( a, b \) tales que \( am+bn=1 \).



\( \bullet \) Definición (Mínimo Común Múltiplo) Dados dos números enteros \( m, n \) cualesquiera, ambos distintos de 0, se llama mínimo común múltiplo al mínimo número entero positivo \( c \) que es múltiplo de \( m \) y \( n \) al mismo tiempo.
Se usan las notaciones \( [m,n]=c \) y también \( mcm(m,n)=c \).

En principio, existe un número positivo que es múltiplo de m, n, a saber: u = |mn|. Luego existe el mínimo de los números que son múltiplos de m y n a la vez, por la minimalidad de los números naturales. Más aún, se tienen las siguientes desigualdades:

\( 1\leq mcd(m,n)\leq min(m,n)\leq max(m,n)\leq mcm(m,n)\leq mn \)


\( \bullet \) Teorema 6 (mcd y mcm). Sean \( m,n \) enteros positivos. Vale la siguiente igualdad:

\( mn=mcd(m,n) mcm(m,n). \)




05 Junio, 2010, 09:01 pm
Respuesta #2

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Sección 3. Congruencias

\( \bullet \) Definición (congruencia). Sean \( a, b \) números enteros cualesquiera, y sea \( d \) un entero positivo. Se dice que \( a,b \) son congruentes módulo \( d \) si al aplicar el algoritmo de la división, el resto \( r \) al dividir \( a \) por \( d \) es igual al resto de dividir \( b \) por \( d \). Más precisamente, si \( q,\tilde q,r,\tilde r \), satisfacen \( a=qd+r,b= \tilde q d+\tilde r \), \( 0\leq r,\tilde r< d \), entonces \( r=\tilde r \). En este caso se escribe la siguiente relación, llamada de congruencia módulo \( d \):

\( a\equiv b \; (mod\quad d) \)

Yo también uso la siguiente forma, que no sé si aparece en algún libro:

\( a\equiv_d b  \)

\( \bullet \) Se puede ver fácilmente que una definición equivalente a la anterior sería la siguiente: \( a\equiv_d{b} \) si y sólo si \( d \) es divisor de \( a-b \).

\( \bullet \) Teorema 1 (toda congruencia es una equivalencia). Dado un entero positivo \( d \), la relación de congruencia \( \equiv_d \) es una relación de equivalencia. Esto significa que, dados enteros \( a,b,c \):

  • Reflexividad: \( a\equiv_d a \).
  • Simetría: Si \( a\equiv_d b \) entonces \( b\equiv_d{a} \).
  • Transitividad: Si \( a\equiv_d b \), \( b\equiv_d c \) entonces \( a\equiv_d{c} \).

Como sabemos, toda relación de equivalencia induce una partición del conjunto total en clases de equivalencia.
En este caso, para un entero positivo d, el conjunto \( \mathbb{Z} \) de enteros queda particionado en \( d \) clases de equivalencia, que son:

\( [j]_d = \{j+dm| m\in\mathbb{Z}\},\qquad j\in\mathbb{Z} \)

Así, \( [0]_d,...,[d-1]_d \) son todas las clases de equivalencia posibles de la relación de congruencia módulo \( d \).

En particular, si \( r \) es el resto obtenido en el algoritmo de división, se obtiene que:

\( a\equiv_d r \)

A veces puede ser útil usar números negativos al operar con congruencias.
Así que observemos que \( r-d < 0 \) y que el resto de dividir el número \( r-d \) por \( d \) es de nuevo \( r \).
Así que:

\( -(d-r)\equiv_d r \)




\( \bullet \) Teorema 2 (Aritmética elemental de restos) Las operaciones elementales de suma,  producto y potencia de exponente positivo, conservan el resto tras aplicar el algoritmo de la división.

Detalles...
Para decirlo más precisamente, sean \( a, b, \bar a, \bar b \) enteros dados, y sea \( d \) un entero positivo.
Sea también \( j \) un entero positivo.
Supongamos ahora que en el algoritmo de la división hemos obtenido que:
  • \( a=md+r,\qquad \bar a=\bar md+ r. \)
  • \( b=nd+s,\qquad \bar b=\bar nd+ s. \)
  • \( a+b=Md+R,\qquad \bar a+\bar b=\bar M+\bar R \)
  • \( ab=\mu d+\rho,\qquad \bar a\bar b=\bar \mu+\bar \rho \)
  • \( a^j=\omega d+t,\qquad \bar a^j=\bar \omega d+\bar t \)

Entonces se tiene que:

\( R=\bar R,\qquad \rho=\bar\rho,\qquad t=\bar t. \)
[cerrar]


En tal caso, están definidas sin ambigüedad las operaciones aritméticas de suma, resta, producto y potencia entera positiva sobre las clases de equivalencia módulo \( d \):

  • \( [a]_d+[b]_d =[a+b]_d \)
  • \( [a]_d [b]_d =[a b]_d \)
  • \( [a]_d^j =[a^j]_d \)

El resultado anterior puede establecerse de forma más clara usando congruencias:

\( \bullet \) Teorema 3 (aritmética de congruencias) Sean números enteros \( a, b, a'.b', \) un entero positivo \( j \). Dado un entero positivo \( d \), si se cumple que \( a\equiv_d{\bar a} \) y \( b\equiv_d{\bar b} \) entonces se tiene que:

  • \( a+b \equiv_d \bar a+\bar b \)
  • \( a b \equiv_d \bar a \bar b \)
  • \( a^j \equiv_d \bar a^j \)

Observación importante: La división en general no está permitida en las igualdades que involucran congruencias.

Sin embargo, hay algunos casos en los que sí está permtido dividir:

\( \bullet \) Teorema 4 (caso que permite dividir en congruencias) Sean \( a,b \) números enteros. Sea \( d \) un entero positivo, y sea \( m \) entero divisor común de \( a, b \).
Si \( a\equiv_d{b} \) y si \( m \) es coprimo con \( d \), entonces \( a/m\equiv_d b/m \).

Antes de seguir, hagamos las observaciones súper-básicas siguientes:

\( \bullet \) Dados \( a,b\in\mathbb{Z},d\in\mathbb{Z}_+ \) se tiene que \( a\equiv_d{b} \) si y sólo si \( d \) es divisor de \( a-b \).

\( \bullet \) Dados \( a\in\mathbb{Z},d\in\mathbb{Z}_+ \) se tiene que \( d \) es divisor de \( a \) si y sólo si \( a\equiv_d{0} \).


\( \bullet \) Teorema 5 (Otras propiedades de las congruencias). Sean \( a,b \) enteros, y sean \( d,D, d_1,...,d_k \) enteros positivos.

  • Si \( a\equiv_{d_1} b,...,a\equiv_{d_k} b \) entonces \( a\equiv_d{b} \) siendo \( d \) el mínimo común múltiplo de \( d_1,...,d_k \).
  • Si \( a\equiv_d b \) y \( D\mid d \), entonces \( a\equiv_D{b} \).
  • Si \( a\equiv_d b \) y \( D\mid a,D\mid b,D \mid d \), entonces \( a/D\equiv_{d/D}{b/D} \).
  • Si \( a\equiv_d b \) y \( m\mid a,m\mid b \) y \( D=mcd(d,m) \), entonces \( a/m \equiv_{d/D}{b/m} \).

\( \bullet \) Teorema 6 (producto de divisores coprimos). Sean \( a,b \) enteros, y sean \( d_1,...,d_k \) enteros positivos. Supongamos además que para par \( i,j \) tal que \( i\neq j \) se tiene que \( mcd(d_i,d_j)=1 \). Entonces:

\( a\equiv_{d_1}{b},...,a\equiv_{d_k}{b}\qquad\Longleftrightarrow{}\qquad a\equiv_{d_1...d_k}{b} \)


05 Junio, 2010, 09:52 pm
Respuesta #3

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Sección 4. Criterios de Divisibilidad

Muchas hemos visto criterios de divisibilidad, y nos parecen reglas mágicas que permiten decir si un número dado es o no divisible por 3 o por 9 tan sólo conociendo sus cifras.
No hay nada sobrenaturales en esto, y ahora vamos a ver cómo encontrar criterios de divisibilidad para cualquier divisor \( d \).

Primero vamos a trabajar con números representados en base 10, y luego generalizaremos a una base b cualquiera.

Base 10.

Sea \( d \) un número entero positivo que supondremos fijado en lo que sigue.
Nos interesa saber si un número entero positivo \( m \) es divisible o no por \( d \), conociendo las cifras de \( m \), y sin tener que hacer la tediosa operación de dividir.

Para ello, recordemos que si la representacion de \( m \) con cifras decimales es \( m = \bar c_k\barr c_{k=1}...\bar c_2\bar c_1\bar c_0 \), quiere decir que el numero tiene \( k+1 \) cifras decimales, cada una satisfaciendo \( c_j\in\{0,1,2,3,4,5,6,7,8,9\} \), y que su valor es igual a:

\( m=c_0 +c_1 10 +c_2 10^2+...+c_k 10^k. \)

Ahora bien, dado que \( d \) es divisor de \( m \) si y solo si \( m\equiv_d{0} \), y dado que las operaciones aritmeticas se conservan modulo \( d \), tenemos que para todo numero entero \( r \) tal que \( 10\equiv_d{r} \), podemos escribir la congruencia modulo \( d \) siguiente:

\( m \equiv_d c_0 10^0+c_1 10^1 +c_2 10^2+...+c_k 10^k \equiv_d c_0 r^0+c_1 r^1 +c_2 r^2+...+c_k r^k  \)

Digamos algo mas, y es que las potencias \( r^0,r^1,r^2,... \) no pueden tener resto siempre distinto modulo \( d \), porque los restos posibles son, a lo sumo, \( d \). Así que en algún momento alguno de ellos tendrá que ser repetición de alguno de los anteriores. Más aún, debido a la conservación del producto por congruencias, las sucesivas potencias tendrán que repetirse con el mismo patrón, y de esa manera los restos modulo \( d \) de las potencias de 10 que siguen se repetirán cíclicamente.

Para saber en con qué exponente se inicia el ciclo de repeticiones de restos, en principio tendremos que buscar a mano las sucesivas potencias hasta detectar que un par se han repetido.
No voy a entrar en mayores detalles por ahora. Quizá más adelante, si surge la inquietud en el público, se pueda ser más exacto.

Llamemos sistema de restos modulo \( d \) a la lista ordenada de restos \( r_0,r_2,r_3,..,r_{\ell-1} \) tales que \( 10^{\alpha-1+\beta \ell+j}\equiv_d{r_j} \), donde \( \alpha \) es el exponente donde comienza el ciclo de repeticiones, \( \beta \) es cualquier entero no negativo, y \( 0\leq j\leq \ell-1 \).

Esto permite dar un criterio de divisibilidad por \( d \).

Tenemos ahora, para el número \( m \) de arriba, lo siguiente:

\( m \equiv_d c_0 1+c_1 10^1 +c_2 10^2+...+c_{\alpha-1} 10^{\alpha-1}+c_{\alpha}r_0 +c_{\alpha+1}r_1 +...+c_{k}r_{s_k}.  \)

donde \( s_k \) indica el índice \( j \) tal que \( j\equiv_\ell{k} \).
Hemos tenido que usar una congruencia modulo \( \ell \) en el subíndice.

Interpretemos un poco la fórmula de arriba. Tiene dos partes.
La primer parte corresponde a las potencias de 10 que no han entrado aún al ciclo de potencias cuyo resto se repite módulo \( d \).
La segunda parte corresponde a las potencias de 10 que ya han entrado al ciclo.
Podemos, pues, escribir las cosas con un formato más acorde a estas observaciones:

\( (*)\qquad\qquad\qquad\qquad\displaystyle  m \equiv_d \sum_{j=0}^{\alpha-1}c_j 10^j\quad  + \sum_{\beta=0}^\infty\sum _{j=0}^{\ell-1}c_{\alpha+\beta\ell+j} \; r_j.  \)

Observemos que hemos escrito una suma infinita.
En realidad esta suma es finita, porque a partir del índice \( k+1 \) en adelante, todos los dígitos de \( m \) son iguales a 0.
Luego, la escritura anterior es más compacta, y evita que tengamos que pensar cuántas cifras tiene \( m \).



Ejemplos de Aplicación a criterios conocidos de divisibilidad, y un par de casitos más

En todo lo que sigue, supondremos que \( m=\displaystyle\sum_{n=0}^\infty c_n10^n \), donde sólo una cantidad finita de las cifras \( c_n \) es distinta de 0.

Divisibilidad por 2

Aquí tenemos \( \alpha=1 \) para la fórmula (*), y que \( 10\equiv_2 0 \), y en general \( 10^j\equiv_2{0} \), para \( j\geq1 \). Se sigue que:

\( m\equiv_2 c_0+\sum_{\beta=0}^\infty c_{1+\beta}\cdot 0\equiv_2{c_0} \)

Esto demuestra que  \( m \) es divisible por 2 si y sólo si la última cifra de \( m \) es divisible por 2.

Divisibilidad por 3

Aquí tenemos \( \alpha=1 \) para la fórmula (*), y que \( 10\equiv_3 1 \), y en general \( 10^j\equiv_3{1^j}=1 \), para \( j\geq1 \). Se sigue que:

\( m\equiv_3 c_0+\sum_{\beta=0}^\infty c_{1+\beta}\cdot 1\equiv_3\sum_{n=0}^\infty c_n \)

Esto demuestra que  \( m \) es divisible por 3 si y sólo si la suma de las cifras de \( m \) es múltiplo de 3.
Si al sumar las cifras de \( m \) se obtiene un número grande, se le vuelven a sumar las cifras a este último número, y así sucesivamente hasta llegar a algo "pequeño" que ya nos permita decidir.

Divisibilidad por 4

Aquí tenemos \( \alpha=2 \) para la fórmula (*), y que \( 10\equiv_4 2 \), \( 100\equiv_4{0} \)y en general \( 10^j\equiv_4{0} \), para \( j\geq2 \). Se sigue que:

\( m\equiv_4 c_0+c_1 \cdot 2+\sum_{\beta=0}^\infty c_{2+\beta}\cdot 0\equiv_4 c_0+2c_1. \)

Esto demuestra que  \( m \) es divisible por 4 si y sólo si la suma de su útlima cifra más el doble de su penúltima cifra es múltiplo de 4.

Divisibilidad por 5

Aquí tenemos \( \alpha=1 \) para la fórmula (*), y que \( 10\equiv_5 0 \), y en general \( 10^j\equiv_5{0} \), para \( j\geq1 \). Se sigue que:

\( m\equiv_5 c_0+ \sum_{\beta=0}^\infty c_{1+\beta}\cdot 0\equiv_5 c_0. \)

Esto demuestra que  \( m \) es divisible por 5 si y sólo si la última cifra de \( m \) es múltiplo de 5.

Divisibilidad por 6

Aquí tenemos \( \alpha=1 \) para la fórmula (*), y que \( 10\equiv_6 4 \), y en general \( 10^j\equiv_6 4 \), para \( j\geq1 \). Se sigue que:

\( m\equiv_6 c_0+ \sum_{\beta=0}^\infty c_{1+\beta}\cdot 4\equiv_6 c_0+4\sum_{\beta=0}^\infty c_{1+\beta}. \)

Esto demuestra que  \( m \) es divisible por 6 si y sólo si la suma de última cifra más 4 veces la suma de las restantes cifras de \( m \) es múltiplo de 6.

Este criterio es algo complicado. Se puede simplificar observando que 6 es el producto de 2 y 3.
Así que si la última cifra de \( m \) es par, y la suma de las cifras de \( m \) es múltiplo de 3, entonces \( m \) es múltiplo de 6.

Divisibilidad por 7

Aquí tenemos \( \alpha=0 \) para la fórmula (*), y que \( 10^0\equiv_7 1 \), \( 10\equiv_7 3 \), \( 10^2\equiv_7 2 \), \( 10^3\equiv_7 6 \), \( 10^4 \equiv_7 4 \), \( 10^5\equiv_7 5 \), \( 10^6\equiv_7 1 \), y en general \( 10^{6n+j}\equiv_7 r_j \), para \( 0\leq j<6 \), siendo \( (r_0,r_1,...,r_5)=(1,3,2,6,4,5) \) el sistema de restos de las potencias de 10 módulo 7. Se sigue que:

\( m\equiv_7 \sum_{\beta=0}^\infty\sum_{j=0}^5 c_{\beta 6+ j} r_j. \)

Esto da un criterio complicado de divisibilidad por 7, pero ciertamente funciona.

Divisibilidad por 8

Aquí tenemos \( \alpha=3 \) para la fórmula (*), y que \( 10\equiv_8 2 \), \( 100\equiv_8{4} \),  \( 1000\equiv_8{0} \), y en general \( 10^j\equiv_8{0} \), para \( j\geq3 \). Se sigue que:

\( m\equiv_8 c_0+c_1 \cdot 2+c_2\cdot 4+\sum_{\beta=0}^\infty c_{3+\beta}\cdot 0\equiv_8 c_0+2c_1+4c_2. \)

Esto demuestra que  \( m \) es divisible por 8 si y sólo si la suma de su útlima cifra más el doble de su penúltima cifra más el cuádruple de su antepenúltima cifra es múltiplo de 8.

Divisibilidad por 9

Aquí tenemos \( \alpha=1 \) para la fórmula (*), y que \( 10\equiv_9 1 \), y en general \( 10^j\equiv_9{1^j}=1 \), para \( j\geq1 \). Se sigue que:

\( m\equiv_9 c_0+\sum_{\beta=0}^\infty c_{1+\beta}\cdot 1\equiv_9\sum_{n=0}^\infty c_n \)

Esto demuestra que  \( m \) es divisible por 9 si y sólo si la suma de las cifras de \( m \) es múltiplo de 9.

Divisibilidad por 10

Aquí tenemos \( \alpha=1 \) para la fórmula (*), y que \( 10^j\equiv_{10} 0 \) para \( j\geq1 \). Se sigue que:

\( m\equiv_{10} c_0+\sum_{\beta=0}^\infty c_{1+\beta}\cdot 0\equiv_{10} c_0 \)

Esto demuestra que  \( m \) es divisible por 10 si y sólo si la última cifra de \( m \) es múltiplo de 10.
Pero esto sólo ocurre si la última cifra de \( m \) es 0.

Divisibilidad por 11

Aquí tenemos \( \alpha=0 \) para la fórmula (*), y que \( 10\equiv_{11} 10 \), \( 100\equiv_{11} 1 \), y luego estos restos se repiten cíclicamente.

\( m\equiv_{11} \sum_{\beta=0}^\infty \sum_{j=0}^1 c_{2\beta+j}r_j, \)

donde \( r_0=1, r_1=10 \).

Esto demuestra que  \( m \) es divisible por 11 si y sólo si la suma de sus cifras pares más 10 veces la suma de sus cifras impares \( m \) es múltiplo de 11.
Este criterio puede simplificarse un poco usando números negativos.
En efecto, observemos que \( 10\equiv_{11}{-1} \). En ese caso, podemos tomar \( r_1=-1 \) en la fórmula anterior, y obtenemos el conocido criterio que dice que \( m \) es múltiplo de 11 si y sólo si lo es la suma de sus cifras pares menos la suma de sus cifras impares.

Divisibilidad por otros números

No lo voy a hacer, pero es de esperar que en la mayoría de los casos se obtengan criterios de divisibilidad complicados, similares al obtenido para la división por 7.







Base b.

Sea \( b \) un entero positivo mayor que 1.
Dado un número entero positivo \( m \) podemos representarlo en base \( b \), con los dígitos \( 0, 1, 2, ..., b-1 \), de forma única, tal que la siguietne identidad se satisface:

\( m=\displaystyle\sum_{n=0}^\infty{c_n b^n} \)

Aquí, sólo una cantidad finta de cifras \( c_n \) es distinta de 0.

Lo único que hay que cambiar en todo esto es la base 10 por la base \( b \), y el desarrollo matemática será el mismo.
Así, tendremos una fórmula como esta:

(*)                       \( \displaystyle  m \equiv_d \sum_{j=0}^{\alpha-1}c_j b^j\quad  + \sum_{\beta=0}^\infty\sum _{j=0}^{\ell-1}c_{\alpha+\beta\ell+j} \; r_j.  \)

Aquí \( \alpha \) es el primer exponente tal que las potencias \( b^j \) comienzan a repetir sus restos módulo \( d \).
Asimismo, \( r_0, r_1,...,r_{\ell-1} \) es el sistema de restos de las potencias \( b^{\alpha+j} \) módulo \( d \).

Veamos un par de ejemplos.

Criterio de divisibilidad en base 2 de divisibilidad por 15.

Tenemos:

\( 2^0\equiv_{15} {1} \)
\( 2^1\equiv_{15} {2} \)
\( 2^2\equiv_{15} {4} \)
\( 2^3\equiv_{15} {8} \)
\( 2^4\equiv_{15} {1} \)

y a partir de aquí se repiten los restos módulo 15.
Así que tenemos \( \alpha=0 \) y \( \ell=4 \). También el sistema de restos es en este caso \( (r_0,r_1,r_2,r_3)=(1,2,4,8) \).
Aplicando la fórmula:

\( (*)\qquad\qquad\qquad\displaystyle  m \equiv_d  \sum_{\beta=0}^\infty\sum _{j=0}^{3}c_{4\betal+j} \; r_j \equiv_d \sum _{j=0}^{3} 2^j \sum_{\beta=0}^\infty c_{4\betal+j}.  \)

El criterio de divisibilidad no es muy simple de expresar verbalmente, pero parece fácil de aplicar en un cálculo.
Se debe separar las cifras binarias del número en 4 grupos, sumar los dígitos de cada grupo y multiplicar por la potencia adecuada de 2.
Si el resultado es múltiplo de 15, ya estamos...


Criterio de divisibilidad en base 27 de divisibilidad por 54.

Tenemos:

\( 27^0\equiv_{54} {1} \)
\( 27^1\equiv_{54} {27} \)
\( 27^2\equiv_{54} {27} \)

y a partir de aquí se repite lo mismo para las siguientes potencias.
El criterio de divisibilidad es muy simple. Se suma la primer cifra a 27 veces la suma de las restantes, y se verifica si el resultado es múltiplo de 54.



Que se diviertan dividiendo...

 :D

05 Junio, 2010, 11:16 pm
Respuesta #4

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

06 Junio, 2010, 12:29 am
Respuesta #5

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

06 Junio, 2010, 12:35 am
Respuesta #6

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Primero, una tontería nada más: en el teorema 3, me parece que sería mejor directamente enunciarlo para divisores enteros no nulos (no necesariamente positivos), porque si lo enunciás sólo para positivos y después extendés la definición de \( m/d \) para divisores negativos, no te queda demostrado que se puede conseguir un cociente y un resto para todo par dividendo-divisor.

Después, una propiedad importante que yo agregaría es que \( \forall n\in\mathbb{N}-(\mathbb{P}\cup\{1\}),\;\;\exists p\in\mathbb{P}/\;\;1<p\leq\sqrt a\;\;\wedge\;\; p\mid a \).
"...parecido pero nada que ver"

06 Junio, 2010, 12:44 am
Respuesta #7

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Primero, una tontería nada más: en el teorema 3, me parece que sería mejor directamente enunciarlo para divisores enteros no nulos (no necesariamente positivos), porque si lo enunciás sólo para positivos y después extendés la definición de \( m/d \) para divisores negativos, no te queda demostrado que se puede conseguir un cociente y un resto para todo par dividendo-divisor.


Bien, mientras escribía, algunas cosas me parecieron mejor si me restringía a divisores positivos.
Creo que porque cuando d es negativo el resto... es no negativo, y queda menor que el valor absoluto de d.
Y después las congruencias se pueden poner algo confusas si d es negativo.

De todos modos es muy posible que cambie el enunciado según tu sugerencia.


06 Junio, 2010, 12:50 am
Respuesta #8

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Digamos algo mas, y es que las potencias \( r^0,r^1,r^2,... \) no pueden tener resto siempre distinto modulo \( d \), porque los restos posibles son, a lo sumo, \( d \). Así que en algún momento alguno de ellos tendrá que ser repetición de alguno de los anteriores. Más aún, debido a la conservación del producto por congruencias, las sucesivas potencias tendrán que repetirse con el mismo patrón, y de esa manera los restos modulo \( d \) de las potencias de 10 que siguen se repetirán cíclicamente.

Para saber en con qué exponente se inicia el ciclo de repeticiones de restos, basta hallar el primer exponente entero positivo \( j \) tal que \( 10^{j+1}> d \).

Esto es falso por ejemplo d=7. Si d es primo con 10 se van a repetir cuando \( 10^k \equiv 1\mod(d) \).


Es cierto, no lo demostré con cuidado, y me confié con lo que pasaba en algunos ejemplos.
Voy a tener que poner eso como una condición suficiente, pero no necesaria.

Saludos

06 Junio, 2010, 12:58 am
Respuesta #9

pepito

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,625
  • Karma: +0/-0
  • Sexo: Masculino
Bien, mientras escribía, algunas cosas me parecieron mejor si me restringía a divisores positivos.
Creo que porque cuando d es negativo el resto... es no negativo, y queda menor que el valor absoluto de d.
Y después las congruencias se pueden poner algo confusas si d es negativo.

De todos modos es muy posible que cambie el enunciado según tu sugerencia.

Puede ser... la congruencia yo siempre la estudié con módulo positivo, pero el algoritmo de división, generalizado a todo \( \mathbb{Z}\times\mathbb{Z}_{\neq 0} \), y lo que se pedía era justamente eso, que el resto sea estríctamente menor que el módulo del divisor.

Después, una propiedad de congruencias (no estoy 100% seguro de que no esté incluida):

\( mcd (d_i:d_j)=1\quad\forall 1\leq i<j\leq k\quad\wedge\quad a\equiv_{d_i} b\quad\forall 1\leq i\leq k \Longleftrightarrow a\equiv_{d_1d_2...d_k} b \).

Y después, si definís el mcm, estaría bueno incluir que \( mcd (a:b)mcm (a:b)=ab \)
"...parecido pero nada que ver"