Elementary Number Theory - question maybe using modular arithmetic

Question

Let $m$, $k$ be natural numbers. Then show that $$\sum\limits_{\substack{1\le n \le mk \\\gcd(n,m)=1}} 1 =k \sum_{\substack{1\le n \le m\\\gcd(n,m)=1}} 1.$$

I've thought about this question a lot, and it makes sense to me. I think that this is true because every solution to $$\sum_{\substack{1\le n \le m\\\gcd(n,m)=1}} 1$$ is congruent to a solution of $$\sum_{\substack{1\le n \le mk\\\gcd(n,m)=1} }1$$ mod $m$. That said I'm not sure how to formally prove this, or if I'm even on the right track.

Answer 1

Hint:

First, $$\sum\limits_{\substack{1\le n \le mk \\\gcd(n,m)=1}} 1 = \sum\limits_{\substack{1\le n \le m \\\gcd(n,m)=1}} 1 + \sum\limits_{\substack{m+1\le n \le 2m \\\gcd(n,m)=1}} 1 + \cdots + \sum\limits_{\substack{(k-1)m+1\le n \le mk \\\gcd(n,m)=1}} 1.$$ Second, $$\sum\limits_{\substack{(r-1)m+1\le n \le rm \\\gcd(n,m)=1}} 1 = \sum\limits_{\substack{1\le n \le m \\\gcd(n+(r-1)m,m)=1}} 1 = \sum\limits_{\substack{1\le n \le m \\\gcd(n,m)=1}} 1.$$

Answer 2

Hint:

Rewrite each $n$ on the left side as $mi+j$ where $1\leq j\leq m.$ Then your left side becomes:

$$\sum_{i=0}^{k-1}\sum_\limits{\substack{1\leq j\leq m\\\gcd(mi+j,m)=1}} 1$$

And then switch the summations and note that $\gcd(mi+j,m)=\gcd(j,m).$