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 5 of 5: The 2 modulo 4 case is impossible
Previous stepNext step
n=4m+2>6:2m+1∣n,gcd⁡(2m+3,n)=gcd⁡(2m+5,n)=1n=4m+2>6:\quad 2m+1\mid n,\quad \gcd(2m+3,n)=\gcd(2m+5,n)=1
Detailed analysis

For n=4m+2, the number 2m+1 divides n. On the other hand, gcd(2m+3,n) divides 4 and is odd, while gcd(2m+5,n) divides 8 and is odd; both are therefore 1. Since n>6, both numbers are below n. They occur in the progression and differ by 2, so d divides 2; d=1 would include 2m+1, and d=2 would also include this odd number. Either way it contradicts its non-coprimality with n.