A question about modular arithmetic

Question

$2^{35}\equiv x\bmod 561$

I have seen this in my book but there is no solution in it, how can we find x?

Answer 1

As $561=3\cdot11\cdot17$

$\displaystyle2\equiv-1\pmod3\implies2^{35}\equiv(-1)^{35}\equiv-1$

$\displaystyle2^5\equiv-1\pmod{11}\implies2^{35}=(2^5)^7\equiv(-1)^7\equiv-1$

$\displaystyle2^{35}\equiv-1\pmod{33}\ \ \ \ (1)$

$\displaystyle2^4=16\equiv-1\pmod{17}\implies2^{35}=2^3(2^4)^8\equiv8\cdot(-1)^8\equiv8\ \ \ \ (2)$

Apply CRT on $(1),(2)$

Answer 2

Binary expansion of 35: $2^5 + 2 + 1$.

$2^{2^1} = 4$ (mod 561) $2^{2^2} = 16$ (mod 561) $2^{2^3} = 256$ (mod 561) $2^{2^4} = 460$ (mod 561) $2^{2^5} = 103$ (mod 561)

$2^{2^5} \times 2^2 \times 2 = 103 \times 4 \times 2 = 263$ (mod 561)

Answer 3

Hint $\,\ \color{#c00}{2^{40}\equiv 1}\pmod {3\cdot 11\cdot 17}\ $ by $\ 2^2\equiv 1\pmod 3,\,\ 2^5\equiv -1\pmod {11},\,\ 2^4\equiv -1\pmod {17},\,$

so $\ 2^{35}\! \equiv\, \dfrac{\color{#c00}{2^{40}}}{2^5}\, \equiv\,\dfrac{\color{#c00}1}{32}\, \equiv\, \dfrac{-560}{\ \ \ 32}\, \equiv \,\dfrac{-35}{\ \ 2}\, \equiv\, \dfrac{526}2\, \equiv\, 263.\ \ $ QED $\ \ $ (all easy mental arithmetic)

Remark $\ $ We exploited the fact that it easy to divide $\,a\,$ by $2$ modulo odd $\,m,\,$ since $\,a\equiv a\pm m\,$ have opposite parity, so one of them is even, so easily divisible by $2.\,$ Therefore, iterating, we can easily divide by $2^k,\,$ just as we did above.