1. ## 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$

2. 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$

3. 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$

4. Hello,
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$

5. 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)