0
$\begingroup$

Given $n\in\mathbb{N}$ we can write for $n>1$: $n=p_1^{a_1}\cdots p_s^{a_s}$ with primes $p_i$. Define $k:=\operatorname{lcm}(\varphi(p_1^{a_1}),\ldots,\varphi(p_s^{a_s}))$ (lowest common multiple)

I have to prove: For all $a\in\mathbb{Z}$ with $\gcd(a,n)=1$ that $a^k\equiv 1\pmod n$.

My idea is to show $k=\varphi(n)$ and use Euler's Totient Theorem: $a^{\varphi(n)}\equiv 1 \pmod n$. We have the equality $\dfrac{ab}{\gcd(a,b)}=\operatorname{lcm}(a,b)$ So we have

$k=\frac{\varphi(n)}{\gcd(\varphi(p_1^{a_1}),\ldots,\varphi(p_s^{a_s}))}$ But we cannot have $\gcd(\varphi(p_1^{a_1}),\ldots,\varphi(p_s^{a_s}))=1$ in general because $p_i=2$ and $p_j=3$ wouldn't work.

Another idea is to use $a^{\varphi(p_i^{a_i})}\equiv 1 \pmod {p_i^{a_i}}$ for $i=1,\ldots, s$. How can I use the Chinese Remainder Theorem? Are there any suggestions?

  • 0
    @AndréNicolas That is the uniqueness part of CRT. And while it is easy to prove directly, any direct proof is actually a reproof of the uniqueness in the CRT ;)2012-04-23

1 Answers 1

1

Chinese Remainder Theorem tells you that there is an unique number $x \mod n$ so that

$x \equiv 1 \mod p_i^{a_i}$

Can you figure any such $x$?

Keep in mind that $a^k$ also satisfies there equivalences... Thus $a^k\equiv ... \mod n$

  • 0
    aaahh ok. The CRT says the solution is unique. But I have two solutions. So these 2 solutions have to be the same modulo n. And this says $a^k\equiv 1 \mod n$.2012-04-23