print 'We will find a (a,b) and x,y which a*x + b*y = (a,b)'
a = int(raw_input('Enter a integer number a: '))
b = int(raw_input('Enter a integer number b: '))
FirstA = str(a) # We have to remember first values of a and b
FirstB = str(b)
x1 = 1 # Start for algorithm
y1 = 0
x2 = 0
y2 = 1
 
while True:
    ta = a 
    a = b
    b = ta-(ta/b)*b
    if b == 0:
        print '('+FirstA+','+FirstB+')='+str(a)
        print 'x='+str(x2)+' y='+str(y2)
        break         
    print a,b
    tx = x1 #We have to remember x1,y1 to calculate x2 and y2, if we didn't it
    ty = y1 #then we couldn't do it
    x1 = x2
    y1 = y2
    x2 = tx - x2*(a/b)
    y2 = ty - y2*(a/b)
 
 

cHJpbnQgJ1dlIHdpbGwgZmluZCBhIChhLGIpIGFuZCB4LHkgd2hpY2ggYSp4ICsgYip5ID0gKGEsYiknCmEgPSBpbnQocmF3X2lucHV0KCdFbnRlciBhIGludGVnZXIgbnVtYmVyIGE6ICcpKQpiID0gaW50KHJhd19pbnB1dCgnRW50ZXIgYSBpbnRlZ2VyIG51bWJlciBiOiAnKSkKRmlyc3RBID0gc3RyKGEpICMgV2UgaGF2ZSB0byByZW1lbWJlciBmaXJzdCB2YWx1ZXMgb2YgYSBhbmQgYgpGaXJzdEIgPSBzdHIoYikKeDEgPSAxICMgU3RhcnQgZm9yIGFsZ29yaXRobQp5MSA9IDAKeDIgPSAwCnkyID0gMQoKd2hpbGUgVHJ1ZToKICAgIHRhID0gYSAKICAgIGEgPSBiCiAgICBiID0gdGEtKHRhL2IpKmIKICAgIGlmIGIgPT0gMDoKICAgICAgICBwcmludCAnKCcrRmlyc3RBKycsJytGaXJzdEIrJyk9JytzdHIoYSkKICAgICAgICBwcmludCAneD0nK3N0cih4MikrJyB5PScrc3RyKHkyKQogICAgICAgIGJyZWFrICAgICAgICAgCiAgICBwcmludCBhLGIKICAgIHR4ID0geDEgI1dlIGhhdmUgdG8gcmVtZW1iZXIgeDEseTEgdG8gY2FsY3VsYXRlIHgyIGFuZCB5MiwgaWYgd2UgZGlkbid0IGl0CiAgICB0eSA9IHkxICN0aGVuIHdlIGNvdWxkbid0IGRvIGl0CiAgICB4MSA9IHgyCiAgICB5MSA9IHkyCiAgICB4MiA9IHR4IC0geDIqKGEvYikKICAgIHkyID0gdHkgLSB5MiooYS9iKQoKICAgICAgICA=