# Thread: Is there a quicker way to solve this congruence

1. ## Is there a quicker way to solve this congruence

Is $2^{35} \equiv 1 \textrm{ mod } 561$?

In the question we were given maple commands to use so I assume we were meant to do it that way. Is there a way to solve this without a calculator?

I had to use one but just did it like...

$2^8 = 256$,
so $2^{16} = 450$ mod 561
and $2^{32} = (2^{16})^2 = 103$ mod 561...

Then $2^{35} = 2^{32} 2^3 = 103 \times 8$ which is not equal to 1 mod 561..

Is $2^{35} \equiv 1 \textrm{ mod } 561$?

Since $561=3\cdot 11\cdot 17$ , we can do:

*** Arithmetic modulo $3$ : $2^{35}=(2^3)^{11}\cdot 2^2=2^{11}\cdot 2^2=(2^3)^4\cdot 2=2^4\cdot 2=2^3\cdot 2^2=2^3=2\!\!\!\pmod 3$

*** Arithmetic modulo $11$ : $2^{35}=(2^{11})^3\cdot 2^2=2^3\cdot 2^2=32=10=-1\!\!\!\pmod {11}$

*** Arithmetic modulo $17$ : $2^{35}=(2^{17})^2\cdot 2=2^2\cdot 2=8\!\!\!\pmod {17}$ .

Well, now use the Chinese Remainder Theorem to find an element $x\in\mathbb{Z}\,\,\,s.t.\,\,\,x=2\!\!\!\pmod 3\,,\,x=-1\!\!\!\pmod {11}\,,\,x=8\!\!\!\pmod{17}$ .

I found $x=-298=263\!\!\!\pmod{561}\Longrightarrow 2^{35}=263\!\!\!\pmod{561}$ , as you can easily check with any calculator.

Tonio

In the question we were given maple commands to use so I assume we were meant to do it that way. Is there a way to solve this without a calculator?

I had to use one but just did it like...

$2^8 = 256$,
so $2^{16} = 450$ mod 561
and $2^{32} = (2^{16})^2 = 103$ mod 561...

Then $2^{35} = 2^{32} 2^3 = 103 \times 8$ which is not equal to 1 mod 561..
.