Teoría de divisibilidad

Idea concreta

Si repartes $24$ caramelos entre $6$ niños y todos reciben lo mismo sin que sobre nada, dices que $24$ es divisible entre $6$, o que $24$ es múltiplo de $6$.

En general:

Un entero $A$ es múltiplo de un entero positivo $m$ si existe un entero $k$ tal que
$$> A=mk. >$$

Notación usual en los exámenes peruanos

$$A=\overset{\circ}{m}$$

se lee «$A$ es múltiplo de $m$» o «$A$ es $m$ múltiplo».

También se dice que $m$ es módulo.

Ejemplos

$$12=\overset{\circ}{3} \quad\text{porque}\quad 12=3\cdot 4.$$

$$-35=\overset{\circ}{7} \quad\text{porque}\quad -35=7\cdot(-5).$$

$$0=\overset{\circ}{m} \quad\text{para todo entero positivo }m.$$

El cero es múltiplo de todo número positivo.

No siempre una división es exacta. Por ejemplo, si divides $50$ entre $8$:

$$50=8\cdot 6+2.$$

Aquí sobran $2$. En notación modular:

$$50=\overset{\circ}{8}+2.$$

Pero también puedes verlo desde el múltiplo siguiente:

$$8\cdot 7=56.$$

Entonces,

$$50=56-6,$$

es decir,

$$50=\overset{\circ}{8}-6.$$

Ambas representaciones son equivalentes:

$$50=\overset{\circ}{8}+2=\overset{\circ}{8}-6.$$

Aquí $2$ es el residuo por defecto y $6$ es el residuo por exceso.

Regla general

Si al dividir un número $N$ entre $m$ el residuo por defecto es $r$, escribimos

$$N=\overset{\circ}{m}+r,$$

con $0\le r<m$.

Si lo que conocemos es cuánto falta para completar un grupo, digamos $f$, escribimos

$$N=\overset{\circ}{m}-f.$$

Además, si $r$ es el residuo por defecto y $f$ el residuo por exceso, entonces

$$r+f=m.$$

Traducción del lenguaje verbal al modular

Cuando varias expresiones tienen el mismo módulo, se pueden sumar, restar, multiplicar y elevar a potencias operando solo sus residuos.

Suma

Si

$$A=\overset{\circ}{m}+a,\qquad B=\overset{\circ}{m}+b,$$

entonces

$$A+B=\overset{\circ}{m}+(a+b).$$

Ejemplo

$$(\overset{\circ}{7}+4)+(\overset{\circ}{7}+5) = \overset{\circ}{7}+9 = \overset{\circ}{7}+2,$$

porque $9=7+2$.

Resta

$$A-B=\overset{\circ}{m}+(a-b).$$

Ejemplo

$$(\overset{\circ}{7}+4)-(\overset{\circ}{7}+5) = \overset{\circ}{7}-1 = \overset{\circ}{7}+6,$$

porque $-1+7=6$.

Multiplicación

$$A\cdot B=\overset{\circ}{m}+ab.$$

Ejemplo

$$(\overset{\circ}{7}+4)(\overset{\circ}{7}+5) = \overset{\circ}{7}+20 = \overset{\circ}{7}+6,$$

ya que $20=7\cdot 2+6$.

También se puede trabajar con residuos por exceso:

$$(\overset{\circ}{7}-3)(\overset{\circ}{7}+2) = \overset{\circ}{7}-6 = \overset{\circ}{7}+1.$$

Potencia

Si

$$A=\overset{\circ}{m}+r,$$

entonces

$$A^2=\overset{\circ}{m}+r^2,$$

$$A^3=\overset{\circ}{m}+r^3,$$

y en general,

$$A^n=\overset{\circ}{m}+r^n.$$

Ejemplo

$$(\overset{\circ}{5}+3)^2 = \overset{\circ}{5}+9 = \overset{\circ}{5}+4.$$

Regla de oro

