Problem 1

Let

n, k \ge 2

be positive integers and let

a_1, a_2, \dots, a_k

be distinct integers in the set

\{1, 2, \dots, n\}

such that

n

divides

a_i(a_{i+1} - 1)

for

i = 1, 2, \dots, k - 1

. Prove that

n

does not divide

a_k(a_1 - 1)

Step 1 of 5: Assume the divisibility relations close into a cycle

Previous step Next step

In plain words

To contradict distinctness we first turn the open chain of relations into a closed loop by assuming the forbidden divisibility as well.

a_i(a_{i+1}-1)\equiv 0 \pmod n \text{ for } i=1,\dots,k \text{ (indices mod } k\text{)}

Detailed analysis

Suppose, for contradiction, that $n$ also divides $a_k(a_1-1)$ . Combined with the $k-1$ given relations, we now have $a_i(a_{i+1}-1)\equiv 0\pmod n$ for every $i=1,\dots,k$ , where indices are read modulo $k$ so that $a_{k+1}=a_1$ . We will show this forces $a_1,\dots,a_k$ to be pairwise congruent modulo $n$ , contradicting that they are distinct elements of $\{1,\dots,n\}$ .