  The structure of the group $(\mathbb{Z}/n\mathbb{Z})^\star$ and Fermat's
little theorem are the basis for some of best-known primality testing
algorithms. Many related concepts arise: Euler's totient function and
Carmichael's lambda function, Fermat pseudoprimes, Carmichael and cyclic
numbers, Lehmer's totient problem, Giuga's conjecture, etc. In this paper, we
present and study analogues to some of the previous concepts arising when we
consider the underlying group
$\mathcal{G}_n:=\{a+bi\in\mathbb{Z}[i]/n\mathbb{Z}[i] : a^2+b^2\equiv 1\
\textrm{$\pmod n$}\}$. In particular we characterize Gaussian Carmichael
numbers via a Korselt's criterion and we present their relation with Gaussian
cyclic numbers. Finally, we present the relation between Gaussian Carmichael
number and 1-Williams numbers for numbers $n \equiv 3 \pmod{4}$. There are also
no known composite numbers less than $10^{18}$ in this family that are both
pseudoprime to base $1+2i$ and 2-pseudoprime.
