# Strange Integers

### Fundamental Theorem of Arithmetic

3 is not prime in Z[3]. Give it a little thought, and the result is not at all surprising. This is what 3 was invented for - 3 times 3 is 3. 5 is a prime number. But what about 2? Is it a prime? No, it is not. We can write

 (1) 2 = (5 + 3√3)(-5 + 3√3),

where none of the factors is a unity (check their N-value.)

In fact, once we found one factorization, we can easily obtain many more. Recollect that U = 2 + 3 as well as U' = 2 - 3 are unities. Multiply the first factor in (1) by U and the second by U'. Apply the same procedure to the result:

(2)
 2 = (5 + 3√3)(-5 + 3√3) = (19 + 11√3)(-19 + 11√3) = (71 + 41√3)(-71 + 41√3)...

Note that the N-value of any factor is 2. This implies that each of them is prime. So we learn not only that, in Z[3], 2 is not prime, but also that its factorization into prime factors is not unique. Indeed, in the presence of an infinite number of unities, no number may have a unique factorization. However, in (2) factors differ by a multiple of unity. Such primes are called associates. For example, 5 + 33 and 71 + 413 are associates, for (71 + 413) = (5 + 33)(7 + 43), where N(7 + 43) = 1 and 7 + 43 is a unity.

By the end of this page I plan to prove the following variant of the Fundamental Theorem of Arithmetic:

In Z[3], factorization of a number into a product of primes is unique up to the order of associated primes.

First let's establish an analogue of the Euclidean Algorithm:

 (3) For any given pair A and B from Z[√3], B≠0, there exist in Z[√3] numbers Q and R such that. A = BQ + R, and |N(R)| < |N(B)|

Let A/B = x + y3, where x and y are rational. Any rational number p lies somewhere between [p] and [p]+1, where [p] is the largest integer smaller than p. Therefore, any rational number is at the distance of at most ½ from an integer. Let r and s be integers such that |x - r| ≤ ½ and |y - s| ≤ ½, respectively.

Let Q = r + s3 and R = B(x - r) + B(y - s)3. Then, of course, A = BQ + R, where A, B, Q all belong to Z[3] and so does R = A - BQ. Let's verify that |N(R)| < |N(B)|.

N(R) = N(B)((x - r)² - 3(y - s)²). By the defintion,

 (4) |(x - r)² - 3(y - s)²| ≤ |x - r|² + 3|y - s|² ≤ (½)² + 3(½)² = 1.

Equality is only achieved when both |x - r| and |y - s| equal ½. But in this case,

|(x - r)² - 3(y - s)²| = |½² - 3½²| = ½ < 1

Therefore always |(x - r)² - 3(y - s)²| < 1, and we have |N(R)| < |N(B)|.

(3) is a very powerful result. Now we may start an analogue of Euclid's Algorithm with confidence, assured that it will terminate in a finite number of steps. When it stops, we shall have found a number D with the property that

1. D|A and D|B, and
2. For any C such that C|A and C|B, we also have C|D.

This D is naturally called the greatest common divisor of A and B, and is denoted as D = gcd(A, B). As in N, the algorithm may be extended to yield two numbers S and T such that

AS + BT = gcd(A, B)

The greatest common divisor is obviously defined up to a factor of unity. Two numbers are called coprime (mutually prime) iff their greatest common divisor is a unity. Since 1 associates with every unity,

AS + BT = 1,

for coprime A and B and some S and T; exactly as was the case with integers.

We are in a position to prove the most fundamental property of division:

 (5) Assume that a prime number P divides the product of two numbers A and B: P|AB. Then either P|A or P|B.

In other words, if, for instance, P∤A, then it must be that P|B. As a prime, the only factors of P are its associates and the unities. If any of the associates divided A, so would P, but, by our assumption, this is not the case. Therefore, gcd(P,A) = 1. We thus conclude that there exist two numbers S and T such that PS + AT = 1. Multiply by B: PBS + (AB)T = B. Now, P|PBS and P|AB. Whence P|B.

Uniqueness of the prime factorization follows immediately from (5). Let A = P1P2...Pn = Q1Q2...Qm, where all P's and Q's are prime. P1 divides Q1Q2...Qm. Therefore, by (5), it divides one of the Q's. Both being prime, they are associates of each other and their ratio is a unity. Assume P1|Q1 and Q1/P1 = U. Replace Q2 with UQ2. This will not affect the primality of Q2. We can chip off factors from one side or another until we get, for example, Q1Q2...Qk = 1, all other factors from the two sides having been matched. The remaining Q's are all unities, hence, not prime. Whence k = 0, n = m, and the proof is completed.

### Remark

6 = 3·2 = 3(3-1) = 3² - 3 = (3 + 3)(3 - 3). Since 2|6, we also have that 2|(3 + 3)(3 - 3). However, 2∤(3 + 3) and 2∤(3 - 3), for, say, (3 + 3)/2 = 3/2 + 3/2 which does not belong to Z[3] at all. Combined with (4), we get another proof that 2 is not prime in Z[3].

### Question

Does or does not the identity 3·2 = (3 + 3)(3 - 3) contradict the fact that the prime factorization in Z[3] is unique?

### Reference

1. H. M. Stark, An Introduction to Number Theory, The MIT Press, 1995, Ninth printing.