# Minimal solution of simultaneous congruences

I would to determine the set of values $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ that minimizes the value of $x$ such that:

$$x\equiv a_1\mod p_1$$ $$\vdots$$ $$x\equiv a_n\mod p_n$$

where every value $a_i$ can assume $m_i<p_i-1$ values fixed a priori in $\lbrace1,\ldots,p_i-1 \rbrace$ (in my case $m_i\sim(p_i-1)/2$ and $p_i$ is the $i_{th}$ prime). Is there a better way than using the Chinese reminder theorem over all the possible combinations of $a_i$? What is the state-of-the-art algorithm for this problem?

Any help or reference would be appreciated. Thanks.

Edit: the possible sets $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ doesn't contain trivial solutions like $\lbrace 1,1,1,\ldots,1 \rbrace$.

Thanks for the answer. I noticed that my question is bad written and i try to explain better here through an example.

In my problem the possible values for every $a_i$ are only a subset of $\lbrace 1,\ldots,p_i-1\rbrace$ (containing $m_i<p_i-1$ different values of $\lbrace 1,\ldots,p_i-1\rbrace$) so no one could decide a priori if $p_{n+1}$ can be represented. For example: $$x\equiv a_1\mod 2,\qquad a_1\in\lbrace1\rbrace$$ $$x\equiv a_2\mod 3,\qquad a_2\in\lbrace1,2\rbrace$$ $$x\equiv a_3\mod 5,\qquad a_3\in\lbrace3,4\rbrace$$ $$x\equiv a_4\mod 7,\qquad a_4\in\lbrace1,6\rbrace$$

has the minimum solution $x=13$ for $a_1=1$, $a_2=1$, $a_3=3$, $a_4=6$. I found this solution through an exhaustive search over the $2^3$ combinations of $a_i$ values and I was wondering if the general case of this problem has been studied in literature and if there was a reference or an algorithm for this purpose.

In particular I faced a problem with about $100$ congruences, and every $a_i$ can take $m_i$ known and fixed values with $m_i\sim (p_i-1)/2$. I know the minimal solution is somewhere near $10^{100}$ but I don't know how to find it.

• What about $x=1$ and $a_i=1$? – joro Nov 19 '15 at 12:31
• Are you perhaps looking for the smallest number that's a "quadratic nonresidue" of each of the first ~100 primes? – Noam D. Elkies Nov 19 '15 at 20:28

Let $A_i$ be the set of allowed values for $a_i$. Then $x$ satisfying the system recurrences represents a zero of the polynomial: $$f(x) = \sum_{i=1}^n \frac{M}{p_i} \prod_{a\in A_i} (x-a)$$ modulo $M$, where $M=p_1p_2\cdots p_n$. Small zeroes of this polynomial modulo $M$ can be found with the Coppersmith method.

UPDATE. For the given example, we have $p_1=2$, $p_2=3$, $p_3=5$, $p_4=7$, and $A_1=\{1\}$, $A_2=\{1,2\}$, $A_3=\{3,4\}$, $A_4=\{1,6\}$. Then $M=2\cdot 3\cdot 5\cdot 7=210$ and $$f(x) = 142\cdot x^2 - 609\cdot x + 719.$$ PARI/GP provides an implementation of the Coppersmith method and can easily find small zeros of $f(x)$ modulo $M$ (I used $\sqrt{M}$ as a bound here):

? zncoppersmith(142*x^2 - 609*x + 719, 210, sqrtint(210))

%1 = [-1, 13]

So $x=-1$ and $x=13$ are the small zeroes (with the absolute value below $\sqrt{210}$) here.

• On pari 2.7.1 this doesn't appear to work if the bound is sufficiently large for large $n$, say $\sqrt{n}$ even if is $n$ is smooth. Does it work for you? (This is unrelated to the question). – joro Nov 19 '15 at 17:25
• @joro: pari documentation on 'zncoppersmith' says that the bound should be smaller than $M^{1/\deg(f)}$ (for the current settings). – Max Alekseyev Nov 19 '15 at 17:29
• Does this work for you (fails for me): n=2^1061-1;zncoppersmith(x^2-1,n,sqrtint(n)-10^8) – joro Nov 19 '15 at 17:40
• @joro: I have no idea why it fails for your code, but using $n^{1/3}$ instead of $n^{1/2}$ seems to fix the problem here: n=2^1061-1;zncoppersmith(x^2-1,n,sqrtnint(n,3)) – Max Alekseyev Nov 19 '15 at 17:45
• Modulo bugs in the algorithm, pari has bugs too IMHO. – joro Nov 19 '15 at 18:22

Not counting "trivial" is not well defined, the solution $x$ is the smallest number $x$, coprime to all $p_i$ (since you exclude zero residue).

This is $p_{n+1}$, which is roughly bounded by $n \log{n} + n(\log \log{n} - 0.9385)$.

So we have $p_{n+1} = a_i \mod p_i$, which gives the $a_i$ after you have found $p_{n+1}$.