Gaussian numbers algorithmic operations.

51 Views Asked by At

I have been working with this idea For some time I am struggling for a particular case, but first I will give the idea of this.

Let be $F=\mathbb{Q}[i]$ and let be $\alpha\in F$, therefore $\alpha=\frac{\beta}{n}$ with $n\in \mathbb{N}$ and $\beta=a+bi\in \mathbb{Z}[i]$.

Now, the only operations I can do are

$i)$ $\alpha\mapsto \alpha+\gamma$ for any $\gamma\in \mathbb{Z}[i]$

and

$ii)$ $\alpha\mapsto \frac{1}{\alpha}=\frac{n\overline{\beta}}{N(\beta)}$ where $\overline{\beta}=a-bi$ and $N(\beta)=a^2+b^2$

I can mix the operations in any order I want so, I want to find if with these operations I can get a fraction where the denominator is strictly less than $n$.

I managed to prove that this work in the next cases:

$a)$ $a\equiv b\;(mod\; n)$

$b)$ $a\equiv 0\;(mod\; n)$ or $b\equiv 0\;(mod\; n)$

For $a)$, if $a\equiv b\equiv r\;(mod\; n)$, by using the operation $i)$ we can get the element $\frac{r(1+i)}{n}$ and by operation $ii)$ we have the element $\frac{n(1-i)}{2r}$. We can always find $r\in \mathbb{Z}$ such that $|2r|\leq n$ and therefore we can get our result. In order to work $n$ must be greater than 2.

For $b)$ The idea is using the operation $i)$, we can find $\gamma \in \mathbb{Z}[i]$ such that $\alpha+\gamma$ is equal to $\frac{bi}{n}$ or $\frac{a}{n}$ depending of the case. In either case we can do the operation $i)$ and after that the operation $ii)$ in order to get a fraction whose denominator is strictly less than $n$

I am struggling for the case $a\not\equiv b\;(mod\; n)$. I am considering the case of $n$ is even, therefore by the operation $i)$ we can get an element of the form $\frac{(\frac{n}{2}-\ell)+(\frac{n}{2}-k)i}{n}$ where $\ell\not= k$ and $\ell,k\in\{1,2,\ldots,\frac{n}{2}-1\}$.

From this I have not found anything concrete yet. I have been working in some particular cases and I always get the result and also that works after a finite number of steps.

I think this works since $\mathbb{Z}[i]$ is a norm Euclidean domain but I do not have anything concrete. But I am not sure why.

Any hint or idea might be helpful.

Thank you for your help.

1

There are 1 best solutions below

3
On

We note that if it is true that you can apply these operations to decrease $n$, then repeating this procedure, you can decrease it to the case where $n=1$. That is that you can apply these operations and end up with a Gaussian integer.

I note that the case of $n=2$ you have solved since in this case either $a\equiv b\pmod{2}$ or at least $a\equiv 0\pmod{2}$ or $b\equiv 0\pmod{2}$.

I was able to show the case $n=3$ as follows.

First note that in the case of $\frac{a+bi}{n}$, if $a^2+b^2<n$, then just applying the inverse operation will decrease the denominator.

Let us denote $\beta=a+bi$ and $\gamma=c+di$, then

$$\alpha+\gamma=\frac{a+bi}{n}+c+di=\frac{a+nc+(b+nd)i}{n}$$

Thus, by choosing the appropriate values of $c$ and $d$, we may assume that $\vert a+nc\vert\leq\frac{n}{2}$ and $\vert b+nd\vert\leq \frac{n}{2}$. Thus, we are reduced to the case of $\frac{a+bi}{n}$ where $\vert a\vert\leq \frac{n}{2}$ and $\vert b\vert\leq \frac{n}{2}$. Then we note that in the case $n=3$, we will have that $a^2+b^2\leq 1+1 <3$.

Note: from the comments below, I have an idea of how to go about the $n=4$ case.

As mentioned, we may assume that $a,b\in\{-1,0,1,2\}$, and if both $a,b=2$, then we are done as they are congruent modulo $4$, and in the case that $a\neq 2$ and $b\neq 2$, then $a^2+b^2<4$, so we can take the inverse and are done. The case that requires some work is where one of them is equivalent to $2$ mod $4$ and the other is not equivalent to $2$ mod $4$. We can further restrict ourselves to the case that the other is equivalent to $1$ mod $2$ (since otherwise there is a common factor of $2$ that can be pulled out and decrease the denominator to $2$). Thus, we may assume that we have something of the form $\frac{\pm 1+2i}{4}$ or $\frac{2\pm i}{4}$, and now it is just a finite check, and each of these is solved analogously to the comment below.