Prove that for any positive integer $a$, $a^{561} \equiv a \pmod{561}$. (Hence, $561$ is a pseudoprime with respect to any base. Such a number is called a Carmichael number.)
This obviously works for $1$ but how do I find $2^{561}$ or any other number to the power of $561?$
On
Fermat's theorem implies that $a^{(p-1)n+1} \equiv a \bmod p$ for all primes $p$, all $a$ and all $n$.
Since $561=3\cdot 11\cdot 17$, apply this to $(p,n)=(3,560/2)$, $(11,560/10)$, $(17,560/16)$.
On
Composite numbers $n>1$, which satisfy $a^{n-1}\equiv 1\pmod{n}$ for all positive integers $a$ with $\gcd(a,n)=1$, are called $\color{red}{\text{Carmichael numbers}}.$
There is a necessary and sufficient criterion for a positive integer to be a Carmichael number known as the Korselt's criterion
$\color{red}{\text{Korselt's Criterion:}}$ A positive integer $n>1$ is a Carmichael number if and only if $(1)$ $n$ is square-free, $(2)$ for any prime divisor $p$ of $n$, $p-1\mid n-1$
Proof: Try yourself. An easy application of Chinese Remainder Theorem
You can verify, using this criterion, that $561$ is a Carmichael number. In fact, there are infinitely many of them.
Since $$a^{561}-a=\left(a^{560}-1\right)a,$$ we see that $a^{561}-a$ is divisible by $a^3-a$, by $a^{17}-a$ and by $a^{11}-a$, which says that it's divisible by $3$, by $17$ and by $11$, which says that it's divisible by $3\cdot17\cdot11=561$.