Modular Congruence Solver

Takes multiple modular congruences and turns them into a single modular congruence.

by wio_dude

HTML

<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&amp;dummy=.js"></script>
<script type="text/x-mathjax-config"> MathJax.Hub.Config({   tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); </script>

<div id="output"></div>

JavaScript

/*
 *    Modular congruence
 *
 *    solution_range:
 *    format  [a, b]
 *    where   a <= x <= b
 *    modeqs:
 *    format  [r, q]
 *    where   x = r (mod q)
 */
var solution_range = [10, 200];
var modeqs = [
    [2, 3],
    [3, 5],
    [2, 7]
];


var output = document.getElementById('output');
function print(i) {
    output.innerHTML += i;
}
function println(i) {
    print(i + '<br />');
}

modularCongruence(modeqs, solution_range);

function modularCongruence(modeqs, solution_range) {
    var N_i = [];
    var x_i = [];
    var N = 1;
    
    for (var i = 0; i < modeqs.length; i++) {
        var r = modeqs[i][0];
        var q = modeqs[i][1];
        N *= q;
    }
    for (var i = 0; i < modeqs.length; i++) {
        var r = modeqs[i][0];
        var q = modeqs[i][1];
        N_i[i] = N / q;
        var a = N_i[i] % q;
        var k = 0;
        while ((k * q + r) % a != 0) {
            k++;
        }
        x_i[i] = (k * q + r) / a;
    }
    var Nx = 0;
    for (var i = 0; i < modeqs.length; i++) {
        Nx += N_i[i] * x_i[i];
    }
    
    var x = Nx % N;
    
    var solutions = [];
    
    var min = solution_range[0];
    var max = solution_range[1];
    
    var min_n = Math.ceil((min - x) / N);
    var max_n = Math.floor((max - x) / N);
    for (var n = min_n; n <= max_n; n++) {
        solutions.push(x + N * n);   
    }
    
    
    print('Problem');
    print('\\begin{array}{rcl}');
    for (var i = 0; i < modeqs.length; i++) {
        var r = modeqs[i][0];
        var q = modeqs[i][1];
        print('x &\\equiv& ' + r + ' \\pmod ' + q + '\\\\');
    }
    print('\\end{array}');
    
    print('General Solution');
    print('$$x \\equiv ' + x + ' \\pmod{' + N + '}$$');
    
    print('Solutions where ');
    print('\\\(' + min + '\\leq x \\leq ' + max + '\\\)');
    print('$$X = \\{' + solutions.join(',') + '\\}$$');
    
    
    print('Info');
    print('\\begin{array}{rcl}');
    print('N &=& ' + N + '\\\\');
    print('\\\\');
   ...