getReversedT.js

/**
 * Code snippet for students ^^
 * Tarnavsky used this function to find t^-1 from prime number t and m.
 * Usage: var tMinusOne = getRevT(m, t);
 * Test case 1: getRevT(121, 5) === 97
 * Test case 2: getRevT(9, 7) === 13
 */
function getRevT (m, t) {
    function stage (a, b) {
        var r = a % b, q = Math.floor(a/b);
        return r === 0 ? [] : [q].concat(stage(b, r));
    }
    function backStage (arr, x, y) {
        if (!arr.length) return y;
        var z = x - y * arr.pop();
        return backStage(arr, y, z);
    }
    return m + backStage(stage(m, t), 0, 1);
}