Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.