3
$\begingroup$

First of all I will introduce original problem (Question 5 from British Mathematical Olympiad).
You can find complete list of BMO'81 there BMO'81.

Find, with proof, the smallest possible value of $| 12^m - 5^n |$, where $m$ and $n$ are positive integers.

After this problem, I can write about my problem.
I have found somewhere in the net a this problem :

Given a function $f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ describe by equation $f(n,m) = 3|7^m \cdot 3^{2m} - 5^{2n}|$
Find minimum value of $f(n,m)$ in natural numbers (assume that $0 \not\in \mathbb{N}$).

I wrote about BMO'81 problem because I find that it can be very similar to upper.
Can somebody solve this problem? Any interesting method other by brute modulo?
(It can be but i don't understand by myself how to do it).

  • 0
    Exactly, the expression is $|63^m - 25^n|$. I played with it in my notepad a little bit but didn't get far.2012-09-25

2 Answers 2

3

I don't have a solution for the second problem, though I suspect its answer is $f(1,1) = 114$. (I have cycled through the first few hundred values and there is no lower). The edit provides a solution for the second problem, too.

To prove that 7 is the answer to the first problem, the Catalan conjecture is enough (as pointed by Yoni Rozenshein), however this is a very strong tool to use on such a simple problem. I provide a solution using only congruences modulo various small integers.

Let's go over the first problem. Assume $f(m, n) = 12^m - 5^n$.
Let us observe that $f(m,n) = 12^m - 5^n \equiv (-1)^{n+1} \pmod 6$ and $f(m,n) \equiv 2^m \pmod 5$.
Let $x = |f(m,n)| = u.f(m,n) = u.(12^m - 5^n)$, where $u$ is either $1$ or $-1$.
Therefore, $x \equiv u.(-1)^n \pmod 6$, $x \equiv u.2^m \pmod 5$.
The possible cases are:
1) $x \equiv 1 \pmod 6 \\ x \equiv 2 \pmod 5 => \\ x \equiv 7 \pmod{30} $
This is actually the case where the minimum is reached. We're not interested in this case.
2) $x \equiv -1 \pmod 6 \\ x \equiv 2 \pmod 5 => \\ x \equiv 17 \pmod{30} $
In this case, both $|17|>|7|$ and $|-13|>|7|$, so the minimum is not reached in this case.
The rest of the cases I will cover more briefly.
3) $x \equiv 19 \pmod{30} $. Again not interesting.
4) $x \equiv -1 \pmod{30} $. This is an important case, we will look at it later.
5) $x \equiv -17 \pmod{30} $. Again not interesting.
6) $x \equiv -7 \pmod{30} $. Not interesting.
7) $x \equiv 1 \pmod{30} $. Important case, save for later.
8) $x \equiv -10 \pmod{30} $. Again not interesting.

So, we have reduced the problem to proving that $f(m, n) \ne \pm 1$ for each $m, n$. Then, by necessity, the minimal value of $f(m, n)$ is $f(1, 1) = 7$.

Back at $f(m, n) = \pm 1$. First case:
1) $f(m,n) \equiv 1 \pmod 6 \\ f(m,n) \equiv 1 \pmod 5 => \\ n \equiv 1 \pmod 2 \\ m \equiv 0 \pmod 4$
This we get by discrete logarithm. Let $m = 4k, n = 2l + 1$. Then, looking again modulo 13 we get another set of congruences:
$ f(m,n) \equiv (-1)^{4k} - 5.(25)^{l} \equiv 1 - 5.(-1)^{l} \pmod{13} $. However, $f(m,n) = 1$, therefore this is a contradiction.
Second case:
2) $f(m,n) \equiv -1 \pmod 6 \\ f(m,n) \equiv -1 \pmod 5 => \\ n \equiv 0 \pmod 2 \\ m \equiv 2 \pmod 4$
Then again by congruence modulo 13, we get this:
$ f(m,n) \equiv (-1)^{4k+2} - 25^{l} \equiv 1 - (-1)^{l} \pmod{13}$. However, $f(m,n) = -1$, therefore we have a contradiction again.

