def mygcdprint(a,b):
    r = a%b
    t=1
    while r !=0:
    	  a=b
	  b=r
	  r= a%b
	  t= t+1
	  print "at step ", t
	  print "new (a,b,r)",a,b,r
    return b, t

def myxgcd(a,b):
    r = a%b
    t=1
    M = matrix(2,2,[-a//b , 1, 1,0])
    while r !=0:
    	  a=b
	  b=r
	  r= a%b
	  M= matrix(2,2, [-a//b , 1, 1,0])*M
	  t= t+1
	  print "new (a,b,r)",a,b,r, M
	  print "at step ", t
    return M, b, t

def mygcd(a,b):
    r = a%b
    t=1
    while r !=0:
    	  a=b
	  b=r
	  r= a%b
	  t= t+1
    return b, t

n = 8
for b in [1..7]:
    print b, mygcd(n,b)

def gcdsteps(a,b):
    r = a%b
    t=1
    while r !=0:
    	  a=b
	  b=r
	  r= a%b
	  t= t+1
    return t

n = 8
for b in [1..7]:
   print b, gcdsteps(n,b)


def worstgcd(a):
    b = 1
    t = 1
    for bb in [2..a-1]:
        tt = gcdsteps(a,bb)
        if tt > t:
           b = bb
           t = tt
    return b, t

worstgcd(8)

worstgcd(1234)