Divisibility (gcd) 8

Printable View

December 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$
December 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$
December 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$
December 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$
December 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)