MODBasic Basic

Problem - 4215

Suppose integers $a$ and $b$ satisfy $ab\equiv -1 \pmod{24}$. Prove $(a + b)$ must be a multiple of $24$.


The fact $ab\equiv -1\pmod{24}$ means that $ab\equiv -1\pmod{3}$, $ab\equiv -1\pmod{8}$, and neither $a$ nor $b$ is zero.

Let's first consider $ab\equiv -1\pmod{3}$. If $a\equiv \pm 1\pmod{3}$, then $b\equiv \mp 1\pmod{3}$. Either way, $(a+b)\equiv 0\pmod{3}$.

Next, let's consider $ab\equiv -1\pmod{8}$. It is clearly $a\pmod{8}$ can only be an odd number, i.e. $a\equiv\pm 1, \pm 3\pmod{8}$.

  • If $a\equiv\pm 1\pmod{8}$, then $b\equiv\mp 1\pmod{8}$. It follows that $(a + b)\equiv 0\pmod{8}$.
  • If $a\equiv\pm 3\pmod{8}$, then $b\equiv\mp 3\pmod{8}$. It follows that $(a + b)\equiv 0\pmod{8}$.

Therefore, we always have $(a+b)\equiv 0\pmod{8}$.

These two mean that $(a+b)$ must be a multiple of $24$.

report an error