Let $p>5$ be a prime number. Prove that there exist $m,n\in \mathbb{N}$ for which $m+n<p$ and $2^m 3^n-1$ is a multiple of $p$.
Problem
Source: VIII International Festival of Young Mathematicians Sozopol 2017, Theme for 10-12 grade
Tags: number theory
20.08.2019 16:36
Assume that there don't exist any such prime. Then take all such possible pairs of m and n such that m+n<p there exist (p-2)(p-3)/2 such pairs. Now observe that this quantity is greater than p for p>2 which is obvious as it is given in the question. Now there must exist 2 pairs of m and n such that 2^m1×3n1-1 and 2^m2×3^n2-1 are congruent to each other. So their difference must be divisible by p. Hence by taking 2's and 3' common out. We get the no. in the bracket too in the form of what is required. Since p>5 it can't divide the 2s and 3s so it must divide what's in the bracket. So it's done from here as it's very trivial now
20.08.2019 18:32
This is a much weaker version of https://artofproblemsolving.com/community/c6h1799463p11939056
20.08.2019 19:34
GammaBetaAlpha wrote: We get the no. in the bracket too in the form of what is required. Why does this happen? More specifically if the bracket has $2^a-3^b$ , which is divisible by p, then how do we get a number of the required form?
21.08.2019 02:49
RudraRockstar I assume that you understood the first half of the solution of GammaBetaAlpha. Anyway, what he meant is that due to the fact that there are $>p$ pairs (m, n) satisfying m+n<p for p>3 (actually I think that their number is $\frac{(p-1)(p-2)}{2}$), there exist 2 pairs $(m_1,n_1)$ and $(m_2, n_2)$ which are congruent modulo p. Hence we get $2^{m_1-m_2}3^{n_1-n_2}\equiv 1 (mod p)$. Now we have 3 cases. wlog let $m_1 \geq m_2$: 1) If both $m_1-m_2$ and $n_1-n_2$ are positive, then we are done; 2) If $n_1-n_2$ is negative, then one of $(m_1-m_2, p-1+n_1-n_2)$ and $(p-1+m_2-m_1, n_2-n_1)$ is a solution; ^^This was the part that wasn't clear. 3) One of the powers is 0 ($m_1=m_2$ or $n_1=n_2$): 3.1) If $2^m3^n=t$ has more than $p-2$ solutions then there $\exists$ $(m_1,n_1)$ and $(m_2,n_2)$ for which $m_1\neq m_2$ and $n_1\neq n_2$. 3.2) Finally if $2^m3^n=t$ has exactly $p-2$ solutions it follows that $2^m3^n$ must be a constant for a fixed m or n, giving us that $2 \equiv 1 (mod p)$ or $3 \equiv 1 (mod p)$. Hence a contradiction. These are some easy calculations that one needs to comply.
21.08.2019 04:20
Pinko wrote: RudraRockstar I assume that you understood the first half of the solution of GammaBetaAlpha. Anyway, what he meant is that due to the fact that there are $>p$ pairs (m, n) satisfying m+n<p for p>3 (actually I think that their number is $\frac{(p-1)(p-2)}{2}$), there exist 2 pairs $(m_1,n_1)$ and $(m_2, n_2)$ which are congruent modulo p. Hence we get $2^{m_1-m_2}3^{n_1-n_2}\equiv 1 (mod p)$. Now we have 3 cases. wlog let $m_1 \geq m_2$: 1) If both $m_1-m_2$ and $n_1-n_2$ are positive, then we are done; 2) If $n_1-n_2$ is negative, then one of $(m_1-m_2, p-1+n_1-n_2)$ and $(p-1+m_2-m_1, n_2-n_1)$ is a solution; ^^This was the part that wasn't clear. 3) One of the powers is 0 ($m_1=m_2$ or $n_1=n_2$): 3.1) If $2^m3^n=t$ has more than $p-2$ solutions then there $\exists$ $(m_1,n_1)$ and $(m_2,n_2)$ for which $m_1\neq m_2$ and $n_1\neq n_2$. 3.2) Finally if $2^m3^n=t$ has exactly $p-2$ solutions it follows that $2^m3^n$ must be a constant for a fixed m or n, giving us that $2 \equiv 1 (mod p)$ or $3 \equiv 1 (mod p)$. Hence a contradiction. These are some easy calculations that one needs to comply. Yes. I mean the same