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.
No comments:
Post a Comment