Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: a number theory problem
Replies: 1   Last Post: May 19, 2012 4:58 PM

 Messages: [ Previous | Next ]
 Don Coppersmith Posts: 60 Registered: 2/2/06
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^m-1,a^n-1). Again suppose
n=m*k+p. Subtract a multiple of (a^m-1) from
(a^n-1) to get (a^p-1), because

(a^m-1)*(a^p + a^(p+m) + a^(p+2m) + ... + a^(n-m)
= a^n - a^p.

(a^n-1) - (a^n-a^p) = (a^p-1).

So gcd(a^n-1,a^m-1) = gcd(a^m-1,a^p-1).

So we just follow the same steps in parallel:
mimicking the steps that compute gcd(n,m)=d
to compute gcd(a^n-1,a^m-1) = a^d-1.

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 t|N 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?

Date Subject Author
5/18/12 Kent Holing
5/19/12 Don Coppersmith