4
$\begingroup$

For which $m$ do all occurrence of 1 lie on the diagonal of the multiplication table of $\mathbb{Z}_m$?

I was think i have got a prove and find all the $m$ is $1,2,3,4,6,8,12$ and $24$. but after a while, there is a bug in my prove.

suppose $m>10$ and $<10$ part is too simple first $m$ cannot be odd, or $(2,m)=1$ and there is x such that $2x\equiv1\mod{m}$, so $x\ne2$ for $m>10$ and this will against the 1 lie on diagonal.

if $(3,m)=1$, then $3^2\equiv1\pmod{m}$, then $m\mid8$ impossible too. so $3\mid m$.

if $(5,m)=1$, using the same strategy, $m|24$, with $m>10$ verify $\mathbb{Z}_{12}$ and $\mathbb{Z}_{24}$ is a solution. so we just consider $5\mid m$.

I also verified $7\mid m$, so $m=210\cdot Q$, $Q\in\mathbb{N}$.

then, if $x\in\mathbb{N}$ and $x<\sqrt{m}$, that is $x^2<m$, so $x^2\not\equiv1\pmod{m}$....

so how to continue...

$\endgroup$

marked as duplicate by JavaMan, José Carlos Santos, Xander Henderson, Ethan Bolker, Shailesh Jun 7 '18 at 0:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

You want to find the $m$ such that $a^2\equiv1\bmod{m}$ for all $a$ with $\gcd(a,m)=1$.

In terms of group theory, you want $U(m)$, the group of units mod $m$, to have exponent at most $2$.

By the Chinese remainder theorem, $U(m)$ is the product of $U(p^e)$ where $p^e \mid\mid m$.

Therefore, $U(m)$ has exponent at most $2$ iff $U(p^e)$ has exponent at most $2$.

For $p=2$, this means $e \le 3$.

For $p$ odd, this means $p=3$ and $e=1$.

Therefore, $m=2^a 3^b$ with $0 \le a \le 3$ and $0 \le b \le 1$.

Collecting all possibilities then leads to $m \in \{ 1,2,3,4,6,8,12,24 \}$.

$\endgroup$
  • $\begingroup$ This is a nice restatement of the question with the correct terminology, but doesn't actually give a hint regarding how to solve it. $\endgroup$ – Arnaud Mortier Jun 6 '18 at 16:35
  • $\begingroup$ @ArnaudMortier, now it does. $\endgroup$ – lhf Jun 6 '18 at 16:37
  • $\begingroup$ See also Carmichael function . $\endgroup$ – lhf Jun 6 '18 at 16:40
  • $\begingroup$ yes, the key is factor $m$ into prime numbers and consider occurrence of each factor. thx. $\endgroup$ – Larry Eppes Jun 7 '18 at 6:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.