Eucledian Algorithm for Linear Congruence (Lua version)

function Reverse (arr)
    local i, j = 1, #arr

    while i < j do
        arr[i], arr[j] = arr[j], arr[i]

        i = i + 1
        j = j - 1
    end
end

-- your code goes here
function FindGreatestCommonDivisor(a,b)
    local tmp = { }
    tmp[1] = { }
    tmp[1].a = a
    tmp[1].b = b
    tmp[1].a_per_b = math.floor(a/b)
    local i = 2
    --local exit_signal = false
    repeat
        tmp[i] = { }
        tmp[i].a = tmp[i-1].b
        tmp[i].b = tmp[i-1].a % tmp[i-1].b
        if tmp[i].b == 0 then tmp[i].a_per_b = 1 else
        tmp[i].a_per_b = math.floor(tmp[i].a / tmp[i].b) end
        i = i + 1
    until tmp[i-1].b == 0
    local gcd = tmp[i-1].a
    return tmp, gcd
end

function Eucledian(a,b)
    local tmp,gcd = FindGreatestCommonDivisor(a,b)
    Reverse(tmp)
    for k,v in pairs(tmp) do
        if k == 1 then
            tmp[k].x = gcd
            tmp[k].y = 0
        else
            tmp[k].x = tmp[k-1].y
            tmp[k].y = tmp[k-1].x - (tmp[k-1].y * tmp[k].a_per_b)
        end
    end
    Reverse(tmp)
    return tmp,gcd
end

function LinearCongruence(x,modulo,divisor)
    local tmp,gcd = Eucledian(divisor,x)
    if modulo % gcd ~= 0 then
        return false -- Unsolvable
    else
        local side_1 = ((tmp[1].a * tmp[1].x) + (tmp[1].b * tmp[1].y)) / gcd
        local side_2 = divisor - modulo
        return true, math.abs((side_2 / side_1) * (tmp[1].y / gcd)), tmp
    end
end

passable,final_solution,tempe = LinearCongruence(125,1210,2070)
for k,v in pairs(tempe) do
    print(v.a .. "\t" .. v.b .. "\t" .. v.a_per_b .. "\t" .. v.x .. "\t" .. v.y)
end
print("Final solution for X: " .. final_solution)