# Euler, Fermat and primes

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?

• You can't apply the $lcm(a,b)=\frac{ab}{gcd(a,b)}$ to more than two terms. – Thomas Andrews Apr 23 '12 at 15:38
• Last paragraph is good start. It follows immediately that $a^k \equiv 1 \pmod{p_i^{a_i}}$. It then follows immediately that $a^k \equiv 1 \pmod{n}$. Chinese Remainder Theorem irrelevant. – André Nicolas Apr 23 '12 at 15:54
• @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 ;) – N. S. Apr 23 '12 at 16:04

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$

• I know that $a_k$ satisfies $a^k\equiv 1 \mod p_i^{a_i}$ for i=1,..., s because of the fact that the lowest common multiple is an multiple of every $p_i^{a_i}$. Did you mean this? – wieschoo Apr 23 '12 at 15:53
• Can you figure any NUMBER which also satisfies those identities? – N. S. Apr 23 '12 at 15:59
• The number 1 satiesfies those identities. I am not sure, waht you mean. The chinese remainder theorem tells that for a system $x\equiv a_1 \mod m_1$, $x\equiv a_2 \mod m_2$, ..., $x\equiv a_s \mod m_s$ we searching x which satifies all identities. So $x+k*lcm(m_1,...,m_s)$ are all solutions if any solutions exists. Is that the way? – wieschoo Apr 23 '12 at 16:14
• CRT says that there exists an unique class modulo n, which satisfies these equations. Since you discovered that $a^k$ and $1$ both satisfy those relations, what does the UNIQUENESS imply? – N. S. Apr 23 '12 at 16:17
• 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$. – wieschoo Apr 23 '12 at 16:31