Show that, for every integer $a$ such that $\gcd(a,100)=1$, we have $a^{20}≡1\pmod{100}$.

Question

Show that, for every integer $a$ such that $\gcd(a,100)\equiv 1$, we have $a^{20}\equiv 1\pmod{100}$.

Based on Euler's theorem, I have $a^{40}\equiv 1\pmod{100}$, but I have problem getting to $a^{20}\equiv 1\pmod{100}$. And I am wondering if it has to do with the fact that $20\mid 40$?

Any hints would be appreciated!

Answer 1

I don't have enough reputation to comment, so I'm going to have to write this in an answer. To answer your question about why $a^{20} \equiv 1 + 50k$, expand $(1 + 10k)^5$. It's just$1+5*10k+10*10^2k^2+10*10^3k^3+5*10^4k^4+10^5k^5$. Notice how all the terms after $50k$ are divisible by $100$, so they can be eliminated. From here, the logic in fleablood's comment works.