Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
I found a quick solution to the original question, which I can't generalize to the 2nd question... but it might help: We can rule out $|12^m - 5^n| = 1$ because that would violate Catalan's conjecture (btw, this was not yet proven in 1981, and it's probably too powerful a tool here... but hey, it works). We can also rule out the values $2, 3, 4, 5, 6$ because $12^m - 5^n$ never has the same value as them modulo $2, 3, 4, 5, 3$, respectively. The next smallest option is $7$ which trivially works, with $m=n=1$. –  Yoni Rozenshein Sep 25 '12 at 16:35
    
We have got something like $|63^m - 25^n|$. I think that minimum value is 38. Am i wrong? Than, how to proof that 38 is the best option? But thanks a lot, now i understand the problem. –  John Smith Sep 25 '12 at 21:05
    
Exactly, the expression is $|63^m - 25^n|$. I played with it in my notepad a little bit but didn't get far. –  Yoni Rozenshein Sep 25 '12 at 21:55

2 Answers 2

up vote 3 down vote accepted
+50

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.