Diremos que un número entero positivo es bueno si sus tres dígitos finales son [math]133. Demostrar que todo número bueno tiene un divisor primo mayor que [math]7.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Mientras que las únicas posibilidades de [math]7^{k} en el módulo [math]100 son: [math]1,\: 7,\: 49,\: 43
Vamos a suponer que existe un número bueno [math]N cuyos factores primos son todos menores o iguales que [math]7. Claramente [math]N no es par ni múltiplo de [math]5. Por lo tanto, existen enteros no negativos [math]a y [math]b tales que [math]N=3^{a}\cdot 7^{b}\equiv 133 \:(\text{mod}\: 1000).
Si [math]7^{b}\equiv 1 \:(\text{mod}\: 100), entonces [math]3^{a}\equiv 33 \:(\text{mod}\: 100), lo cual es falso.
Si [math]7^{b}\equiv 7 \:(\text{mod}\: 100), entonces [math]3^{a}\equiv 19 \:(\text{mod}\: 100), lo cual es falso.
Si [math]7^{a}\equiv 49 \:(\text{mod}\: 100), entonces [math]3^{a}\equiv 17 \:(\text{mod}\: 100), lo cual es falso.
Si [math]7^{b}\equiv 43 \:(\text{mod}\: 100), entonces [math]3^{a}\equiv 31 \:(\text{mod}\: 100), lo cual es falso.
Por lo tanto, cualquier número bueno posee algún divisor primo mayor que [math]7.
Para este problema voy a usar Congruencia de numeros. Para entenderla bien es necesario tener claro el concepto.
Un numero $bueno$ es un numero de la forma $1000K + 133$
Sabemos que para todo $n \geq 2$ , $n$ tiene al menos un factor primo.
Si demostramos que los primos $\{2, 3, 5, 7\}$ no son los unicos factores primos de $n$, es suficiente para saber que $n$ tiene un factor primo mayor a $7$
Tomemos $n = 1000K + 133$ e intentemos demostrarlo.
Supongamos que $\{2, 3, 5, 7\}$ son los unicos factores primos de $n$:
$1000K + 133 \equiv 0 + 1 \equiv 1 \neq 0(2)$
$1000K + 133 \equiv 0 + 3 \equiv 3 \neq 0(5)$
De aqui decimos que ni $2$ ni $5$ dividen a $n$
Luego, $3$ y $7$ son los unicos factores primos de $n$.
Tenemos:
$n = 3^a7^b \Rightarrow \left.\begin{matrix} n \equiv 3^a7^b \equiv 3^a3^b \equiv 3^{a+b}(4) \\ n \equiv 1000K + 133 \equiv 0 + 1 \equiv 1(4) \end{matrix}\right\} \Rightarrow 3^{a+b} \equiv 1(4)$
$\Rightarrow (a+b) \text{ es par}$
*Observese que si (a+b) fuera impar 3^{a+b} = 3(4). Absurdo.
Lo que haremos ahora es mirar la congruencia modulo 10 del numero.
Sabemos que $n = 1000K + 133 \equiv 0 + 3 \equiv 3(10)$
Tenemos 3 casos.
Caso 1: $(a = b) \Rightarrow n =3^a7^b = 3^a7^a = 21^a \equiv 1^a \equiv 1 (10)$. Absurdo.
Un número bueno, digamos $N$, tiene la forma $\overline{A133}$, donde $A$ es un entero no negativo. De este modo, a $N$ lo podemos escribir como $N=1000A+133$.
Supongamos que todos los divisores primos de $N$ son menores o iguales a $7$, lo que implica que a lo sumo tiene $4$ divisores primos: el $2, 3, 5$ y $7$. Notar que $N$ termina en $3$, con lo que no es par ni múltiplo de $5$,
O sea que su factorización en primos es $N=3^{a}\cdot7^{b}$, donde ambos exponentes son enteros no negativos.
Tenemos $1000A+133=N=3^a\cdot 7^b$, donde al tomar módulo $8$ se obtiene $5\equiv 3^a\cdot 7^b\pmod8$.
Hagamos una tabla de restos módulo $8$
O sea que $3^a$ y $7^b$ tienen un ciclo de longitud $2$ en módulo $8$, que depende de la paridad de su exponente.
Notemos que $5\not\equiv 1, 3, 7\pmod8$, pero $5\equiv 21\equiv 3\cdot 7\pmod8$, o sea que $a$ y $b$ son impares.
Y si tomamos $N$ en módulo $10$ se obtiene $3\equiv 3^a\cdot 7^b\pmod{10}$.
Hagamos una lista de restos módulo $10$
O sea que los restos $3^a$ y $7^b$ se repiten en un ciclo de longitud $4$, y en particular cuando su exponente es impar (que es la condición que encontramos para $a$ y $b$) dejan resto $3$ y $7$. Entonces $N$ solo puede ser congruente a $3\cdot3\equiv 9\pmod{10}$, $3\cdot7\equiv 21\equiv 1\pmod{10}$ o $7\cdot7\equiv 49\equiv 9\pmod{10}$, lo que es absurdo porque $3\equiv 3^a\cdot 7^b\pmod{10}$. Luego $N$ siempre tiene al menos un factor primo mayor a $7$.
Buscamos un numero de la forma $\overline{a}133$, donde $\overline{a}$ puede tomar cualquier entero positivo.
Los casos donde $\overline{a}133$ es múltiplo de 3 o 5 quedan inmediatamente descartados ya que el numero no termina en un numero par, ni tampoco en 5.
Nos quedaría analizar que pasa cuando $\overline{a}133 = 3^{k_1}.7^{k_2}, k \in \mathbb Z^+$. Primero veamos el caso $k = x$ en $\overline{a}133 = 3^{x}$
Notemos que $3^4 \equiv 1(mod 20) \Rightarrow 3^{4x} \equiv 1(mod 20)$. Luego sabemos que los restos de las potencias de $3(mod 20)$ van a ser cíclicas, precisamente: $3^x \equiv 1, 3, 9, 27 \equiv(mod 20)$. Como $\overline{a}133 \equiv 13(mod 20)$ entonces no hay solución para este caso.
De manera similar podemos analizar el caso $\overline{a}133 = 7^{x}$. Notemos que $7^4 \equiv 0 (mod 20) \Rightarrow 7^{4x} \equiv 0(mod 20)$. Como las potencias son cíclicas, entonces $7^x \equiv 1, 7, 9, 3 (mod 20)$. Como $\overline{a}133 \equiv 13(mod 20)$ entonces no hay solución para este caso.
Finalmente podemos combinar a mano ambos casos para ver los restos de $\overline{a}133 = 3^{k_1}.7^{k_2} mod 20$
$1.1 | 1.7 | 1.9 | 1.3$
$ - | 3.7 | 3.9 | 3.3$
$ - | 9.7 | 9.9 | -$
$27.1 |27.7 |27.9 |27.3$
Ninguno tiene resto $13 mod 20$ por lo que no hay solución. Entonces, concluimos que todo numero de la forma $\overline{a}133$ tiene sus factores primos mayores que $7$
oráculo y magia negra
