Let $n$ be a positive integer, $p$ and $q$ be prime numbers such that \[ pq \mid n^p+2 \quad \text{and} \quad n+2 \mid n^p+q^p. \]Prove that there exists a positive integer $m$ satisfying $q \mid 4^m \cdot n +2$.
Problem
Source: Turkey JBMO TST 2016 P3
Tags: number theory, prime numbers
tastymath75025
23.05.2016 02:03
Assume $q>2$, otherwise the result is trivial.
Note that $q|4^m*n+2 \iff q| (4^m*n+2)* 2^{q-1-2m} = 2^{q-1} n + 2^{q-2m} \iff q| n + 2^{odd}$ so we just need to show there is some odd $k$ with $q|n+2^{k}$.
The key point is noting $\gcd (p, q-1)=1$. In other words, we must show $q$ is not equivalent to $1$ mod $p$. But this is easy- by FLT, $p|n^p+2 \implies p|n+2$. Then in the second equation, $p|n+2 | n^p+q^p \implies p|n+q$ by FLT again. Then $p|n+q, n+2 \implies p|q-2$ so that $q \equiv 2$ mod $p$, and the claim is proven.
Let $x = p^{-1}$ mod $q-1$ so $px \equiv 1$. Since $p$ is odd but $q-1$ is even, $x$ is odd. Then $q | n^p - (-2) | n^{px} - (-2)^x \equiv n- (-2)^x$ by FLT, and this is equivalent with $q| n+2^x$ as desired.
Dilshodbek
05.02.2017 09:13
good problem and effective solution thank a lot
Telman
19.06.2022 20:27
tastymath75025 wrote:
Assume $q>2$, otherwise the result is trivial.
Note that $q|4^m*n+2 \iff q| (4^m*n+2)* 2^{q-1-2m} = 2^{q-1} n + 2^{q-2m} \iff q| n + 2^{odd}$ so we just need to show there is some odd $k$ with $q|n+2^{k}$.
The key point is noting $\gcd (p, q-1)=1$. In other words, we must show $q$ is not equivalent to $1$ mod $p$. But this is easy- by FLT, $p|n^p+2 \implies p|n+2$. Then in the second equation, $p|n+2 | n^p+q^p \implies p|n+q$ by FLT again. Then $p|n+q, n+2 \implies p|q-2$ so that $q \equiv 2$ mod $p$, and the claim is proven.
Let $x = p^{-1}$ mod $q-1$ so $px \equiv 1$. Since $p$ is odd but $q-1$ is even, $x$ is odd. Then $q | n^p - (-2) | n^{px} - (-2)^x \equiv n- (-2)^x$ by FLT, and this is equivalent with $q| n+2^x$ as desired.
Hi i wonder that where did you know 2^(q-1-2m) is an integer? Thanks.