Arithmetic Progression modulo $2018$

Let's consider the generalized version of the problem, replacing $2017$ , the first term of AP, with $b_1$ and $2018$ , the divisor, with $M$ ; and let me show that─

Let $b_i$ denote $i$ -th term of the AP: $b_1, b_1+n, b_1+2n, \ldots \ldots \ldots$ . Every non-negative integers from $0$ to $(M-1)$ is a possible remainder of $b_i$ when divided by $M$ if and only if $M$ and $n$ are coprime to each other. ( $b_1, n, M$ are integers).

---

Proof :

• Let $b_p$ and $b_q$ be two different terms of the AP, such that they give same remainders when divided by $M$ . So, $(b_p-b_q)$ is divisible by $M$ .
• $b_p=b_1+(p-1)n$ and $b_q=b_1+(q-1)n$ .
• $b_p-b_q=(p-q)n$ .
• As $(b_p-b_q)$ is divisible by $M$ . $(p-q)n$ is divisible by $M$ .
• Now, if $n$ and $M$ are coprime, then $p-q$ have to be divisible by $M$ . So, each of any consecutive $M$ terms of the AP will have remainder different from other $(M-1)$ terms So, every non-negative integers from $0$ to $(M-1)$ will occur as remainders. That proves the if part.
• I don't like typing much and I believe, at this point anyone can prove the only if part.

---

So, to solve the problem, we have to find number of positive integers $n\leq 2018$ such that $n$ and $2018$ are coprime. Yes, we need $\phi (2018)$ , when $\phi ()$ is the Euler's Totient Function .

Hence the answer is $\phi (2018) = \phi(2 \times 1009) = \phi(2) \times \phi(1009) = 1 \times 1008 = \boxed{1008}$ .

Relevant wiki: Euler's Totient Function

The possible remainders of $b_{i}$ are each respectively congruent to $k * gcd(n, 2018) + 2017 (mod \ 2018)$ , for some $k \in \mathbb{Z}$ .

From this, it can be seen that $gcd(n, 2018) = 1$ if the conditions are to be met.

So the number of different values for $n$ is $φ(2018)$ , where $φ(n)$ is Euler's Totient (phi) Function.

As $φ(mn)=φ(m)φ(n)$ where $gcd(m,n) = 1$ ;

And $gcd(2,1009) = 1$ ;

And $φ(p) = p - 1$ when $p$ is prime;

$φ(2018) = φ(2)φ(1009) = 1 * 1008 = 1008$

Generalisation: For an initial term $a$ and a divisor $b$ , the number of different values for $n$ is always $φ(b)$ , irrespective of $a$ .