0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What have you done for the first question so far? Were you at least thinking of applying Euler's theorem? $\endgroup$ – астон вілла олоф мэллбэрг Sep 6 '17 at 5:47
  • $\begingroup$ 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! $\endgroup$ – Alexander Collins Sep 6 '17 at 6:05
1
$\begingroup$

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.

$()$

$\endgroup$

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.