If $k\geq 3$ is a given positive integer, prove that there exist prime numbers $p_{1}<p_{2}<\cdots<p_{k}$ and positive integers $a_{1},a_{2},\cdots,a_{k}$, such that $$p_{1}p_{2}\cdots p_{k} \mid (p_{1})^{a_{1}}+(p_{2})^{a_{2}}+\cdots+(p_{k})^{a_{k}}$$

I need to prove

$$p_{i} \mid (p_{1})^{a_{1}}+(p_{2})^{a_{2}}+\cdots+(p_{i-1})^{a_{i-1}}+(p_{i+1})^{a_{i+1}}+\cdots+(p_{k})^{a_{k}}\quad\forall i=1,2,\ldots,k$$ from Fermat's little theorem, we need prove there exist $a_{1},a_{2},\ldots,a_{n}$ s.t. \begin{align} a_{1} &= 0 \pmod {(p_{i}-1)} &(i &\neq 1) \\ a_{2} &= 0 \pmod {(p_{i}-1)} &(i &\neq 2) \\ &\;\;\vdots \\ a_{k} & = 0 \pmod {(p_{i}-1)} & (i &\neq k) \end{align}

it seem use CRT, but in fact we can't use this theorem, because this problem not such Chinese remainder theorem condition, so How to prove this problem

  • $\begingroup$ What is the source of this problem, please? $\endgroup$ May 7 at 4:25
  • $\begingroup$ asked by a student is said to be a contest question $\endgroup$
    – math110
    May 7 at 4:27
  • $\begingroup$ An ongoing contest? $\endgroup$ May 7 at 5:04
  • $\begingroup$ The end of, our country for the examination questions management is very strict, in all did not end the examination questions if published on the Internet, was found, is illegal $\endgroup$
    – math110
    May 7 at 7:00
  • $\begingroup$ I wonder about the point of such contests in the internet era anyway considering how often cheating is done or at least tried , as many questions having appeared here during an ongoing contest show. The organizers should know this. $\endgroup$
    – Peter
    May 8 at 8:41

1 Answer 1


Choose $q_{1}$ to be a prime that divides $k-1$

By lemma 3 (proved below) exists $j_{1}$ so that $q_{1}^{j_{1}}+k-2$ is a multiple of some prime $q_{2}>q_{1}$. $\text{ }$ By lemma 3 there exists $j_{2} $ so that $q_{1}^{j_{1}}+q_{2}^{j_{2}(q_{1}-1)}+k-3$ is a multiple of some prime $q_{3}>q_{2}$...(doing this process many times)...by lemma 3 there exists $j_{k-1}$ so that $$q_{1}^{j_{1}}+q_{2}^{j_{2}(q_{1}-1)}+...+q_{k-1}^{j_{k-1}(q_{1}-1)(q_{2}-1)...(q_{k-2}-1)}$$ is a multiple of some prime $q_{k}>q_{k-1}$. Thus $$q_{1}^{j_{1}}+q_{2}^{j_{2}(q_{1}-1)}+...+q_{k-1}^{j_{k-1}(q_{1}-1)(q_{2}-1)...(q_{k-2}-1)}+q_{k}^{(q_{1}-1)(q_{2}-1)...(q_{k-2}-1)(q_{k-1}-1)} \equiv 0 \mod q_{1}q_{2}...q_{k}$$

We will prove Lemma 3, an important ingredient for our proof below.

$\textbf{Definition:}$ Given a prime $p$ and a positive integer $n$. $M(p,n)$ is the unique non-negative integer such that $p^{M(p,n)}|n$ but $p^{M(p,n)+1} \not | n$

$\textbf{Lemma 1:}$ If $$a \in \mathbb{N}$$ $$b \in \mathbb{N}; b > 1$$ $$c \in \mathbb{Z}; c \neq 0$$ then given a prime $p$, there exists a non-negative integer $e_{1}$, natural numbers $u, v$ such that for all $t \in \mathbb{N}\cup \{0\}$ we have $$M(p,ab^{u+vt} + c) = e_{1}$$ $\textbf{Proof:}$ If $p|c$ then there exists $h$ sufficiently large so that $M(p,ab^{h} + c) = M(s_{1},ab^{h+1} + c)=....$ thus it sufficies to take $u = h$ and $v = 1$. If $p \not | c$ but $p| a$ or $b$ then it sufficies to take $u = 1, v = 1$. If $s_{1} \not | a, b$ or $c$ then suppose $a b^{s} + c > 1$ we can take $$u = s$$ $$v = (s_{1}-1)s_{1}^{M(s_{1},a b^s +c)}$$ $$e_{1} = M(s_{1},a b^s +c)$$ $\textbf{Lemma 2:}$ If $$a \in \mathbb{N}$$ $$b \in \mathbb{N}; b > 1$$ $$c \in \mathbb{Z}; c \neq 0$$ then given a set of primes $\{s_{1},...,s_{k}\}$, there exists non-negative integers $e_{1},...,e_{k}$ and natural numbers $u_{k},v_{k}$ such that for all $1 \leq j \leq$, $t \in \mathbb{N} \cup \{0\}$ we have $$M(s_{j}, a b^{u_{k}+v_{k}t}+c) = e_{j}$$ $\textbf{Proof:}$ By the above lemma there exists $v_{1} \in \mathbb{N}\cup \{0\}, r_{1},s_{1} \in \mathbb{N} $ so that for all $t \in \mathbb{N}\cup \{0\}$ we have $M(s_{1}, a b^{r_{1}+s_{1}t}+c) = e_{1}$, for some fixed $e_{1} \in \mathbb{N}\cup \{0\}$. Now $ a b^{r_{1}+s_{1}t}+c = (ab^{r_{1}})(b^{s_{1}})^t+c$ thus we can continually apply Lemma 1 to prove this lemma.

$\textbf{Lemma 3:}$ If $$a \in \mathbb{N}$$ $$b \in \mathbb{N}; b > 1$$ $$c \in \mathbb{Z}; c \neq 0$$ then given a set of primes $\{s_{1},...,s_{k}\}$. There exists a prime $q \not \in \{s_{1},...,s_{k}\}$ and an integer $s$ so that $q | ab^s+c$.

$\textbf{Proof:}$ Suppose that this is not the case. Note that by lemma two $M(s_{j},ab^{u_{k}+v_{k}t}+c)$ is fixed for a fixed $j$ and variable $t \in \mathbb{N}\cup \{0\}$. Thus we must have $ab^{u_{k}+v_{k}0}+c = ab^{u_{k}+v_{k}1}+c = ...$ which is impossible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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