Let $n = ka + r$ where $0 \le r < a.$ Then, we want to find a positive integer $b$ so that $b$ divides an odd number of $n, n-a, n-2a, \cdots, n-ka.$ If $a = 1$, then we're done by taking $b = \frac{n-1}{2}.$ In any other case, let's consider the smallest $i$ with $n-ia < \frac{n}{2}.$ Then, we know that $n-ia > \frac{n}{4}$ by some simple casework. We claim that $b = n-ia$ actually works. If not, then one out of $2b, 3b$ is in the list $n, n-a, n-2a, \cdots, n-ka$ and the other is not. If $2b$ was in it, then we would have that $n-ja = 2(n-ia)$ for some $j$, which gives us that $n = (2i-j)a$ and so $a | n.$ But since we're assuming $a \neq 1$, this is impossible. If $3b$ was in it, then we would have that $n-ja = 3(n-ia)$ for some $j$, which gives us that $2n = (3i-j)a.$ Therefore, $a|2n$ implies that $a = 2.$ So we now only need to show that there is some positive integer $b < \frac{n}{2}$ which divides an odd number of $1, 3, 5, 7, \cdots, n.$ Letting $b$ be the smallest odd number less than $\frac{n}{2}$ does the job here. $\square$