Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Prove that if $a>1$ then $(a^n-1,a^m-1)= a^{(m,n)}-1$
where $(a,b) = \gcd(a,b)$
I've seen one proof using the Euclidean algorithm, but I didn't fully understand it because it wasn't very well written. I was thinking something along the lines of have $d= a^{(m,n)} - 1$ and then showing $d|a^m-1$ and $d|a^n-1$ and then if $c|a^m-1$ and $c|a^n-1$, then $c\le d$.
I don't really know how to show this though...
I can't seem to be able to get $d* \mathbb{K} = a^m-1$.
Any help would be beautiful!
We want to prove $\forall n, m :P(n,m)$, where $P(n,m)$ is defined as $(a^n - 1, a^m - 1) = a^{(n,m)} - 1$.
This proof uses a kind of strong induction on $(n,m)$. In other words, it is assumed, outside of base cases, that if $a < n$ and $b < m$, we can assume $P(a,m)$ and $P(n,b)$ in a proof of $P(n,m)$..
Since gcd is symmetric, $P(n,m) \Leftrightarrow P(m,n)$
Base case 1, $m = n$. $(a^m-1, a^n-1) = a^n - 1 = a^{(n,n)} - 1 = a^{(m,n)} - 1$
Base case 2, $m = 0$. $(a^n - 1, a^0 - 1) = (a^n - 1, 0) = a^n - 1 = a^{(n,0)} - 1$.
Base case 3, $n = 0$. same as case 2 by symmetry.
Case 4, $0 < n < m$. Since $y > x \Rightarrow (x,y) = (x, y-x)$, $(a^n - 1, a^m - 1) = (a^n - 1, a^m - a^n) = \left(a^n - 1, a^n(a^{m-n} - 1\right))$ Since $a^n$ and $a^n - 1$ have no factors in common, $(a^n - 1, a^m - 1) = (a^n - 1, a^{m-n} - 1)$.
From induction, $(a^n - 1, a^{m-n} - 1) = a^{(n,m-n)} - 1 = a^{(n,m)} - 1$. So $(a^n - 1, a^m - 1) = a^{(n,m)} - 1$
Case 5, 0 < m < n: Use symmetry and case 4.
Hint $\ $ By below $\rm\,\ a^M\!-\!1,\:a^N\!-\!1\ $ and $\rm\,\ a^{\,(M,N)}\!-\!1\ $ have the same set $\rm\,S\,$ of common divisors $\rm\,d,\, $ therefore they have the same greatest common divisor $\rm\ (= \max\ S).$
$$\begin{eqnarray}\rm\ \ mod\,\ d\!:\ \ a^M,\:a^N\equiv 1&\iff&\rm ord(a)\ |\ M,N\color{#c00}\iff ord(a)\ |\ (M,N)\iff a^{\,(M,N)}\equiv 1\\ \rm i.e.\ \ \ d\ |\ a^M\!-\!1,\:a^N\!-\!1\ &\iff&\rm\ d\ |\ a^{\,(M,N)}\!-\!1,\qquad\ \ \, where \rm\quad\! (M,N)\, :=\, gcd(M,N) \end{eqnarray}$$
Note $\,\ $ Above we used $\ a\mid b,c \color{#c00}\iff a\mid (b,c),\ $ the fundamental universal property of the gcd. Compare $\, a<b,c \!\iff\! a< \min(b,c),\ $ and $\ a\subset b,c\iff a\subset b\cap c.\,$ Exploiting such "iff" definitions allows us to easily simultaneously prove both directions of the eqivalence.
The conceptual structure that lies at the heart of this simple proof is the ubiquitous order ideal. $\ $ See my post here for more on this and the more familiar additive form of a denominator ideal.
More generally $\rm\ gcd(f(m), f(n)) = f(gcd(m,n))\ \ \, if\, \ \ f(n) \equiv f(n\!-\!m)\,\ \ (mod\ f(m)),\, $ and $\rm\, f(0) = 0.\, $ See my post here for a simple inductive proof.
In fact there is a q-analog: the result also holds true for polynomials $\rm \ f(n) = (x^n\!-\!1)/(x\!-\!1),\, $ and $\rm\ x\to 1\ $ yields the integer case (Bezout identity) - see my post here for a simple proof.
