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?

  • $\begingroup$ You can't apply the $lcm(a,b)=\frac{ab}{gcd(a,b)}$ to more than two terms. $\endgroup$ – Thomas Andrews Apr 23 '12 at 15:38
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Apr 23 '12 at 15:54
  • $\begingroup$ @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 ;) $\endgroup$ – 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$

  • $\begingroup$ 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? $\endgroup$ – wieschoo Apr 23 '12 at 15:53
  • $\begingroup$ Can you figure any NUMBER which also satisfies those identities? $\endgroup$ – N. S. Apr 23 '12 at 15:59
  • $\begingroup$ 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? $\endgroup$ – wieschoo Apr 23 '12 at 16:14
  • $\begingroup$ 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? $\endgroup$ – N. S. Apr 23 '12 at 16:17
  • $\begingroup$ 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$. $\endgroup$ – wieschoo Apr 23 '12 at 16:31

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.