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

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?

• What is the source of this problem? It has already been asked recently : math.stackexchange.com/questions/1823972/… – Jack D'Aurizio Jun 13 '16 at 16:25
• @JackD'Aurizio evidently 1972 IMO Longlist-31 although I do not seem to be able to get a look at it. Most IMO stuff is on AOPS, artofproblemsolving.com/wiki/index.php?title=1972_IMO – Will Jagy Jun 13 '16 at 17:24
• The IMO long list question is "Find the values of $n\in\mathbb{N}$ for which the fraction $\frac{3^n-2}{2^n-3}$ is reducible." So the answer to that would appear to be $n=3\bmod4$, although I have not yet found a proof. It is easy to show that 5 is a common factor if $n=3\bmod4$, but absence of any common factor if $n\ne3\bmod4$ is not so easy. – almagest Jun 13 '16 at 17:27

## 2 Answers

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.

• Out of curiosity, how did you find that? – Jack D'Aurizio Jun 13 '16 at 16:26
• Brute force and ignorance (takes a few seconds on Mathematica): For[n = 5, n < 10000, n++,If[GCD[2^n - 3, 3^n - 2] > 5, Print[n]]]; – almagest Jun 13 '16 at 16:27
• Writing a SAGE code would have also given these examples since the numbers $3783$, $9115$ are small. – i707107 Jun 13 '16 at 16:28
• How does this answer the question? – Puzzled417 Jun 13 '16 at 17:01
• Well it shows that $gcd(2^n-3,3^n-2)\ne gcd(2^n-3,5)$ for all $n$. In other words you were asking us to prove a result which is false! – almagest Jun 13 '16 at 17:02

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.