The Euclidean algorithm for the Gaussian integers.

The Gaussian integers define a grid on the complex plane.

ListPlot[Flatten[Table[{i, j}, {i, -12, 12}, {j, -9, 9}], 1]]

[Graphics:../HTMLFiles/NumberTheory_132.gif]

-Graphics -

The multiples of a complex number like (5+2 i)define a grid, too:

Show[%, Graphics[{PointSize[0.02], Table[Point[{Re[(5 + 2) (i + j )], Im[(5 + 2) (i + j )]}], {i, -2, 2}, {j, -1, 1}]}]]

[Graphics:../HTMLFiles/NumberTheory_135.gif]

-Graphics -

The diagonal of a cell of the lattice of multiples of a Gaussian integer n is 2^(1/2)|n|. This means that all Gaussian integers are within (| n |)/2^(1/2)of a multiple of n. Since 1/2^(1/2)<1, any Gaussian integer can be expressed in the form: n=q m+r, where q and m are Gaussian integers and r is a remainder with modulus less than m.

The greatest common divisor of two Gaussian integers, gcd(a,b), can be defined as a Gaussian integer d of maximum modulus which divides both a and b. It is not unique because we can multiply by ±1 or ±i to get another Gaussian integer of the same modulus which also divides a and b. Any of these quantities can be considered as the gcd. Since Mathematica defines functions for general arguments the same algorithm will work.

myGCD[7 - 11 , 8 - 19 ]

1 + 2 

myGCD[5 + 6 , 3 - 2 ]

1

From Koblitz (A Course in Number Theory and Crypthography),we may use the complex gcd algorithm to write certain large primes as a sum of two squares. Suppose a prime p divides b^6+1. Then we may write p=c^2+d^2for some integers c and d. Since c^2+d^2=(c+di)(c-di), we only have to find a nontrivial Gaussian integer of p. Then

b^6 + 1 = (b^2 + 1) (b^4 - b^2 + 1), and

b^4 - b^2 + 1 = (b^2 - 1)^2 + b^2 .

Since p is prime it must divide one of the factors in the right hand side of the first equality. If p|b^2+1=(b+i)(b-i), then gcd(p,b+i)will give c+di. If p|b^4-b^2+1=((b^2-1)+bi)((b^2-1)-bi), then gcd(p,(b^2-1)+bi)will give c+di.

Example. The prime 12277 divides the second factor in 20^6+1=(20^2+1)(20^4-20^2+1), so we find gcd(12277,(20^2+1)+20i):

myGCD[12277, 399 + 20 ]

-66 + 89 

Therefore, 12277 = (-66)^2+89^2

(-66)^2 + 89^2

12277

The native Mathematica algorithm gives another equally correct gcd:

GCD[12277, 399 + 20 ]

89 + 66 

Maximum power of a prime dividing n!

What is the maximum power of a prime p dividing n!? One way to obtain this answer is by using the formula , where S_p(n) is the sum of the digits of the base p representation of n. This formula is easily obtained by writing the quotients and remainders when expressing n in base p.
n=p⌊n/p⌋+d_0,
⌊n/p⌋=p⌊n/p^2⌋+d_1,
⌊n/p^2⌋=p⌊n/p^3⌋+d_2,
...
⌊n/p^(k - 1)⌋=d_ (k - 1),
where n=d_ (k - 1)p^(k - 1)+d_ (k - 2)p^(k - 2)+...+d_1p+d_0. Observe that we readily get the formula by solving for the d_i in each equation and then adding them all.

Created by Mathematica  (June 3, 2006) Valid XHTML 1.1!