System of congruences

Question

I have a system of $n$ congruences.

the generic $m$_th congruence of the system ($m = 1,\dots,n$) is in the form:

$(p_n\#)^2(\displaystyle\sum_{\substack{i=1\\i\neq m}}^n{\frac{x_iy_m}{p_ip_m}}+\sum_{\substack{j=1\\j\neq m}}^n{\frac{x_my_i}{p_jp_m}}+\frac{x_my_m}{p_m^2}-n_2\frac{x_m}{p_m}-n_1\frac{y_m}{p_m})\equiv b_m \:\:\: (mod \:\: p_m^2)$

where:

$p_n\#=\displaystyle\prod_{\substack{i=1}}^np_i$ and $p_i$ is the $i$_th prime number.

$x_i$ and $y_i$ are the unknows while $n_1$ and $n_2$ are known.

for every couple of unknowns $(x_m,y_m)$ $(m=1,\dots,n)$ i know $p_m-1$ couple of values where the solution lies, therefore, in order to avoid nonlinearity, for every congruence of the system i can build a set of $p_m-1$ linear congruences in which the values of $(x_m,y_m)$ are fixed. The problem now is to choose the correct combination of linear congruences (one for each set) in order to build a consistent system. Every congruence of the complete system should be $0\equiv0\:\:(mod\:p_m^2)$ because every time i choose a congruence from the $m$_th set, i choose implicitly the values of the couple of unknowns $(x_m,y_m)$.

I know that there is at least a solution (and i am interested in finding a single solution) but i'm afraid of not being able to do an exaustive search over the linear congruences because the size of the problem is too big (30+ nonlinear congruences resulting in a 30+ set of linear congruences).

Any help would be appreciated. Thanks.

Answer 1

Here is a reduction to a bivariate polynomial equation modulo $p_n\#^2$.

Let $C_m$ denote the set of candidate values for $(x_m,y_m)$.

Set $P:=p_n\#$, $X:=P\sum_{i=1}^n \frac{x_i}{p_i}$, and $Y:=P\sum_{i=1}^n \frac{y_i}{p_i}$. Then the $m$-th congruence takes form: $$P(\frac{y_m}{p_m} X + \frac{x_m}{p_m} Y) - P^2(\frac{x_my_m}{p_m^2} + n_2\frac{x_m}{p_m} + n_1\frac{y_m}{p_m})\equiv b_m\pmod{p_m^2}.$$

From the candidate values for $(x_m,y_m)$, we obtain the following congruence holds: $$f_m(X,Y)\equiv 0\pmod{p_m^2},\qquad(\star)$$ where $$f_m(X,Y) := \prod_{(x_m,y_m)\in C_m} \left[ P(\frac{y_m}{p_m} X + \frac{x_m}{p_m} Y) - P^2(\frac{x_my_m}{p_m^2} + n_2\frac{x_m}{p_m} + n_1\frac{y_m}{p_m}) - b_m\right].$$

Clearly, $\deg f_m \leq p_m-1$. Then, we combine congruences $(\star)$ into a single one: $$F(X,Y) \equiv 0\pmod{P^2},$$ where $$F(X,Y) := \sum_{m=1}^n \frac{P^2}{p_m^2} f_m(X,Y).$$

If we solve the resulting congruence for $(X,Y)$, then from $X\equiv \frac{P}{p_m}x_m\pmod{p_m}$ and $Y\equiv \frac{P}{p_m}y_m\pmod{p_m}$ we can find a suitable pair $(x_m,y_m)$ from $C_m$ for each $m$, and then verify that they altogether deliver a solution (as they may be extraneous ones).