Solution $ 5\mid 2^{1} 3^{1} -1$ and $ 1+1\leq ( 5+1) /2$. Suppose that $ p >5$. Let $ h=\frac{p-1}{\text{ord}_{p}( 2)}$. We consider the following cases (1)(2)(3): (1) $ h=1$ We can take $ t( 1< t< p)$ such that $ 3\equiv 2^{t}\pmod p$. If $ t\geq ( p-1) /2$, then $ ( n,m) =( p-t-1,1)$ satisfies the condition. Suppose that $ t< ( p-1) /2$. We can take $ i( 0\leq i< t-1)$ for which $ t-1\mid ( p-3) /2+i$. Then $ ( n,m) =( p-tu-1,u)$ satisfies the condition where $ u=\frac{( p-3) /2+i}{t-1}$. (2) $ h=2$ We can take $ t( 1\leq t\leq ( p-1) /2)$ for which $ p\mid 3^{2} 2^{t} -1$. Assume that $ t=( p-1) /2$. Then $ 0\equiv 3^{2} 2^{( p-1) /2} -1\equiv \pm 3^{2} -1\pmod p$. Thus, $ p=2,5$, which contradicts the assumption $ p >5$. So we have $ t\leq ( p-3) /2$. So $ ( n,m) =( t,2)$ satisfies the condition. (3) $ h\geq 3$ We can verify that $ p\geq 13$ Since $ p >3$, we have $ \text{ord}_{p}( 2) \geq 3$, which implies $ h\leq ( p-1) /3$.$ $ We can take $ t( 1\leq t\leq ( p-1) /h)$ for which $ p\mid 3^{h} 2^{t} -1$. Since $ p\geq 13$ and $3\leq h\leq ( p-1) /3$, we have $ h+( p-1) /h\leq ( p+1) /2$. Therefore, $ ( n,m) =( t,h)$ satisfies the condition. $ \blacksquare $

Let $g$ be a primitive root modulo $p,$ and suppose that $2 \equiv g^a, 3 \equiv g^b$ (mod $p$). Firstly, note that it's trivial that $\frac{p-1}{2} \nmid a, b$, as that would mean that $p|2^2 - 1$ or $p|3^2-1,$ both absurd. Then we wish to show the existence of positive integers $m, n$ such that $m+n \leq \frac{p+1}{2}$ and $na + mb$ is a multiple of $p-1.$ Firstly, observe that if $a$ isn't relatively prime to $p-1$, then we would have that $d | p-1, a$ for some $d = \gcd(a, p-1) \geq 2,$ and so hence $p-1 | db + xa$ for some $x \leq \frac{p-1}{d}.$ As $d + \frac{p-1}{d} -1 \leq \frac{p+1}{2}$ with equality iff $d = 2$, we are done unless we have that $d = 2$ and $p-1| db + \frac{p-1}{d} * a.$ In that case, we would have that $\frac{p-1}{2} | b,$ i.e., $b$ has order $2$ or less mod $p$. However, this would imply that $p | 3^2 - 1 = 8,$ impossible. An analogous argument handles the case where $b$ isn't relatively prime to $p-1.$ Hence, we need only deal with the case where $a, b$ are both relatively prime to $p-1.$ From now on, all integers will be taken mod $p-1$. In that case, let $r$ be a positive integer which is congruent to $\frac{-b}{a}$ mod $p-1,$ i.e., $p-1 | ar + b$. Then, if one of $r, 2r, \cdots, \frac{p-3}{2} r$ is $\leq \frac{p-3}{2},$ say $ir \leq \frac{p-3}{2}$, then that implies that $p-1| ira + ib, p-1 | (\frac{p-1}{2} - ir)a + (\frac{p-1}{2} - i)b$ since $a+b$ is even. Since one of the pairs $(ir, i), (\frac{p-1}{2} - ir, \frac{p-1}{2} - i)$ has sum at most $\frac{p-1}{2}$, we are done. Otherwise, we must have that $\{r, 2r, \cdots, \frac{p-3}{2}r\}$ must be, in some order, $\{\frac{p+1}{2}, \frac{p+3}{2}, \cdots, p-2\}.$ This easily implies that $r = p-2,$ and so that means that $p-1|a(p-2) + b \Rightarrow p-1| a-b.$ However, this means that $2 \equiv g^a \equiv g^b \equiv 3$ (mod $p$), clearly absurd. $\square$ Edit: thanks @below, fixed.

@above Quote: $(x_i - x_j) a \equiv (y_j- y_i)b \Rightarrow a \equiv b$ (mod $p-1$) This implication is clearly wrong.

