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

Note  fn:= an1 = anm(am1)+anm1, i.e.  fn=fnm+k fm, kZ. Now apply
Theorem Let  fn be an integer sequence with  f0=0 and fnfnm (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)=(fnm,fm)  follows from the hypothesis.
Since  (nm)+m < n+m,  induction yields   (fnm,fm)=f(nm,m)=f(n,m).
See also this post for a conceptual proof exploiting the innate structure - an order ideal.


Post a Comment

Don't Forget to comment

About Me

My photo

HI i am mohammed  a Embedded Software Developer ,SEO specialist,Electronic engineer   Read more