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$.
Answer
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.
$()$
No comments:
Post a Comment