13
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 11 minor edits in the span of 90 minutes is quite much, please think about it. $\endgroup$ – Alex M. Dec 26 '16 at 23:32
  • 2
    $\begingroup$ I don't understand where you get $p\leq 7$ from. $\endgroup$ – Eric Wofsey Dec 27 '16 at 0:01
  • 3
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Dec 27 '16 at 0:07
  • 1
    $\begingroup$ @user19405892 I don't understand your prior comment. What is the source of your question? $\endgroup$ – Bill Dubuque Dec 27 '16 at 0:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Dec 27 '16 at 2:04
17
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't see why this is a proof. The statement says that given $n\in \mathbb{N}$, not for all $n$. $\endgroup$ – MonsieurGalois Dec 27 '16 at 1:35
  • $\begingroup$ @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. $\endgroup$ – Michael Biro Dec 27 '16 at 1:41
  • $\begingroup$ Now I understand what you did. Thanks for the explanation. $\endgroup$ – MonsieurGalois Dec 27 '16 at 1:42
  • 1
    $\begingroup$ @ToanQuangPham $\gcd(2^{104}-5,5^{104}-2) = 1031$ $\endgroup$ – Michael Biro Dec 27 '16 at 2:35
  • 2
    $\begingroup$ @ToanQuangPham A possible interesting pattern - for even $n$ up to 20000, the only values the gcd takes is $1$ or $1031$. Weird. $\endgroup$ – Michael Biro Dec 27 '16 at 2:40
0
$\begingroup$

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$

enter image description here

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Biro Dec 27 '16 at 19:47
  • $\begingroup$ 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$? $\endgroup$ – Piquito Dec 27 '16 at 20:39
0
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ 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}\ \ $ $\endgroup$ – Bill Dubuque Dec 28 '16 at 23:20

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.