Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties.

Question

$2^{561}\equiv ? \pmod{561}$

Few observations :
$561 = 3\times 11\times 17$
So Fermat's little theorem is not useful here. Any hints ?

If possible, kindly avoid carmichael numbers/group theory/euler theorems as this is from elementary number theory and we have just started congruences chapter.

Answer 1

We have $2^2=4\equiv1\pmod3,$

$2^5=32\equiv-1\pmod{11}\implies2^{10}\equiv(-1)^2\equiv1\pmod{11}$

$2^4=16\equiv-1\pmod{17}\implies2^8\equiv{-1}^2\equiv1\pmod{17}$

$\displaystyle\implies2^{\text{lcm}(2,10,8)}\equiv1\pmod{3\cdot11\cdot17}$

i.e., $\displaystyle2^{40}\equiv1\pmod{561}$

$\displaystyle\implies2^{561}=2(2^{40})^{14}\equiv2(1)^{14}\pmod{561}$

Reference : Carmichael function

Answer 2

Fermats or Euler is exactly what you need :) (or anything else you know )

what you need to know is this :-

if $n= p_1p_2...p_i $ such that $p_1,p_2,..., p_i$ are distinct primes which means $GCD(p_j,p_k)=1$ for $j,k \leq i$ , and $x=m \bmod p_1=m \bmod p_2 = ...=m \bmod p_i$ then $x=m \bmod (p_1p_2...p_i) \rightarrow x=m \bmod n$

now GCD(3,7 )=1 ,GCD(3,11)=1 , GCD(7,11)=1 :-

$2^{{\color{DarkBlue} {16}}}={\color{Green} 1} \bmod {\color{Red} {17} }\\ 2^{{\color{DarkBlue} 2}}={\color{Green} 1} \bmod {\color{Red} 3}\\ 2^{{\color{DarkBlue} {10}}}={\color{Green} 1} \bmod {\color{Red} {11} }\\ 2^{{\color{DarkBlue} {16\times35}}}=2^{{\color{Magenta} {560} }}={\color{Green} 1} \bmod {\color{Red} {17} }\\ 2^{{\color{DarkBlue} {2\times280}}}=2^{{\color{Magenta} {560 } }}= {\color{Green} 1} \bmod {\color{Red} 3}\\ 2^{{\color{DarkBlue} {10\times56 } }}=2^{{\color{Magenta} {560} }}= {\color{Green} 1} \bmod {\color{Red} {11} }$

$2^{\color{Magenta}{560} }= {\color{Red} 1} \bmod {\color{Blue} {3\times 11\times 17}}\\ 2^{\color{Magenta}{560} }= {\color{Red} 1} \bmod {\color{Blue} {561}}\\$

thus :-

$2^{\color{Magenta}{561} }= {\color{Red} 2} \bmod {\color{Blue} {561}} $

let me know if you dint get it yet :D