Finally, a few words on how I picked the numbers 5, 6 and 13 for the congruences. 5 and 6 are pretty obvious, since they allow us to "throw out" either $12^m$ or $5^n$ and have small numbers in the congruences. 13 is also pretty easy to figure out, since $5^2 = 25 \equiv -1 \pmod{13}$ and $12 \equiv -1 \pmod{13}$. Since we already have data for the parity of $m$ and $n$, this substantially helps us (allowing us to remove the last cases: $f(m,n) = \pm 1$).

EDIT: I believe the second problem can also be solved using similar techniques. I'm currently trying this.

EDIT 2: I believe I have found the solution to the second problem, too. It involves congruences modulo 3, 5, 8 and 13. I will upload it here later today (if it proves correct).

EDIT 3: As promised earlier, the solution to the second problem. The answer is indeed 114.

Let $g(m,n) = 63^m-25^n$, that is $f(m,n) = 3.|g(m,n)|$.
Let's look at $g(m,n)$ modulo 3, 5 and 8.
$g(m,n) \equiv (-1)^m - 1^n \equiv 0 \; or \; -2 \pmod8 \\ g(m,n) \equiv 0 - 1^n \equiv 2 \pmod 3 \\ g(m,n) \equiv 3^m \pmod 5$.
$3^m \equiv 3,\, 4,\, 2 \; or \; 1 \pmod 5$

Now let's look at the possible values of $m$ modulo 4:
1) $m=4k$
$g(m,n) \equiv 1 \pmod 5 \\ g(m,n) \equiv 2 \pmod 3 \\ g(m,n) \equiv 0 \pmod 8 => \\ g(m,n) \equiv 56 \pmod{120}$
However, both 56 and -64 have greater absolute values than $g(1,1)$, therefore the minimal value is not achieved here.
2) $m=4k+1$
$g(m,n) \equiv -2 \pmod 8 \\ g(m,n) \equiv 2 \pmod 3 \\ g(m,n) \equiv 3 \pmod 5 => \\ g(m,n) \equiv 38 \pmod{120}$
$|-82|>|38|$ and therefore for now $g(1,1)=38$ is a good candidate for the minimum.
3) $m=4k+2$
By similar logic we get $g(m,n) \equiv 104 \pmod{120}$, but $|104|>|g(1,1)|$, so if the minimum of $|g(m,n)|$ is lower than $|g(1,1)|$, then $g(m,n)=-16$
But then, taking congruence modulo 13, we get this:
$g(m,n) \equiv (-2)^m-(-1)^n \equiv -16 \equiv -3 \pmod{13}$
Then, $(-2)^m \equiv -3 \pm 1 \pmod{13}$. That is, either $(-2)^m \equiv -2 \pmod{13} => m \equiv 1 \pmod{12}$, or $(-2)^m \equiv -4 \pmod{13} => m \equiv 8 \pmod{12}$.
The congruences modulo 12 we get because $-2$ is a generator of $\mathbb{Z_{13}^*}$ and therefore it is an element of order 12.
Obviously both $m \equiv 8 \pmod{12}$ and $m \equiv 1 \pmod{12}$ are contradictory to $m=4k+2$, so $g(m,n) \ne -16$ and the minimum value is not reached in this case.
4) $m=4k+3$
Again by similar congruences we get $g(m,n) \equiv 62 \pmod{120}$, but $|62|>|g(1,1)|$ and $|-58|>|g(1,1)|$. So the minimum is not reached here, either.

1

Another solution to the first problem: let $x$ be the minimum value. Clearly $x\le 7$ and $x$ odd. Moreover $x\neq 3, 5$, because we'd get a contradiction looking modulo $3$ and $5$. So we have to see if $x=1$, i.e. solving two equations (i) $12^m-5^n=1$ and (ii) $5^n-12^m=1$. Observe that $5^n=1,3,4,5,9$ modulo $11$. Look at (i) and (ii) modulo $11$ we obtain $5^n=0,2$ respectively. Hence $x=7$.