MathLabs

Problem 2

Let n>6 be an integer and let a1,a2,…,aka_1,a_2,\ldots,a_k be all positive integers less than n and relatively prime to n, in increasing order. If a2−a1=a3−a2=⋯=ak−ak−1>0a_2-a_1=a_3-a_2=\cdots=a_k-a_{k-1}>0, prove that n is either a prime or a power of 2.
Step 2 of 5: Odd n forces n to be prime
Previous stepNext step
n odd ⟹ 1,2 are reduced ⟹d=1 ⟹n primen\text{ odd}\ \Longrightarrow\ 1,2\text{ are reduced}\ \Longrightarrow d=1\ \Longrightarrow n\text{ prime}
Detailed analysis

If n is odd, both 1 and 2 are relatively prime to n. Thus d divides 2−1=1, so d=1. The arithmetic progression then contains every positive integer below n; hence every such integer is relatively prime to n. A composite n would have a proper divisor below n, contradiction.