如何证明哈希函数h(x)=x²mod 4只产生0和1

让我们先讨论偶数, 2n (其中 n 是自然数):

(2n) 2 = (2n)(2n) = (2)(n)(2)(n) = (2)(2)(n)(n) = 4n 2 = 4(n 2 )

这是四的精确倍数,所以余数除以四时 总是 为零。

现在让我们讨论奇数, 2n + 1 :

(2n + 1) 2 = (2n + 1)(2n + 1) = (2n)(2n) + (2n)(1) + (1)(2n) + (1)(1) = 4n 2 + 2n + 2n + 1 = 4n 2 + 4n + 1 = 4(n 2 + n) + 1

这正好比四的倍数多一倍,所以余数除以四会 总是 做一个。

现在,让我们看看任何既不是偶数也不是偶数的自然数 也没有 古怪的

等等,那里 不是的 任何我想这意味着我们完成了:-)

在有人指出某些语言可能会 消极的 当参数为负数时,这实际上不适用于这里,因为自然数的平方永远不会 是 消极的