Cómo solucionar $2^{33} \mod 4725$?

Question

Básicamente lo que debes hacer es:

$2^{33} \equiv x \mod4725$

Necesito saber x que dará el mismo resultado como $2^{33}$ al $\mod4725$.

Debo encontrar los factores primos de $4725$ cuales son

$4725 = 3^3 5^2 7^1$

y los utilizan para calcular

$2^{33} \equiv x \mod3^3$

$2^{33} \equiv x \mod5^2$

$2^{33} \equiv x \mod7^1$

así que se podría aplicar el teorema del resto Chino para calcular el resultado.

Estoy atascado con el cálculo de estos:

$2^{33} \equiv x \mod3^3$

...

No sé qué hacer con $2^{33}$, cómo se descompone?

Cualquier ayuda es bienvenida.

Answer 1

Voy a calcular $2^{33}\pmod {27}$ como el OP está bien con el resto de los cálculos.

En lo que sigue, $\equiv $ denota la congruencia $\pmod {27}$.

Método I (a afirmar cuadratura): Esto funciona excepcionalmente bien en este caso debido a que $33=32+1$ es así que cerca de un poder de $2$. Escribimos:

$$2^2=4\implies 2^4=16\implies 2^8=16^2\equiv 13 \implies 2^{16}\equiv 13^2\equiv 7$$

$$\implies 2^{32}\equiv 7^2\equiv -5$$

De ello se desprende que $$2^{33}=2^{32}\times 2\equiv 17\pmod {27}$$

Método II (Euler): Como $\varphi(27)=18$ tenemos $2^{18}\equiv 1$. Por lo tanto $2^{36}\equiv 1$ lo $2^{33}\equiv 2^{-3}$. Como la inversa de $2\pmod {27}$ es claramente $14$ vemos que $$2^{33}\equiv 14^3\equiv 17\pmod {27}$$

Nota: no Es especialmente difícil hacer todo el problema por iterada de cuadratura. Trabajo $\pmod {4725}$ hemos $$2^8=256 \implies 2^{16}\equiv 4111 \implies 2^{32}\equiv {4111}^2 \equiv 3721$$ So $$2^{33}=2^{32}\times 2 \equiv 2717\pmod {4725}$$

Answer 2

Calcular las órdenes de $2$ mod. $27$ y mod. $25$: es un divisor de $\varphi(3^3)=18$ e $\varphi(5^2)=10$. Así $$2^{33}\equiv 2^{33\bmod o_{27}(2)}\mod 27,\qquad2^{33}\equiv 2^{33\bmod o_{25}(2)}\mod 25.$$