0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Induction?..... $\endgroup$ – MATHS MOD Mar 14 at 3:51
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tim Mar 14 at 4:08
  • $\begingroup$ I added some explanations. Hope that helps. $\endgroup$ – Poon Levi Mar 15 at 16:47
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.