如何证明哈希函数 h(x) = x² mod 4 只产生 0 和 1
how to prove that the hash function h(x) = x² mod 4 yields only to 0 and 1
如何证明散列函数 h(x) = x² mod 4 仅产生 {0, 1}，其中 x 作为自然数的一个元素？
我们先覆盖偶数，2n（其中n是自然数）：
(2n)<sup>2</sup>
= (2n)(2n)
= (2)(n)(2)(n)
= (2)(2)(n)(n)
= 4n<sup>2</sup>
= 4(n<sup>2</sup>)
这是四的倍数，所以除以四的余数总是为零。
现在让我们覆盖奇数，2n + 1:
(2n + 1)<sup>2</sup>
= (2n + 1)(2n + 1)
= (2n)(2n) + (2n)(1) + (1)(2n) + (1)(1)
= 4n<sup>2</sup> + 2n + 2n + 1
= 4n<sup>2</sup> + 4n + 1
= 4(n<sup>2</sup> + n) + 1
正好比四的倍数多一，因此除以四的余数 总是 为一。
现在，让我们看一下既不是偶数 也不是 奇数的任何自然数。
等一下，没有。我想这意味着我们完成了:-)
并且，在有人指出某些语言可能会在参数为负数时给出 负数 余数之前，这实际上并不适用于此，因为自然数的平方可以永远不会成为负数。
如何证明散列函数 h(x) = x² mod 4 仅产生 {0, 1}，其中 x 作为自然数的一个元素？
我们先覆盖偶数，2n（其中n是自然数）：
(2n)<sup>2</sup> = (2n)(2n) = (2)(n)(2)(n) = (2)(2)(n)(n) = 4n<sup>2</sup> = 4(n<sup>2</sup>)
这是四的倍数，所以除以四的余数总是为零。
现在让我们覆盖奇数，2n + 1:
(2n + 1)<sup>2</sup> = (2n + 1)(2n + 1) = (2n)(2n) + (2n)(1) + (1)(2n) + (1)(1) = 4n<sup>2</sup> + 2n + 2n + 1 = 4n<sup>2</sup> + 4n + 1 = 4(n<sup>2</sup> + n) + 1
正好比四的倍数多一，因此除以四的余数 总是 为一。
现在，让我们看一下既不是偶数 也不是 奇数的任何自然数。
等一下，没有。我想这意味着我们完成了:-)
并且，在有人指出某些语言可能会在参数为负数时给出 负数 余数之前，这实际上并不适用于此，因为自然数的平方可以永远不会成为负数。