Arithmetic of Gaussian Integers

Štefan Porubský

Institute of Computer Science AS CR, v.v.i.
Pod Vodárenskou věží 2
182 07 Prague 8
Czech Republic 
email: porubsky@cs.cas.cz

Author was supported by project 1ET200300529 of the program Information Society of the National Research Program of the Czech Republic and by the Institutional Research Plan AV0Z10300504.

Introduction

As the birth certificate of complex numbers is usually taken Ars Magna by G.Cardano which appeared in 1545. He solved here the equation x(10-x)=40 finding 5±(Sqrt[-15]) as its roots. Howvever, he said that  work with them is  “as subtle as it would be useless”, and to work with he described as a “mental torture.” The next milestone was the year 1572 when appeared the L'Algebra by R.Bombieli, who carried out the first calculations with complex numbers. In 1702 Leibniz write that the square root of -1 is "amphibian between existence and non-existence". In 1777 l.Euler introduced the symbol i stand for (Sqrt[-1]). In 1832 C.F. Gauss introduced the name complex numbers. The term imaginary quantity was for the first time used by R. Descartes in his La Géométrie , [Descartes, p.65] but Descartes originally used this term for what we today understand by the term complex number. He wrote that “the roots . . . are not always real, but sometimes imaginary.”  (http://www.friesian.com/imagine.htm)

Gaussian integers were used first by Gauss in his second memoire [Gauss2] on biquadratic reciprocity published 1832. The first [Gauss1] of two papers was submitted already in 1825  (Pieper, p. 25). Here Gauss writes that he started to study the complex of problems around biquadratic reciprocity in 1805, and that from the very first moment it was clear that the subject of the higher arithmetic should be unfolded in an infinite extent [Gauss1, §1; Gauss2, §30], or that a natural source of one arithmetic theory is to be found in an extension of the field of the arithmetic [Gauss2, §30] . The biquadratic reciprocity generalizes the quadratic reciprocity which he had first succeeded in proving on April 8, 1796 (Pieper, p. 20).

Let ℤ denote the set of integers, ℝ the set of real numbers and  ℂ={a+b i: a∈ℝ,b∈ℝ} the set of complex numbers. With every complex number z=a+b i we associate its
• real part Re[a+b i]=a
• imaginary part Im[a+b i]=b
• absolute value Abs[a+b i]=(Sqrt[(a^2)+(b^2)])
• the (principal) argument Arg[a+b i]=φ∈[0,2π), where φ satisfies both equalities Sin[φ]=((Im[z])/(Abs[z])) and  Cos[φ]=((Re[z])/(Abs[z])) or  z=Abs[z](e^(i φ)) (another possibility is to select φ∈(-π,π] in the exponential form to get the so called phasor representation mainly used in technical application).

Manipulate[r=Norm[{x,y}];If[r==0,r=.1];If[showAngle,θ=Arg[x+y I],θ=If[Arg[x+y I]≥0,Arg[x+y I],Arg[x+y I]+2 π]];LocatorPane[Dynamic[{x,y}],Dynamic[Graphics[{{White,Rectangle[{-6,6},{6,8}]},{Lighter[Yellow,0.85],Rectangle[{-6,-6},{6,6}]},{Lighter[Black,0.5],Opacity[0.5],AbsoluteThickness[1],Arrow[{{0,-5},{0,5}}],Arrow[{{-5,0},{5,0}}]},{Green,Opacity[1],AbsoluteThickness[2],Line[{{0,0},Dynamic[{x,y}]}]},{Blue,Opacity[1],AbsoluteThickness[2],Line[{{x,0},Dynamic[{x,y}]}]},{Red,Opacity[1],AbsoluteThickness[2],Line[{{0,y},Dynamic[{x,y}]}]},{Black,Opacity[1],AbsolutePointSize[5],Point[{x,y}]},{Green,Opacity[0.2],Disk[{0,0},r,If[showAngle&&θ<0,{θ,0},{0,θ}]]},{Opacity[0.7],If[showGon,Text[Style[TraditionalForm[ToString[PaddedForm[Abs[x+I y],{4,3}]]*Power[E,ToString[PaddedForm[θ,{4,3}]]<>ToString["I"]]],Blue,14],{x,y},If[0≤θ≤π,{0,-1},{0,1}]],Text[Style[TraditionalForm[PaddedForm[Chop[x+I y],{4,3}]],Black,14],{x,y},If[0≤θ≤π,{0,-1},{0,1}]]]},{Opacity[0.7],Text[Style[TraditionalForm["Re[z]="<>ToString[PaddedForm[Chop[Re[x+I y]],{4,3}]]],Red,12],{-5.5,7.4},{-1,0}]},{Opacity[0.7],Text[Style[TraditionalForm["Im[z]="<>ToString[PaddedForm[Chop[Im[x+I y]],{4,3}]]],Blue,12],{-5.5,6.6},{-1,0}]},{Opacity[.7],Text[Style[TraditionalForm["Abs[z]="<>ToString[PaddedForm[Chop[Abs[x+I y]],{4,3}]]],Green,12],{2,7.4},{-1,0}]},
{Opacity[.7],Text[Style[TraditionalForm["Arg[z]="<>ToString[PaddedForm[Chop[θ],{4,3}]]],Green,12],{2,6.6},{-1,0}]}
},PlotRange->{{-6,6},{-6,8}},ImageSize->300]],Appearance->Text[Style["●",12,Green]]],{{showAngle,True,"argument (phase) from (-π,π]"},{True,False}},{{showGon,False,"phasor form"},{True,False}},{{x,2.,"Real part"},-4,4,ControlType->None},{{y,2.5,"Imaginary part"},-4,4,ControlType->None}]

Basic definitions

Gaussian (Argand) plane

A Gaussian integer is a complex number of the α=a+b i whose real and imaginary parts a and b are both integers.