Nice problem. Let $g$ be a primitive root, let $2=g^a$ and $3=g^b$. WLOG assume that $\gcd(a,b)=1,$ and assume that $b$ is odd. Let $D=\gcd(p-1,b)$ and let $d=\frac{p-1}{D}$ and $b'=\frac{b}{D}.$ I claim that for any $2\le t\le d-2,$ there exist positive integers $n_1$ and $m_1$ with $n_1+m_1 \le \frac{d}{2}+1$ such that $tn_1+m_1$ is divisible by $d$. Indeed, if $t$ divides $d$, let $n_1=\frac{d-t}{t}$ and $m_1=t$, otherwise let $n_1=\left \lfloor \frac{d}{t} \right \rfloor$ and $m_1=d-tn_1$. the verification for both cases is immediate. Now suppose that $t$ is such that $t \equiv \frac{a}{b'} \pmod{d}$ is divisible by $d,$ then let $tn_1+m_1 \equiv 0\pmod{d} \implies$ $$an_1+b'm_1 \equiv 0 \pmod{d} \implies aDn_1+Db'm_1 \equiv 0 \pmod{p-1} \implies aDn_1+bm_1 \equiv 0 \pmod{d}$$And because $n_1+m_1 \le \frac{d}{2}+1,$ we have that $Dn_1+m_1+(D-1)(m_1-1) \le \frac{p-1}{2}+1 \implies Dn_1+m_1 \le \frac{p+1}{2},$ hence $n=Dn_1$ and $m=m_1$ satisfy the conditions of the problem.

@above Quote: WLOG assume that $\gcd(a,b)=1$ can't

kaede wrote: @above Quote: WLOG assume that $\gcd(a,b)=1$ can't why, if a and b have additional common factors it only benefits us. if the assertion holds for coprime a and b, then it also will for those who have something in common. no one cares about the 2 and 3

@above I have understood your argument. I meant that such an assumption might disturb your argument. In your notation, if $(p,a,b)=(7,2,3)$, then $d=2, b'=1, t=2$. This implies $(n_1,m_1)=(1,1)$ because $d/2+1=2$. However, $t\cdot n_1 + m_1 = 3$ is not divisible by $2$. Another example is $(p,a,b)=(11,4,5)$. In this case, $d=2, b'=1, t=4, n_1=m_1=1$. However, $t\cdot n_1+m_1 = 5$ is not divisible by $2$. if you consider only the case $d>2$, there is no counter-example, of course.

kaede wrote: Solution $ 5\mid 2^{1} 3^{1} -1$ and $ 1+1\leq ( 5+1) /2$. Suppose that $ p >5$. Let $ h=\frac{p-1}{\text{ord}_{p}( 2)}$. We consider the following cases (1)(2)(3): (1) $ h=1$ We can take $ t( 1< t< p)$ such that $ 3\equiv 2^{t}\pmod p$. If $ t\geq ( p-1) /2$, then $ ( n,m) =( p-t-1,1)$ satisfies the condition. Suppose that $ t< ( p-1) /2$. We can take $ i( 0\leq i< t-1)$ for which $ t-1\mid ( p-3) /2+i$. Then $ ( n,m) =( p-tu-1,u)$ satisfies the condition where $ u=\frac{( p-3) /2+i}{t-1}$. (2) $ h=2$ We can take $ t( 1\leq t\leq ( p-1) /2)$ for which $ p\mid 3^{2} 2^{t} -1$. Assume that $ t=( p-1) /2$. Then $ 0\equiv 3^{2} 2^{( p-1) /2} -1\equiv \pm 3^{2} -1\pmod p$. Thus, $ p=2,5$, which contradicts the assumption $ p >5$. So we have $ t\leq ( p-3) /2$. So $ ( n,m) =( t,2)$ satisfies the condition. (3) $ h\geq 3$ We can verify that $ p\geq 13$ Since $ p >3$, we have $ \text{ord}_{p}( 2) \geq 3$, which implies $ h\leq ( p-1) /3$.$ $ We can take $ t( 1\leq t\leq ( p-1) /h)$ for which $ p\mid 3^{h} 2^{t} -1$. Since $ p\geq 13$ and $3\leq h\leq ( p-1) /3$, we have $ h+( p-1) /h\leq ( p+1) /2$. Therefore, $ ( n,m) =( t,h)$ satisfies the condition. $ \blacksquare $ We can take $ t( 1\leq t\leq ( p-1) /h)$ for which $ p\mid 3^{h} 2^{t} -1$. why $\boxed{t}$ exist?

its mongolian teachers olympiad of 2017 p5

Quote: We can take $ t( 1\leq t\leq ( p-1) /h)$ for which $ p\mid 3^{h} 2^{t} -1$. why $\boxed{t}$ exist? I think he mean something like this: There are $h'\leq h, t \leq (p-1)/h$ such that $ p\mid 3^{h'} 2^{t} -1$.

https://artofproblemsolving.com/community/c6h1524749 ... Coincidence?

ManuelKahayon wrote: https://artofproblemsolving.com/community/c6h1524749 ... Coincidence? This is a lot stronger than that

and so hence $p-1 | db + xa$ for some $x \leq \frac{p-1}{d}.$ Why is this?

Pathological wrote: 1. $d + \frac{p-1}{d} -1 \leq \frac{p+1}{2}$ 2. Otherwise, we must have that $\{r, 2r, \cdots, \frac{p-3}{2}r\}$ must be, in some order, $\{\frac{p+1}{2}, \frac{p+3}{2}, \cdots, p-2\}.$ This easily implies that $r = p-2,$ Can you proof these statements?

niksic wrote: and so hence $p-1 | db + xa$ for some $x \leq \frac{p-1}{d}.$ Why is this? Because $gcd(a/d,(p-1)/d)=1$, then the follow equation $$x\cdot \frac{a}{d}\equiv -b\pmod{\frac{p-1}{d}}$$have a solution in $\{1,\dots,\frac{p-1}{d}-1\}$