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 + 16  I, 1 + 9  I]

Here is the first example from the book:

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

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.

<< Statistics`DataManipulation`; << 
      Graphics`Graphics`;
RCI[n_Integer] := 
        Random[Integer, {10^n, 10^(n + 1)}] + 
          Random[Integer, {10^n, 10^(n + 1)}] I;
Proportion[n_Integer, M_Integer]:=(Print["GCD distribution for ",  
          M,  " pairs of random complex integers whose components are \
chosen between ",  NumberForm[10^n, DigitBlock -> 3],  " and ",  
          NumberForm[(10^(n + 1)), DigitBlock -> 3]]; store = {}; 
        Do[store = Append[store, GCD[RCI[n], RCI[n]]], {M}]; 
        Print[TableForm[Frequencies[store], 
            TableHeadings -> {None, {"Frequency", "GCD"}}]]; 
        BarChart[Frequencies[store], 
          PlotLabel -> StringForm["`` trials", M], 
          PlotRange -> {{1, 20}, All}]; )

Here is an example.  The graph may be less useful than before, and you may want to graph the data in a different way.

Proportion[3, 1000]

Art Duval, artduval@math.utep.edu
November 21, 2004.