title: System of congruences with non-pairwise coprime moduli
body: <p>I have a set of congruences</p>
  
  <pre><code>x = a1 (mod n)
  ...
  x = ak (mod nk)
  </code></pre>
  
  <p>And I want to find <code>x</code>, this can be solved by the Chinese remainder theorem and related algorithms: <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Chinese_remainder_theorem</a></p>
  
  <p>Some examples: <a href="https://rosettacode.org/wiki/Chinese_remainder_theorem" rel="nofollow noreferrer">https://rosettacode.org/wiki/Chinese_remainder_theorem</a></p>
  
  <p>For this particular example:</p>
  
  <pre><code>x = 1031 (mod 1473)
  x = 1141 (mod 1234)
  x = 50   (mod 1827)
  </code></pre>
  
  <p>All the algorithms that I have tried won't work, since the moduli are not pairwise coprime.
  However, <code>1024360583</code> is a valid solution:</p>
  
  <pre><code>1024360583 % 1473 == 1031
  1024360583 % 1234 == 1141
  1024360583 % 1827 == 50
  </code></pre>
  
  <p>What algorithm could find such a solution ?</p>
  
  <p>I have also implemented Garner's Algorithm from the Handbook of Cryptography: it didn't solve that example.</p>