Exercise 1.2.45 (Strange decomposition into base $3$)

Prove that any positive integer is uniquely expressed in the form

a = 3 m + b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 0

where each b j = 0 , 1 , or − 1 .

Answers

Proof. This is not the usual decomposition of a into base 3 , because some digits may be negative (and b m = 1 ).

∙ We prove the existence of such a decomposition. If a = 1 , then a = 3 0 , and if a = 2 , then a = 3 1 − 1 , thus 1 and 2 have the waited representation.

Let a ≥ 2 . Reasoning by in induction, assume that every positive integer k < a has a decomposition in the form

k = 3 l + c l − 1 3 l − 1 + c l − 2 3 l − 2 + ⋯ + c 0 , c j ∈ { − 1 , 0 , 1 } ,

where l depends on k .

By Problem 20, a is of the form a = 3 k + r , where r ∈ { − 1 , 0 , 1 } (the integers 3 k + 2 are of the form 3 k ′ − 1 , where k ′ = k + 1 ). Then a − 1 ≤ a − r ≤ a + 1 , thus k ≤ a + 1 3 < a , and k ≥ a − 1 3 > 0 , since a ≥ 2 . We may apply the induction hypothesis to k , so

a = 3 ( 3 l + c l − 1 3 l − 1 + c l − 2 3 l − 2 + ⋯ + c 0 ) + r = 3 l + 1 + c l − 1 3 l + c l − 2 3 l − 1 + ⋯ + c 0 3 + r = 3 m + b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 1 3 + b 0 ,

where m = l + 1 , b i = c i − 1 ∈ { − 1 , 0 , 1 } if 1 ≤ i ≤ m − 1 , and b 0 = r ∈ { − 1 , 0 , 1 } .

The induction is done, so every positive integer a is expressed in the form

a = 3 m + b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 0 .

∙ Now we prove the unicity of this decomposition. Suppose that

a = 3 m + b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 0 = 3 n + c n − 1 3 n − 1 + c n − 2 3 n − 2 + ⋯ + c 0 .

Then

| ∑ i = 0 m − 1 b i 3 i | ≤ ∑ i = 0 m − 1 | b i | 3 i ≤ ∑ i = 0 m − 1 3 i = 3 m − 1 2 ,

and similarly

| ∑ i = 0 n − 1 c i 3 i | ≤ 3 n − 1 2 .

Therefore

3 n − 3 n − 1 2 ≤ a ≤ 3 m + 3 m − 1 2 ,

thus

3 n 2 < 3 n − 3 n − 1 2 ≤ a ≤ 3 m + 3 m − 1 2 ≤ 3 2 3 m ,

thus 3 n < 3 m + 1 , so n < m + 1 , where n , m are integers, so that n ≤ m . Exchanging the roles of n and m , we obtain similarly m ≤ n , so m = n is proved. Then

b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 0 = c m − 1 3 m − 1 + c m − 2 3 m − 2 + ⋯ + c 0 .

Assume for the sake of contradiction that ( b m − 1 , b m − 2 , … , b 1 , b 0 ) ≠ ( c m − 1 , c m − 2 , … , c 1 , c 0 ) , and let i ∈ [ [ 0 , m − 1 ] ] be the least index for which b i ≠ c i . Then

b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b i 3 i = c m − 1 3 m − 1 + c m − 2 3 m − 2 + ⋯ + c i 3 i ,

and

b m − 1 3 m − 1 − i + b m − 2 3 m − 2 − i + ⋯ + b i = c m − 1 3 m − 1 − i + c m − 2 3 m − 2 − i + ⋯ + c i .

Then 3 ∣ b i − c i , where b i , c i ∈ { − 1 , 0 , 1 } , hence b i = c i , in contradiction with the definition of i . This contradiction shows that ( b m − 1 , b m − 2 , … , b 1 , b 0 ) = ( c m − 1 , c m − 2 , … , c 1 , c 0 ) . This proves that the decomposition is unique. □

Note : These python functions return the representation of an integer n , following the algorithm of this solution. The first is recursive, the second iterative. The function ”value” computes the inverse operation.

def representation(n):
    if n == 1:
        return [1]
    else:
        r , q = n % 3, n // 3
        if r == 2:
            r -= 3
            q += 1
        l = representation(q)
        l.append(r)
        return l

def value(l):
    s = 0
    power = 1
    while l != []:
        s += power * l.pop()
        power *= 3
    return s

n = 1234567891
l = representation(n); print(l)
print(value(l))

       
        [1, 0, 1, -1, -1, 0, 0, 1, 0, 1, -1, -1, -1, 0, -1, 1, 0, -1, 0, 1]
        1234567891

