Math Help - Modulo help

1. Modulo help

hey guys, I have a question here which I dont quite understand how my tutor got from a certain step...

Compute: $2^21$ mod 53

$\Rightarrow 2^{21}$ = x (mod 53)
$\Rightarrow 2^{21}$ = $2^{16} \cdot 2^{5}$ (mod 53)
$\Rightarrow 2^{16}$ = $2^8 \cdot 2^8$ (mod 53)
$\Rightarrow 2^{8}$ = $256$ (mod 53) <--FROM HERE
$\Rightarrow 256$ = $-9$ (mod 53) <-- TO HERE, mainly where that -9 came from

thanks for the help!

2. Originally Posted by jvignacio
hey guys, I have a question here which I dont quite understand how my tutor got from a certain step...

Compute: $2^21$ mod 53

$\Rightarrow 2^{21}$ = x (mod 53)
$\Rightarrow 2^{21}$ = $2^{16} \cdot 2^{5}$ (mod 53)
$\Rightarrow 2^{16}$ = $2^8 \cdot 2^8$ (mod 53)
$\Rightarrow 2^{8}$ = $256$ (mod 53) <--FROM HERE
$\Rightarrow 256$ = $-9$ (mod 53) <-- TO HERE, mainly where that -9 came from

thanks for the help!
53 divides into 256 four times with remainder of 44. That is, 256= 4(53)+ 44. But it is also true, then, that 256= 4(53)+ 53- 9= 5(53)- 9. That is, -9+ 53= 44 so 44= -9 (mod 53). All numbers that differ by 53 are equivalent modulo 53.

3. Hello, jvignacio!

I have no idea why your tutor used such a roundabout approach!

Compute: $2^{21}$ mod 53

$2^8 \:\equiv\: 256 \:\equiv\:44 \:\equiv\:-9 \text{ (mod 53)}$
I would solve it like this . . .

. . $\begin{array}{cccc}2^{21} &\equiv& 2,\!097,\!152 & \text{(mod 53)} \\ \\[-3mm]

& \equiv& 48 & \text{(mod 53)} \end{array}$

4. Originally Posted by Soroban
Hello, jvignacio!

I have no idea why your tutor used such a roundabout approach!

I would solve it like this . . .

. . $\begin{array}{cccc}2^{21} &\equiv& 2,\!097,\!152 & \text{(mod 53)} \\ \\[-3mm]

& \equiv& 48 & \text{(mod 53)} \end{array}$

To avoid using big numbers?

5. Originally Posted by jvignacio
To avoid using big numbers?

$2^6=11\!\!\!\pmod {53}\Longrightarrow 2^{12}=11^2=15\!\!\!\pmod {53}\Longrightarrow$ $2^{18}=2^6\cdot 2^{12}=11\cdot 15 = 165=6\!\!\!\pmod {53}$ $\Longrightarrow 2^{21}=2^3\cdot 2^{18}=8\cdot 6=48\!\!\!\pmod {53}$

Tonio