Math 2325
(Chapter 16) - Euclidean Algorithm for Complex Integers

Single pair of complex integers (EuclidC)

"EuclidC" computes the GCD of two complex integers.  The output shows and counts all intermediate steps.  The code is identical to that for ordinary integers.

EuclidC[a_,b_]:=Module[{c=a,d=b,ctr=1},{c,d}=Sort[{c,d}];Print["Step ", ctr, ":\t ",c,"\t",d];While[c≠0,{c,d}={Mod[d,c],c};ctr++;Print["Step ", ctr, ": \t",c,"\t",d]]]

Here is an example,the GCD of 2+16I and 1+9I (note the use of "I" to input the imaginary unit, though the output of the imaginary unit is a stylized "i"):

EuclidC[2+16I,1+9I]

Here is the first example from the book:

EuclidC[7+8I,4+3I]

Counting relatively prime pairs (Proportion)

This program is adapted from Euclid4. It uses Mathematica's built-in GCD function, and so the GCD's all have positive real component.  Thus two numbers are relatively prime precisely when their GCD equals 1.  The graph is less useful in this case, and so the program just outputs a table.

RCI[n_Integer]:=RandomInteger[{(10^n),(10^(n+1))}]+RandomInteger[{(10^n),(10^(n+1))}] I;
Prop[n_Integer,M_Integer]:=(Print["GCD distribution for ",M," pairs of random complex integers whose components are chosen between ",(("10")^n)," and ",(("10")^(n+"1"))];store={};Do[store=Append[store,GCD[RCI[n],RCI[n]]],{M}];Print[TableForm[Sort[Tally[store]],TableHeadings->{None,{"GCD","Frequency"}}]])

Here is an example.

Prop[3,1000]

Art Duval, artduval@math.utep.edu
November 21, 2004.
Modified for Mathematica6
November 25, 2008.