Prove that $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$

Solution 1:

We have $2^n=1,2,4,3\bmod5$ and $3^n=1,3,4,2\bmod5$ for $n=0,1,2,3\bmod4$. Hence $2^n-3,3^n-2$ are both divisible by 5 iff $n=3\bmod4$ and $\gcd(2^n-3,5)=5$ iff $n=3\bmod4$ (for other $n$ it is 1).

The original question on this site asked for a proof that $\gcd(2^n-3,5)=\gcd(2^n-3,3^n-2)$ for all $n$. Given the observation above, that amounted to the assertions that (1) $\gcd(2^n-3,3^n-2)=5$ for $n=3\bmod4$ and (2) $\gcd(2^n-3,3^n-2)=1$ for $n\ne3\bmod4$.

I found that $$\gcd(2^{3783}-3,3^{3783}-2)=26665=5\cdot5333$$ which showed that (1) is false for $n=3783$.

By Fermat's Little Theorem we have that $2^{5332}=3^{5332}=1\bmod5333$, so it follows that $2^n-3=3^n-2=0\bmod5333$ for all $n=3783\bmod5332$. Since $3783=3\bmod4$ and $5332=0\bmod4$, the values of $n$ for which $5333$ is a factor of $\gcd(3^n-2,2^n-3)$ are a subset of those for which $5$ is a factor.

However, it emerged that the question came from the IMO LongList for 1972 which simply asked for which values of $n$ we have $\gcd(3^n-2,2^n-3)>1$. The question on this site has now been modified to ask (in effect) for a proof of (2).

It looks as though (2) is probably true, but at the moment I do not see how to prove it.

---------- Added 17 June 2016 --------

@i707107 has kindly provided references to some papers by Russian and Polish mathematicians in the period 1999-2003 (see http://www.fq.math.ca/Papers1/43-2/paper43-2-6.pdf and references therein). They include $$\gcd(2^{712999}-3,3^{712999}-2)=5\cdot18414001$$ where 18414001 is a prime and $712999=3\bmod4$. The last paragraph of the 2000 paper by Kazimierz Szymiczek (who died last year) reads:

"Another conjecture we want to make goes in the opposite direction. The numerical results suggest that three of the successive four couples $2^n-3$ and $3^n-2$ are relatively prime. Yet we do not know whether there are infinitely many exponents $n$ for which the numbers $2^n-3$ and $3^n-2$ are relatively prime. The conjecture is that there are infinitely many such exponents."

So it appears that it is still an open question whether $\gcd(2^n-3,3^n-2)=1$ for $n\ne3\bmod4$. That is presumably the reason that the question proposed by Romania for the IMO never got beyond the IMO 1972 Long List.