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
    tb = b 
    a = b
    b = ta-(ta/b)*b
    if b == 0:
        print '('+FirstA+','+FirstB+')='+str(a)
        print 'x='+str(x2)+' y='+str(y2)
        break         
 
    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*(ta/tb)
    y2 = ty - y2*(ta/tb)
 
 

cHJpbnQgJ1dlIHdpbGwgZmluZCBhIChhLGIpIGFuZCB4LHkgd2hpY2ggYSp4ICsgYip5ID0gKGEsYiknCmEgPSBpbnQocmF3X2lucHV0KCdFbnRlciBhIGludGVnZXIgbnVtYmVyIGE6ICcpKQpiID0gaW50KHJhd19pbnB1dCgnRW50ZXIgYSBpbnRlZ2VyIG51bWJlciBiOiAnKSkKRmlyc3RBID0gc3RyKGEpICMgV2UgaGF2ZSB0byByZW1lbWJlciBmaXJzdCB2YWx1ZXMgb2YgYSBhbmQgYgpGaXJzdEIgPSBzdHIoYikKeDEgPSAxICMgU3RhcnQgZm9yIGFsZ29yaXRobQp5MSA9IDAKeDIgPSAwCnkyID0gMQoKd2hpbGUgVHJ1ZToKICAgIHRhID0gYQogICAgdGIgPSBiIAogICAgYSA9IGIKICAgIGIgPSB0YS0odGEvYikqYgogICAgaWYgYiA9PSAwOgogICAgICAgIHByaW50ICcoJytGaXJzdEErJywnK0ZpcnN0QisnKT0nK3N0cihhKQogICAgICAgIHByaW50ICd4PScrc3RyKHgyKSsnIHk9JytzdHIoeTIpCiAgICAgICAgYnJlYWsgICAgICAgICAKICAgIAogICAgdHggPSB4MSAjV2UgaGF2ZSB0byByZW1lbWJlciB4MSx5MSB0byBjYWxjdWxhdGUgeDIgYW5kIHkyLCBpZiB3ZSBkaWRuJ3QgaXQKICAgIHR5ID0geTEgI3RoZW4gd2UgY291bGRuJ3QgZG8gaXQKICAgIHgxID0geDIKICAgIHkxID0geTIKICAgIHgyID0gdHggLSB4MioodGEvdGIpCiAgICB5MiA9IHR5IC0geTIqKHRhL3RiKQoKICAgICAgICA=