# Divisibility (gcd) 8

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

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

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

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

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

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

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

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

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

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

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

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

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

Consider the geometric series of $\displaystyle a^d$ :
$\displaystyle \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 $\displaystyle a^d-1$ divides $\displaystyle a^m-1$
• Dec 19th 2008, 03:53 AM
PaulRS
A slightly different way.

We have $\displaystyle \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 $\displaystyle \left( {a^{\left( {m,n} \right)} - 1} \right)\left| {\left( {a^n - 1,a^m - 1} \right)} \right.$ (1)

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

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

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