Proof any arithmetic progression coprime count same as toting function of n

Question

Euler's totient function of n gives us the number of integers coprime to n that are less than or equal to n and greater than or equal to 1. Clearly the arithmetic progression {d, 2d, ..., nd} with common difference d and length n has a count of integers coprime to n equal to the totient function of n if d is already coprime to n. However I am having trouble proving that any arithmetic progression is also equal to totient function of n. That is, why is the count of integers coprime to n for {a+d, a+2d, ..., a+nd} the same as the totient function of n, where a can be any integer and d is coprime to n? I tried both simple and strong induction but it doesn't work.

Answer 1

To tackle this problem, we will use three facts.

1) Look at {$d, 2d, \cdots, nd$} (mod $n$). Then since $n$ is coprime to $d$, this will be simply a permutation of {$1, 2, \cdots, n$} [e.g., we can go from the first to the second by multiplying by $d^{-1}$ (mod $n$)].

2) {$a+1, a+2, \cdots, a+n$} is also a permutation of {$1, 2, \cdots, n$} (mod $n$). [e.g., we can go from the first to the second by adding $-a$ (mod $n$)].

3) Given $k\in\Bbb Z$, $a + kn$ is coprime to $n$ if and only if $a$ is.

Proof: Suppose $a$ is NOT coprime to $n$. Then there exists $c=$GCD($a, n$)$>1$ so that $a = cd$ and $n=ce$ for some $d, e\in\Bbb N$. Then $a+kn=cd+kce = c(d+ke)$, and $n=ce$; so $c>1$ divides the GCD($a+kn,n$), and so $a+kn$ is NOT coprime to $n$.

Conversely, if $a+kn$ is NOT coprime to $n$ then let $a'=a+kn$. By the argument above, $a'+(-k)n=a$ is NOT coprime to $n$ as well. Therefore, $a$ is coprime to $n$ iff $a+kn$ is coprime to $n$.

This implies that we can reduce a set (mod $n$) without affecting the number of integers that are coprime to $n$. So, let us count the number of integers in {$a+d, a+2d, \cdots, a+nd$} coprime to $n$.

• Since given $k\in\Bbb Z$, $a+kn$ is coprime to $n$ if and only if $a$ is coprime to $n$, then this number will equal the number of integers in {$a+d, a+2d, \cdots, a+nd$} (reduced mod $n$) coprime to $n$.

• Since {$a+d, a+2d, \cdots, a+nd$} is a permutation of {$d, 2d, \cdots, nd$} (mod $n$), then this number will equal the number of integers in {$a+d, a+2d, \cdots, a+nd$} (reduced mod $n$) coprime to $n$.

• Since {$d, 2d, \cdots, nd$} is a permutation of {$1, 2, \cdots n$} (mod $n$), then this number is equal to the number of integers in {$1, 2, \cdots, n$} coprime to $n$.

• Therefore, by definition of $\phi(n)$, the number we are looking for equals $\phi(n)$.