You probably know the trick that a number is a multiple of 9 if and only if the sum of its decimal digits is a multiple of 9. Here is a similar trick for multiples of 3 in binary Prove that a number is a multiple of 3 if and only if writing that number backwards in binary is also a multiple of 3. Example: 0011 bin-3dels a multiple of 3, and so is 1100bin-12dec. However, 100 101bin- 37dec is not a multiple of 3, and neither is 101001 bin-41d Hint: First transform this to a statement about regular languages over alphabet {0, 1)