We consider
in
for coprime integers m=9, 13, 17, and the result will follow from the Chinese Remainder Theorem.
Lemma: If
is coprime with
, then, dividing by
(which I may do since m and n are coprime), I must prove that
, which one can reduce, by Euler-Fermat, to showing that
For 9, if 3|n it is trivial, so we consider when 3 and n are coprime. Using the lemma, we must show
. Modulo 2 this is either 0-0 or 1-1, both of which are clearly zero. Modulo 3, since
by FLT, if
is even we get 1-1, and if
is odd we get n-n, so in both cases we get a zero, so
and we are done.
For 13, again, if 13|n then it is trivial, so we assume 13 and n are coprime. Again we can apply the lemma and must show
, but we showed 3 works already, so it remains to show
. If n is even this is obvious. If n is odd, then
so
and we are done.
For 17, clearly if 17 divides n then we are done, so let us suppose it is not, so n must be coprime to 17.
If
is even,
, so
, since
. But then by Fermat's Little Theorem the above equation reduces to
which is clearly true.
If
is odd, then I use the lemma.
. Now, since
for all odd n,
for all odd n, so
, and
, so since 2|n, n being coprime to 16, Euler's Theorem states that
, which is
, so we are done.
