Mar 092016

This is going to be another one of my “selfish” posts – written primarily for me to refer back to in the future and not because I believe it will benefit anyone other than me. The idea is one that I always took for granted but had a hard time proving to myself once I decided to try.

Theorem: Suppose we have an M bit unsigned binary integer with value A. Consider the first (least significant) N bits with value B. Then:

A \equiv B \bmod{2^N}

Put another way, arithmetic with unsigned binary integers of a fixed length N is always performed modulo 2^N.
Continue reading »