I have to prove one thing that combines logical xor and arithmetical sum of binary representation of some numbers.
Specifically, I need to prove that there exist no solution for a following equation.
$$
(a_1 \times 2^{k + i}) \oplus 2^m \mod 2^{k+i} = 0
$$
For any given $a_1, k, i, m$.
Here $+$ is an arithmetical sum, $\times$ is a multiplication, $\oplus$ is xor on binary representation of operands.
I assume that I can write a program which tries all possible combinations of parameters in a given range, but I'm curious if it is possible to find an analytical solution.
Best Answer
Note that xor'ing with $2^m$ simply inverts the $m+1$-th binary digit from the right, and $\!\! \mod 2^{k+i}$ simply trunctates the binary number to the last $k+i$ binary digits. $a_1\times 2^{k+i}$ ends with $k+i$ zeroes, so all the equation requires is that $2^m$ ends with $k+i$ zeroes as well, that is $m\ge k+i$.