3
$\begingroup$

Let $n\ge 3$ be an integer. Prove that there exist positive integers $a_1, a_2, ..., a_n$ other than 1 such that $a_1a_2...\hat a_i...a_n \equiv 1 \pmod {a_i}$, for $i=1,2, ...n$. Here, $\hat a_i$ means the term $a_i$ is omitted.

I am having problems solving this question. I have tried small value since of $n$ up to 5 and honestly have no idea how to solve this rigorously. Help is appreciated thank you!

$\endgroup$
  • $\begingroup$ Are you free to choose the $n$ integers or some of them are previously given? $\endgroup$ – Stefan4024 Jun 22 '16 at 16:21
  • $\begingroup$ For $a_i \le 1000$, the only solution for $n=3$ is $2,3,5$ and for $n=4$ are $2,3,7,41$ and $2,3,11,13$. $\endgroup$ – lhf Jun 22 '16 at 16:56
7
$\begingroup$

$$a_1=2,\quad a_j=\left(\prod_{i=1}^{j-1}a_i\right)+1\ \ (j=2,3,\cdots, n-1),\quad a_n=\left(\prod_{i=1}^{n-1}a_i\right)-1$$ works since, in mod $a_i$ where $i=1,2,\cdots, n-1$, $$\begin{align}a_1a_2\cdots a_{i-1}a_{i+1}\cdots a_n&\equiv a_1a_2\cdots a_{i-1}\cdot1\cdot 1\cdots1\cdot (-1)\\&\equiv -a_1a_2\cdots a_{i-1}\\&\equiv -(a_i-1)\\&\equiv 1\end{align}$$ and, in mod $a_n$, $$a_1a_2\cdots a_{n-1}\equiv a_n+1\equiv 1.$$

$\endgroup$
  • $\begingroup$ I was thinking along the same line, but didn't know how to deal with the case $a_1,$ as I forgot $-1\equiv1\pmod2.$ Nice answer! $\endgroup$ – awllower Jun 22 '16 at 16:49
  • $\begingroup$ @mathlove it is a wonderful solution and a magical construction! By the way, how did you happen to see such a construction? It seems almost as if this question couldn't be solved without foresight? $\endgroup$ – WilliamKin Jun 22 '16 at 17:04
  • 1
    $\begingroup$ @WilliamKin: By trial and error, I got $2,3,5$ for $n=3$, and $2,3,7,41$ for $n=4$. For $n=5$, I set the five numbers as $p,q,r,s,pqrs-1$. Then, I noticed that $s=pqr+1,r=pq+1,q=p+1$ work. Finally, we have to have $-1\equiv 1\pmod p$, from which we have $p=2$. So, I reached the construction I wrote in my answer. $\endgroup$ – mathlove Jun 23 '16 at 4:12

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.