# 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:=lcm(\varphi(p_1^{a_1}),\ldots,\varphi(p_s^{a_s}))$ ( lowest common multiple)

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

My idea is to show $k=\varphi(n)$ to use the euler theorem $a^{\varphi(n)}\equiv 1 \mod n$. We know the equality $(ab)/gcd(a,b)=lcm(a,b)$. So we have

$k=\frac{\varphi(n)}{gcd(\varphi(p_1^{a_1}),\ldots,\varphi(p_s^{a_s}))}$. But this cannot be $gcd()=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 \mod p_i^{a_i}$ for i=1,...., 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