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$

1 Answer 1

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$
4
  • $\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, 2013 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, 2013 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, 2013 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, 2013 at 1:18

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .