# 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 of congruences represents a zero of the following polynomial modulo $$M$$: $$f(x) := \sum_{i=1}^n \frac{M}{p_i} \prod_{a\in A_i} (x-a),$$ 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(142x^2 - 609x + 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}$.