Let $z$ be a complex non-zero number such that $Re(z),Im(z)\in \mathbb{Z}$. Prove that $z$ is uniquely representable as $a_0+a_1(1+i)+a_2(1+i)^2+\dots+a_n(1+i)^n$ where $n\geq 0$ and $a_j \in \{0,1\}$ and $a_n=1$. Time allowed for this problem was 1 hour.
Problem
Source: Iran 3rd round 2009 - final exam problem 6
Tags: induction, algorithm, function, trigonometry, number theory unsolved, number theory
15.01.2015 21:49
16.01.2015 00:52
This is actually proven the exact same way one shows that there is a (unique) representation in base $2$ (or $3$, $4$, ...). Which goes like this: Let $R$ be a nice enough set of numbers (exact assumptions left to the less lazy reader and not relevant here anyway) and let $b$ be the base. Let $D=\{d_1, ..., d_r\}$ be the "digits" we will use; for the sake of this post this at least means that they uniquely cover the residue classes $\mod b$; having $0 \in D$ is also a good idea. Note: this depends on $R$, for example we could use $0,1$ if the set is $\mathbb Z$ or $\mathbb N$ with $b=2$, but we would need a larger set, e.g. $0,1,i,1+i$, if the set is $\mathbb Z[i] = \{a+bi | a,b \in \mathbb Z\}$. We want to show that every element of $R$ can be (uniquely) written as $a_0+a_1b+...+a_n b^n$ with $a_i \in D$. Algorithm to show the existence: Let $x$ be the number we want to represent. a) Pick a $a_0 \in D$ such that $x \equiv a_0 \mod b$. b) Write $x = a_0 + bx^\prime$ for some $x^\prime \in R$. c) Go back to a) to represent $x^\prime$ in base $b$ as desired. Obviously, one needs to prove that this actually terminates. For example because we have $|x^\prime| < |x|$ for some suitable function $| \cdot |$ with values in nonnegative integers (e.g. $|a+bi| = a^2+b^2$). Uniqueness: Assume $a_0 + ... + a_m b^m = c_0 + ... + c_n b^n$. Looking $\mod b$ gives that $a_0 \equiv c_0 \mod b$ and thus $a_0 = c_0$. Now subtract them on both sides, divide by $b$ and get $a_1 + ... + a_m b^{m-1} = c_1 + ... + c_{n-1} b^{n-1}$. Rince and repeat.
16.01.2015 01:02
That's exactly my motivation for the proof, I recalled that for natural numbers, and simply modified it in order to have $D=\{0,1\}$ and not $\{0,1,i\}$
21.01.2015 08:04
ZetaX wrote: c) Go back to a) to represent $x^\prime$ in base $b$ as desired. Obviously, one needs to prove that this actually terminates. For example because we have $|x^\prime| < |x|$ for some suitable function $| \cdot |$ with values in nonnegative integers (e.g. $|a+bi| = a^2+b^2$). . $ - 1 = 1 + (i - 1)(1 + i)$, but $\left| { - 1} \right| < \left| {i - 1} \right|$?
21.01.2015 09:20
Nanas wrote: ... $i = 1+ (1+i) + (1+i)^2 + (1+i)^3 + (1+i)^4 + (1+i)^5$ ... No, $1+ (1+i) + (1+i)^2 + (1+i)^3 + (1+i)^4 + (1+i)^5 =$ $ \dfrac {(1+i)^6-1}{(1+i)-1} =$ $\dfrac {-8i-1}{i} =$ $ -8 + i \neq i$. In fact, $1+i = \sqrt{2}\left (\cos \dfrac {\pi}{4} + i\sin \dfrac {\pi}{4}\right )$, so $(1+i)^n = \sqrt{2^n}\left (\cos \dfrac {n\pi}{4} + i\sin \dfrac {n\pi}{4}\right )$, so for $n\geq 2$ the coefficient of $i$ in $(1+i)^n$ is even. Assume now $i = a_0 + a_1(1+i) + a_2(1+i)^2 + \cdots + a_{n-1}(1+i)^{n-1} + (1+i)^n$ for some $n$ and $a_j \in \{0,1\}$ for $0\leq j \leq n-1$. This forces $n\geq 1$ and $a_1=1$, and so $- (1+a_0) = i - a_0 - (1+i) = a_2(1+i)^2 + \cdots + a_{n-1}(1+i)^{n-1} + (1+i)^n$. But $- (1+a_0)\neq 0$, which forces $n\geq 2$ and $1+i \mid - (1+a_0)$, therefore $a_0=1$ and so $- (1+a_0) = -2 = (i-1)(1+i)$. Cancelling $1+i$ we get $i-1 = a_2(1+i) + \cdots + a_{n-1}(1+i)^{n-2} + (1+i)^{n-1}$. This forces $a_2=1$, so $(i-1)(1+i) = -2 = a_3(1+i)^2 + \cdots + a_{n-1}(1+i)^{n-2} + (1+i)^{n-1}$, thus $n\geq 3$ and cancelling $1+i$ we get $i-1 = a_3(1+i) + \cdots + a_{n-1}(1+i)^{n-3} + (1+i)^{n-2}$. This procedure repeats, and leads to an obvious contradiction. Therefore $i$ cannot be so represented, and the problem is wrong as stated.
21.01.2015 14:44
yunxiu wrote: ZetaX wrote: c) Go back to a) to represent $x^\prime$ in base $b$ as desired. Obviously, one needs to prove that this actually terminates. For example because we have $|x^\prime| < |x|$ for some suitable function $| \cdot |$ with values in nonnegative integers (e.g. $|a+bi| = a^2+b^2$). . $ - 1 = 1 + (i - 1)(1 + i)$, but $\left| { - 1} \right| < \left| {i - 1} \right|$? This shows that the usual modulus does not work. I did not check this special problem (as I don't find it particulary interesting), and as mavropnevma shows it is actually wrong.
22.02.2021 00:13
If $(1+i)$ is replaced with $(-1+i)$ everywhere the problem should work. In fact for a fixed $k$, any such $z$ can be uniquely represented as $a_0+a_1(-k+i)+a_2(-k+i)^2+\cdots+a_n(-k+i)^n$ where $a_n \neq 0$ and $a_i \in \{0,1,\ldots n^2\}$.