How to solve $2^{33} \mod 4725$?

205 Views Asked by At

Basically what I should do is:

$$2^{33} \equiv x \pmod{4725}.$$

I need to find $x$ which will give same result as $2^{33}$ when modulo $4725$.

I should find prime factors of $4725$ which are $4725 = 3^3 × 5^2 × 7^1$, and use them to calculate \begin{align*} 2^{33} &\equiv x \pmod{3^3}\\ 2^{33} &\equiv x \pmod{5^2}\\ 2^{33} &\equiv x \pmod{7^1} \end{align*}

so I could apply Chinese remainder theorem to calculate result, but I am stuck with calculating these. I don't know what to do with $2^{33}$, how to decompose it?

Any help is welcome.

2

There are 2 best solutions below

0
On BEST ANSWER

I will compute $2^{33}\pmod {27}$ as the OP is ok with the rest of the calculation.

In what follows $\equiv $ denotes congruence $\pmod {27}$.

Method I (iterated squaring): This works unusually well in this case because $33=32+1$ is so near a power of $2$. We write:

$$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$$

It follows that $$2^{33}=2^{32}\times 2\equiv 17\pmod {27}$$

Method II (Euler): As $\varphi(27)=18$ we have $2^{18}\equiv 1$. Thus $2^{36}\equiv 1$ so $2^{33}\equiv 2^{-3}$. As the inverse of $2\pmod {27}$ is clearly $14$ we see that $$2^{33}\equiv 14^3\equiv 17\pmod {27}$$

Note: It's not especially harder to do the entire problem by iterated squaring. Working $\pmod {4725}$ we have $$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}$$

0
On

Compute the orders of $2$ mod. $27$ and mod. $25$: it is a divisor of $\varphi(3^3)=18$ and $\varphi(5^2)=10$. So $$2^{33}\equiv 2^{33\bmod o_{27}(2)}\mod 27,\qquad2^{33}\equiv 2^{33\bmod o_{25}(2)}\mod 25.$$