___________________________________ BINARY TRAILING ZEROS OF PRODUCTS Leon Rische ___________________________________ [2020-03-11 Wed 22:10] Table of Contents _________________ Let $T(n) = \max \{ k \in \mathbb{N} \mid 2^k | n\}$. This is equivalent to the number of trailing zeros when $n$ is written in binary. - $1 = 1_2$, $T(1) = 1$ - $2 = 10_2$, $T(2) = 1$ - $3 = 11_2$, $T(3) = 0$ - $4 = 100_2$, $T(4) = 2$ - $5 = 101_2$, $T(5) = 0$ - $6 = 110_2$, $T(6) = 1$ - $7 = 111_2$, $T(7) = 0$ - $8 = 1000_2$, $T(8) = 3$ Choose $a'$ so that $a = 2^T(a) a'$ and $2 \nmid a'$. Choose $b'$ so that $b = 2^T(b) b'$ and $2 \nmid b'$. Then $ab = 2^{T(a)} a' 2^{T(b)} b' = 2^{T(a) + T(b)} a' b'$ and $2 \nmid a'b'$, so $T(ab) = T(a) + T(b)$.