3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Yes my bad..... $\endgroup$
    – AEIOUY
    Jul 8, 2017 at 13:05
  • 6
    $\begingroup$ 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. $\endgroup$
    – egreg
    Jul 8, 2017 at 13:10
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – lulu
    Jul 8, 2017 at 13:17

3 Answers 3

8
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$ ? $\endgroup$
    – AEIOUY
    Jul 9, 2017 at 8:06
  • $\begingroup$ 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 ? $\endgroup$
    – Jon
    Sep 23, 2019 at 6:52
6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .