10*15+13*125, 10*15-27*125

def euclides_gcd(a,b):
    if b > a: # put in increasing order
        t = a; a = b; b = t
    if a == b or a%b == 0: # test equality or null remainder
        return b    
    r = a%b
    print('a =', a, ', b =', b, ', k =', a//b, ', r =', r)
    while r != 0:
        a = b; b = r
        gcd = b
        r = a%b
        print('a =', a, ', b =', b, ', k =', a//b, ', r =', r)
    return b

import math
a = 6825; b = 1430; egcd = euclides_gcd(a,b)
print('euclides_gcd('+str(a)+','+str(b)+')=',egcd, ', python_gcd = ', math.gcd(a,b))

-9*6825 + 43*1430 # ok!

a = 126; p = 23; a%p, (a**p)%p, (a**(p-1))%p 





