2
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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.

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