OMA Foros

por **Nacho** » Jue 26 Abr, 2012 8:25 pm

La idea de este apunte es poder familiarizarse con una notación que introduce mucha técnica y facilita muchisimos problemas de la Teoría de Números: las congruencias.

¿Qué quiere decir que dos números sean "congruentes"? Decimos que dos números $a$ y $b$ son congruentes módulo $m$ si el resto de $a$ en la división por $m$ es igual al resto de $b$ en la división por $m$ . Esto se escribe $a \equiv b \pmod{m}$ .

Por ahora no parece nada muy interesante. Exploremos un poco más. Supongamos que el cociente de $a$ en la división por $m$ es $q_1$ y tiene un resto $r$ . De la misma manera, $q_2$ el cociente de $a$ en la división por $m$ y $r$ el resto (ya que $a\equiv b\pmod{m}$ ).

Recordemos que "El dividendo es igual al cociente por el divisor más el resto". Se sigue que $a=mq_1 + r$ y $b=mq_2 + r$ . Notemos que $a-b = m(q_1-q_2)$ , por lo que
$\dfrac{a-b}{m} = q_1-q_2$ . Es decir, que $m$ divide a $a-b$ (ya que el resultado de la división es entero).

Entonces $a\equiv b\pmod{m} \Leftrightarrow m \mid a-b$ .

Por ejemplo, $15 \equiv 5 \pmod{10}$ , $75\equiv 3 \pmod{4}$ , $753 \equiv 261 \pmod{123}$ .

¡Los números de las congruencias también pueden ser negativos! Por ejemplo, $15 \equiv -1 \pmod{16}$ pues $16 \mid 15 - (-1)$ .

La congruencia conserva varias propiedades de la igualdad:

(Transitividad) Si $a\equiv b\pmod{m}$ y $b\equiv c\pmod{m}$ , entonces $a\equiv c \pmod{m}$ .

(Suma, resta, producto y potenciación) Si $a\equiv b \pmod{m}$ y $c\equiv d \pmod{m}$ entonces:

$a+c \equiv b+d\pmod{m}$
$a\cdot c &\equiv b\cdot d \pmod{m}$
$a^n &\equiv b^n \pmod{m}$ si $n$ es natural

Notemos que no siempre se puede dividir: por ejemplo $2\equiv 14 \pmod{4}$ : si dividimos por $2$ a ambos lados, obtenemos $1 \equiv 7 \pmod{4}$ , que es mentira ya que $4$ no divide a $7-1=6$ .
Otra aclaración importante es que $x\equiv y \pmod{m}$ no implica $a^x \equiv a^y \pmod{m}$ . Un ejemplo de que eso es mentira es $2^{6} \not\equiv 2^{11} \pmod{5}$ ya que $5$ no divide a $2^{11} - 2^6 = 1984$ .

Después vamos a ampliar estas cuestiones en una próxima entrega.

Por ahora no parece muy importante, ¿no?. Ilustremos la magia de las congruencias con un par de ejemplos:

Ejemplo 1: Demostrar que la ecuación $3x^2 +2 = y^2$ no tiene soluciones enteras.

Solución:

Notemos que $3$ divide a $3x^2$ , y $2$ tiene resto $2$ en la división por $3$ . Entonces, tenemos que $3x^2 + 2 \equiv 2 \pmod{3}$ .

Por otro lado, si $y$ es un número entero, sus posibles restos en la división por $3$ son $0$ , $1$ ó $2$ .

$y\equiv 0\pmod{3} \qquad y \equiv 1 \pmod{3} \qquad y \equiv 2 \pmod{3}$
$y^2 \equiv 0^2 \pmod{3} \qquad y^2 \equiv 1^2 \pmod{3} \qquad y^2 \equiv 2^2 \pmod{3}$
$y^2 \equiv 0 \pmod{3} \qquad y^2 \equiv 1 \pmod{3} \qquad y^2 \equiv 4\equiv 1 \pmod{3}$

En ningún caso pasa que $y^2 \equiv 2 \pmod{3}$ , y por lo tanto es imposible que $3x^2 + 2 = y^2$ .

Ejemplo 2: (Criterio de divisibilidad por $9$ ) El resto de un número en la división por $9$ es igual a la suma de las cifras del número.

Solución:

