# A question about modular arithmetic

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

• Note that $561= 3\times 11\times 17$ – Mark Bennet Jun 11 '14 at 19:16

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

• @Downvoter, Please pinpoint the mistake here – lab bhattacharjee Jun 13 '14 at 15:25

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.

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)