Newton interpreted negative and positive qunatities as line segments taken in oposite direction. Wallis realised that real numbers could be represented on a line and made an early attempt to represent complex numbers as points in the plane in 1673 (Stillwell 1989, p. 191). Then Caspar Wessel (1797),  Gauss (1800) and  Jean-Robert Argand (1806) independently  represented complex numbers as points in the plane, now known as the Gauss or Argand plane (Wessel's and Argand's publications of the geometric interpretation of complex numbers went unnoticed) .

gaussianNet[z_,dim_,col_,siz_]:=(* lattice points around z  given in the form a+bI *)
(* dimension of the net is dim×dim; col is color of the points; siz is PoniSize *)
Module[{a=Re[IntegerPart[z]]-Ceiling[dim/2-1],b=Im[IntegerPart[z]]-Ceiling[dim/2-1]},Graphics[{{col,PointSize[siz],Table[Point[{x,y}],{x,a,a+dim},{y,b,b+dim}]},
{Table[Text[Style[TraditionalForm[x+I y],col,9],{x,y-.1},{0,1}],{x,a,a+dim},{y,b,b+dim}]}
},ImageSize->250]];

gaussianPoint[z_,col_,siz_]:=(* z given in the form a+bI as a point of color col and size siz in Gaussian complex plane *)Graphics[{col,PointSize[siz],Point[{Re[z],Im[z]}]}];

gaussianNet[0,4, Red, .03]

Is z a Gaussian integer?

gaussianIntegerQ[z_]:=
If[NumericQ[z], If[IntegerQ[FullSimplify[Re[z]]]&& IntegerQ[FullSimplify[Im[z]]], IntegerQ[FullSimplify[Re[z]]]&& IntegerQ[FullSimplify[Im[z]]], Return["False"]],Return["False"]]

gaussianIntegerQ[2+3I]
gaussianIntegerQ[2+3.I]

Immediate implementation of the command in the form

gaussianIntegerQQ[z_]:=IntegerQ[Re[z]]&&IntegerQ[Im[z]]

does not work properly because not all commands always propagate into arguments

gaussianIntegerQQ[1-2π+(π^2)-(((1-π))^2)-I]
gaussianIntegerQ[1-2π+(π^2)-(((1-π))^2)-I]

gaussianIntegerQ[π+I]

Basic algebraic properties

The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain usually denoted by ℤ[i], i.e.

ℤ[i]={a+b i : a,b∈ℤ}.

ComplexExpand[(a+b I)+(c+d I)]

ComplexExpand[(a+b I)-(c+d I)]

ComplexExpand[(a+b I)(c+d I)]

Its quotient field is the field ℚ[i]={r+s i : r,s∈ℚ}

ComplexExpand[((a+b I)/(c+d I))]

Neither ℤ[i] nor ℚ[i] is algebraically closed because

