245 views

Compute $2^{32} \; \mod \; 37$

$2^{-4} \ 2^{36} \mod 37 = 2^{-4} \mod 37$  (By Fermat’s Little Theorem)

Since, $2 \times 19 \equiv 1 \mod 37. \$ So, $2^{-1} \mod 37 = 19$

Hence, $2^{-4} \mod 37 = 19^4 \mod 37 = 7$
$2^{-4} \mod 37 = 16^{-1} \mod 37$

Using Euclidean Algorithm

$37 = 2*16 + 5$ and $16 = 3*5 + 1 \Rightarrow 1 = 16 \ – \ 3*(37 \ – \ 2*16) \Rightarrow 1 = 7*16 \ – \ 3*37$

Hence, $16^{-1} \mod 37 = 7$

Hello sir @ankitgupta.1729
where can i learn the above approaches?

Extended Euclidean Algorithm

These are quite famous, so, if you don’t get it from here then you can search some text over web or videos on youtube also.

$2^2\equiv 4\; \mod \; 37\\ 2^4 \equiv 16 \; \mod \; 37\\ 2^8 \equiv 256 \equiv 34 \; \mod \; 37\\ 2^{16} \equiv (-3)^2 \equiv 9 \; \mod \; 37\\ 2^{32} \equiv 81 \; \mod \; 37\\ 2^{32} \equiv 7 \; \mod \; 37$