# Proving that no integer has multiplicative order 40 (mod 100)

I am trying to prove that no integer has multiplicative order 40 (mod 100), so far I have listed the facts that I know:

$\phi(100) = 40$, this means that for any integer $a$ relatively prime to $100$ we definitely have $a^{40} \equiv 1 \pmod{100}$ by Euler's theorem. Furthermore, the order of $a \pmod{b}$ must divide $40$; therefore, we can never have an order that is more than $40$.

However, I am unable to prove that it can not be $40$?

Edit: I am unable to understand the notation used in the answers below since I have only studied the bare minimum of elementaty number theory, but I think I got the idea:

We have $a^{40} \equiv 1 \pmod{25}$ and $a^{40} \equiv 1 \pmod{4}$ since $4$ and $25$ are coprime. However, $a^{40}$must still be coprime to both 25 and 4, not sure how to prove this but I think it is natural since $100$ had them as divisors and $a^{40}$ was coprime to 100. Inspecting the two new equations we have $\phi(4) = 2$; therefore, the order of $a$ must not be more than 2 now.

Edit: I just realized it doesn't make sense to say not more than 2 since we are looking for $\pmod{100}$....not sure where to go from here?

Please correct if my proof is incorrect, thank you.

• Do you know the Chinese remainder theorem? – Kevin Carlson Oct 24 '15 at 22:35
• yea I know it but how would you apply it? Don't you need two modulus? – fYre Oct 24 '15 at 22:41
• Yeah, as below, try 25 and 4. – Kevin Carlson Oct 24 '15 at 22:46

You can have a direct proof: in $$(\mathbf Z/100\mathbf Z)^\times\simeq(\mathbf Z/4\mathbf Z)^\times\times(\mathbf Z/25\mathbf Z)^\times\simeq\mathbf Z/2\mathbf Z\times\mathbf Z/20\mathbf Z,$$ (the last groups are the additive groups), an element $(a,b)$ has order the l.c.m. of the orders of $a$ and $b$, which are divisors of $2$ and $20$, hence a divisor of $\;\operatorname{lcm}(2,20)=20$.
We have that $\Bbb{Z}/100 \cong \mathbb{Z}/25 \times \mathbb{Z}/4$ so $$(\Bbb{Z}/100)^\times \cong (\mathbb{Z}/25)^\times \times (\mathbb{Z}/4)^\times.$$ Now suppose there is an element of order $40$ and try to find a contradiction.