$ab+ac+bc \equiv 1 \bmod abc$ or "easy chinese remainder theorem problems"

Question

When teaching students about the Chinese remainder theorem, it is traditional to ask them questions like: "An integer $n$ is equivalent to $r_1 \bmod m_1$, to $r_2 \bmod m_2$ and to $r_3 \bmod m_3$. Compute $n \bmod m_1 m_2 m_3$." For example,

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there? -- Sunzi Suanjing, 3rd century CE.

If it happens that $m_1 m_2 \equiv 1 \bmod m_3$, $m_1 m_3 \bmod m_2$ and $m_2 m_2 \bmod m_1$, then the question is particular easy to answer: One has $n = r_1 m_2 m_3 + r_2 m_1 m_3 + r_3 m_1 m_2$. I noticed this when preparing for my class today and planning to ask such a question with $(m_1, m_2, m_3) = (2,3,5)$, which has this property. Note that we can rewrite this property as $m_1 m_2 + m_1 m_3 + m_2 m_3 \equiv 1 \bmod m_1 m_2 m_3$.

So, for the fun of it, here is my question:

Can we describe all $k$-tuples of integers $(m_1, m_2, \ldots, m_k)$ such that $$m_1 m_2 \cdots m_{j-1} m_{j+1} \cdots m_k \equiv 1 \bmod m_j$$ for $1 \leq j \leq k$?

Answer 1

The trick is nice, but I am afraid it is hard to find any tuples, except for (2,3,5).
I tried brute force with 3 mods. For mods below 1000, only (2,3,5) satisfied.

However, even if you have only 1 pair that has $m_1\,m_2 \bmod m_3 = ±1$, it helps.

Example, $x ≡ a \bmod 5, x ≡ b \bmod 7, x ≡ c \bmod 9$

Since $5\times7 = 4\times9 - 1$, do mod 9 last.
Let $x'$ be 1 solution to $x ≡ a \bmod 5, x ≡ b \bmod 7$

$x' = a + 5k' ≡ a - 2k' ≡ b \bmod 7$

$k' = 2^{-1}(a - b) \bmod 7$

We leave $2^{-1} \bmod 7$ un-evaluated. You'll see why later ...

Let $x''$ be 1 solution to all three mods

$x'' = x' + 35k'' ≡ x' - k'' ≡ c \bmod 9$

$k'' = x' - c$

$x'' = x' + 35(x'-c) = 18(2x') - 35c = 18(2a + 5(a-b)) - 35c = 126a-90b-35c$

No inverse calculations were needed !

$$x ≡ x'' ≡ 126a-90b-35c \bmod 315$$

Answer 2

$(1,1,1)$, $(1,1,m)$ for $m \geq 2$ and $(2,3,5)$ and are the only solutions with three positive integers. I'll limit myself to positive solutions in the following.

Note that $(m_1, m_2, \ldots, m_k, 1)$ obeys the conditions if and only if $(m_1, \ldots, m_k)$ do, so we may reduce to studying solutions with $m_j \geq 2$. (Or $|m_j| \geq 2$ if we allow negative solutions.) Thus, we want to show the only solutions with $k \leq 3$ are $\emptyset$, $(m)$ and $(2,3,5)$.

We can rewrite $$ \sum m_1 m_2 \cdots m_{j-1} m_{j+1} \cdots m_k = N m_1 \cdots m_k + 1$$ as $$\sum \frac{1}{m_j} = N + \frac{1}{m_1 \cdots m_k}.$$ Note that the $m_j$ must be relatively prime and $\geq 2$, so we can bound $N$ by $1/p_1+1/p_2 + \cdots + 1/p_k$, where $p_j$ is the $j$-th prime.

When $k=0$ we get $\emptyset$. When $k=1$, any $m$ works. When $k=2$ we must have $N < 1/2+1/3 =5/6$ so $N=0$, but $1/m_1 + 1/m_2$ is never of the form $1/n$. When $k=3$, we must have $N < 1/2+1/3+1/5 = 1+1/30$, so $N=0$ or $1$, and $N=0$ doesn't work as above. Moreover, the only case of $1/a+1/b+1/c > 1$ with $(a,b,c)$ pairwise relatively prime is $(2,3,5)$.

---

A few thoughts on larger $k$. There is an infinite sequence of examples as follows: Define $x_1 = 2$ and $x_{j+1} = x_1 x_2 \cdots x_j +1$, so the $x$'s start off $2$, $3$, $7$, $43$, $1807$, ... Then $(x_1, x_2, \ldots, x_{k-1}, x_k-2)$ is always a solution.

For any finite $k$, there are only finitely many solutions, and we can find them with a backtracking search. For example, if $k=4$, then $1/a+1/b+1/c+1/d \leq 1/2+1/3+1/5+1/7 = 1+37/210$, so $N=0$ or $1$, and there are no solutions with $N=0$. Assume that $a<b<c<d$. If $a \geq 3$, then $1/a+1/b+1/c+1/d \leq 1/3+1/5+1/7+1/8 <1$, so that doesn't work and $a$ must be $2$. If $b \geq 5$ then $1/a+1/b+1/c+1/d \leq 1/2+1/5 + 1/7 + 1/8<1$, so we must have $b=3$ (as $\mathrm{GCD}(2,4) \neq 1$). When $b=3$, if $c>12$ then $1/2+1/3+1/c+1/d < 1$, so instead $c \leq 12$ and we have $(2,3,7,\ast)$ or $(2,3,11,\ast)$. Each of these completes to one value of $d$: $(2,3,7,41)$ and $(2,3,11,13)$.

Saying anything about all $k$ at once, or about negative $m_j$, seems hard.