## Weird relationship: Exists x(not 1), x^3=1 MOD M if and only if 3|Phi(M) [closed]

I found a weird relationship and was hoping someone could explain why it happens:

In module M, there exists a x not equal to 1, such that x^3=1

If and only if:

3 divides the Euler Totient Phi function of M.

Any insights? (if this is not accurate, please let me know, but this relationship seems to hold true for all modulo bellow 300)

Thanks.

(Sorry if my tagging is bad... don't know enough to properly tag this)

-
The order of multiplicative group of the ring Z/mZ is phi(m). This and Lagrange's theorem solve the problem. The question is not appropriate for MO, though. – Boris Bukh Jan 16 2010 at 17:31
This seems not appropriate for MO, I suggest looking at sites listed in the FAQ. I'm flagging to close. – Grétar Amazeen Jan 16 2010 at 17:31
You need to adjust your definition of weird... – Mariano Suárez-Alvarez Jan 16 2010 at 17:37
Boris, Lagrange takes care of the "only if" part. The "if" part seems less trivial and requires either the classification of finite abelian groups, or Sylow's theorems, or the structure of (Z/mZ)^*. Or am I missing something? – algori Jan 16 2010 at 18:35
@algori - This is not hard to do without using group theory (see Niven and Zuckerman, for example), but it's true that Boris should have used Cauchy's theorem, not Lagrange's. en.wikipedia.org/wiki/… – Ben Webster Jan 16 2010 at 19:27
show 1 more comment