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$
2
  • $\begingroup$ Are you free to choose the $n$ integers or some of them are previously given? $\endgroup$
    – Stefan4024
    Jun 22, 2016 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, 2016 at 16:56

1 Answer 1

Reset to default
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$
3
  • $\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, 2016 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, 2016 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, 2016 at 4:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .