(32SII) Solving a Single Congruence Equation for the HP 32Sii

[Albert Chan]

This version handle cases when a (mod n) has no inverse

Code:

def LC(a,b,n):
    'if a x = b (mod n), solve for x'
    p, q, m = 0, 1, n
    while a != 0:
        d = n // a
        p, q = q, p-d*q
        n, a = a, n-d*a
    d = b // n
    m = abs(m//n)
    return (p * d % m, m) if b == d*n else ()

>>> LC(5, 3, 17)        # 1 solution
(4, 17)
>>> LC(123,320,777) # no solution
()
>>> LC(123,321,777) # 3 solutions (mod 777)
(110, 259)
>>> [ 123*x % 777 for x in range(110,777,259)]
[321, 321, 321]