这不是显然？

参考华章系列，数论概貌 有详细证明

设n的最小既约剩余系为a[1],a[2],...,a[φ(n)]
那么对于固定的t，a[i]+tn i=1,2，..,φ(n)也是一组既约剩余系
其中t=1,2,...,m-1
由于m,n互质，所以可取t=kn^(-1) mod(m)，即a[i]+tn≡a[i]+k (mod m).其中k=1,2,...,m-1
可恰好取遍模m的完全剩余系。且对于不同的k, t两两不等。因此只有φ(m)个k可以使得a[i]+tn与m互素。所以
a[i]+t[j]n是模mn的既约剩余系（其中i=1,2,...,φ(n). j=1,2,...,φ(m)）其个数为φ(n)φ(m)