# Find a positive integer $n$ (or prove that none exists) such that $\gcd(3^{n+1}-2,2^n-3) > 1$

Find a positive integer $n$ (or prove that none exists) such that $\gcd(3^{n+1}-2,2^n-3) > 1$.

The greatest common divisor here seems to be equal to one for most values (I checked up to $7000$), but I didn't see an easy way of finding an $n$ for which this it is greater than $1$. How could we go about solving this?

• Can you find $x,y$ such that $x(3^{n+1}-2) + y(2^n-3) = 1$ for all $n$? Then, you are done. Try this direction. – астон вілла олоф мэллбэрг Jan 31 '17 at 2:57
• @астон Are you certain that will work, or is that a guess? – Bill Dubuque Jan 31 '17 at 3:05
• @BillDubuque It's a guess. The first thing that came in mind. I was just wondering if it was possible. I've had a close look, but it seems a bit difficult. Anyway, there is an answer below. – астон вілла олоф мэллбэрг Jan 31 '17 at 3:08
• @астон That's what I surmised, so it is good that you clarified that so that the OP doesn't end up on a wild goose chase. – Bill Dubuque Jan 31 '17 at 3:10
• @BillDubuque Yes, it absolutely does not work. Thank you for anyway surmising it, I was on a wild goose chase for some time too! – астон вілла олоф мэллбэрг Jan 31 '17 at 3:11

If $n$ is such that $\gcd(3^{n+1}-2,2^n-3)>1$, then there exists a prime $p$ such that $3^{n+1}=2\bmod p$ and $2^n=3\bmod p$. But this implies $$3^{n+1}=(2^n)^{n+1}=2^{n^2+n}=2\bmod p,$$ hence $2^{n^2+n-1}=1\bmod p$, and hence $\varphi(p)=p-1$ divides $n^2+n-1$, no, all we can conclude is $\gcd(p-1,n^2+n-1)>1$. Considering the possibilities modulo 4 shows that this is not possible.
Elaboration on the mod 4 argument: If $p-1$ divides $n^2+n-1$ then $$n^2+n-1=k(p-1)$$ for some integer $k$. Note that $p$ is odd since both $3^{n+1}-2$ and $2^n-3$ are odd. Thus $p=1,3\bmod 4$, so $$k(p-1)=0,2\bmod 4.$$ On the other side, if $n$ is odd or $n=2\bmod 4$ then $$n^2+n-1=1\bmod 4,$$ and if $n=0\bmod 4$ then $$n^2+n-1=3\bmod 4.$$ Therefore $n^2+n-1\ne k(p-1)$, so $p-1$ does not divide $n^2+n-1$.
• It would probably be helpful to many readers if you elaborated on the mod $4$ argument. – Bill Dubuque Jan 31 '17 at 3:13
• @BillDubuque Can you explain why $\varphi(p)$ divides $n^2+n-1$ here? – user19405892 Jan 31 '17 at 14:02
• @user19405892 You have pointed out the fatal mistake in my argument. I made the assumption that $2$ is a primitive root mod $p$, which is certainly not necessarily true. I will leave the wrong answer here in case someone can patch this hole. – Heath Winning Jan 31 '17 at 18:52
• Heath, suggest a separate argument for when $3$ is a primitive root. Then whatever you can think of when neither one is a primitive root, rather some $r$ which will remain unspecified. – Will Jagy Jan 31 '17 at 19:56