Vamos a escribir el número en notación decimal. Por ejemplo $1326$ es igual a $1000 + 3\times 100 + 2\times 10 + 6$ . En general, se puede decir $N= a_n\times 10^n + a_{n-1}\times 10^{n-1} + \ldots + a_{1}\times 10 + a_0$ . Pero veamos que $10 \equiv 1 \pmod{9}$ . Por las propiedades de las congruencias, tenemos que $10^k \equiv 1\pmod{9}$ .

Entonces, tenemos que ${N= a_n\times 10^n + a_{n-1}\times 10^{n-1} + \ldots + a_{1}\times 10 + a_0 \equiv a_n + a_{n-1} \ldots a_1 + a_0 \pmod{9}}$ , que es precisamente la suma de las cifras. Y estamos.

Ejercicio: Demostrar el criterio de divisibilidad por $11$ usando congruencias: El resto de dividir un número $N$ por $11$ es igual al resto de dividir la suma alternada de sus cifras por $11$ .

por **tuvie** » Dom 07 Oct, 2012 6:55 pm

Tenemos que un numero es multiplo $11$ si la resta alternada de sus cifras lo es. En otras palabras, tenemos el numero $\underset{n}{\underbrace{{a_n}{a_{n-1}}{a_{n-2}}\ldots{a_3}{a_2}{a_1}}}$ que en notacion decimal es $10^{n-1}\times{a_n}+10^{n-2}\times{a_{n-3}}+10^{n-3}\times{a_{n-2}}+\ldots+10^2\times{a_3}+10^1\times{a_2}+10^0\times{a_1}$
Ahora miro los restos de las potencias de $10$ modulo $11$

$\begin{align*}{10^0\equiv1\pmod{11}}\\10^1\equiv-1\pmod{11}\\10^2\equiv1\pmod{11}\end{align*}$

De esto sigue lo siguiente:

$\begin{align*}10^k\equiv1\pmod{11}\\10^{k+1}\equiv-1\pmod{11}\end{align*}$ con $k\in{\mathbb{Z}}$ y de la forma $k=2i$ .

Sea ${r}$ el resto en la division por $11$ de la suma de todas las cifras, por lo tanto:
$r\equiv1\times{$a_1+a_3+a_5+\ldots+{a_{n-3}+a_{n-1}+a_{n+1}}$-1\times$a_2+a_4+a_6+\ldots+a_{n-4}+a_{n-2}+a_{n}$\pmod{11}$
$r\equiv{a_1-a_2+a_3-a_4+\ldots+a_{n-1}-a_n+a_{n+1}\pmod{11}$ y estamos. $\blacksquare$
COMENTARIO:Al final de la solucion, $9\geq{a_{n+1}}\geq{0}$ y $n=2j$

por **turko.cnlp** » Dom 07 Oct, 2012 9:28 pm

Me parece que sale asi masomenos: la gracia está en ver que $\forall$ $n=2k$ se cumple que $10^n\equiv 1\pmod{11}$ , con $k$ entero positivo, y que $\forall$ $m=2q+1$ se cumple que $10^m\equiv -1\pmod{11}$ , con $q$ entero positivo. Por lo tanto al sumar todos los términos del desarrollo en base $10$ y ver su resto módulo $11$ podemos reescribir a nuestro número $q$ de la siguiente manera:
$q\equiv -1(a_1+a_3+a_5+...+a_{2k+1})+1(a_2+a_4+a_6+...+a_{2n}) \pmod{11}$
$q\equiv -a_1+a_2-a_3+a_4-...-a_{2k+1}+a_{2k+2}\pmod{11}$ (en caso de tener cantidad impar de cifras el último término sería $a_{2k+1}$ ).
Y bueno, con eso queda demostrado que el resto en la división por $11$ de un número es la diferencia entre la suma de sus cifras de posición impar y la suma de sus cifras de posición par.

por **turko.cnlp** » Lun 08 Oct, 2012 12:24 am

Bueno, se ve que ya editó el comentario jaja cuando lo puse no habia puesto la solución.

por **tuvie** » Lun 08 Oct, 2012 9:59 am

Jajaja si es que no habia tenido tiempo de terminarlo pero habia pensado lo mismo que vos turko

por **Ivan** » Lun 08 Oct, 2012 5:34 pm

tuvie escribió:Tenemos que un numero es multiplo 11 si la resta alternada de sus cifras lo es.

Fijate que esto no lo usás en la demostración. Justamente el argumento que hiciste demuestra que el criterio de divisibilidad por $11$ es cierto

OMA Foros

Congruencias

Congruencias

Re: Congruencias

Re: Congruencias

Re: Congruencias

Re: Congruencias

Re: Congruencias

¿Quién está conectado?