2018-12-08-模k系统

今天看数字电路，看到一个有趣的电路图：一个一位十进制BCD码加法器 circuit.jpg

(来自西北工业大学教学ppt)
这个电路采用加法来代替取模运算，令人耳目一新。不过也是具有一定的局限性的：
对于一个模k系统，对于n取模(n>=k时不需要考虑，只看n<k时)，对于数a，一个已知在范围k-n~k-1的数进行取模运算时，可以使用加法替代：
a%n=a+n。
是不是很神奇！只能说数字电路的设计真的是难度非常高的一件事。
在我之前写过的一篇博客中提到：(n+1)**k%n=1恒成立(k为任意正整数)。
证明过程用的是二项式展开。同样也是很神奇的一件事！一些相似的感想在下一篇关于CF的博客中写。