Prove that gcd(an−1,am−1)=agcd(n,m)−1

Note  fn:= an−1 = an−m(am−1)+an−m−1, i.e.  fn=fn−m+k fm, k∈Z. Now apply
Theorem Let  fn be an integer sequence with  f0=0 and fn≡fn−m (mod fm)  for n>m.  Then (fn,fm) = f(n,m) where  (i,j)  denotes  gcd(i,j).
Proof   By induction on n+m. The theorem is trivially true if  n=m  or  n=0  or m=0.
So we may assume n>m>0.  Note  (fn,fm)=(fn−m,fm)  follows from the hypothesis.
Since  (n−m)+m < n+m,  induction yields   (fn−m,fm)=f(n−m,m)=f(n,m).
See also this post for a conceptual proof exploiting the innate structure - an order ideal.