2
$\begingroup$

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

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

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

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

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.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.