# Fore some co-prime's m, n and some integer a given gcd(a, mn) = 1, prove the following...

I'm having some trouble with the following question from my homework. I searched all over the exchange to find some common question but to my dismay I couldn't find anything. I apologise if this question has already been asked.

Let $m$ and $n$ be two co-prime positive integer numbers.

Let $a$ be an integer such that $\gcd(a, mn) = 1$.

First Show that:

$a^{\text{lcm}(\phi(m), \phi(n))} \equiv 1\bmod(mn)$,

where $\text{lcm}(\phi(m), \phi(n))$ is the least common multiple of $\phi(m)$ and $\phi(n)$.

Then Deduce that for any $a$ which is co-prime with $10$

$a^{20} \equiv 1 \bmod 100$.

• What have you done for the first question so far? Were you at least thinking of applying Euler's theorem? Sep 6 '17 at 5:47
• Yeah that was what came to mind first, Im currently studying the topic and my lecturer makes it very difficult to understand. I guess i'm just trying to wrap my head around which concepts the question actually requires me to apply rather than a particular answer. Thankyou for your positive response! Sep 6 '17 at 6:05

Indeed, one does use Euler's theorem.

Since $a$ is co-prime to $m$, we have $a^{\phi(m)} \equiv 1 \mod m$. Now, $\operatorname{lcm}(\phi(m),\phi(n))$ is a multiple of $\phi(m)$, hence it follows that by raising both sides of the previous equation to the power $\frac{\operatorname{lcm}(\phi(m),\phi(n))}{\phi(m)}$, we get that $a^{\operatorname{lcm}(\phi(m),\phi(n))} \equiv 1 \mod m$.

Use the same argument as above to show that $a^{\operatorname{lcm}(\phi(m),\phi(n))} \equiv 1 \mod n$. Then $m$ and $n$ are co-prime, they both divide something, so their product must divide that... should give you the answer.

EDIT: For the second part, we have to use the previous part, so all you need is $m$ and $n$. I claim $m=4,n=25$ will do the job. Note that any number which is coprime to $m$ and $n$ is coprime to $10$ and hence to $100$. Also, $\phi(25) = 20$ and $\phi(4)=2$. Now just apply the lemma.

$()$

• Thank you so much, How would I then deduce the second part of the question? I've tried but i'm still having trouble. Sep 7 '17 at 2:49
• Okay, I will edit my answer. Actually,I'm done editing my answer. Sep 7 '17 at 2:52
• Thank you so much, you've been a great help to my understanding! Sep 7 '17 at 2:58
• You are welcome! Sep 7 '17 at 2:58