如何证明自然数域下哈希函数h(x)=x² mod 4仅输出{0,1}

要搞定这个证明很直观，咱们把自然数拆成偶数和奇数两类分别分析就行——毕竟所有自然数跑不出这两种情况：

情况1：x是偶数 #

如果x是偶数，那它肯定能写成 x = 2k 的形式，这里k是个非负整数（自然数包含0，当x=0时k=0，完全成立）。

计算x的平方：
x² = (2k)² = 4k²

对这个结果取模4：4k² mod 4。因为4k²是4的整数倍，除以4后余数为0，所以x² mod 4 = 0。

情况2：x是奇数 #

如果x是奇数，那它可以表示为 x = 2k + 1，k同样是非负整数。

展开x的平方：
x² = (2k+1)² = 4k² + 4k + 1 = 4(k² + k) + 1

观察这个式子：4(k² + k) 是4的整数倍，加上1之后，整个数除以4的余数就是1。所以x² mod 4 = 1。

结论 #

不管x是偶数还是奇数，x² mod 4的结果只能是0或者1，也就是说哈希函数h(x)的输出必然属于集合{0, 1}。

内容的提问来源于stack exchange，提问作者random-user