Numerical answer
Let be the number of integers with for which is odd and also divisible by . Find .
Show answer and solution
Answer: 6
Odd: by Lucas' theorem (base 2), is odd iff the binary digits of are dominated by those of . This has three 1-bits, so values of : .
Not divisible by 3: by Lucas (base 3), , and iff each base-3 digit of is at most the matching digit of . Among the eight values above, only and satisfy this (for example has digit in the place where has ).
So of the odd values are not multiples of , and .
Not divisible by 3: by Lucas (base 3), , and iff each base-3 digit of is at most the matching digit of . Among the eight values above, only and satisfy this (for example has digit in the place where has ).
So of the odd values are not multiples of , and .
Saved on this device. Sign in or create a free account to keep it on every device.