INAMO 2022/5 wrote: Given a natural number $N \ge 2$ and natural numbers $a_1, a_2, \dots, a_{N + 1}$ such that for any index $1 \le i \le j \le N + 1$, \[ a_i a_{i + 1} \cdots a_j \not \equiv 1 \pmod{N} \]Prove that there exists index $i$ such that $\gcd(a_i, N) \not= 1$. We'll actually prove this for any $N$ numbers instead of $N + 1$ numbers (and this bound could be further improved) Let us suppose otherwise, that $\gcd(a_i, N) = 1$ for all the index $i$. Consider the following $N$ numbers \[ a_1, a_1 a_2, a_1 a_2 a_3, \dots, a_1 a_2 a_3 \cdots a_N \]By assumption, none of the above value is equal to $1$ modulo $N$ -- and thus all of them only cover at most $N - 1$ residues modulo $N$. By PigeonHole Principle, there exists $i < j$ such that \[ a_1 \cdots a_i \equiv a_1 \cdots a_j \pmod{N} \]As $\gcd(a_1 a_2 \cdots a_i, N) = 1$, we conclude that $a_{i + 1} \cdots a_j \equiv 1 \pmod{N}$, which is a contradiction, as desired.

Yea it can be improved to $\varphi(N)$ and still have the same method

What a troll problem. This is P5? Too easy. The other problems this day must be too easy as well. /s The following solution is just the same with the above solution, except avoiding a negligible amount of technicality introduced above. Suppose that $\gcd(a_k, N) = 1$ for all $k \leq N + 1$. Consider that by pigenhole principle, there must exist indices $1 \leq i < j \leq N + 1$ such that \[ a_1 a_2 \ldots a_i \equiv a_1 a_2 \ldots a_j \pmod{N}. \]Now since all the $a_k$s are coprime with $N$, one can cancel out $a_1 a_2, \ldots a_i$ from both sides and get a contradiction: \[ a_{i + 1} a_{i + 2} \ldots a_j \equiv 1 \pmod{N}. \] More generally, let $G$ be a finite abelian group (treated multiplicatively), and consider sequences $a_1, a_2, \ldots, a_k$ of elements of $G$. Then we can choose the $a_i$s such that $a_i a_{i + 1} \ldots a_j \neq 1$ for all $i < j$, if and only if $k < |G|$. The proof is essentially the same as #2 for the case $k \geq |G|$. For the other direction, we instead choose the values of the $b_j := a_1 a_2 \ldots a_j$ that satisfies the condition. Indeed, just let $b_0 = 1$, and $b_1, \ldots, b_k$ be arbitrary distinct elements of $G$ not equal to $1$. This is possible by the assumption $k < |G|$. Then take $a_i = b_i b_{i - 1}^{-1}$ for each $1 \leq i \leq k$.

Jeez, what level math is this?