# Fermat's Little Theorem and congruences.

I am taking number theory and have hit a roadblock taking the next logical step in one of my proofs. I am told that $n=195=3 \cdot 5 \cdot 13$. I am asked to show that $a^{n-2} \equiv_n a, \; \forall a \in \mathbb{Z}.$

The previous part of the problem was relatively straight-forward, but this one has me stuck. So far, I have established the trivial result by considering $$n | a \Rightarrow n|a^{n-2}$$ thus, $$a^{n-2} \equiv_n 0 \equiv_n a.$$ At which point, I'd be finished. To show that this holds for all results, it seems I need to consider the congruences mod $3, 5, \text{and } 13$ and show that $a^{n-3}=a^{192}$ is congruent to $1$ for each prime factor. The problem is that I can't assume that $p \nmid a$ for $p \in \{3,5,13\}$ to be able to invoke Fermat's without loss of generality.

Could someone please point me in the right direction? I feel like I'm missing an easy (albeit fundamental) step here. Thanks!

To prove $$a^{193}-a\equiv 0\pmod{195}$$ it suffices to prove it mod $3,5,13$ then use the CRT. Prove this modulo each prime. Either $3|a$ or $3\nmid a$; in either case you should be able to prove $a^{193}-a\equiv 0\pmod{3}$. Etc.
• Sorry if this is an ignorant question, but isn't CRT used to find solutions to systems of congruences? I could certainly get the said system, but it doesn't seem like getting a solution (a set of values for $a$) would get me any closer. I'm sorry if I misunderstood, I am still pretty new to CRT. In addition, this section is about Fermat's Little Theorem, so it seems unlikely there wouldn't be at least one application of it. Thanks! – Nico Oct 20 '13 at 0:39
• Then forget CRT; if you show $a^{193} \equiv a \mod 3, 5, 13$, then you can easily conclude $a^{193} \equiv a \mod 195$, since $195 = \lcm\{3, 5, 13\}$. – user43208 Oct 20 '13 at 0:42
• You only need the uniqueness part of CRT: $a\equiv b\pmod{3,\ 5,\ 13}\ \implies\ a\equiv b\pmod{195}$. – Berci Oct 20 '13 at 0:42