3
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Nico Oct 20 '13 at 0:39
  • $\begingroup$ 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\}$. $\endgroup$ – user43208 Oct 20 '13 at 0:42
  • $\begingroup$ You only need the uniqueness part of CRT: $a\equiv b\pmod{3,\ 5,\ 13}\ \implies\ a\equiv b\pmod{195}$. $\endgroup$ – Berci Oct 20 '13 at 0:42
  • $\begingroup$ You guys nailed it. Thank you for the help. I split up the congruences and showed them to hold in each case then recombined. I wasn't taught that that specific fact was part of CRT, but that makes absolute sense. Thanks again! $\endgroup$ – Nico Oct 20 '13 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.