# CRT on prime vector

I have a question that intrigue me:

Given primes and some reminder vector

P=primes(13)=[2 3 5 7 11 13]

R=[1 2 1 3 9 11]  (R=mod(1571,P))


What option do i have to reconstruct 1571 from R?

Is there any other way? (assumming that direct brute force search is not practical)

• Why doesn't CRT suffice? – Bill Dubuque Aug 9 at 19:07
• It suffice and works well, but it is little involved – Mendi Barel Aug 9 at 19:13
• We want to find x. So we know $x \equiv 11 \pmod {13}$ Then $x = 13k + 11$ for some $k$. Plug this in into the equation $x \equiv 9 \pmod {11}$ to get $13 k + 11 \equiv 9 \pmod{11}$ $13k \equiv -2 \equiv 9 \pmod{11} \Rightarrow 2k \equiv 9 \pmod{11} \Rightarrow k \equiv 10 \pmod{11}$. So $x$ is now $13(11p + 10) + 11$ for some integer $p$. Now plug this into another equation and keep going until you get $x = 1571 + 30030 * q$  for any integer $q$ – Francisco José Letterio Aug 9 at 19:18
• Probably because you don't know optimizations. Are you solving them all-at-once or stepwise, two-at-a-time (e.g.in prior comment). – Bill Dubuque Aug 9 at 19:20
• we can use that it's odd, to sieve a lot out. but that's mostly CRT. – Roddy MacPhee Aug 9 at 19:32

It's easy if you solve them stepwise - two-at-a-time.

$$x\equiv -2\, \bmod 11\, \&\, 13 \iff x\equiv -2\pmod{\!143}\$$ by CCRT = Constant case CRT. Similarly

$$\ x \equiv\ 1\,\bmod\ 2\ \, \&\ \ 5\ \iff\, x\ \equiv\ 1\ \pmod{\!10}.\$$ Solving them pairwise we obtain:

$$\!\!\bmod \color{#c00}{10}\!:\,\ 1\equiv x\equiv -2+143\,\color{#c00}i\equiv -2+3i\iff 3i\equiv 3\iff \color{#c00}{i\equiv 1}$$

Therefore $$\ x = -2+143(\color{#c00}{1\!+\!10j}) = \color{#0a0}{141 + 1430j}$$

$$\!\!\bmod 7\!:\,\ 3\equiv x\equiv\color{#0a0}{ 1+2j}\iff 2j\equiv 2\iff j\equiv 1$$

Therefore $$\,x \equiv 141+1430(1\!+\!7k) = \color{#90f}{1571 + 10010k}$$

$$\!\!\bmod 3\!:\,\ 2\equiv x\equiv\color{#90f}{ 2+2k}\iff k = 0\iff k =3n$$

Therefore $$\,x \equiv 1571+ 30030n.\,$$ Just a couple minutes mental arithmetic (with practice).

• Can you write function in matlab that solve the problem for any R length and value? Input should be R only. first line should be P=primes(length(R)). – Mendi Barel Aug 9 at 20:35
• @MendiBarel Yes, that could be done (I implemented something similar in Macsyma long ago). – Bill Dubuque Aug 9 at 20:41