def repr(n):
    l = []
    while n != 0:
        r , q = n % 3, n // 3
        if r == 2:
            r -= 3
            q += 1
        l.append(r)
        assert (n-r) % 3 == 0
        n = (n - r) // 3
    l.reverse()
    return l

                                                                  

                                                                  
n = 1234567891
print(repr(n))

         [1, 0, 1, -1, -1, 0, 0, 1, 0, 1, -1, -1, -1, 0, -1, 1, 0, -1, 0, 1]

User profile picture
2024-10-02 11:04
Comments
  • Hi Richard, this looks good with 2 typos after words "apply the induction hypothesis to k, so" a = etc ... there are powers to m-2 and m-1 that should be l-2 and l-1, respectively. Those are the only typos I can see.
    BretSherfinski • 2025-03-08
  • Observation: 0(3^1)+0=3^{0}-1 = 0. Therefore, the result may not apply to 0. No information about m is declared in the statement of the problem.
    BretSherfinski • 2025-03-08
  • Thank you Richard for proving that m=n for the uniqueness. I have spent more time on this problem than expected. There is a small problem further along in the proof. In particular, how do we know that m-1-i>0 in showing 3 divides b_i-c_i ? This can be easily fixed but I wanted to make you aware of this. We don't need to introduce the word degree(of a polynomial) but the representation is indeed unique which I will attempt to complete by an induction argument. I apoligize for not being able to type mathematically here. I am very new to this website.
    BretSherfinski • 2025-03-08
  • The typos are corrected.
    richardganaye • 2025-03-10
  • The statement specifies that $a$ is a positive integer, which means generally (and particularly in NKM) that $a>0$, so we don't have to consider the case $a = 0$. Your interesting counterexample shows that one cannot extend the uniqueness result to $a \in \mathbb{N} = \{0, 1, 2,\ldots\}$, but note that in the statement, all powers of $3$ are distinct, and this is not the case in the representation $0 = 3^0 - 1 = 3^0 - 3^0$. (If $a = 0$, the algorithm given in the note returns an empty list).
    richardganaye • 2025-03-10
  • If $m - i - 1 = 0$, then the sums contains a unique term $b_i$ in the left member and $c_i$ in the right member, so $3 \mid b_i - c_i = 0$. If we write the sum with a symbol $\sum$, then the sum is written $\sum\limits_{j= 0}^{m-i+1} b_{m-1-j}3^{m-1-i-j} \equiv b_i \pmod 3$. Here I prefer to write $b_{m-1} 3^{m-1-i} + b_{m-2} 3^{m-2-i} + \cdots + b_i$ which is more readable, being understood that this sum contains only the term $b_i$ if $m-1-i = 0$. I don't think this is an obstacle to understanding the solution.
    richardganaye • 2025-03-10
  • The proof of existence or unicity by induction in the usual representations of integers may start from the lower powers or start from the higher powers (teachers in primary school may use one method or the other). The defect of my solution is that it mixed the two approaches. I think that $3^m$ is not a particular term, as we see in the algorithm which computes the coefficients $b_i$. It turns out that $b_m = 1$ is always true, even if we don't explicitly ask it in the program. So I will rewrite another shorter proof of unicity, without showing first that $n = m$.
    richardganaye • 2025-03-10
  • I have no exclusive rights to these solutions! If you want to give an alternative solution, it is easy to insert it on the site "solverer". It suffices to click on the button "add new solution", and paste some latex code (without "begin document", "end document"). I have been visiting this website for less than a year, and, although I am a "boomer", I was able to use it easily.
    richardganaye • 2025-03-10

Another proof for the part "unicity".

Proof. Suppose that a > 0 and

a = 3 m + b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 0 = 3 n + c n − 1 3 n − 1 + c n − 2 3 n − 2 + ⋯ + c 0 ,

where b i ∈ { 0 , 1 , − 1 } , c i ∈ { 0 , 1 , − 1 } .

We may assume without loss of generality that m ≥ n (otherwise, we exchange the roles of m and n ). Then

a = ∑ i = 0 m b i 3 i = ∑ i = 0 m c i 3 i , (1)

where b m = 1 , c n = 1 and c i = 0 if n < i ≤ m (if such indices i exist).

We prove by induction that b i = c i for all i ∈ [ [ 0 , m ] ] .

Consider the proposition

𝒫 ( l ) : ∀ ⁡ j ∈ [ [ 0 , l ] ] , b j = c j

defined for 0 ≤ l ≤ m .

First

b 0 ≡ ∑ i = 0 m b i 3 i ≡ ∑ i = 0 m c i 3 i ≡ c 0 ( mod 3 ) ,

