Modular Arithmetic
Modular arithmetic allows you to calculate efficiently with extremely large integers. When someone writes:
\[32 = 4 \bmod 7\]they mean "the remainder of 32 upon divsion by 7 is 4". To perform modular addition or multiplication with large numbers, we can actually use their remainders and get the same answer as if we used the original large numbers. For example:
\[430 = 3 \bmod 7\] \[748 = 6 \bmod 7\]and if we wanted to know the remainder of 430 + 748 or (430)(748) upon division by 7, we need only add or multiply their remainders! In other words we can calculate:
\[430 + 748 = 3 + 6 \bmod 7 = 9 \bmod 7 = 2 \bmod 7\] \[(430)(748) = (3)(6) \bmod 7 = 18 \bmod 7 = 4 \bmod 7\]Test this yourself! Compute the remainders of 430 + 748 = 1,178 and (430)(748) = 321,640 upon division by 7.