Las partes que son múltiplos del módulo se combinan entre sí y siguen siendo múltiplos del módulo. Solo operamos los residuos.

⚠️ Cuidado: no se pueden sumar directamente expresiones con módulos distintos. Primero hay que reducirlas a un módulo común o trabajar separadamente.

La notación $\overset{\circ}{m}$ es muy conveniente para operar. El método formal equivalente es la congruencia.

Definición

Sean $a,b$ enteros y $m$ un entero positivo. Decimos que

$$a\equiv b \pmod m$$

si y solo si

$$a-b=\overset{\circ}{m}.$$

Es decir, $a\equiv b\pmod m$ significa que $a$ y $b$ dejan el mismo residuo al dividirse entre $m$.

Ejemplos

$$47\equiv 5\pmod 7$$

porque $47-5=42$, y $42$ es múltiplo de $7$.

También:

$$47\equiv -2\pmod 7$$

porque $47-(-2)=49$, que es múltiplo de $7$.

Observa que $5$ y $-2$ son equivalentes módulo 7, pues $5-(-2)=7$.

Propiedades básicas

Para un módulo fijo $m$:

1. $a\equiv a \pmod m$.
2. Si $a\equiv b \pmod m$, entonces $b\equiv a \pmod m$.
3. Si $a\equiv b \pmod m$ y $b\equiv c \pmod m$, entonces $a\equiv c \pmod m$.
4. Si $a\equiv b \pmod m$ y $c\equiv d \pmod m$, entonces
   $$a+c\equiv b+d \pmod m,$$ $$a-c\equiv b-d \pmod m,$$ $$ac\equiv bd \pmod m.$$
5. Si $a\equiv b \pmod m$, entonces
   $$a^n\equiv b^n \pmod m.$$

Como los numerales se escriben en base diez:

$$\overline{abc}=100a+10b+c.$$

Podemos analizar la congruencia tomando $10$ módulo un número.

Módulo 9 y módulo 3

Como

$$10\equiv 1\pmod 9,$$

también

$$100\equiv 1\pmod 9,\qquad 1000\equiv 1\pmod 9,$$

entonces

$$\overline{abc}=100a+10b+c \equiv a+b+c \pmod 9.$$

Por eso, un número es múltiplo de $9$ si y solo si la suma de sus cifras es múltiplo de $9$.

Análogamente, como $10\equiv 1\pmod 3$, el residuo módulo 3 también se obtiene sumando las cifras.

Módulo 11

Como

$$10\equiv -1\pmod{11},$$

se tiene

$$100\equiv 1\pmod{11},\qquad 1000\equiv -1\pmod{11},$$

y así alternadamente. Por ello, para el módulo 11 se usa la suma alternada de las cifras.

Una aplicación muy importante de las operaciones modulares es hallar el residuo de potencias grandes.

Si queremos el residuo de $a^n$ módulo $m$:

1. reducimos $a$ a su residuo $r$ módulo $m$;
2. calculamos los primeros residuos de $r^0,r^1,r^2,r^3,\ldots$;
3. cuando se repite un residuo, se forma un período.

Ejemplo

Calculemos los residuos de las potencias de $3$ módulo $7$:

$$3^0\equiv 1,\quad 3^1\equiv 3,\quad 3^2\equiv 2,\quad 3^3\equiv 6,\quad 3^4\equiv 4,\quad 3^5\equiv 5,\quad 3^6\equiv 1.$$

El período es $6$. Por lo tanto, para calcular $3^{20}\pmod 7$, como

$$20=6\cdot 3+2,$$

se tiene

$$3^{20}\equiv 3^2\equiv 2\pmod 7.$$

Una congruencia es lineal cuando tiene la forma

$$ax\equiv b \pmod m.$$

Método práctico

1. Reducir $a$ y $b$ módulo $m$ si es posible.
2. Si $d=\gcd(a,m)$, la congruencia tiene solución solo si $d\mid b$.
3. Si $d\mid b$, se divide toda la congruencia entre $d$:

