Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties. $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.
 A: 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
A: 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
