solution_comparison/euler.py

import sys, re

def gcd(a, b):
    while b != 0:
        b, a = a % b, b
    return a

def euler(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

def solve(task):
    f = re.fullmatch(r'(\d+)x=(\d+)mod(\d+)', task)
    if f == None:
        return "Usage Example: py euler.py '7x=8mod13'"
    a, b, m = int(f.groups()[0]), int(f.groups()[1]), int(f.groups()[2]) 
    d = gcd(a, m)
    if d > 1 and b % d != 0:
        return 'No solutions'
    a1, b1, m1 = a // d, b // d, m // d
    x0 = (b1 * pow(a1, euler(m1) - 1, m1)) % m1
    s=''
    for i in range(d):
        s += f'x={(x0+m//d*i)%m}mod{m}\n'
    return s[:-1]

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print("Usage Example: py euler.py '7x=8mod13'")
        sys.exit(1)
    print(solve(sys.argv[1]))