Let m, n be positive integers and let a be an integer greater than 1. Show that (a^m − 1, a^n − 1) = a^(m,n) − 1.How would I grind through it? Couldn't I use m>n with m=qn+r and then...use GCD / Euclid's Algorithm.. and then..again..then... Created by Unknown. science-mathematics-en - mathematics-en

(a^m − 1, a^n − 1) = a^(m,n) − 1.?

May 2021 3 67 Report

(a^m − 1, a^n − 1) = a^(m,n) − 1.?

Let m, n be positive integers and let a be an integer greater than 1. Show that (a^m − 1, a^n − 1) = a^(m,n) − 1.

How would I grind through it? Couldn't I use m>n with m=qn+r and then...

use GCD / Euclid's Algorithm.. and then..again..then..

let d=(m;n)

m=d*m1 and n=d*n1 with (m1;n1)=1

a^m-1=a^(d*m1)-1=(a^d)^m1-1

a^m-1=(a^d-1)(a^d(m1-1)+ ...+a^d+1) = (a^d-1)*A(n)

same:

a^n-1=(a^d-1)(a^d(n1-1)+ ...+a^d+1)= ( a^d-1)*B(n)

(a^m-1, a^n-1)=(a^d-1)*(A(n) ; B(n))

now it's easy to prove using euclid's algorithm that

(A(n) ; B(n) )=1

we know that a^n - 1 = (a-1) (a^(n-1) + a^(n-2) + ... + 1) (1)

it can be shown that, for (m, n) = 1

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

Now let k = (m,n)

a^m-1 = a^(xk) - 1 = ((a^k)^x-1)

a^n-1 = a^(yk) - 1 = ((a^k)^y-1)

Where (x,y) = 1

Apply (1) and (2) we got the proof.