Number of Homomorphisms $ℤ_n→ℤ_m$

hbghlyj

正整数$m,n$, 有多少个映射$f:ℤ_n→ℤ_m,∀a,b∈ℤ_n:f(a+b)=f(a)+f(b)$
例如$n=4,m=2$有2个映射$x\bmod4\mapsto1\bmod2$和$x\bmod4\mapsto x\bmod2$
答:
$f(0+0)=f(0)+f(0)\implies f(0)=0$
设$a=f(1\bmod n)$, 则$∀x∈ℤ_n:f (x)=f(\underbrace{1+\dots+1}_x)=\underbrace{f(1)+\dots+f(1)}_x= ax$.
设$d=\gcd(m,n)$, 则$\gcd(\frac md,\frac nd)=1$,
$$0=f(0)=f(n\bmod n)=an\bmod m\implies m\mid an\implies \frac md\mid a\frac nd\implies\frac md\mid a$$
所以共有$d$个映射:
$$f (x) = ax,\;a=\frac mdk,\;k=0,1,\dots,d-1$$
Gallian 1984

1
2

hbghlyj

相关问题
正整数$m,n$, 有多少个映射$f:ℤ_n^×→ℤ_m^×,f(a\times b)=f(a)\times f(b)$

hbghlyj

相关问题
正整数$m,n$, 有多少个映射$f:ℤ_n→ℤ_m,f(a+b)=f(a)+f(b),f(a\times b)=f(a)\times f(b)$

Czhang271828

hbghlyj 发表于 2023-5-15 23:39
相关问题
正整数$m,n$, 有多少个映射$f:ℤ_n^×→ℤ_m^×,f(a\times b)=f(a)\times f(b)$

$\mathrm{Hom}_{\mathrm{Grp}}(\mathbb Z_n^\times,\mathbb Z_m^\times)$ 的结果比较复杂, 毕竟 $\mathbb Z_n^\times $ 的结构可以直接写出来.

Czhang271828

hbghlyj 发表于 2023-5-15 23:42
相关问题
正整数$m,n$, 有多少个映射$f:ℤ_n→ℤ_m,f(a+b)=f(a)+f(b),f(a\times b)=f(a)\times f(b)$ ...

关于环同态(不必保持单位元) $f:\mathbb Z_n\to \mathbb Z_m$, 有以下事实

1. 显然 $f(1)$ 唯一确定了 $f$.
2. 显然 $nf(1)=0$, 即 $f(1)=\dfrac{mk}{\gcd(m,n)}$, $k\in \mathbb Z$.
3. $f(1)=f(1^2)=f(1)^2$, 即 $f(1)(f(1)-1)\equiv 0\mod m$.

以上条件其实是充要的. 应该是交换代数的常见习题, 证明不难. 综上,
\[
f(1)=x,\qquad x(x-1)\equiv nx\equiv 0\mod m.
\]

数量好像也不难算, 记 $v_p(-)$ 为 $\mathbb N_+$ 的 $p$-进赋值, 即, 使得 $p^k\mid -$ 的最大 $k\in \mathbb N$. 那么 $f$ 的数量为
\[
2^{|\{p\mid v_p(n)\geq v_p(m)\geq 1\}|}.
\]