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?

  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Jan 31 '17 at 2:57
  • $\begingroup$ @астон Are you certain that will work, or is that a guess? $\endgroup$ – Bill Dubuque Jan 31 '17 at 3:05
  • $\begingroup$ @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. $\endgroup$ – астон вілла олоф мэллбэрг Jan 31 '17 at 3:08
  • $\begingroup$ @астон 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. $\endgroup$ – Bill Dubuque Jan 31 '17 at 3:10
  • $\begingroup$ @BillDubuque Yes, it absolutely does not work. Thank you for anyway surmising it, I was on a wild goose chase for some time too! $\endgroup$ – астон вілла олоф мэллбэрг Jan 31 '17 at 3:11

This is not correct!

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

  • $\begingroup$ It would probably be helpful to many readers if you elaborated on the mod $4$ argument. $\endgroup$ – Bill Dubuque Jan 31 '17 at 3:13
  • $\begingroup$ @BillDubuque Can you explain why $\varphi(p)$ divides $n^2+n-1$ here? $\endgroup$ – user19405892 Jan 31 '17 at 14:02
  • $\begingroup$ @user19405892 Only Heath can explain that, since no justification is given above. That's why I was nudging him to elaborate. $\endgroup$ – Bill Dubuque Jan 31 '17 at 14:49
  • $\begingroup$ @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. $\endgroup$ – Heath Winning Jan 31 '17 at 18:52
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Jan 31 '17 at 19:56

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.