Informática

Question

Calcular $$(3^{999^{100}} + 7^{960^{961}}) \bmod 225. $$

Yo primero calcula la izquierda de la expresión, y finalmente encontrado, pero me tomó como una hora, así que me preguntaba si no hay manera más rápida. Primero escribí $$3^{999^{100}} \bmod 225 = (3^{999} \bmod 225)^{100} \bmod 225. $$ I noticed that $225 = 3 \cdot 75 = 3 \cdot (3 \cdot 25)$. So I tried working on the system $$ \begin{cases} 3^{999^{100}} \bmod 25 = 0 \\ (27^{333} \bmod 25)^{100} \bmod 25 \end{cases}$$ and then using Chinese Remainder theorem. For the last equation, We have $27^{333} \equiv 2^{333} \equiv (8^{111} \bmod 25)^{100} \bmod 25. $ To compute $(8^{111} \bmod 25)$, I just kept squaring, computing $8^2, 8^4, 8^8$ etc, and taking the modulo each time. Eventually I found $8^{111} \equiv 17 \bmod 25$. Then I needed to find $$17^{100} \bmod 25 \equiv (17^4 \cdot 17^{25} ) \bmod 25. $$ By squaring again I found the answer as $22 \bmod 25$. So I used the Chinese Remainder theorem to find the solution of $$ \begin{cases} x \bmod 25 = 22 \\ x \bmod 3 = 0 \end{cases}$$ which gave me $x = 72$. So I managed to find $$3^{999^{100}} \bmod 225 = 72 \bmod 225. $$ Ahora, Me preguntaba si no hay mejor truco/manera más rápida de encontrar la respuesta correcta a mano (sin calculadora), ya que no estoy mirando adelante a hacer una hora de cálculo para encontrar la segunda expresión. Gracias de antemano.

Adición posterior: Con la ayuda de Arturo sugerencias: Tenemos $225 = 9 \cdot 25$. Por lo tanto para la primera expresión que tiene el sistema de $$ \begin{cases} 3^{999^{100}} \bmod 9 = 0 \\ 3^{999^{100}} \bmod 25 = a. \end{cases}. $$ I want to find $un$ now. I have $\phi(25) = 20$, so $3^{20} \bmod 25 = 1 \bmod 25$ by Euler. Now I wanted to write the exponent $999^{100}$ as a multiple of $20$. I have $3^{(20 \cdot (50-1))^{100}} = 3^{20^{100} \cdot (50-1)^{100}} = (3^{20})^{(20^{99} \cdot (50-1)^{100})}$. So taking the modulo would give me $1$?

Answer 1

Para encontrar un número $a$ que satisfacer $$3^{999^{100}}+7^{960^{961}}\equiv a\pmod {225}$$ is equivalent to solving the system $$\begin{cases}3^{999^{100}}+7^{960^{961}}\equiv a\pmod {9}\\\\3^{999^{100}}+7^{960^{961}}\equiv a\pmod {25}\end{cases}.$$ Edit: añado una prueba de la anterior afirmación aquí. Puede omitir este si sabe de la prueba.

Para demostrar la equivalencia, podemos considerar el caso general $$a\equiv b\pmod n$$ and let $$n=\prod_{i=1}^{m}{p_i}^{k_i}$$ be the prime decomposition of $n$. Since $n\mediados de los a-b$ and ${p_i}^{k_i}\mediados de n$ for each of $i=1,2,...,m$, we immediately have ${p_i}^{k_i}\mediados de los a-b$. Esto demuestra que el original de la congruencia implica que el sistema de congruencias.

Por el contrario, supongamos ${p_i}^{k_i}\mid a-b$ para cada uno de $i=1,2,...,m$. Es decir, asumimos que el sistema de congruencias sostiene. El uso de este teorema, ya que el primer poderes son coprime, usted puede mostrar de forma inductiva que la totalidad del producto se divide $a-b$. Que es, $$\prod_{i=1}^{m}{p_i}^{k_i}\mid a-b.$$ But the product is just equal to $n$. So $n\mediados de los a-b$. Esto demuestra que el sistema de congruencias implica el original de la congruencia.

Ahora podemos simplificar cada una de las congruencias. Es fácil ver que $3^{999^{100}}$ es un múltiplo de a $9$. Desde $\phi(9)=6$, $960$ es un múltiplo de a$6$, $7^{960^{961}}\equiv 7^{6n}\equiv 1\pmod {9}$ donde $n=\frac{960^{961}}{6}$ es un entero positivo.

Para la segunda congruencia, se observa que la $\phi(25)=20$, e $999^{100}\equiv (-1)^{100}\equiv 1\pmod{20}$, lo $999^{100}-1=20m$ donde $m=\frac{999^{100}-1}{20}$ es un entero positivo. Entonces $3^{999^{100}}\equiv 3^{20m+1}\equiv 3\pmod{25}$. $960$ es un múltiplo de a $20$. Por lo $7^{960^{961}}\equiv 7^{20k}\equiv 1 \pmod{25}$ donde $k=\frac{960^{961}}{20}$. Hemos llegado al sistema de $$\begin{cases}a\equiv 1\pmod {9}\\\\a\equiv 4\pmod {25}\end{cases}.$$ Se pueden resolver por el Teorema del Resto Chino.

