Let $n=2^km\ \ ,k\ge1$ be a positive integer with $m$ odd ($>1$ )and $r$ the greatest prime that divides $m$. Now, are there $\frac{r-1}{2}$ numbers $a_i$, less than $\frac{n}{2}$ and coprime to $n$ that $\textbf{do not}$ satify the congruence $$a_{i_1}\equiv a_{i_2}\pmod r$$
I think yes. The numbers $a_i$ are also coprime to $r$. The congruence implies that differences of $a_i$s are all multiples of $r$ less than $n$. There are $\lfloor\frac{n}{2r}\rfloor$ multiples of $r$ less than or equal to $\frac{n}{2}$. Now, $a_{i_1}$ and $a_{i_2}$ are just partitions of the $\lfloor\frac{n}{2r}\rfloor$ multiples of $r$ into two coprime parts. Are there $\frac{r-1}{2}$ such partitions? Any hints? Thanks beforehand.