You probably know the trick that a number is a multiple of 9 if and only...

Transcribed Image Text:

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: 0011bin = 3dec is a multiple of 3, and so is 1100bin = 12dec. However, 100101bin = 37 dec is not a multiple of 3, and neither is 101001bin = 41dec. Hint: First transform this to a statement about regular languages over alphabet {0, 1}. 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: 0011bin = 3dec is a multiple of 3, and so is 1100bin = 12dec. However, 100101bin = 37 dec is not a multiple of 3, and neither is 101001bin = 41dec. Hint: First transform this to a statement about regular languages over alphabet {0, 1}.

Answer rating: 100% (QA)

Requir... View the full answer