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

Question

Prove that $\gcd(3^n-2,2^n-3)=1$ if and only if $\gcd(5,2^n-3)=1$ where $n$ is a natural number.

I didn't see an easy way to prove this using the Euclidean algorithm, but it seems true that both gcd's are not $1$ only if $n = 3+4k$. Is there an easy way to prove the statement?

Answer 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.

Answer 2

This does not completely answer the question. This provides some more information than those given by previous answers and comments. Also, the method I provide here slightly differs from the following reference, but main ideas are from the paper.

According to the reference http://www.fq.math.ca/Papers1/43-2/paper43-2-6.pdf

We obtain common prime divisors of $2^n-3$ and $3^n-2$ in the following way:

1. Find a prime number $p$ satisfying $$ \gcd(\mathrm{ord}_p (3\cdot 2^{-1}), \mathrm{ord}_p (6)) = 1 \ \mathrm{or} \ 2. $$

2. For such prime $p$, let $\ell = \mathrm{ord}_p(3\cdot 2^{-1})$ and $k=\mathrm{ord}_p(6)$. Find integer solutions to: $$ \ell x - k y = 2.$$

3. We want $x\geq 1$ from Step 2. Starting from $1$, find: $$ 2^{\ell x -1} \ \mathrm{mod} \ p, \ \mathrm{and} \ 3^{\ell x -1} \ \mathrm{mod} \ p $$

4. If they are $3$ and $2$ respectively, then the prime $p$ is the common divisor of $2^n-3$ and $3^n-2$ where $n=\ell x -1$.

A SAGE program that I wrote, doesn't exactly follow the above algorithm, but it was successful in finding at least the three primes $5$, $5333$, $18414001$.

for p in primes(4,40000000): 
a=2.inverse_mod(p); 
b=Mod(Mod(3,p)*a,p).multiplicative_order(); 
c=Mod(6,p).multiplicative_order(); 
if gcd(b, c)==1: 
    g,s,t=xgcd(b, -c); 
    h=(2*s)%c; 
    print p, Mod(b*h-1,4), power_mod(3,b*h-1,p), power_mod(2,b*h-1,p);

with the following results:

5 3 2 3
5333 1 5331 5330
18414001 3 2 3

The second line result may be due to the program lacking to proceed Step 2 and Step 3. With more care, it might be possible to implement those and get a correct result 5333 3 2 3.

It was not possible for me to completely settle the (equivalent) problem:

$\bullet$ If $p|\gcd(2^n-3,3^n-2)$, then $n\equiv 3 \ \mathrm{mod} \ 4$.

But, I now have one more conjecture:

$\bullet$ If $\gcd(\mathrm{ord}_p (3\cdot 2^{-1}), \mathrm{ord}_p (6)) = 1$, then there exists $n$ such that $p|\gcd(2^n-3,3^n-2)$.

Both of these questions still remain open.