Divisibility

Divisibility means one integer divides another with no remainder: a mod b is the remainder when $a$ is divided by $b$. The key trick for this chapter is to work with remainders instead of full numbers. If a mod m = r and b mod m = s, then (a+b) mod m = (r+s) mod m and (ab) mod m = (rs) mod m. Powers repeat in cycles: compute a^1, a^2, a^3, mod m until a remainder repeats, then use the cycle length to find any higher power. For divisibility by 9, a number has the same remainder mod 9 as the sum of its digits, because 10 mod 9 = 1. Squares mod 4 are always 0 or 1, since $(2k{)}^2=4k^2$ and $(2k+1{)}^2=4k^2+4k+1$.