Let $p$ be a prime number greater than 10. Prove that there exist positive integers $m$ and $n$ such that $m+n < p$ and $5^m 7^n-1$ is divisible by $p$.
Problem
Source: Hong Kong 2019 TST 2 P2
Tags: number theory
01.05.2019 18:11
By contradiction, let it wrong. If exists such $m_1|p-1,n_1|p-1$ that $5^{m_1} \equiv 7^{n_1} \equiv 1 \pmod {p}$ then obvious. Let such $m_1,n_1$ does not exist. Let there are not such $n_1$ Then $5*7,5*7^2,...,5*7^{p-2}$ give different remainders $\pmod{p}$ And also $5*7^n \pmod{p}$ can not take values $0,1,5$ so exist $n_1<n_2<p-1; 5*7^{n_1}\equiv 5*7^{n_2} \pmod{p} \to 7^{n_2-n_1} \equiv 1 \pmod {p}$ - contradiction.
12.05.2019 10:32
RagvaloD wrote: By contradiction, let it wrong. If exists such $m_1|p-1,n_1|p-1$ that $5^{m_1} \equiv 7^{n_1} \equiv 1 \pmod {p}$ then obvious. Let such $m_1,n_1$ does not exist. Let there are not such $n_1$ Then $5*7,5*7^2,...,5*7^{p-2}$ give different remainders $\pmod{p}$ And also $5*7^n \pmod{p}$ can not take values $0,1,5$ so exist $n_1<n_2<p-1; 5*7^{n_1}\equiv 5*7^{n_2} \pmod{p} \to 7^{n_2-n_1} \equiv 1 \pmod {p}$ - contradiction. A very nice solution, and another as follows: If for any $2\leq m+n \leq p-1$, $5^m7^n \neq 1(modp)$, then $f(m,n)=(5^m7^n-1)^{p-1}=1(modp)$, we consider its sum: $$F=\sum\limits_{m=1}^{p-2}\sum\limits_{n=1}^{p-1-m} f(n,m)=\sum\limits_{m=1}^{p-2}(p-1-m)=-\frac{(p+1)(p-2)}{2}=1(modp).$$Let's exchange sum crazily: $$F=\sum\limits_{m=1}^{p-2}\sum\limits_{n=1}^{p-1-m}\sum\limits_{i=0}^{p-1}(-1)^iC_{p-1}^{i}(5^m)^i(7^n)^i=\sum\limits_{m=1}^{p-2}\sum\limits_{i=0}^{p-1}(-1)^iC_{p-1}^{i}\frac{7^i}{7^i-1}(5^m)^i((7^i)^{p-m-1}-1).$$Then $$F=\sum\limits_{m=1}^{p-2}\sum\limits_{i=0}^{p-1}(-1)^iC_{p-1}^{i}\frac{7^i}{7^i-1}(((\frac{5}{7})^i)^m-(5^i)^m).$$We notice $(a,p)=1, a \neq 1(modp)$, then $\sum\limits_{m=1}^{p-2}a^m=-1(modp)$, it follows that $F=0(modp)$, a contradiction.
12.05.2019 14:14
The following solution is concise: If $ord_p(5), ord_p(7)<p-1$, we have done. If $ord_p(5)=p-1$, we select $n=1$, $7^m=5(modp)$, $m<p-1$, it's Okay.
12.05.2019 16:03
weaker than https://artofproblemsolving.com/community/c6h1799463p11939056
23.05.2019 12:07
Here is another solution. Consider the $p - 2$ numbers ${5 \cdot 7^{p - 2}, 5^2 \cdot 7^{p - 3},..., 5^{p - 2} \cdot 7}$. Suppose all these numbers are different in $Z_p$. If one of these equals $1$, we are done. Otherwise, there exist $\alpha, \beta$ with $\alpha + \beta = p - 1$ such that $5^{\alpha} \cdot 7^{\beta} \equiv 5 \pmod p$, Assume $\alpha = 1$. Then $\beta = p - 2$ and Fermat's Theorem yields $7 \equiv 1 \pmod p$, contradiction since $p > 10$. So $\alpha > 1$ and we have $5^{\alpha - 1} \cdot 7 ^{\beta} \equiv 1\pmod p$ and the sum of the exponents has decreased, therefore remaining less than $p$. In the other case where these numbers are not all different, it follows that there exists $\gamma \geq 1$ such that $5^{\gamma} \equiv 7^{\gamma} \pmod p$, in which case the pair of exponents $(\gamma, p - 1 - \gamma)$ works, completing the proof.