Question 4 (Base b expansions). In number theory and computer science we often nd it helpful to express numbers in different bases. If we x an integer b > 1, we can write n E Z, n 2 O, in \"base b\" as: Llogbni _ n: 2 aib', where a,{0,1,...,b1}. i=0 (Notice the base b logarithm simply determines how large a power of b can possibly go into n, and [:13] indicates that we round down the value of :r to largest integer S 51:.) As an example, in binary (or base 2), you can show that 52 = 1101002 (the subscript is often used as a reminder of the base). How do we compute the expansion? We proceed like this: (1) First, compute the remainder of 77. when we divide by b: n = bq + 9". Then 7\" = a0. (2) Let q be our new \"72.,\" call it n' = q. Divide n' = q by b to get a new q', 7" given by n' = bq' + 7". This is al. (3) Repeat this process on the quotient from each division to get the next at,- until we are done, i.e., the quotient is 0. As a warmup, compute the binary (base 2), octal (base 8), and hexadecimal (base 16; use digits a, E {0, 1,2, 3,4,5, 6, 7,8,9,A,B,C, D,E,F} where A is a digit that carries the value of 10, B is 11, etc.) expansions of 2623. Then prove that the base b expansion always exists for every n 2 0 and b > 1, and that the choices of a,- are unique for each n and b. (Hint: First, you need to prove that the process above really results in something that equals n when you plug in the digits you get in the base b expansion. Then to show uniqueness, you will prove your result by induction on 2' for the ith digit, using the uniqueness of the remainder from the division algorithm.)