Originally Posted by

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

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

*** Arithmetic modulo $\displaystyle 3$ : $\displaystyle 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 $\displaystyle 11$ : $\displaystyle 2^{35}=(2^{11})^3\cdot 2^2=2^3\cdot 2^2=32=10=-1\!\!\!\pmod {11}$

*** Arithmetic modulo $\displaystyle 17$ : $\displaystyle 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 $\displaystyle x\in\mathbb{Z}\,\,\,s.t.\,\,\,x=2\!\!\!\pmod 3\,,\,x=-1\!\!\!\pmod {11}\,,\,x=8\!\!\!\pmod{17}$ .

I found $\displaystyle 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...

$\displaystyle 2^8 = 256$,

so $\displaystyle 2^{16} = 450$ mod 561

and $\displaystyle 2^{32} = (2^{16})^2 = 103$ mod 561...

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