Finding values of quotient and remainders for Gaussian integers.

Question

There is an example copied from example at page 6 of this, that states example of dividend of $3+2i$, divisor of $-1+3i$, and states that as long as the $N_r \lt N_b$, (with $r$ denoting remainder, $b$ the dividend) can compute by division algorithm non-unique set of values of quotient and remainder. The example has dividend as : $3 + 2i$ with norm = $13$, divisor as : $-1 + 3i$ with norm = $10$, and multiplying the fraction with conjugate of the denominator(divisor) yielding : $\frac{3}{10} + i\frac{-11}{10}$.

The first set of values derived is : $q = -i, r = i$. There is derivation of the first set of values by the ratio of $3/10$ being closer to $0$, & of $-11/10$ being closer to $-1$, leading to quotient of $-i$.

The alternate value set suggested is: $q = 1-i$, $r= 1-2i$, as the norm of remainder $\lt$ than that of divisor.
$(-1 + 3i)(1-i) + (1-2i) \implies (-1 +4i +4) + (1 -2i) = 3 +2i$.

There is no clue to me how to check for different such quotients. Can I take any quotient for any non prime dividend with $N_a \gt N_b, \text{ with } (a$= dividend), and it will always succeed (as I always expect: $N_r \lt N_b$). So, the first step should be the check of dividend being not a prime. But, how? I mean the check should be $(a+bi)(x+yi) = 3 + 2i$, and its conjugate $(a-bi)(x-yi) = 3 - 2i, \exists a,b,x,y \in \mathbb {Z}$. This should lead to :$$ \begin{align} & (a+bi)(x+yi) = 3 + 2i & \ (a-bi)(x-yi) = 3 - 2i \\ & (a^2 + b^2)(x^2 + y^2) =13 \\ \end{align} $$ which to me leads nowhere, as $13$ cannot be factorized into product of two non-unit factors.

Please tell me where I am wrong, as it is not possible to consider the ratio of $a/b$ to be considered for checking primality. So, what is wrong? Totally confused!

Answer 1

Let's say you want to check with dividend $5+i$ (norm $26$) and divisor $1+2i$ (norm $5$). First, we carry out the division this way:

$$\frac{5+i}{1+2i}=\frac{5+i}{1+2i}\cdot\frac{1-2i}{1-2i}=\frac{7-9i}{5}=\frac75-\frac95i$$

Now, we have $\frac75$ between $1$ and $2$, and we have $-\frac95$ between $-2$ and $-1$. Thus, in principle, we have four options for $q$: $1-2i, 1-i, 2-2i, 2-i$. Usually, we round to the closest integer quotient, because this guarantees that the remainder will be small enough. It will always be true, though, that at least two of these work, assuming there is a non-zero remainder. In some cases, all four will work.

With this example, the closest quotient is $1-2i$. Since $|\frac75-1|=\frac25$, and $|\frac95-(-2)|=\frac15$, we can calculate $(\frac25)^2+(\frac15)^2=\frac15$, so the remainder will have norm $\frac15$ that of the divisor. Indeed, $5+i=(1-2i)(1+2i)+i$, so the norm of the remainder is $1$.

If we choose the "worst case scenario", and go with $2-i$ as our quotient, then the same calculation leads to $(\frac35)^2+(\frac45)^2=1$, so the remainder in that case will be no smaller than the divisor, so that doesn't work for the division algorithm. The other three options, though, are all good.

Does this help?

Answer 2

The idea here is borrowed from the same idea when dividing integers: the quotient must be close to the "real" (rational) quotient, and this makes the remainder small.

For example, $7:3=2.333333\ldots $ exactly. You want the quotient to be the whole number, so you round it, or truncate it - in effect approximate it with a whole number. Here it is going to be 2 (though 3 is not a bad approximation, either).

However, multiplying back, you don't get 7 back: $2\times 3=6$, or $7=2\times 3+1$, where 1 is the remainder. It is small, because the approximation was good. Generally, if you divide $a\in \mathbb Z $ with $b\in \mathbb Z, b\ne 0$, you can always pick a whole $q\in\mathbb Z $ such that $|\frac {a}{b}-q|\lt 1$, where $\frac {a}{b}$ is the "real" (rational) quotient and $q $ is a good approximation (a nearby integer). Thus, $|a-bq|\lt |b|$, and let's now call this number $r=a-bq $ a remainder, you will have $a=bq+r $ with $|r|\lt|b|$.

Back to the Gaussian integers... It is just the same as above, except that all the numbers are complex. For example, divide $a=7+3i$ by $2-i$:

$$\frac {7+3i}{2-i}=\frac {(7+3i)(2+i)}{(2-i)(2+i)}=\frac {11+13i}{5}=2.2+2.6i $$

Now, pick one Gaussian integer "close" to this. Make sure the distance (the modulus of the difference) is less than 1 (as in the real case).

The four Gaussian integers "surrounding" your quotient are: $2+2i, 2+3i, 3+2i$ and $3+3i$. Some may be too far:

• $|(2.2+2.6i)-(2+2i)|=|0.2+0.6i|=\sqrt{0.4}\lt 1$
• $|(2.2+2.6i)-(2+3i)|=|0.2-0.4i|=\sqrt{0.2}\lt 1$
• $|(2.2+2.6i)-(3+2i)|=|-0.8+0.6i|=\color {red}{\sqrt{1}= 1}$
• $|(2.2+2.6i)-(3+3i)|=|-0.8-0.4i|=\sqrt{0.8}\lt 1$

So, $3+2i $ is too far, but the other three are just fine, and any of them can serve as a quotient. Pick the first one, for example, and the remainder is $(7+3i)-(2-i)(2+2i)=1+i$ with $|1+i|\lt |2-i|$.

That is pretty much it!

Note: throughout I've used the modulus of a complex number: $|a+bi|=\sqrt {a^2+b^2}$. In your book, they use the square of it, i.e the norm is given as $N (a+bi)=a^2+b^2=|a+bi|^2$. This doesn't change the above logic at all, not even a single bit. However, the norm will later turn out to be more useful than the modulus:

• The norm of a Gaussian integer is itself an integer, and the properties of a Gaussian integer are linked to the properties of its norm.
• The norm can be generalised to other number rings, e.g. to numbers of the form $a+b\sqrt {2}$ ($a,b\in\mathbb Z$), where $N (a+b\sqrt {2})$ can be taken to be $a^2-2b^2$.