# Prove that if a prime $p$ divides $5^n-2$ and $2^n-5$, then $p = 3$

The result below has been disproven.

Let $n \in \mathbb{N}$. Prove that if a prime $p$ divides $5^n-2$ and $2^n-5$, then $p = 3$.

We know that $p \neq 2,5$. We need to have \begin{align*}5^n &\equiv 2 \pmod{p}\\2^n &\equiv 5 \pmod{p}.\end{align*} This gives us $10^{n-1} \equiv 1 \pmod{p}$. Thus $\text{ord}_{p}(10) \mid (n-1)$. How do we continue?

• 11 minor edits in the span of 90 minutes is quite much, please think about it. – Alex M. Dec 26 '16 at 23:32
• I don't understand where you get $p\leq 7$ from. – Eric Wofsey Dec 27 '16 at 0:01
• This is a variant of a famous problem proposed by Schinzel, e.g. see A.S.Izotov, On the prime divisors of $\,\gcd(3^{\large n}-2,2^{\large n}-3)$. Do you have any reason to believe that this case is more elementary? If not, you may be on a wild goose chase. – Bill Dubuque Dec 27 '16 at 0:07
• @user19405892 I don't understand your prior comment. What is the source of your question? – Bill Dubuque Dec 27 '16 at 0:10
• Please don't change the question after you receive a counterexample in an answer. It will cause confusion, e.g. in prior comments addressing the original question. – Bill Dubuque Dec 27 '16 at 2:04

$\gcd(5^{65} - 2, 2^{65} - 5) = 12681 = 3^2 \cdot 1409$

• I don't see why this is a proof. The statement says that given $n\in \mathbb{N}$, not for all $n$. – MonsieurGalois Dec 27 '16 at 1:35
• @MonsieurGalois I understood the statement to be about an arbitrary $n$, so I gave a counterexample. If $n$ is not arbitrary, then someone needs to specify which $n$ we are considering. – Michael Biro Dec 27 '16 at 1:41
• Now I understand what you did. Thanks for the explanation. – MonsieurGalois Dec 27 '16 at 1:42
• @ToanQuangPham $\gcd(2^{104}-5,5^{104}-2) = 1031$ – Michael Biro Dec 27 '16 at 2:35
• @ToanQuangPham A possible interesting pattern - for even $n$ up to 20000, the only values the gcd takes is $1$ or $1031$. Weird. – Michael Biro Dec 27 '16 at 2:40

Waiting for a counterexample not found by trial and error with calculator (which I intend to find later) I have verified in Wolfram that $n=65$ (Michael Biro's answer) is the minimum possible value of $n$. However calculator Desmos gives the wrong example $\color{blue}{\gcd(5^{54} - 2, 2^{54} - 5) = 4}$ which would imply the counterexample $p=2$

In view of this, it would not be impertinent to check whether Wolfram's answer is correct. Is not it?

• To be fair, I didn't double check the calculation. However, the numbers are not so large as to make a check infeasible, even by hand. 65 is nicely achievable by repeated squaring mod 1409. – Michael Biro Dec 27 '16 at 19:47
• Of course. I was referring to a formal aspect because if Desmos is wrong why not Wolfram? Have you seen Wolfram for $n$ till $65$? – Piquito Dec 27 '16 at 20:39

Proof that $1409 \mid \gcd(5^{65}-2,2^{65}-5$):

We have \begin{align*}5^5 &\equiv 307 \pmod{1409}\\5^{10} &\equiv 1255 \pmod{1409}\\5^{20} &\equiv 1172 \pmod{1409}\\5^{40} &\equiv 1218 \pmod{1409}\\5^{65} &\equiv 2 \pmod{1409}\end{align*} and \begin{align*}2^{12} &\equiv 1278 \pmod{1409}\\2^{24} &\equiv 253 \pmod{1409}\\2^{48} &\equiv 604 \pmod{1409}\\2^{60} &\equiv 1189 \pmod{1409}\\2^{65} &\equiv 5 \pmod{1409}.\end{align*}

• It suffices to check one - the other is just the $65$th power because $\,x^{\large 65}\,$ is self-inverse mod $p=1409\,$ by $\ \color{#c00}{65^2\equiv1}\pmod{p-1},\,$ i.e. $\,1408 = 128\cdot 11\mid 65^{\large 2}-1 = 64\cdot 66.\,$ This implies that $\,\left[2^{\large \color{#c00}{65}}\!\equiv 5\right]^{\large\color{#c00}{ 65}}\!\!\Rightarrow\, 2\equiv 5^{\large 65}\ \$ – Bill Dubuque Dec 28 '16 at 23:20