What is the smallest possible value of $\left|12^m-5^n\right|$, where $m$ and $n$ are positive integers?
Problem
Source:
Tags: number theory, optimization
rayfish
11.04.2021 05:55
This is for 3rd graders? Even I can't solve this problem! Here is my work at a proof that the smallest possible value is $7$. You can't use Catalan's conjecture, of course.
We know that $|12^1 - 5^1| = 7$. I will prove that this is the minimum value.
Claim: There are no solutions to $|12^m - 5^n| = k$ if $k < 7$.
Proof. Suppose there exists a nonnegative integer $k < 7$ that satisfies $|12^m - 5^n| = k$. Since $12^m$ is even and $5^n$ is odd, the distance between them must be odd. Thus, $k$ must be $1$, $3$, or $5$. Clearly, $3$ and $5$ don't work because $3 \nmid 5^n$ and $5 \nmid 12^m$. Thus, $k=1$.
We must have $12^m - 5^n = \pm 1 \implies 5^n = 12^m \pm 1$.
Case 1: $5^n = 12^m - 1$. By the difference of nth powers factorization, the RHS is divisible by $11$, but the LHS is not, contradiction.
Case 2: $5^n = 12^m + 1$. Idk how to do this.
EDIT: I have solved the problem.
Case 2: $5^n = 12^m + 1$. This means $2^m + 1 \equiv 0 \pmod{5}$, which means $m \equiv 2 \pmod{4}$. We can let $m = 4p - 2$ for some positive integer $p$. Thus, we have:
$$12^{4p - 2} + 1 = 5^n$$$$144^{2p - 1} + 1 = 5^n$$By sum of nth powers factorization, the LHS is divisible by $145$, meaning it is divisible by $29$, contradiction.
natmath
11.04.2021 06:39
For case 2, we have
$$5^n-1=12^m$$Note that $5^n-1$ is only divisibly by $12$ when $n$ is even (take $\mod 3$ and $\mod 4$)
Moreover by LTE, $v_2(5^{2k}-1)=3+v_2(k)$ and $v_3(5^{2k}-1)=1+v_3(k)$
For this to be a power of 12, a requirement is that $v_2(5^{2k}-1)=2\cdot v_3(5^{2k}-1)$,
$$3+v_2(k)=2+2v_3(k)$$$$1+v_2(k)=2 v_3(k)$$That means that $k$ can be expressed in the form $2^{2a-1}3^a\ldots$. This implies that $12|n$.
However, if $12|n$, we have that $5^n-1\equiv 0\mod 13$, hence it is not a power of $12$.
I'm not sure if this is the most efficient solution lol. Edit: well it looks like @above finished their own solution, and it's definitely quicker than mine. I just saw something looking like LTE and decided to see where that went.