$$\frac a d x\equiv \frac b d \pmod{\frac m d}.$$

4. Como ahora $\frac a d$ y $\frac m d$ son PESI, se puede hallar su inverso módulo $\frac m d$.

Ejemplo

Resolver

$$6x\equiv 4\pmod{10}.$$

Aquí $\gcd(6,10)=2$, y $2\mid 4$. Dividimos entre $2$:

$$3x\equiv 2\pmod 5.$$

El inverso de $3$ módulo $5$ es $2$, porque $3\cdot 2=6\equiv 1\pmod 5$.

Multiplicamos:

$$x\equiv 4\pmod 5.$$

Entonces,

$$x=5t+4,\qquad t\in\mathbb{Z}.$$

En módulo $10$, las soluciones son $x\equiv 4\pmod{10}$ y $x\equiv 9\pmod{10}$.

Muchos problemas de admisión piden contar cuántos números de un intervalo son múltiplos de cierto módulo.

Fórmula

La cantidad de múltiplos de $m$ entre $a$ y $b$, inclusive, es

$$\left\lfloor \frac{b}{m}\right\rfloor - \left\lfloor \frac{a-1}{m}\right\rfloor.$$

Aquí $\lfloor x\rfloor$ es la parte entera de $x$.

Ejemplo

¿Cuántos múltiplos de $7$ hay entre $100$ y $200$?

$$\left\lfloor\frac{200}{7}\right\rfloor - \left\lfloor\frac{99}{7}\right\rfloor = 28-14=14.$$

Unión de múltiplos: inclusión-exclusión

Si queremos contar cuántos números son múltiplos de $2$ o de $3$ o de $5$, no podemos sumar los conteos directamente, porque hay números que son múltiplos de más de uno.

Para dos conjuntos $A$ y $B$:

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

Para tres:

$$|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|.$$

En términos de múltiplos, la intersección de «múltiplos de $a$» y «múltiplos de $b$» son los múltiplos del $\mathrm{MCM}(a,b)$.

Ejemplo

En $\{1;2;\ldots;60\}$, los múltiplos de $2$, $3$ o $5$ son:

• múltiplos de $2$: $30$
• múltiplos de $3$: $20$
• múltiplos de $5$: $12$
• múltiplos de $6=\mathrm{MCM}(2,3)$: $10$
• múltiplos de $10=\mathrm{MCM}(2,5)$: $6$
• múltiplos de $15=\mathrm{MCM}(3,5)$: $4$
• múltiplos de $30=\mathrm{MCM}(2,3,5)$: $2$

Entonces,

$$30+20+12-10-6-4+2=44.$$

Hay $44$ números que son múltiplos de $2$, $3$ o $5$.

Muchos problemas de admisión dan condiciones simultáneas:

$$N\equiv r_1\pmod{m_1},$$ $$N\equiv r_2\pmod{m_2},$$ $$N\equiv r_3\pmod{m_3}.$$

El teorema chino del resto dice que, si los módulos son primos entre sí dos a dos, el sistema tiene solución única módulo el producto de ellos.

Pero en los exámenes no suele usarse la fórmula complicada; se usa un método paso a paso.

Caso particular: el mismo residuo

Si un número deja el mismo residuo $r$ al dividirse entre $m_1,m_2,\ldots,m_k$, entonces

$$N-r$$

es múltiplo de todos esos módulos. Por lo tanto, es múltiplo de su MCM.

Así,

$$N=\mathrm{MCM}(m_1,m_2,\ldots,m_k)\cdot t + r.$$

Ejemplo

Si $N$ al dividirse entre $6$, $8$ y $10$ siempre deja residuo $3$, entonces

$$N=\mathrm{MCM}(6,8,10)\cdot t+3 = 120t+3.$$

Caso general: método paso a paso

Ejemplo resuelto