(Sqrt[a+b i])={({{±(Sqrt[(((Sqrt[(a^2)+(b^2)])+a)/2)])+i(Sqrt[(((Sqrt[(a^2)+(b^2)])-a)/2)]),   if  b>0,}, {±(Sqrt[(((Sqrt[(a^2)+(b^2)])+a)/2)])-i(Sqrt[(((Sqrt[(a^2)+(b^2)])-a)/2)]),    if  b<0.}})

z=.;Solve[(z^2)-(a+b I)==0,z,Complexes]//ComplexExpand

sol=Solve[{(x^2)-(y^2)==a,2x y==b},{x,y}]

{x,y}/.sol//FullSimplify//TableForm

Associates

The units of this subring are the four Gaussian integers which have multiplicative inverses, namely +1,-1 and  +i,-i. Gauss calls them [Gauss2, $31] the positive, the negative, the positive imaginary or the negativ imaginary unit, respectively.

gaussianUnits:={1,-1,I,-I}

gaussianIntegerQ/@gaussianUnits

The three multiples of a Gaussian integer α by -1,i,-i are called the associates of α.

gaussianAssociatesQ[z1_,z2_]:=If[TrueQ[gaussianIntegerQ[z1]]&&TrueQ[gaussianIntegerQ[z2]],MemberQ[gaussianUnits,z1/z2],Return["Input not a Gaussian integer"]]

gaussianAssociatesQ[2+3I,-3+2I]

gaussianAssociatesQ[2+3.I,-3+2I]

gaussianAssociatesQ[2+3I,-π+2I]

gaussianAssociates[z_] :=If[TrueQ[gaussianIntegerQ[z]],Return[z*gaussianUnits],Return["Input not a Gaussian integer"]]

gaussianAssociates[2-3I]

gaussianAssociates[2-3.I]

Conjugates

Gaussian integer a-b i is called the conjugate of the Gaussian integer a+b i. The conjugate of a complex number z can be determined by the Mathematica command Conjugate[z]. We define our conjugate function because again the command Conjugate does not always propagate properly into arguments

gaussianConjugate[z_]:=If[TrueQ[gaussianIntegerQ[z]],Return[FullSimplify[Re[z]]-FullSimplify[Im[z]] I], Return["Not a Gaussian integer"]]

gaussianConjugate[1-2π+(π^2)-(((1-π))^2)-I]

Mathematica command Conjugate returns in this case

Conjugate[1-2π+(π^2)-(((1-π))^2)-I]

gaussianConjugate[π+I]

The norm

The norm of a Gaussian integer a+b i  is defined as product of itself with its conjugate

gaussianNorm[z_]:=
If[TrueQ[gaussianIntegerQ[z]],z*gaussianConjugate[z], Return["Not a Gaussian integer"]]

gaussianNorm[2-5I]

gaussianNorm[2.-5I]

gaussianNorm[π-5I]

Divisibility

We say that a Gaussian integer (Subscript[z, 1]) divides a Gaussian integer (Subscript[z, 2]) if there is a Gaussian integer (Subscript[z, 3]) such that (Subscript[z, 2])=(Subscript[z, 1])(Subscript[z, 3]).

The set of non-associate divisors

div1=Divisors[5+I,GaussianIntegers->True]

The set of all divisors is

div2=Flatten[Outer[Times,div1,gaussianUnits]]

Show[{gaussianNet[0,12,Yellow,.02],gaussianPoint[#,Black,.03]&/@div2,gaussianPoint[#,Blue,.03]&/@div1},ImageSize->400]

Complex sum of divisors

What is a proper definition of the complex-sum-of-divisors to preserve the property of its real prototype?

Gegenbauer [Gegenbauer1, Gegenbauer2] based his approach to sum-of-divisors function using the norms of divisors

gegenbauerDivisorsSum[z_]:=Plus@@(Abs[#]^2&/@Divisors[z,GaussianIntegers->True])

gegenbauerDivisorsSum[5+I]

How should would-be definition of sums-of-divisors function depened on the choice of associates

qq=2+I;
PrimeQ[qq]

Sum-of-divisors function 1+π+(π^2)+…+(π^k) of a Gausian prime π dependent on the choice of the associates of (π^t), t=0,1,…,k.

k=5;
(* generate random k gaussian units *)
uu=Table[gaussianUnits[[RandomInteger[{1,4}]]],{i,k}] 
(* sum of corresponding associates of qq *)
Inner[Times,uu,Table[qq^i,{i,k}],Plus]

Spira [Spira] took these natural requirements on DivisorSigma[1,n]:=σ(n):
• multiplicativity, i.e. σ(a b)=σ(a)σ(b) for GCD[a,b]=1. This implies σ(ϵ)=1 for a Gaussian unit ϵ.
• the value σ((π^k)) should be independent of the choice of associate of (π^k)
• |σ((π^k))|≥|(π^k)|,  π a Gaussian prime

Lemma [Spira, Lemma]: For Gaussian integer z, such that |z|>1,
|1+z+(z^2)+…+(z^k)|≥|(z^k)|,  for  Re[z]>0, and
 |1+z+(z^2)+…+(z^k)|≤|(z^k)|,  for  Re[z]<0.

Let z be a Gaussian integer. To calculate σ(z), factor z into a product of powerss of distinct Gaussian primes, z=ϵ∏(Subscript[π, i]^(Subscript[α, i])), each (Subscript[π, i]) lying in the first quadrant and then put σ(z)=∏(((Subscript[π, i]^((Subscript[α, i])+1))-1)/((Subscript[π, i])-1)).

Plus@@por1

FactorInteger[5+I]

(((((1+I))^2)-1)/(1+I-1))*(((((2+3I))^2)-1)/(2+3I-1))

DivisorSigma[1,5+I,GaussianIntegers->True]

div1

(((((1+i))^2)-1)/(1+i-1))*(((((2+3i))^2)-1)/(2+3i-1))=(1+(1+i))*(1+(2+3i))=1+(1+i)+(2+3i)+(5i-1)

Division with remainder

Rational integers arithmetic

The basic theorem of the arithmetic of rational integers, the so-called divison algorithm says:

Theorem. Given two rational integers a and d with d≠0, there exist unique integers q and r such that a=q d+r  and 0≤|r|<|d|, where |d| denotes the absolute value of d.

The integer q is called the quotient,  r the remainder, d the divisor, and a the dividend.

The proof depends on the fact that given a real number, in this case the rational number (a/d) we can always find an  integer, say q, ,within a distance 1 to the a/d, i.e. |(a/d)-q|<1. This guarrantes that the difference r=a-q d is in absolute value <|d|.

Manipulate[Graphics[{
{Thickness[.006],Line[{{-2.7,0},{2.7,0}}]},
{PointSize[.025],Table[Point[{i,0}],{i,-2,2}]},{Red,PointSize[.028],Point[{x,0}]},{Red,Dashed,Thickness[.004],Circle[{x,0},1]},{Blue,Dashed,Thickness[.004],Circle[{x,0},1/2]}
},ImageSize->{500}],
{{x,-1.5,"x coordinate"},-2,2}
]

At distance 1 we have actualy two possibilities how to choose q. At distance 1/2 we have one possibility unless (a/q) is in the middle between two integers. Following Gauss this leads us the least possitive, least negative or least magnitude remainder.

The process of finding the quotient or the remainder in Mathematica is implemented throught the division functions Quotient[m,n,d], and  Mod[m,n,d], respectively. Mod[m,n,d] gives a result r satisfying d≤r<d+n and Quotient[m,n,r] a result q such that d≤q=m-n r<d+n. The parameter d influences the range of the remainder, thus
• the offset d=0 the remainder r represents the least non-negative remainder
• the offset d=1 the remainder r represents the least positive remainder
• the offset d=-n+1  the remainder r represents the least non-positive remainder,
• the offset d=-n/2  the remainder r represents the least absolute remainder, etc. For instance

These integer quotients can be implemented by the following variants of the Mod function

Mod[#,7]&/@Range[7]
Mod[#,7,1]&/@Range[7]
Mod[#,7,-6]&/@Range[7]
Mod[#,7,-7/2]&/@Range[7]

Three of these integer remainders in domain of rational integers are produced by the following four division functions:
• Floor
• IntegerPart
• Ceiling
• Round

Range[7]-(7*Floor[#]&/@ (Range[7]/7))
Range[7]-(7*IntegerPart[#]&/@ (Range[7]/7))
Range[7]-(7*Ceiling[#]&/@ (Range[7]/7))
Range[7]-(7*Round[#]&/@ (Range[7]/7))

The definitions of integer division functions say

Floor[x]             gives the greatest integer less than or equal to x
IntegerPart[x]    gives the integer part of x
Ceiling[x]          gives the smallest integer greater than or equal to x
Round[x]          gives the integer closest to x but rounds numbers of the form x.5 toward the nearest even integer

Weisstein, Eric W. "Nearest Integer Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/NearestIntegerFunction.html

Weisstein, Eric W. "Floor Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/FloorFunction.html

Weisstein, Eric W. "Ceiling Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CeilingFunction.html

Weisstein, Eric W. "Integer Part." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/IntegerPart.html

<<Utilities`Plot`

PlotDiscontinuous[IntegerPart[x],{x,Sequence@@DeleteCases[Range[-4,4],0]
},AxesLabel->TraditionalForm/@{x,int[x]},PlotRange->All,PlotLabel->Style[Framed[IntegerPart],14,Blue,Background->Lighter[Yellow]]]

PlotDiscontinuous[Ceiling[x],{x,Sequence@@Range[-4,4]},AxesLabel->TraditionalForm/@{x,Ceiling[x]},PlotRange->All,PlotLabel->Style[Framed[Ceiliing],14,Blue,Background->Lighter[Yellow]]]

PlotDiscontinuous[Floor[x],{x,Sequence@@Range[-4,4]},AxesLabel->TraditionalForm/@{x,Floor[x]},PlotRange->All,PlotLabel->Style[Framed[Floor],14,Blue,Background->Lighter[Yellow]]]

PlotDiscontinuous[Round[x],{x,Sequence@@Range[-7/2,7/2]},AxesLabel->TraditionalForm/@{x,Round[x]},PlotRange->All,PlotLabel->Style[Framed[Round],14,Blue,Background->Lighter[Yellow]]]

Integer function Round[x] implements in Mathematica the nearest integer function, defined as the integer closest to x.  Since this definition is not unique for half-integers, the additional rule are added, the most common says that half-integers are always rounded to even numbers to avoid statistical biasing.

In number theory it is more usual to define the Round function to satisfy the inequality (1/2)≤Round[x]<(1/2), that is

nearestInteger[x_]:=Floor[x+1/2]

Thus

Round[-1.5]
nearestInteger[-1.5]

Also note that nearestInteger[x]=Floor[2x]-Flor[x].

PlotDiscontinuous[nearestInteger[x],{x,Sequence@@Range[-4.5,4.5]},AxesLabel->TraditionalForm/@{x,Floor[x]},PlotRange->All,PlotLabel->Style[Framed[nearestInteger],14,Blue,Background->Lighter[Yellow]]]

In some programming languages there is a truncate function, which rounds the argument toward zero. It is equivalent to floor if the argument or quotient is positive, or to ceiling otherwise.

We have

Abs[x-Floor[x]]<1,    Abs[x-IntegerPart[x]]<1,  Abs[x-Ceiling[x]]<1, Abs[x-Round[x]]≤1/2.

functs={Identity,Floor,IntegerPart,Ceiling,Round,nearestInteger};

a=-3.5;b=5.5;
{a,b}// Floor
{a,b}// IntegerPart
{a,b}// Ceiling
{a,b}// Round
{a,b}// nearestInteger

As mentioned above the main idea of a proof of Theorem is to "approximate" the complex number (a/d) by a suitable chosen rational integer quotient q and then choose r=a-q d.  In the arithmetic of rational integers to produce integer quotient q the division functions  Floor, IntegerPart, Ceiling and Round  are used. When used in the proof of the Theorem they produce a quotient q and a remainder r  such that a=q d+r and 0≤|r|≤|d|. The function 
• Floor gives a remainder r of the same sign as the divisor
• Ceiling produces a remainder r of the opposite sign as the divisor
• IntegerPart yield a remainder r of the same sign as the dividend
• Round leads to a remainder r of the least absolute value.

Gaussian integers division

The so-called divison algorithm has formally the same form as above

Theorem. Given two Gaussian integers α and δ with δ≠0, there exist unique integers θ and ρ such that α=θ δ+ρ  and 0≤gaussianNorm[ρ]<gaussianNorm[θ].

The Gaussian integer θ is again called the quotient,  ρ the remainder, δ the divisor, and α the dividend.

The main idea of the proof remains the same, but the situation is more complicated. A complex number (α/δ) falls in one of the cells of the integer lattice. At least one corner of the cell is within distnce 1 of  (α/δ).  Each such corner can be choosen for the quotient θ. The remainder is then ρ=α-θ δ. Since |(α/δ)-θ|<1, we have gaussianNorm[ρ]<gaussianNorm[δ].

However, for most positions within a cell in the integer lattice there are 2 or 3 or even 4 corners for selection as the quotient.

Manipulate[(* cell corners *)z=x+y I;
ll={Floor[Re[z]],Floor[Im[z]]};
lu={Floor[Re[z]],Ceiling[Im[z]]};
ru={Ceiling[Re[z]],Ceiling[Im[z]]};
rl={Ceiling[Re[z]],Floor[Im[z]]};
aa=Count[(#<1)& @ EuclideanDistance[{#1, #2}, {Re[z], Im[z]}]& @@@{lu, ll, ru, rl},True];
points=Point@@@{{lu},{ll},{ru},{rl}};
circumf=Line@@{{lu,ll,rl,ru,lu}};
LocatorPane[Dynamic[{x,y}],
Dynamic[Graphics[{{Blue,circumf},
Circle[lu,1,{3π/2,2π}],Circle[ll,1,{0,π/2}],Circle[ru,1,{π,3π/2}],Circle[rl,1,{π/2,π}],
{Red,PointSize[.04],points},
Text[Style[ToString[aa]<>" posible quotients",20,Black],{-.5,4.1}],
Text[Style[#1+#2 I,If[EuclideanDistance[{#1,#2},{Re[z],Im[z]}]<1,{Black,Background->Yellow},Red],15],{#1-.1,#2},{1,0}]&@@@{ll,lu},
Text[Style[#1+#2 I,If[EuclideanDistance[{#1,#2},{Re[z],Im[z]}]<1,{Black,Background->Yellow},Red],15],{#1+.1,#2},{-1,0}]&@@@{ru,rl}(*,
Graphics[{Black,PointSize[.05],Point[{Re[z],Im[z]}]}]*)
},ImageSize->300]],
Appearance->Text[Style["●",12,Green]]],
{{x,-.5,"Real part"},-1,0,ControlType->None},{{y,3.4,"Imaginary part"},3,4,ControlType->None}]

Unfortunately, the Floor, IntegerPart or Ceiling function yield a remainder that does not satisfy the condition 0≤gaussianNorm[r]<gaussianNorm[d]. On the other hand, the Round function gives the following bound

0≤gaussianNorm[r]≤(1/2)gaussianNorm[d] .

Gaussian integer functions

Mathematica functions Floor, IntegerPart, Ceiling and Round apply separately to real and imaginary parts of complex numbers. No pair of these functions yields generally the same result. Function hurwitzRound  for complex nuber was defined for the first time by Hurwitz [Hurwitz].

a=(10+36I)/(2+3I);b=(10-36I)/(2+4I);
a1=Table[a//functs[[i]],{i,Length[functs]}]
a2=Table[b//functs[[i]],{i,Length[functs]}]

{a,b,c,d,e,f}=a1

The location of these points with respect to the lattice of Gaussian integers looks as follows

aa=Flatten[Outer[List,{gaussianNet[a,3,Red,.03]},{gaussianPoint[#1,#2,.03]&@@@{{a,Blue},{b,Black},{c,Black},{d,Black},{e,Black},{f,Black}}}],2];

TableForm[Table[Show[{aa[[1]],aa[[i]]},Background->Hue[2i/22]],{i,2,Length[functs]-1}],TableHeadings->{Table[functs[[i]],{i,2,Length[functs]-1}],None}]

Catchment (gravity) regions of these functions are

z=2+4I;a=Re[z];b=Im[z];
Show[{Graphics[{Lighter[Blue,.8], Rectangle[{a,b},{a+1,b+1}]}],Graphics[{Thickness[.01],Line[{{a,b+1},{a,b},{a+1,b}}]}],Graphics[{Dashed,Thickness[.01],Line[{{a,b+1},{a+1,b+1},{a+1,b}}]}],gaussianNet[z,3, Red, .03],gaussianPoint[z,Black,.04],
Graphics[Text[Style["Floor",18],{a+.5,b+1.5}]]},ImageSize->300]

In the case of IntegerPart we get different borders on the upper and lower half-plane

z=1+2I;a=Re[z];b=Im[z];Show[{Graphics[{Lighter[Blue,.8], Rectangle[{a,b},{a+1,b+1}]}],Graphics[{Thickness[.01],Line[{{a,b+1},{a,b},{a+1,b}}]}],Graphics[{Dashed,Thickness[.01],Line[{{a,b+1},{a+1,b+1},{a+1,b}}]}],gaussianNet[z-1,3,Red, .03],gaussianPoint[z-1,Black,.04],
Graphics[Text[Style["IntegerPart",18],{a-.5,b+1.5}]],
Graphics[{Lighter[Yellow,.1], Rectangle[{a-1,b-1},{a,b}]}],Graphics[{Thickness[.01],Line[{{a-1,b},{a,b},{a,b-1}}]}],Graphics[{Dashed,Thickness[.01],Line[{{a,b-1},{a-1,b-1},{a-1,b}}]}],gaussianNet[z-1, 3,Red, .03],gaussianPoint[z-1,Black,.04]},ImageSize->300]

z=2+3I;a=Re[z];b=Im[z];Show[{Graphics[{Lighter[Blue,.8], Rectangle[{a,b},{a+1,b+1}]}],Graphics[{Dashed,Thickness[.01],Line[{{a,b+1},{a,b},{a+1,b}}]}],Graphics[{Thickness[.01],Line[{{a,b+1},{a+1,b+1},{a+1,b}}]}],gaussianNet[z,3, Red, .03],gaussianPoint[z,Black,.04],
Graphics[Text[Style["Ceiling",18],{a+.5,b+1.5}]]},ImageSize->300]

z=3+3I;a=Re[z];b=Im[z];Show[{Graphics[{Lighter[Blue,.8], Rectangle[{a-1.5,b-.5},{a-.5,b+.5}]}],
Graphics[{Lighter[Yellow,.1], Rectangle[{a-.5,b-1.5},{a+.5,b-.5}]}],
Graphics[{Lighter[Blue,.8], Rectangle[{a+.5,b-.5},{a+1.5,b+.5}]}],
Graphics[{Lighter[Yellow,.1], Rectangle[{a-.5,b+.5},{a+.5,b+1.5}]}],
Graphics[{Thickness[.01],Line[{{a-1.5,b-.5},{a-1.5,b+.5}}]}],
Graphics[{Thickness[.01],Line[{{a-.5,b-.5},{a-.5,b+.5}}]}],
Graphics[{Thickness[.01],Line[{{a+.5,b-.5},{a+.5,b+.5}}]}],
Graphics[{Thickness[.01],Line[{{a+1.5,b-.5},{a+1.5,b+.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a-.5,b+.5},{a-.5,b+1.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a+.5,b+.5},{a+.5,b+1.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a-.5,b-1.5},{a-.5,b-.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a+.5,b-1.5},{a+.5,b-.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a-1.5,b+.5},{a-.5,b+.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a-1.5,b-.5},{a-.5,b-.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a+.5,b+.5},{a+1.5,b+.5}}]}],
Graphics[{Dashed,Thickness[.01],Line[{{a+.5,b-.5},{a+1.5,b-.5}}]}],
Graphics[{Thickness[.01],Line[{{a-.5,b+1.5},{a+.5,b+1.5}}]}],
Graphics[{Thickness[.01],Line[{{a-.5,b+.5},{a+.5,b+.5}}]}],
Graphics[{Thickness[.01],Line[{{a-.5,b-.5},{a+.5,b-.5}}]}],
Graphics[{Thickness[.01],Line[{{a-.5,b-1.5},{a+.5,b-1.5}}]}],
gaussianNet[z-1, 3,Red, .03],gaussianPoint[z-1,Black,.04],
gaussianPoint[z-I,Black,.04],gaussianPoint[z+1,Black,.04],gaussianPoint[z+I,Black,.04],
Graphics[Text[Style["Round",18],{a-1,b+1.3}]]},ImageSize->340]

Complex Floor functions

Integer division functions play central role in the division theorem a through it in Euclidean algorithm, algorithms for greatest common divisor, or for continued fraction expansions etc. Namely, given a definition of  floor function, the division theorem follows, and one of its strengths is that it is the identical division theorem obtaining among the reals, and that residues will always be strictly less than the divisors.

Once we have defined a floor function, say F[·], we can define other integer functions. For instance, we can define the  corresponding ceiling function C[·] by relationships
C[z]=-F[-z].

In 1973 McDonnell [McDonnell , McDonnell]  formulated some properties of the extension of  the floor function F[·] to the complex plane:

• existence: every number has a floor

• uniqueness: every number has only one floor

• integrity: the floor of a number is an integer, i.e. F[z]∈ℤ

• fractionality: the magnitude of the difference of a number and its floor should be lless thna 1, i.e. |z-F[z]|<1

• convexity: if f is the floor of the number (Subscript[z, 1]) and (Subscript[z, 2]), then it is also the floor of all numbers on the line segment between (Subscript[z, 1]) and (Subscript[z, 2]), i.e. If F[(Subscript[z, 1])]=F[(Subscript[z, 2])] and (Subscript[z, 3]) lies on the line between (Subscript[z, 1]) to (Subscript[z, 2]), then F[(Subscript[z, 3])]=F[(Subscript[z, 1])]. In other worlds, if F[(Subscript[z, 1])]=F[(Subscript[z, 2])],  thenF[a (Subscript[z, 1])+b (Subscript[z, 2])]=F[(Subscript[z, 1])] for a+b=1 and a≥0, b≥0.

• integer translation: for (Subscript[z, 1]) a Gaussian integer (Subscript[z, 1])+F[z]=F[(Subscript[z, 1])+z]

• compability:

* the commplex floor function is compatible with the real floor function, i.e. if Im[z]=0 then F[z]=Floor[z]

* the action on purely imaginary numbers is similar to the action of the real floor function on real numbers. In particular Re[F[z]]≤Re[C[z]] and Im[F[z]]≤Im[C[z]]

Forkes [Forkes] listed some other properties or modifications of McDonnell's ones:

• symmetry: if p+q i=F[a+b i] then q+p i=F[b+a i]
In other words, the real and imaginary parts should be treated similarly (but not necessarily independently). A weaker condition requires: if F[a]=z, then F[a i]=w i for all real a.

• separation: floor and ceiling function at z are to be equal if and only if z is an integer (i.e. not at some other point)

• extendability: the floor function can be extended to quaternions
(Forkes  [Forkes, p.109] claims that constrains imposed by the symmetry and convexity extended to four dimensions imply a quaternional floor such that the region {z: F[z]=0, z  quaternion} does not tessalate the quaternion domain.

McDonnell's floor

In 1973 McDonnell [McDonnell , McDonnell] proposed an extension of the usual floor function to the complex plane.

mcdonnellFloor[z_]:=Module[{bb=Floor[z],a,b},a=Re[z-bb];b=Im[z-bb];a1=a+b;Which[a1<1,Return[bb],((a1≥1)&&(a≥b)),Return[bb+1],((a1≥1)&&(a<b)),Return[bb+I]]]

mcdonnellFloor[0.0986+0.00111I]

Note: In Forkes reproduced version of McDonnell's floor seems to be incorecct:

mcdonnellFloorForkes[z_]:=Module[{a=Re[z],b=Im[z],a1,b1,t},t=Floor[a+b];b1=Ceiling[.5t-1+a-b];a1=t-b1;Return[a1+I b1]]

zz=.0986+I .1111;
mcdonnellFloor[zz]
Show[{gaussianNet[mcdonnellFloorForkes[zz],3,Red,.03],gaussianPoint[zz,Blue,.03],gaussianPoint[mcdonnellFloorForkes[zz],Blue,.03]}]

z=4+3I;a=Re[z];b=Im[z];Show[{Graphics[{Lighter[Blue,.8], Polygon[{{a-.5,b+.5},{a+.5,b-.5},{a+1,b},{a,b+1}}]}],Graphics[{Thickness[.01],Line[{{a,b+1},{a-.5,b+.5},{a+.5,b-.5}}]}],Graphics[{Dashed,Thickness[.01],Line[{{a,b+1},{a+1,b},{a+.5,b-.5}}]}],gaussianNet[z,3, Red, .03],gaussianPoint[z,Black,.04],
Graphics[Text[Style["mcdonnellFloor's floor",18],{a+1,b+1.5}]]},ImageSize->330]

Hurwitz' round

In 1888 Hurwitz [Hurwitz] extended the nearest integer function to complex domain in connection with his investigation of continued fractions expansions.

hurwitzRound[x_]:=Floor[x+1/2]

z=2+3I;a=Re[z];b=Im[z];Show[{Graphics[{Lighter[Blue,.8], Rectangle[{a+.5,b-.5},{a+1.5,b+.5}]}],Graphics[{Thickness[.01],Line[{{a+.5,3.5},{a+.5,2.5},{a+1.5,2.5}}]}],Graphics[{Dashed,Thickness[.01],Line[{{a+.5,b+.5},{a+1.5,b+.5},{a+1.5,b-.5}}]}],gaussianNet[z,3, Red, .03],gaussianPoint[z+1,Black,.04],
Graphics[Text[Style["hurwitzRound",18],{a+1,b+1.5}]]},ImageSize->330]

We have FractionalPart[x]=x-Floor[x] for complex x. If we define ‖z‖=z-hurwitzRound[z] then we have

hurwitzRound[z]=Floor[z+((1+i)/2)]
Floor[z]=hurwitzRound[z-((1+i)/2)]
‖z‖=FractionalPart[z+((1+i)/2)]-((1+i)/2)
FractionalPart[z]=‖z-((1+i)/2)‖+((1+i)/2)

From other idnetities between these functions let us mention

FractionalPart[‖z‖]=FractionalPart[z]
‖FractionalPart[z]‖=‖z‖
Floor[‖z‖]=Floor[z]-ntRound[z]
hurwitzRound[FractionalPart[z]]=hurwitzRound[z]-Floor[z].

Comparisions

The followiing table shows comparision of some of McDonnell's reqiurements on a floor function (cf. [Forkes])

({{ , mcdonnellFloor, hurwitzFloor, Floor}, {Compatibility, +, -, +}, {Convexity, +, +, +}, {Fractionality, +, +, -}, {Symmetry, -, +, +}})

Tesselation

integer translation: The translation property that  (Subscript[z, 1])+F[z]=F[(Subscript[z, 1])+z] for any integer (Subscript[z, 1]) implies that the region whose floor is (Subscript[z, 2]) can be found by shifting of the region whose floor is 0 by an amount (Subscript[z, 2]). Since every point has a uniquelu determined floor, we get a tesselation of the complex plane using the region whose floor is, e.g. 0.

A Voronoi diagram of a set of "sites" (points) is a collection of regions that divide up the plane. Each region corresponds to one of the sites, and all the points in one region are closer to the corresponding site than to any other site.

Hurwitz round function leads to a Voronoi diagram in the complex plane.

Complex remainders

In complex case the procedure with the selection of the suitable region for the remainder is far more complicated. For instance, not the sign of the divisor  is decisive, but its phase have been taken into account. It is known that for a Gaussian divisor a+i b we need (a^2)+(b^2)=gaussianNorm[a+i b] distinct remainders.

Remainder (or residue) rem[w,z] of w modulo z can be formally defined as follows ({Forkes])

• res[w,0]=w (or 0)

• res[w,1]=w-floor[w]

• res[w,z]=z*res[(w/z),1]  if z≠0,       i.e.  z((w/z)-floor[(w/z)])=w-z*floor[(w/z)]

McDonell's remainder

To find mcdonnellRes[w,z] can be found geometrically in such a way that the tile for 0 with corners i, -(1/2)+(1/2)i,  (1/2)-(1/2)i, 1 is blowed up by the dividend z, and the whole plane is tesellated by such tiles. w is the located in some of these tesselationg tiles, which is then translated to overlay tile 0, say by a Gaussian integer k  and the point w' corresponding to the position of w and lying in this translated tile is mcdonnellRes[w,z].

mcdonnellRemainder[w_,z_]:=w-z*mcdonnellFloor[w/z]
mcdonnellRemainder[w_,0]:=0

z=3+2I;
w=7-5I;
mcdonnellRemainder[w,z]

z=3+2I;
w=7-5I;
quot=mcdonnellFloor[w/z];
wPrime=w-z*quot;
a=Re[z];b=Im[z];
tile0={{-.5,.5},{.5,-.5},{1,0},{0,1}};
corners0=(#1+I*#2)&@@@tile0; (* conversion to Gaussian integers *)
cornersz=z*corners0;
trans1=cornersz[[2]]-cornersz[[1]];
trans2=cornersz[[4]]-cornersz[[1]];

cornersw=cornersz+w-wPrime;
cornersw=cornersz[[1]]+Flatten[Table[i*trans1+j*trans2,{i,0,3},{j,1,-2,-1}]];
cornerszw=w+cornersz;
xMax=Ceiling[Max[Union[Re[#]&/@cornersz,Re[#]&/@cornersw]]];
xMin=Floor[Min[Union[Re[#]&/@cornersz,Re[#]&/@cornersw]]];
yMax=Ceiling[Max[Union[Im[#]&/@cornersz,Im[#]&/@cornersw]]];
yMin=Floor[Min[Union[Im[#]&/@cornersz,Im[#]&/@cornersw]]];
net=gaussianPoint[#,Yellow,.02]&/@Flatten[Table[ x+y I,{x,xMin,xMax},{y,yMin,yMax}]];
Show[{gaussianPoint[wPrime,Black,.03],gaussianPoint[#,Blue,.029]&/@cornersw,net,gaussianPoint[#,Red,.03]&/@cornersz,gaussianPoint[z,Yellow,.015],gaussianPoint[w,Black,.03]},Axes->True]

Evaluation criteria for the reaminders are ([McDonnell],[Forkes],[Baker]):

• the set of remainders forms a simple shape

• the set of remainders 'tiles' the complex plane in a doubly periodic faashion

• each remainder should have its norm smaller than the norm of the divisors

• the set of remainders is a convex set

GCD

Given a remainder function derived from a floor function satisfying the fractionality property we can apply the Euclidean algorithm to compute the GCD. The fractionality property ensures that the process converges.

To find the GCD of w and z proceed as follows ([McDonnell]):

Step 1: x←w
Step 2: w←res[z,w]
Step 3: z←x
Step 4: goto 1 if w≠0.

w=44+23I; z=123-34I;

mcdonnellEuclideanAlgorithmList[a_,b_]:=First/@Most[FixedPointList[{Last[#],mcdonnellRemainder@@#}&,{a,b}]]

w=44+23I; z=123-34I;
mcdonnellEuclideanAlgorithmList[w,z]

mcdonnellEuclideanAlgorithmGCD[a_,b_]:=FixedPointList[{Last[#],mcdonnellRemainder@@#}&,{a,b}][[-3,1]]

mcdonnellEuclideanAlgorithmGCD[w,z]

Weisstein, Eric W. "Euclidean Algorithm." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EuclideanAlgorithm.html

(*w=99+I; z=99+2I;*)
w=99+I; z=23+2I;
mcdonnellEuclideanAlgorithmList[w,z]
Length[%]

hurwitzRemainder[w_,z_]:=w-z*hurwitzRound[w/z]
hurwitzRemainder[w_,0]:=0

hurwitzEuclideanAlgorithmList[a_,b_]:=First/@Most[FixedPointList[{Last[#],hurwitzRemainder@@#}&,{a,b}]]

hurwitzEuclideanAlgorithmList[w, z]
Length[%]

References:

Amerbaev, V.M.; Pak, I.T.; Parallel calculations in the complex plane.(Parallel' nye vychisleniya v kompleksnoj ploskosti).(Russian). Alma - Ata : Izdatel' stvo "Nauka" Kazakhskoj SSR.184 p.R.1.90 (1984).

Baker, H.G.: Complex integers for 'Gaussian graphics'. ACM SINGPLAN Notices 28, No.11 (1993).

Descartes, R.; The geometry of René Descartes translated from the french and latin by D. E. Smith and M. L. Latham with a facsimile of the first edition, 1637. (English) XIV + 246 p. Chichago and London, The Open Court, Publishing Company (1925); Dover Reprint 1954.

Duprat, J., et al.:  New Redundant Representations of Complex Numbers and Vectors. IEEE Trans. Computers 42, No.7 (1993), 817-824.

Forkes, D.: Complex floor revisited, ACM  (1981), 107-111.

[Gauss1] Gauss, C.F.: "Theoria residuorum biquadraticorum. Commentatio secunda.", Comm. Soc. Reg. Sci. Gottingen (Göttingen Abh.) 6 (1828) 1-34; reprinted in Werke, Georg Olms Verlag, Hildesheim, 1973, pp. 67-92.

[Gauss2] Gauss, C.F.: "Theoria residuorum biquadraticorum. Commentatio secunda.", Comm. Soc. Reg. Sci. Gottingen 7 (1832) 1-34; reprinted in Werke, Georg Olms Verlag, Hildesheim, 1973, pp. 93-148.

[Gegenbauer1] Gegenbauer, L. Ueber die ganzen complexen Zahlen von der Form a+b i. ( On complex integers of the form a+b i). S.-B. Wien. Akad. Wiss. 91 (1885), 1047-1058.

[Gegenbauer2] Gegenbauer, L. Zur Théorie der aus den vierten Einheitswurzeln gebildeten complexen Zahlen. (On the theory of the complex numbers formed from the fourth roots of unity). Dekschr. Wien. Akad. Wiss. 50 (1885),  153-184.

Goffinet, D.: Number Systems with a Complex Base: a Fractal Tool for Teaching Topology. Amer. Math. Monthly  98, No. 3  (1991), 249-255.

Harmon, C.J.: Complex Fibonacci Numbers. Fibonacci Quart. 19, No. 1 (1981), 82-86.

Holladay, T.M. "An Optimum Algorithm for Halftone Generation for Displays and Hard Copies". Proc. Soc. Info. Disp. 21, No. 2 (1980), 185-192.

Hurwitz, A. Über die Entwicklung complexer Grossen in Kettenbrüche. Acta Math. 11 (1888).

Kleiner, I.: From Numbers to Rings: The Early History of Ring Theory,  Elem. Math. 53 (1998), 18 – 35.

McDonnell, E.E.: Complex floor. Proceedings of APL Congress 73, (eds. Per Gjerlov, H.G.Helms and John Nielsen),  Copenhagen 1973, 299-305.

McDonnell, E.E.: Integer Functions on Complex Numbers, with Applications, IBM Philadelphia Scientific Center, Tech. Report No. 320-3015, February, 1973.

Penney, W.: A 'Binary' System for Complex Numbers. JACM 12, No. 2 (1965), 247-248.

Pieper, H.: Variationen über ein zahlentheoretisches Thema von C. F. Gauss. Mit einem Geleitwort von H. Reichardt. (German) Berlin: VEB Deutscher Verlag der Wissenschaften (1978), 183 pp. (available also as Wissenschaft und Kultur. Vol  33. Basel - Stuttgart: Birkhäuser Verlag. (1978)).

Schwerdtfeger, Hans. Geometry of Complex Numbers: Circle Geometry, Moebius Transformation, Non-Euclidean Geometry. Dover Publs., New York, 1962.

Spira, R.: The complex sum of divisors. Amer. Math. Mon. 68 (1961), 120-124.

Williams, K.S.: On the Supplement to the Law of Biquadratic Reciprocity  Proceedings of the American Mathematical Society, Vol. 59, No. 1 (Aug., 1976), pp. 19-22

Cohn, J. H. E.: Shorter Notes: Sums of Cubes of Gaussian Integers  Proceedings of the American Mathematical Society, Vol. 29, No. 2 (Jul., 1971), pp. 426.

Gilbert, W.J.: The Division Algorithm in Complex Bases, Can. Math. Bull.  39, No. 1  (1996), 47-54.

Jordan, J.H.: The divisibility of Gaussian integers by large Gaussian primes, Duke Math. J. 32, No. 3 (1965),  503-509