# $\!\!\bmod 24\!:\ mn+1\equiv 0\Rightarrow m+n \equiv 0\,$ using group theory

I would like to prove that : if $m, n \in \mathbb{N}$ such that : $mn+1 \equiv 0 \pmod{24}$ then $m+n \equiv 0 \pmod{24}$.

I know how to prove that but it's quite annoying : just look at every possible rest of $m$ and $n$ mod $24$. Yet it's annoying because they are $24^2$ cases to be treated.

I think we can solve that more easily using group theory, that's why I am just asking : does any one have an idea of how to solve this problem using group theory ? Maybe by looking at : $\mathbb{F}_{3}$ and $\mathbb{F}_2$...

• Yes my bad..... Jul 8, 2017 at 13:05
• SInce $\varphi(24)=8$, there are actually eight cases to check, because $mn+1\equiv0\pmod{24}$ implies $\gcd(m,24)=1$ and determines uniquely $n$ once $m$ is fixed. Jul 8, 2017 at 13:10
• Just to be clear, this is not a broadly true result. For example $3\times 3+ 1\equiv 0 \pmod {10}$ but $3+3=6$ is not $0\pmod {10}$. So at some point you are going to have to look at the invertible elements $\pmod {24}$.
– lulu
Jul 8, 2017 at 13:17

You're trying to prove that if $mn \equiv -1 \pmod{24}$ then $m \equiv -n \pmod{24}$.

Let $k = -n$. Then you're trying to show that if $-mk \equiv -1 \pmod{24}$ then $m \equiv k \pmod{24}$.

Of course if $-mk \equiv -1$ then $mk \equiv 1$. So what you want to show is that in the integers $\mod 24$, every invertible element is its own inverse. Group-theoretically, this amounts to showing that every element of $(\mathbb{Z}/24\mathbb{Z})^\times$has order $1$ or $2$.

But by the Chinese remainder theorem, $(\mathbb{Z}/24\mathbb{Z})^\times$ is isomorphic to $(\mathbb{Z}/3\mathbb{Z})^\times \times (\mathbb{Z}/8\mathbb{Z})^\times$. It's enough to show that every non-identity element of $(\mathbb{Z}/3\mathbb{Z})^\times$ and of $(\mathbb{Z}/8\mathbb{Z})^\times$ has order $2$. But that's easy to do by direct computation: $2^2 \equiv 1 \pmod{3}$ and $3^2 \equiv 5^2 \equiv 7^2 \equiv 1 \pmod{8}$.

• Ok I like this answer a lot ! :) Yet I have a question : you say that we should show that every element of : $(\mathbb{Z} / 24 \mathbb{Z}, \times)$ has order $1$ or $2$, but that's false ? Take for example $4 \in \mathbb{Z} / 24 \mathbb{Z}$, $4 \not\equiv 1 \pmod{24}$ and $4^2 \not\equiv 1 \pmod {24}$. So maybe you should say that every invertible element of : $(\mathbb{Z} / 24 \mathbb{Z}, \times)$ has order $1$ or $2$ ? Jul 9, 2017 at 8:06
• Why does showing that every element in $\left(\mathbb{Z}/_{3}\mathbb{Z}\right)^{\times}$ and $\left(\mathbb{Z}/_{8}\mathbb{Z}\right)^{\times}$ has order less than or equal to 2 imply that every element in $\left(\mathbb{Z}/_{24}\mathbb{Z}\right)^{\times}$ also has order less than or equal to 2 ?
– Jon
Sep 23, 2019 at 6:52

Swapping sign of $$\:\!n\:\!$$ it becomes $$\,mn \equiv 1\Rightarrow m\equiv n,\,$$ i.e. $$\:\!n\:\!$$ invertible $$\:\!\Rightarrow\, n^{-1}\equiv n\, [\!\iff\! n^2\equiv 1],\,$$ true mod $$8$$ and mod $$3$$, since invertibles mod $$8$$ are odd, therefore $$\,{\rm odd}^2\!\equiv \{\pm1, \pm3\}^2\equiv 1,$$ and mod $$3$$ invertibles are $$\pm 1$$ which also square to $$1$$. Thus $$\,3,8\mid n^2\!-\!1\,\Rightarrow\,{\rm lcm}(3,8)\!=\! 24\mid n^2\!-\!1.\,$$ Proving the converse is trickier, but it has a one line proof.

Via group theory: using Carmichael's lambda function (universal group exponent) we compute $$\lambda(8\cdot 3) = {\rm lcm}(\phi(8)/2,\phi(3)) = {\rm lcm}(2,2) = \color{#c00}2,\,$$ so $$\,(n,24)=1\,\Rightarrow\, n^{\color{#c00}{\large 2}}\equiv 1\pmod{\!24}$$

Remark  This characteristic property of $$24$$ lies at the heart of many results - even in more advanced contexts, e.g. see Chebolu: What Is Special about the Divisors of 24? (2017), and Gannon: Moonshine beyond the monster: The bridge connecting algebra, modular forms and physics. (2006), and see the prior question A high-powered explanation for $$\exp U(n)=2\iff n\mid24$$?

The OP can solve this without resorting to the brute force breakdown of $$24^2$$ cases; they can employ 'staring you in the face' group theory and then roll up their sleeves.

With

$$mn+1 \equiv 0 \pmod{24}$$

we can write

$$m \cdot (-n) \equiv 1 \pmod{24}$$
$$(-m) \cdot n \equiv 1 \pmod{24}$$

and so

$$m^{-1} \equiv -n \pmod{24}$$
$$n^{-1} \equiv -m \pmod{24}$$

It is elementary to write

$$\mathbb{Z}/24\mathbb{Z}^\times = \{1,5,7,11,13,17,19,23\}$$

and to solve for $$m$$ and $$n$$:

$$(m,n) \in A \cup A^T$$

where

$$A = \{(1,23),(5,19),(7,17),(11,13)\}$$

So as they say, "if the glove fits you must wear it" and, indeed,

$$\bmod 24\!:\ mn+1\equiv 0\Rightarrow m+n \equiv 0$$