# If $\gcd(a,b)=1$, is $\gcd(a^x-b^x,a^y-b^y)=a^{\gcd(x,y)}-b^{\gcd(x,y)}$?

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.

• – lab bhattacharjee Apr 2 '15 at 18:40
• I already know this result, I am looking for a generalization. – steedsnisps Apr 2 '15 at 18:43
• It clearly fails for $b = 0$, at least. – anomaly Apr 2 '15 at 18:54
• 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 – Elaqqad Apr 2 '15 at 18:55
• 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{}$ – Michael Hardy Apr 2 '15 at 19:10

$\ (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}$$

• 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$? – steedsnisps Apr 6 '15 at 19:36
• @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}\ \$ – Bill Dubuque Apr 6 '15 at 19:56
• Ok and you are working mod $d$? – steedsnisps Apr 6 '15 at 19:59
• @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. – Bill Dubuque Apr 6 '15 at 20:09
• Ok thank you it is fully clear now. Can you look at my answer and tell me if it is correct? – steedsnisps Apr 6 '15 at 20:21

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)}$

• 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. – Bill Dubuque Apr 7 '15 at 3:50
• 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)$ – steedsnisps Apr 7 '15 at 12:16