3
$\begingroup$

I have encountered a problem in my research that requires solving two coupled modular equations for integers x,y for general integral coefficients. As someone without much experience in discrete math, I am not sure the best way to tackle this problem, and not sure the best way to phrase the general solution. The equations are as follows:

$nx + my \equiv 0 \mod p \\ mx - ny \equiv 0 \mod q \\ gcd(p,q) = 1 \\ m,n,x,y \in \mathbb{Z}$

It seems to me that the solution (x,y) will be phrased in terms of new, integral degrees of freedom (as in x,y will only be defined modulo some quantity, maybe pq). But I am not sure exactly how to write this. The other complication is that there are in theory no restrictions that I can find on $m,n$ with respect to $p,q$. I considered something along the lines of the Chinese remainder theorem, but that seems only to apply when $n,m < p,q$, unless I am mistaken. Coprimality of the $p,q$ seems to be relevant but I am unsure the way to best use this fact.

I tried rewriting these as:

$nx + my = pl \\ mx - ny = qk \\ l,k \in \mathbb{Z}$

But it is not clear to me how to solve for x,y without appealing to division.

I should also state that $x = y = 0$ is too trivial to be interesting in this context, as is $n = m = 0$.

I would like to write down something like: $ x = pn + q(m+l) \ \ \forall n,m,l \in \mathbb{Z}$, or something similar. Any tips from those more experienced solving this would be greatly appreciated, or directions on theorems or references that may apply to the solution of the problem.

EDIT: /u/functor7 from reddit supplied the following:

"We'll assume that m,n are both not divisible by p and q. In this case, both m and n have multiplicative inverses mod p and mod q. Set y equal to literally anything, we can then move everything except x to one side to get something like

x = A mod p

x = B mod q

The Chinese Remainder Theorem then says that there is a solution to this system."

This seems to answer the question to a good degree. I will edit again in the morning with an update.

$\endgroup$
  • $\begingroup$ I attempted subtract and regroup, got me to $(m+n)(x-y)=rk\bmod p$, r being q's remainder on division by p. $\endgroup$ – Roddy MacPhee Apr 3 at 11:36
1
$\begingroup$

You want to solve

$$nx + my \equiv 0 \pmod p \tag{1}\label{eq1}$$ $$mx - ny \equiv 0 \pmod q \tag{2}\label{eq2}$$ $$\gcd(p,q) = 1 \tag{3}\label{eq3}$$

First, given \eqref{eq3}, Bézout's identity says there exists integers $a$ and $b$ such that

$$ap + bq = 1 \tag{4}\label{eq4}$$

There are usually many solutions. I will start by showing how to solve it for general values of $x$ and $y$ modulo $p$ and $q$. For \eqref{eq1}, let

$$x \equiv x_1 \pmod p \; \; \text{ and } \; \; y \equiv y_1 \pmod p \tag{5}\label{eq5}$$

be a solution. For \eqref{eq2}, let

$$x \equiv x_2 \pmod q \; \; \text{ and } \; \; y \equiv y_2 \pmod q \tag{6}\label{eq6}$$

be a solution. The $x$ values in \eqref{eq5} and \eqref{eq6} mean that there exists integers $c$ and $d$ such that

$$x = cp + x_1 = dq + x_2 \; \Rightarrow \; cp - dq = x_2 - x_1 \tag{7}\label{eq7}$$

Multiplying both sides of \eqref{eq3} by $x_2 - x_1$ gives

$$a(x_2 - x_1)p + b(x_2 - x_1)q = x_2 - x_1 \tag{8}\label{eq8}$$

Comparing the multipliers of $p$ and $q$ with \eqref{eq7} shows that

$$c = a(x_2 - x_1) \; \; \text{ and } \; \; d = -b(x_2 - x_1) \tag{9}\label{eq9}$$

Using $c$ and $d$ in \eqref{eq7} gives

$$x = a(x_2 - x_1)p + x_1 = -b(x_2 - x_1)q + x_2 \tag{10}\label{eq10}$$

The general solution is, for specific values of $a$ and $b$, the value in \eqref{eq10} plus $kpq$ for all $k \in \mathbb{Z}$. You can use a similar procedure to determine the $y$ values to be

$$y = a(y_2 - y_1)p + y_1 = -b(y_2 - y_1)q + y_2 \tag{11}\label{eq11}$$

plus $kpq$ for all $k \in \mathbb{Z}$. A specific solution is $x_1 = -m$, $y_1 = n$, $x_2 = n$ and $y_2 = m$. In this case, \eqref{eq10} becomes

$$x = a(n + m)p - m = -b(n + m)q + n \tag{12}\label{eq12}$$

and \eqref{eq11} becomes

$$y = a(m - n)p + n = -b(m - n)q + m \tag{13}\label{eq13}$$

More generally, if $m$ and $n$ are both relatively prime to $p$ and $q$, they will each have a multiplicative inverse modulo $p$ and $q$, so you could choose a value for one variable, e.g., $x$, and solve it for the other, e.g., $y$, in \eqref{eq1} and \eqref{eq2}. However, if $m$ and $n$ are not both relatively prime to $p$ and $q$, there may be some cases where there are no solutions for certain values of one variable. For example, if $\gcd(n,p) = 1$ and $\gcd(m,p) = e$ for some $e \gt 1$, then only $x$ which are multiples of $e$ can work in \eqref{eq1}.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.