10
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ What is the source of this problem? It has already been asked recently : math.stackexchange.com/questions/1823972/… $\endgroup$ – Jack D'Aurizio Jun 13 '16 at 16:25
  • 3
    $\begingroup$ @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 $\endgroup$ – Will Jagy Jun 13 '16 at 17:24
  • 2
    $\begingroup$ 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. $\endgroup$ – almagest Jun 13 '16 at 17:27
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Out of curiosity, how did you find that? $\endgroup$ – Jack D'Aurizio Jun 13 '16 at 16:26
  • 1
    $\begingroup$ 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]]]; $\endgroup$ – almagest Jun 13 '16 at 16:27
  • $\begingroup$ Writing a SAGE code would have also given these examples since the numbers $3783$, $9115$ are small. $\endgroup$ – Sungjin Kim Jun 13 '16 at 16:28
  • 1
    $\begingroup$ How does this answer the question? $\endgroup$ – Puzzled417 Jun 13 '16 at 17:01
  • 4
    $\begingroup$ 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! $\endgroup$ – almagest Jun 13 '16 at 17:02
0
$\begingroup$

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.

$\endgroup$

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.