# How does the Euclidean Algorithm apply on exponents m and n to show that $gcd(p^m-1, p^n-1) = p^{gcd(m,n)}-1$

No, this is not a duplicate of any thread. In fact, it is about a thread that I am still struggling to understand after all this time. I cannot comment on the thread because it was posted a very long time ago and it's extremely unlikely that anyone is going to see it. So this is why I am making a new thread about it.

$\gcd(b^x - 1, b^y - 1, b^ z- 1,...) = b^{\gcd(x, y, z,...)} -1$

In Qiaochu Yuqn's response on the thread, he says you can apply the Euclidean Algorithm on the exponents m and n to show that $$gcd(p^m - 1, p^n-1) = gcd (p^n-1, p^n - p^{n-m})$$. The part I don't get though is how that came to be. I thought for the Euclidean Algorithm, you had to have a remainder r such that if a = bq + r where gcd(a,b) = gcd(b,r), then r is greater than or equal to 0 but less than b. What I'm struggling to understand is how he ended up getting $$p^n-p^{n-m}$$ as a remainder. Because there won't exist a quotient otherwise such that $$p^m-1=q(p^n-1) + (p^n - p^{n-m})$$. But if there were a quotient, say, $$p^{m-n}$$, then $$(p^n - p^{n-m})$$ wouldn't satisfy the conditions of being a remainder. And if $$p^n-p^{n-m}$$ isn't supposed to be a remainder, then it's not really using the Euclidean Algorithm, is it?

I appreciate any clarification on this. Thank you in advance.

• Induction?..... – MATHS MOD Mar 14 at 3:51

This is one step of the justification of applying the Euclidean algorithm to the exponent. This step works because $$\gcd(p^n-1, p^{n-m}) =1$$ (since prime factors of $$p$$ cannot divide $$p^n-1$$) and $$p^n-p^{n-m} =p^{n-m} (p^m-1)$$:

Suppose $$d$$ is a common factor of $$p^n-1$$ and $$p^n-p^{n-m}=p^{n-m} (p^m-1)$$.

Then since $$p^n-1$$ and $$p^{n-m}$$ are relatively prime, so are $$d$$ and $$p^{n-m}$$. Since $$d$$ divides $$p^n-p^{n-m}$$, it must divide $$p^m-1$$. Hence, $$d$$ is a common fatcor of $$p^n-1$$ and $$p^m-1$$. The equality of the gcd then follows.

• I'm not really sure how you arrived at the conclusion that $gcd(p^n-1,p^{n-m}-1)=1$ and why it matters. – Tim Mar 14 at 4:08
• I added some explanations. Hope that helps. – Poon Levi Mar 15 at 16:47

Here's a basic explanation using base 3 as an example:$$3^n-1=\underbrace{222\ldots2}_\text{n times}$$ and likewise:$$3^m-1=\underbrace{222\ldots2}_\text{m times}$$

Subtracting the two we get:$$(3^n-1)-(3^m-1)=\underbrace{222\ldots2}_\text{n-m times}\underbrace{000\ldots0}_\text{m times}$$ Subtraction of multiples of $$3^m-1$$ with multipliers of $$3^y$$ where y is a multiple of m, takes the number of 0's up by a multiple of m. Which also, takes the number of 2's down by a multiple of m.This leads eventually takes us to: $$\underbrace{222\ldots2}_{n \bmod m\text{ times}}\underbrace{000\ldots0}_{\lfloor\frac{n}{m}\rfloor\text{ times}}$$ or:

$$(3^{n \bmod m}-1)(3^{m\lfloor\frac{n}{m}\rfloor})$$ which is then $$(3^{n \bmod m}-1)\bmod m$$ repeating with m and $$n\bmod m$$ we subtract multiples of the exponents just like we do in normal Euclidean GCD for numbers. This takes the gcd of the exponents as the final non-zero power.