Even number of final steps

In the bracketed representations we use on this website, you may notice how the first two numbers have always the same parity. For example,

$10 = \lbrace 5,1 \rbrace &= \frac{2^5 - 2^1}{3} & \mbox{(with 5 and 1 being both odd)} \\ 11 = \lbrace 10,6,3,1,0 \rbrace &= \frac{2^{10} - (2^6 + 3 \cdot 2^3 + 9 \cdot 2^1 + 27)}{81} & \mbox{(with 10 and 6 being both even)}$

Let m > 0 .

If $2^{a_m} - \displaystyle\sum_{i=0}^{m-1} 2^{a_i} 3^{m-1-i}$ is divisible by 3^m , with $a_m > a_{m-1}$ , then $a_m \equiv a_{m-1} \pmod 2$ .

We require m > 0 , so that there are at least two numbers in the representation.

The converse is not true; for a counterexample, note that $2^7 - (2^3 + 3 \cdot 2^1)$ is not divisible by , so $\lbrace 7,3,1 \rbrace$ is not a valid representation.

$2^{a_m} - \displaystyle\sum_{i=0}^{m-1} 2^{a_i} 3^{m-1-i} = 2^{a_m} - 2^{a_{m-1}} - 3 \displaystyle\sum_{i=0}^{m-2} 2^{a_i} 3^{m-2-i}$

If the above is divisible by 3^m it follows that it is also divisible by and, as a result, so is $2^{a_m} - 2^{a_{m-1}}$ . Therefore

$2^{a_m} - 2^{a_{m-1}} = 2^{a_{m-1}} \left( 2^{a_m-a_{m-1}} - 1 \right)$

is divisible by . By Euclid's Lemma, $2^{a_m-a_{m-1}} - 1$ is divisible by , and

$2^{a_m-a_{m-1}} \equiv 1 \pmod 3$

It should be evident at this point that only an even power of could be congruent to modulo , but we will give this a detailed treatment.

By the Division Algorithm, let $a_m-a_{m-1} = 2q+r$ for some integers and , where is either or .

Our goal is to show that r=0 . So far we have

$2^{a_m-a_{m-1}} = 2^{2q+r} = (2^2)^q \cdot 2^r \equiv 1 \pmod 3$

But $2^2 = 4 \equiv 1 \pmod 3$ . By the rules of modular arithmetic, we then have

$1^q \cdot 2^r = 2^r \equiv 1 \pmod 3$

But we know that can only be or , and only r=0 will satisfy the congruence above.

Therefore $a_m-a_{m-1} = 2q$ , and

$a_m \equiv a_{m-1} \pmod 2$

$\square$