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 5 of 5: Combine via CRT to reach the contradiction

Previous step Next step

In plain words

Agreement modulo every prime power factor of n means agreement modulo n itself, but the $a_i$ were chosen to be distinct residues mod n.

a_1 \equiv a_2 \equiv \dots \equiv a_k \pmod n

Detailed analysis

In either case, every $a_i$ is congruent to the same constant ( $0$ or $1$ ) modulo $q$ . Since $q=p^e$ was an arbitrary prime power exactly dividing $n$ , the Chinese Remainder Theorem gives $a_1\equiv a_2\equiv\dots\equiv a_k\pmod n$ . But $a_1,\dots,a_k$ are distinct elements of $\{1,\dots,n\}$ , a complete residue system mod $n$ , so they cannot all be congruent modulo $n$ (as $k\ge2$ ). This contradiction shows the assumption was false, so $n$ does not divide $a_k(a_1-1)$ . $\blacksquare$