A Curious Question on Modular Arithmetic

In this post, we investigate a curious question: say we are given $b = (a\mod p)$ and $c = (a\mod q)$ , where $p,q$ are primes. Can we calculate $a \mod{pq}$ in terms of just $b$ and $c$ ? (Maybe assuming $p \neq q$ .)

We have $a = pm + b = qn + c$ , so $pm + b = qn + c \rightarrow pm - qn = c - b$ .

Conjecture. If $rx + sy = t$ then $r,s$ are $\frac{t}{\gcd(x,y)}$ times some pair of Bezout coefficients for $x,y$ . (The converse is obvious — if $r,s$ are $\frac{t}{\gcd(x,y)}$ times some pair of Bezout coefficients then $rx + sy = t$ .)

Attempt. Note that it suffices to show the result assuming that $\gcd(x,y) = 1$ : if $\gcd(x,y)$ is not necessarily 1, then calling $\gcd(x,y) = g$ , we know that $t$ must be a multiple of $g$ in order for $rx + sy = t$ to hold. Divide out both sides of the equation by $g$ to yield $rx^{'} + sy^{'} = t^{'}$ where $x^{'} = \frac{x}{g},y^{'} = \frac{y}{g},t^{'} = \frac{t}{g}$ . This means that $\gcd\left( x^{'},y^{'} \right) = 1$ , so we have that $r,s$ are $\frac{t^{'}}{\gcd\left( x^{'},y^{'} \right)} = t^{'}$ times some pair $P$ of Bezout coefficients for $x^{'},y^{'}$ . But this pair is also a pair of Bezout coefficients for $x,y$ (if $rx^{'} + sy^{'} = 1$ then $rx + sy = g\left( rx^{'} + sy^{'} \right) = g$ ), so $r,s$ are $t^{'} = \frac{t}{\gcd(x,y)}$ times some pair of Bezout coefficients for $x,y$ , as desired.

Thus, assume $\gcd(x,y) = 1$ ; we want to show that $r,s$ is $\frac{t}{\gcd(x,y)} = t$ times some pair of Bezout coefficients for $x,y$ . If $\gcd(x,t),\gcd(y,t) > 1$ , then try to show a contradiction or reduction?

Actually, it is possible for $\gcd(x,t),\gcd(y,t) > 1$ but $\gcd(x,y,t) = \gcd(x,y) = 1$ :

$\displaystyle x = 3,y = 2,t = (3)(2)$

Let’s consider this case: $3r + 2s = (3)(2)$ . Must $r,s$ be $6$ times some pair of Bezout coefficients for $(3,2)$ ? We have $\frac{r}{2} + \frac{s}{3} = 1$ . This means that $2|r,3|s$ , so $r = 2k,s = 3l$ , and $k + l = 1$ . Thus, the possibilities are $r = 2k,s = 3 - 3k$ . Conversely, does this always work? We have $3(2k) + 2(3 - 3k) = 6$ . So that always works. Now, is it true that for all pairs $(2k,3 - 3k)$ , that this is 6 times a pair of Bezout coefficients for $(3,2)$ ? No, it’s not: simply take $k = 1$ . Then, the pair is $(2,0)$ , which is not 6 times anything. Or any $k$ that’s not divisible by 3 would work: take $k = 2$ , yielding the pair $(4, - 3)$ , which is definitely not 6 times anything. So my conjecture is false. (It doesn’t have the “lowest possible generation.”) $\blacksquare$

If we can find a formula for $a \mod{pq}$ in terms of $a \mod p$ and $a \mod q$ , then we can use this to calculate $a$ mod any squarefree number. Actually, it seems like we could find a formula with a similar approach for $a \mod{bc}$ in terms of $a \mod b$ and $a \mod c$ if $\gcd(b,c) = 1$ , which then could allow us to calculate $a \mod{p_{1}^{e_{1}}\ldots p_{k}^{e_{k}}}$ in terms of $a \mod{p_{i}^{e_{i}}}$ for each $i$ . If we can somehow (probably separately) calculate $a \mod{p^{k}}$ in terms of $a \mod p$ and $k$ , even for a specific form of $a$ , this would allow us to compute $a \mod{n}$ for all $n$ .

—

EDIT (07/04/2023): We can clearly show this to be impossible with some simple counterexamples, even if $\gcd(a,p) = \gcd(a,q) = 1$ . For example, let $p=2, q=3$ , then consider $a=1, a=3, a=5$ ; from these examples, $a \mod{pq}$ can’t possibly be a function of just $a \mod p$ and $a \mod q$ .

Share and like (need WordPress account to like):

Leave a comment Cancel reply