thus b 0 ≡ c 0 ( mod 3 ) , where b 0 ∈ { 0 , 1 , − 1 } , c 0 ∈ { 0 , 1 , − 1 } , so b 0 = c 0 .

Suppose now that 𝒫 ( l ) is true for some integer l < m , so that

( b 0 , b 1 , … , b l ) = ( c 0 , c 1 , … , c l ) .

is true. Then the equality (1) becomes

∑ i = l + 1 m b i 3 i = ∑ i = l + 1 m c i 3 i ,

and after division by 3 l + 1 , the equality (1) gives

∑ i = l + 1 m b i 3 i − l − 1 = ∑ i = l + 1 m c i 3 i − l − 1 , (2)

or equivalently, with the change of index k = i − l − 1 ,

∑ k = 0 m − l − 1 b l + k + 1 3 k = ∑ k = 0 m − l − 1 c l + k + 1 3 k , (3)

Then

b l + 1 ≡ ∑ k = 0 m − l − 1 b l + k + 1 3 k ≡ ∑ k = 0 m − l − 1 c l + k + 1 3 k ≡ c l + 1 ( mod 3 ) ,

thus b l + 1 ≡ c l + 1 ( mod 3 ) , where b l + 1 ∈ { 0 , 1 , − 1 } , c l + 1 ∈ { 0 , 1 , − 1 } , so b l + 1 = c l + 1 . This shows that 𝒫 ( l + 1 ) is true.

The induction is done, which proves that b j = c j for all j ∈ [ [ 0 , m ] ] .

Since b m = 1 , we obtain c m = 1 , so n = m , and the two representations are identical. □

User profile picture
2025-03-10 10:36
Comments
  • Richard, I appreciate all the work you are doing here and thankful to have this resource. This is helping me pickup Number Theory Studies in a serious way again. I will take back the comment about there being a problem. I will make my first attempt to contribute by expanding your ideas and adding another proof on my own.
    BretSherfinski • 2025-03-13

The author has not declared any information about m , but when m ≥ 1 there can be no representation of 0 .

....so m=n. Then

b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b 0 = c m − 1 3 m − 1 + c m − 2 3 m − 2 + ⋯ + c 0

If m − 1 = 0 then the above equation becomes b 0 = c 0 ensuring uniqueness. If m − 1 > 0 assume for the sake of contradiction that ( b m − 1 , b m − 2 , … , b 1 , b 0 ) ≠ ( c m − 1 , c m − 2 , … , c 1 , c 0 ) and let i ∈ [ 0 , m − 1 ] be the least index for which b i ≠ c i . Then

b m − 1 3 m − 1 + b m − 2 3 m − 2 + ⋯ + b i 3 i = c m − 1 3 m − 1 + c m − 2 3 m − 2 + ⋯ + c i 3 i

and

b m − 1 3 m − 1 − i + b m − 2 3 m − 2 − i + ⋯ + b i = c m − 1 3 m − 1 − i + c m − 2 3 m − 2 − i + ⋯ + c i

If i = m − 1 then b m − 1 = c m − 1 , contrary to the choice of i . Therefore, for such an i the inequality i < m − 1 must hold. Furthermore, if b j = c j for every i < j ≤ m − 1 , the equation above would still force b i = c i , so for some j where i < j ≤ m − 1 we must conclude b j ≠ c j . Nevertheless, even with such j the equation above yields 3 ∣ b i − c i where b i , c i ∈ { − 1 , 0 , 1 } hence b i = c i , contradicting the definition of i . This argument shows that no such i exists and establishes that ( b m − 1 , b m − 2 , … , b 1 , b 0 ) = ( c m − 1 , c m − 2 , … , c 1 , c 0 ) . This proves that the decomposition is unique.



Another proof of unicity: Assume we had

3 m + a m − 1 3 m − 1 + ⋯ + a 0 = 3 n + b n − 1 3 n − 1 + ⋯ + b 0

two different representations of the same number and have it be the example that has the smallest maximal power of 3 , say m . Looking at each side, all summands are divisible by 3 except a 0 and b 0 . Therefore, 3 ∣ a 0 − b 0 . But since these two numbers are each 0 , 1 or − 1 , that shows that in fact a 0 = b 0 . Subtracting them from each side and dividing by 3 gives

3 m − 1 + a m − 1 3 m − 2 + ⋯ + a 2 3 + a 1 = 3 n − 1 + b n − 1 3 n − 2 + ⋯ + b 2 3 + b 1 ,

and this example has a smaller maximal power of 3 , namely m − 1 . This contradiction shows there cannot be two different representations of the same number.

User profile picture
2025-03-13 02:11
Comments
  • Hi Bret. I agree with your writing. Your contributions are welcome.
    richardganaye • 2025-03-13