Answer 2

Si no sabes Teorema de Euler o de la CRT todavía podemos computarlo muy simplemente. Aviso

${\rm mod}\ 25\!:\,\ 3^{\large 3}\equiv 2\,\Rightarrow\, 3^{\large 9}\equiv 8\,\Rightarrow\, 3^{\large 10}\equiv -1\,\Rightarrow\,\color{#0a0}{3^{\large 20}\equiv 1},\ $ por lo tanto

$$ \color{#90f}{3^{\large 20J-1}}\equiv \dfrac{(\color{#0a0}{3^{\large 20}})^{\large J}}{3}\equiv \dfrac{\color{#0a0}1^{\large J}}3\equiv \dfrac{-24}3\equiv\,\color{#90f}{ -8\!\pmod{25}}\quad\ $$

Por lo tanto $\ 3^{\large 20J+1}\! = 3^{\large 2}(\color{#90f}{3^{\large 20J-1}}) = 9(\color{#90f}{-8+25n}) \equiv -72\pmod{9\cdot 25},\ $ y

$\qquad\quad\ \ \begin{align} {\rm mod}\ 9\!:\,\ 7^{\large 3}\equiv (-2)^{\large 3}\equiv1\\ {\rm mod}\ 25\!:\ 7^{\large 4}\equiv (-1)^{\large 2}\equiv 1\end{align}\,\ $ % por lo tanto $\,\ \color{#c00}{7^{\large 12}\equiv 1}\pmod{9\cdot 25}$

Combinar rendimiento $\ \ \bbox[10px,border:1px solid black]{3^{\large 20J+1}\! + \color{#c00}7^{\large \color{#c00}{12}K}\!\equiv -72+ \color{#c00}1^{\large K}\equiv -71 \pmod{9\cdot 25}}$

Nota $\ $ OP es un caso especial ya que sus exponentes tienen sobre la forma. De hecho

Nota $\,\ {\rm mod}\ 20\!:\ 999^{\large 100}\equiv (-1)^{\large 100}\equiv 1\ $ % que $\,\ 999^{\large 100}\! = 20J+1,\ $

y $\,\ 12\mid 96\,\Rightarrow\,12\mid 960\,\Rightarrow\,12\mid 960^{\large 961}\ $ % que $\,\ 960^{\large 961} = 12K$

Answer 3

Por suerte, desde $7$ y $225$ son coprimos, usted puede utilizar Teorema de Euler.

Podemos calcultate que $\phi(225) = 120$.

Así, $$7^{960^{961}} = 7^{(8\cdot 120)^{961}} = 7^{120\cdot (8^{961}120^{960})}$$$$ = (7 ^ {120}) ^ {8 ^ {961} 120 ^ {960}} = (7^{\phi(225)}) ^ {8 ^ {961} 120 ^ {960}} \equiv 1 ^ {8 ^ {961} 120 ^ {960}} = 1 \mod 225$ $

Answer 4

Para calcular el $\;3^{999^{100}}$ más rápido, use el Teorema de Euler: $\;\varphi(25)=20$, que $$3^{999^{100}}\equiv3^{999^{100}\bmod20}\equiv3^{(999\bmod20)^{100}}\equiv3^{(-1)^{100}}=3\mod25.$ $

Como una relación de Bézout entre $9$y $25$ es $\;-11\cdot 9+4\cdot 25=1$, las soluciones del sistema de congruencias $\;\begin{cases} x\equiv 0\mod 9,\\x\equiv 3\mod 25, \end{cases}\;$: $$x\equiv-3\cdot11\cdot 9+0\cdot4\cdot 25=-297\equiv-72\mod 225.$ $

Answer 5

Escribí una pequeña biblioteca de python para sus cálculos como este hace algunos días. Se basa en el pensamiento acerca de los autómatas finitos. No necesito el módulo de tener ningún tipo especial de divisibilidad propiedades; el método sólo exige que sea lo suficientemente pequeño.

>>> import roll
>>> (roll.mod([3, 999, 100], 225) + roll.mod([7, 960, 961], 225)) % 225
154

Mi respuesta está de acuerdo con edm.

La parte esencial de la biblioteca de código:

def nat_mod_roll(a, b):
    flat, loop = b
    return a if a < flat else (a - flat) % loop + flat

def roll_of_powers(a, b):
    powers = [1]
    while True:
        c = nat_mod_roll(a*powers[-1], b)
        if c in powers:
            return powers.index(c), len(powers) - powers.index(c)
        powers.append(c)

def tower_mod_roll(a, b):
    if len(a) == 0:
        return nat_mod_roll(1, b)
    return nat_mod_roll(a[0]**tower_mod_roll(a[1:], roll_of_powers(a[0], b)), b)

def mod(a, b):
    if isinstance(a, int): a = a,
    if isinstance(b, int): b = 0, b
    return tower_mod_roll(a, b)

Para más explicaciones ver el código completo o a solicitud de ellos.