# A simple modular arithmetic query.

Given $a,b,c\in\Bbb N$ with $\mathsf{gcd}(a,b)=\mathsf{gcd}(b,c)=\mathsf{gcd}(c,a)=1$ we know that there are $m_1,m_2,m_3\in\Bbb N$ such that $a\equiv m_1a^2\bmod abc$, $ab\equiv m_2ab\bmod abc$ and $b\equiv m_3b^2\bmod abc$ holds.

It is also easy to see there is a single $m$ such that $$a\equiv ma\bmod ab,\quad b\equiv mb\bmod ab$$ holds.

However how to find a single $m$ coprime to $c$ such that $$1\equiv ma\bmod abc,\quad 1\equiv mb\bmod abc$$ holds?

At least how to find a single $m$ such that $$\ell_1 a\equiv ma^2\bmod abc, \quad \ell_2 ab\equiv mab\bmod abc,\quad\ell_3b\equiv mb^2\bmod abc$$ holds where $0<\ell_1,\ell_2,\ell_3<\log abc$ holds and at least one of $\ell_1,\ell_2,\ell_3$ is distinct?

If not how small can we make $\max(\ell_1,\ell_2,\ell_3)$ where $a\nmid\ell_1$ and $b\nmid\ell_3$ holds?

• What is the point of the last $\equiv ab$ in "$ab\equiv mab\bmod abc\equiv ab$"? Commented Jan 12, 2017 at 6:44
• @Arthur corrected there. Commented Jan 12, 2017 at 7:00

You ask how to find a single $m$ such that

\begin{align*} 1 &\equiv ma \text{ mod } (abc)\\ 1 &\equiv mb \text{ mod } (abc)\\ \end{align*}

But

\begin{align*} &1 \equiv ma \text{ mod } (abc)\\ \implies\; &1 \equiv ma \text{ mod } (a)\\ \implies\; &1 \equiv 0 \text{ mod } (a)\\ \implies\; &a = 1\\ \end{align*}

Similarly

\begin{align*} &1 \equiv mb \text{ mod } (abc)\\ \implies\; &1 \equiv mb \text{ mod } (b)\\ \implies\; &1 \equiv 0 \text{ mod } (b)\\ \implies\; &b = 1\\ \end{align*}

Thus, unless $a = b = 1$, there will be no such $m$.

At least how to find a single $m$ such that $$\ell_1 a\equiv ma^2\bmod abc, \quad \ell_2 ab\equiv mab\bmod abc,\quad\ell_3b\equiv mb^2\bmod abc$$ holds where $0<\ell_1,\ell_2,\ell_3<\log abc$ holds?

First note that $gcd(ma^2,abc)=a, gcd(ma^2,a\ell_1)=a$. This is a direct result of $\gcd(a,r)=a \iff \gcd(a,b)=a$ in $a \equiv r \pmod b$

Then rewrite $ma^2 \equiv \ell_1 \pmod{abc}$ as:

$ma^2 = abck + a\ell_1$

$ma = bck + \ell_1$

Then $ma \equiv \ell_1 \pmod{bc}$

It is easy to follow these simplification to obtain the others.

You can simplify as:

$$\ell_1 \equiv ma \pmod{bc}, \quad \ell_2 \equiv m \pmod c, \quad \ell_3 \equiv mb \pmod{ac}$$

Now choose a value $r \in (0,\log abc)$

Note that if $m<c$ then $m=r$ and $\ell_1=\ell_2=\ell_3=r$

When $c \mid m$ then $\ell_1=\ell_2=\ell_3=0$

When $m>c \Rightarrow$ $m=ck+r, a=b$ then $\ell_1=\ell_2=\ell_3=r$ and you will have:

$$a\ell_1 \equiv ma \pmod{ac}, \quad \ell_2 \equiv m \pmod c, \quad b\ell_3 \equiv mb \pmod{bc}$$

For $m>c$ then $\ell_1\neq\ell_2\neq\ell_3 \iff a,b,c$ are pairwise coprime thus the solution must follow these restrictions:

$$\ell_1 < bc < \log abc$$

$$\ell_2 < c < \log abc$$

$$\ell_3 < ac < \log abc$$

• @kubox How can you simplify to $\ell_1\equiv m\mod bc$? Commented Jan 12, 2017 at 10:59
• @kubox also if possible try make not $\ell_1=\ell_2=\ell_3$. Commented Jan 12, 2017 at 11:06
• @AJ.: I fixed an error in my simplification. Also I included a case where $\ell_1\neq\ell_2\neq\ell_3$. Hope it helps. Commented Jan 12, 2017 at 11:52
• all are positive right? Commented Jan 12, 2017 at 11:59
• 'Note that if $m<c$ then $m=r$ and $\ell_1=\ell_2=\ell_3=r$' I do not see this. I only see $\ell_2=r$ and $\ell_1=ra$ and $\ell_3=rb$. Commented Jan 12, 2017 at 12:03