Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: a number theory problem
Posted:
May 19, 2012 4:58 PM


Recall how we compute gcd: repeatedly subtract multiples of the smaller number from the larger until we reach gcd(g,0)=g. At each step, if n=m*k+p, use gcd(n,m) = gcd(m,p).
Now consider gcd(a^m1,a^n1). Again suppose n=m*k+p. Subtract a multiple of (a^m1) from (a^n1) to get (a^p1), because
(a^m1)*(a^p + a^(p+m) + a^(p+2m) + ... + a^(nm) = a^n  a^p.
(a^n1)  (a^na^p) = (a^p1).
So gcd(a^n1,a^m1) = gcd(a^m1,a^p1).
So we just follow the same steps in parallel: mimicking the steps that compute gcd(n,m)=d to compute gcd(a^n1,a^m1) = a^d1.
Don Coppersmith
> For m and n positive integers and a > 1, why is d = > gcd(a^m  1, a^n  1) = a^(m,n)  1 where (m.n) = > gcd(m,n)? > > It easy to see if tN then a^t  1 divides a^N  1 > (geometrical series), so it follows that a^(m,n)  1 > divides d. But why is it equal to d?



