# Divisibility (gcd) 8

• Dec 19th 2008, 01:03 AM
Sea
Divisibility (gcd) 8
Show that: $m,n ,a \in \mathbf{Z^{+}}$ and $a>1$

$\Rightarrow (a^{m}-1 , a^{n}-1)=a^{(m,n)}-1$
• Dec 19th 2008, 01:40 AM
Isomorphism
Let $(m,n) = d$ and $(a^m - 1, a^n -1) = l$

$d|m \Rightarrow a^d - 1 | a^m - 1$

$d|n \Rightarrow a^d - 1 | a^n - 1$

Thus $a^d - 1 | l$. -----------------(1)

By Bezout's identity we know that there exists non negative integers x and y such that $mx = ny + d$.

$(a^m - 1, a^n -1) = l \Rightarrow l| a^m - 1 \Rightarrow l| a^{mx} - 1$

But $a^{mx} - 1 = (a^{ny} - 1)a^d + a^d - 1$

Thus $l| a^{mx} - 1 \Rightarrow l|a^d - 1$ -------------(2)

(1) and (2) imply $l = a^d -1$
• Dec 19th 2008, 02:17 AM
Sea
I don't know...

$d|m$ (Why?) $\Rightarrow a^d - 1 | a^m - 1
$

$d|n$ (Why?) $\Rightarrow a^d - 1 | a^n - 1$
• Dec 19th 2008, 02:29 AM
Moo
Hello,
Quote:

Originally Posted by Sea
I don't know...

$d|m$ (Why?) $\Rightarrow a^d - 1 | a^m - 1
$

$d|n$ (Why?) $\Rightarrow a^d - 1 | a^n - 1$

Consider the geometric series of $a^d$ :
$\sum_{k=0}^{m/d} (a^d)^k=\sum_{k=0}^{m/d} a^{dk}=\frac{a^m-1}{a^d-1}$
(m/d is an integer since d|m)

The LHS is an integer, so the RHS has to be an integer. Hence $a^d-1$ divides $a^m-1$
• Dec 19th 2008, 03:53 AM
PaulRS
A slightly different way.

We have $
\left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^n - 1} \right)} \right. \wedge \left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^m - 1} \right)} \right.
$
(as Moo points out) thus $
\left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^n - 1,a^m - 1} \right)} \right.
$
(1)

Now let $q$ be a common divisor of $a^n-1$ and $a^m-1$ i.e. $
a^n \equiv 1\left( {\bmod .q} \right) \wedge a^m \equiv 1\left( {\bmod .q} \right)
$

From the first congruence we get $
\left. {{\text{ord}}_q \left( a \right)} \right|n
$
and from the second $
\left. {{\text{ord}}_q \left( a \right)} \right|m
$
thus it must be that $
\left. {{\text{ord}}_q \left( a \right)} \right|\left( {n,m} \right)
$
hence $
a^{\left( {n,m} \right)} \equiv 1\left( {\bmod .q} \right)
$

So every common divisor divides $
a^{\left( {n,m} \right)} - 1
$
and by (1) we are done (because it's the greatest possible)