gcd(a^m - 1, a^n - 1) (m > n)

if m = p*n + r
then 
   a^m - 1 = a^(p*n+r) - a^r + a^r - 1
           = a^r(a^(p*n)-1) + (a^r-1)

   since (a^n-1) | (a^(p*n)-1)

gcd(a^m - 1, a^n - 1) = gcd(a^r - 1, a^n-1)

so  gcd(a^m - 1, a^n - 1) = a^gcd(m,n) - 1

so ......

• prove it like this (320) achilles 2005-08-08 19:51:37
  • Re:prove it like this (691) gemenhao 2006-04-07 14:48:19
  • good prove (0) hello__world 2009-02-11 15:18:17