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(bx−1,by−1,bz−1,...)=bgcd(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(pm−1,pn−1)=gcd(pn−1,pn−pn−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 pn−pn−m as a remainder. Because there won't exist a quotient otherwise such that pm−1=q(pn−1)+(pn−pn−m). But if there were a quotient, say, pm−n, then (pn−pn−m) wouldn't satisfy the conditions of being a remainder. And if pn−pn−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