3
$\begingroup$

If $\gcd(a,b)=1$, is it true that $$\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}\;?$$

I know that $a^{\gcd(x,y)}-b^{\gcd(x,y)}\mid a^x-b^x$ and $a^{\gcd(x,y)}-b^{\gcd(x,y)}|a^y-b^y$, so I thought of something like let $n$ be a divisor of $a^x-b^x$ and $a^y-b^y$, then $n$ must also be a divisor of $a^{\gcd(x,y)}-b^{\gcd(x,y)}$ but I am stuck.

Improve this question
$\endgroup$
  • $\begingroup$ See math.stackexchange.com/questions/7473/… $\endgroup$ – lab bhattacharjee Apr 2 '15 at 18:40
  • $\begingroup$ I already know this result, I am looking for a generalization. $\endgroup$ – steedsnisps Apr 2 '15 at 18:43
  • $\begingroup$ It clearly fails for $b = 0$, at least. $\endgroup$ – anomaly Apr 2 '15 at 18:54
  • $\begingroup$ and you can see also that $gcd(a,b)^{\min(x,y)}$ divides both of the terms, and does not divide $a^{gcd(x,y)}-b^{gcd(x,y)}$ so as a conclusion the main equation is not correct $\endgroup$ – Elaqqad Apr 2 '15 at 18:55
  • $\begingroup$ Notice the proper use of \gcd and \mid in my edit. Both result in proper spacing. Notice the difference between $a|b$ and $a\mid b$; the latter uses \mid. And in $a\gcd(b,c)$, if I had written a gcd(b,c) instead of a\gcd(b,c), then you would have seen $a gcd(b,c)$ instead of $a\gcd(b,c)$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Apr 2 '15 at 19:10
2
$\begingroup$

$\ (a,b)=1\Rightarrow (b,a^n\!-b^n) = (b,a^n) = 1$ so $\,\color{#c00}{b\ {\rm is\ coprime}}$ to $\,a^x\!-b^x,\,a^y\!-b^y\,$ so coprime to any common divisor $\,d.\,$ So $\,{\rm mod}\ d\!:\, c = a/b = a\color{#c00}{b^{-1}\rm\ exists}$, so $\,a^n\equiv b^n\!\!\iff\! c^n =(a/b)^n\!\equiv 1\,$ so

$$c^x\equiv 1\equiv c^y\iff {\rm ord}\, c\mid x,y\iff {\rm ord}\, c\mid(x,y)=:g\iff c^g\equiv 1\quad {\bf QED}$$

Improve this answer
$\endgroup$
  • $\begingroup$ What's ord $c$? Do you mean $c^n \equiv 1$ mod $d$? With $(a/b)^n$ do you mean $a^n*(b^{-1})^n$? $\endgroup$ – steedsnisps Apr 6 '15 at 19:36
  • $\begingroup$ @wow $\ {\rm ord}\, c\,$ is the least $\,k>0\,$ such that $\,c^k\equiv 1.\,$ Then $\, c^n\equiv 1\iff {\rm ord}\, c\mid n.\ $ $\ c := a/b = ab^{-1}\ \ $ $\endgroup$ – Bill Dubuque Apr 6 '15 at 19:56
  • $\begingroup$ Ok and you are working mod $d$? $\endgroup$ – steedsnisps Apr 6 '15 at 19:59
  • $\begingroup$ @wow yes, all congruences are mod $\,d,\,$ where $\,d\,$ is any common divisor of $\,a^x-b^x,\, a^y-b^y.\ $ I edited the answer clarify it a bit. Please feel welcome to ask further questions. $\endgroup$ – Bill Dubuque Apr 6 '15 at 20:09
  • $\begingroup$ Ok thank you it is fully clear now. Can you look at my answer and tell me if it is correct? $\endgroup$ – steedsnisps Apr 6 '15 at 20:21
0
$\begingroup$

To prove: if $a^x \equiv b^x$ mod $n$ and $a^y \equiv b^y$ mod $n$, then $a^{gcd(x,y)} \equiv b^{gcd(x,y)}$ mod $n$.

($\gcd(a,b)=1$)

Let $d=\gcd(x,y)$, $x=p*d$, $y=q*d$, then $\gcd(p,q)=1$ so there exists $m,o > 0$ so that $po=1+qm$ or vice versa. Let $y>x$.

$(a^d)^{po} \equiv (b^d)^{po}$ mod $n$, so $(a^d)^{1+qm} \equiv (b^d)^{1+qm}$ mod $n$, so $a^d*(a^{dq})^m \equiv b^d*(b^{dq})^m$ mod $n$ so $a^d \equiv b^d$ mod $n$, so every $n$ that divides both $a^x-b^x$ and $a^y-b^y$ also divides $a^d-b^d$, so $\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}$

Improve this answer
$\endgroup$
  • $\begingroup$ Here's the proof using $\,x,y\,$ vs. $\,pd,qd$ $$\begin{align} a^x\equiv b^x\, \Rightarrow&\quad\ \ \ a^{ox}\equiv b^{oy}\\ \Rightarrow&\ \ a^{d+my}\equiv b^{d+my}\\ \Rightarrow&\ \ a^d (a^y)^m\equiv b^d (b^y)^m\\ \Rightarrow&\ \ a^d (a^y)^m\equiv b^d (a^y)^m\,\ {\rm by}\,\ b^y\equiv a^y\\ \Rightarrow&\ \ a^d \equiv b^d\,\ {\rm by\ cancel}\,\ a^{ym} \end{align}$$ Looks good, except you need to prove $\,(a,n)=1\,$ to be able to cancel $\,a.\,$ Also, you should probably say more about how you use this to get the gcd equality. $\endgroup$ – Bill Dubuque Apr 7 '15 at 3:50
  • $\begingroup$ Nice, it is very similar. $(a,n)=1$, because $(a,n)|(a,a^x-b^x)=1$ because $(a,b)=1$. I don't understand what you mean? I'm saying every $n$ that divides both $a^x-b^x$ and $a^y-b^y$ will also divide $a^d-b^d$, so $(a^x-b^x,a^y-b^y) | a^d-b^d$ but $a^d-b^d|(a^x-b^x,a^y-b^y)$ so $a^d-b^d=(a^x-b^x,a^y-b^y)$ $\endgroup$ – steedsnisps Apr 7 '15 at 12:16

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.