Resolver

$$\begin{cases} N\equiv 2\pmod 5,\\ N\equiv 1\pmod 6,\\ N\equiv 2\pmod 7. \end{cases}$$

Paso 1. De la primera congruencia:

$$N=5k+2.$$

Paso 2. Sustituimos en la segunda:

$$5k+2\equiv 1\pmod 6.$$

Restamos $2$:

$$5k\equiv -1\equiv 5\pmod 6.$$

Como $5$ es inverso de sí mismo módulo $6$,

$$k\equiv 1\pmod 6.$$

Entonces,

$$k=6t+1.$$

Reemplazamos en $N$:

$$N=5(6t+1)+2=30t+7.$$

Paso 3. Usamos la tercera congruencia:

$$30t+7\equiv 2\pmod 7.$$

Pero $30\equiv 2\pmod 7$ y $7\equiv 0\pmod 7$. Entonces,

$$2t\equiv 2\pmod 7.$$

Luego,

$$t\equiv 1\pmod 7.$$

Por lo tanto,

$$t=7s+1.$$

Reemplazamos:

$$N=30(7s+1)+7=210s+37.$$

Entonces,

$$N\equiv 37\pmod{210}.$$

Esta es la solución única módulo $210$.

Cuando los módulos no son PESI

A veces los módulos no son primos entre sí. En ese caso no se usa el producto directamente; se usa el MCM y se verifica la compatibilidad.

Ejemplo

Resolver

$$\begin{cases} N\equiv 3\pmod 8,\\ N\equiv 7\pmod{12}. \end{cases}$$

De la primera:

$$N=8k+3.$$

En la segunda:

$$8k+3\equiv 7\pmod{12}.$$

Entonces,

$$8k\equiv 4\pmod{12}.$$

Como $\gcd(8,12)=4$, dividimos todo entre $4$:

$$2k\equiv 1\pmod 3.$$

El inverso de $2$ módulo $3$ es $2$:

$$k\equiv 2\pmod 3.$$

Así,

$$k=3t+2.$$

Luego,

$$N=8(3t+2)+3=24t+19.$$

Por lo tanto,

$$N\equiv 19\pmod{24}.$$

Observa que $24=\mathrm{MCM}(8,12)$, no $8\cdot 12=96$.

Una ecuación diofántica es una ecuación con coeficientes enteros y soluciones enteras.

La más importante es la lineal de dos variables:

$$ax+by=c.$$

Condición de existencia

Si $d=\gcd(a,b)$, la ecuación tiene soluciones enteras si y solo si

$$d\mid c.$$

Método de resolución

1. Si $d=\gcd(a,b)$, dividir toda la ecuación entre $d$.
2. Convertir la ecuación en una congruencia: $$ax+by=c \quad\Longleftrightarrow\quad ax\equiv c\pmod b.$$
3. Resolver la congruencia para $x$.
4. Reemplazar en la ecuación original para hallar $y$.
5. Escribir la solución general.

Ejemplo

Resolver

$$7x-5y=4.$$

Aplicamos congruencia módulo $5$:

$$7x\equiv 4\pmod 5.$$

Pero $7\equiv 2\pmod 5$, por lo que

$$2x\equiv 4\pmod 5.$$

Multiplicamos por el inverso de $2$ módulo $5$, que es $3$:

$$x\equiv 12\equiv 2\pmod 5.$$

Entonces,

$$x=5t+2.$$

Reemplazamos:

$$7(5t+2)-5y=4.$$

$$35t+14-5y=4.$$

$$5y=35t+10.$$

$$y=7t+2.$$

Por lo tanto, las soluciones son

$$x=5t+2,\qquad y=7t+2,\qquad t\in\mathbb{Z}.$$

Uso de desigualdades

En muchos problemas, las variables representan cantidades positivas o limitadas. Entonces, después de hallar la solución general, se aplican las condiciones del problema para elegir una o varias soluciones.