设m,n∈ℤ且m|n，证明映射f:ℤₙ*→ℤₘ*是满射（求提示）

先把核心目标明确下来：要证明这是满射，就是要对任意 ( b \in \mathbb{Z}_m^* )，都能找到 ( a \in \mathbb{Z}_n^* ) 使得 ( f(a \mod n) = b \mod m )。翻译成整数条件就是：找一个整数 ( a ) 满足：

1. ( a \equiv b \pmod{m} )
2. ( \gcd(a, n) = 1 )

给你几个逐步推进的思考方向：

• 先利用整除关系拆解互质条件
  因为 ( m \mid n )，设 ( n = m \cdot k )（k是整数）。那么 ( \gcd(a, n) = \gcd(a, m \cdot k) )。由于 ( b \in \mathbb{Z}_m^* )，所以 ( \gcd(b, m) = 1 )；再结合 ( a \equiv b \pmod{m} )，可得 ( \gcd(a, m) = \gcd(b, m) = 1 )。这时候，我们只需要额外保证 ( \gcd(a, k) = 1 )，就能推出 ( \gcd(a, n) = 1 ) 了。

• 构造符合要求的a
  考虑形如 ( a = b + t \cdot m ) 的数（t是整数），我们的目标变成找某个t，使得 ( \gcd(b + t \cdot m, k) = 1 )。这里可以用两个思路简化：

  • 假设 ( d = \gcd(m, k) )，因为 ( \gcd(b, m) = 1 )，所以 ( \gcd(b, d) = 1 )（毕竟d是m的因数）。那么 ( b + t \cdot m \equiv b \pmod{d} )，天然和d互质。接下来只需要让它和 ( k/d ) 互质——由于m和 ( k/d ) 互质，这个表达式 ( b + t \cdot m ) 在模 ( k/d ) 上可以取遍所有剩余类，必然存在一个t让它等于某个与 ( k/d ) 互质的数，这样整体就和k互质了。
  • 或者用鸽巢原理：模k的剩余类里，与k互质的元素有 ( \phi(k) ) 个，而 ( b + t \cdot m ) 模k的取值是一个公差为m的等差数列，由于m和k的公因数d与b互质，这个数列里不会有重复的模k剩余类，且必然覆盖到至少一个与k互质的剩余类。

• 更直观的小结论
  你可以回忆一下：如果 ( m \mid n )，那么模n中与m互质的剩余类，在模m下会覆盖所有与m互质的剩余类——而我们要找的就是其中同时与k互质的那个元素，这样的元素一定存在，因为与m互质的剩余类在模k上是“均匀分布”的，不会全部和k有公因数。

内容的提问来源于stack exchange，提问作者Davide Gallo