How can I prove the following?
There exists an integer $a$ other than 1 such that $a^n = 1 \mod q$ when $q = 1 \mod n$.
- $q$: either a prime or an arbitrary integer.
- $n$: even integer
If $q$ is a prime, yes we can prove that using Fermat's little theorem.