# When is the product of two "primitive" complex integers also "primitive"?

I define a complex integer $$z = a + b\cdot i$$ (with $$a, b \in \mathbb{Z}$$) to be primitive if $$gcd(a, b) = 1$$ and $$a$$ and $$b$$ have opposite parity (i.e., one is odd and the other is even).

[These are precisely the pairs that generate primitive Pythagorean triples, and hence the name.]

I'm trying to find a condition to determine when the product of two complex integers $$z = a + b\cdot i$$ and $$w = c + d\cdot i$$ is also primitive.

The product $$z\cdot w = (a + b\cdot i) \cdot (c + d\cdot i) = (a\cdot c - b\cdot d) + (a\cdot d + b \cdot c)\cdot i \equiv (e + f\cdot i) \equiv v$$

Verifying that $$e$$ and $$f$$ have opposite parity is easy.

So far, I have been able to conclude that $$gcd(e, f) \vert gcd(z\cdot \bar{z}, w \cdot \bar{w})$$. My idea uses the fact that any integer linear combination of $$e$$ and $$f$$ is divisible by $$\delta$$, the $$gcd$$ of $$e$$ and $$f$$.

$$a\cdot e + b\cdot f = c\cdot (a^2 + b^2)$$, and

$$-b\cdot e + a\cdot f = d\cdot (a^2 + b^2)$$.

Now, since these are integer linear combinations of $$e$$ and $$f$$, $$\delta \vert c\cdot (a^2 + b^2)$$ and $$\delta \vert d\cdot (a^2 + b^2)$$. Since $$w$$ is a primitive complex integer and $$gcd(c, d) = 1$$, it can be concluded that $$\delta \vert (a^2 + b^2)$$. Similarly, one can show that $$\delta \vert (c^2 + d^2)$$. Therefore, $$\delta \vert gcd(a^2 + b^2, c^2 + d^2)$$.

However, I haven't been able to do much beyond this and haven't been able to determine exactly when $$e$$ and $$f$$ are co-prime (and $$v$$ is a primitive complex integer). Any help would be appreciated.

• Just to be clear – you're asking for the product of two primitives to be primitive? not just for the product of two arbitraries to be primitive? Jun 20, 2020 at 7:27
• A condition is $\gcd(a+bi,c-di)=1$ but I don't know whether you consider that a useful condition. Jun 20, 2020 at 7:33
• @GerryMyerson That's correct. I'm considering the case where the product of two primitives is primitive. In your second comment, are you considering the $gcd$ of two complex integers?
– Art
Jun 20, 2020 at 8:57
• You bet. The Gaussian integers (the name often used for what you are calling "the complex integers") are a unique factorization domain. Everything about greatest common divisors that works in the integers works in the Gaussian integers. Many introductory Number Theory textbooks have a chapter about this. Jun 20, 2020 at 11:22
• Thanks for the clarification! I'll read up more about the Gaussian integers and their properties. The condition that you mentioned - $z \cdot w$ is primitive $\leftrightarrow$ $gcd(a + bi, c - di) = 1$ - explains the observation I made earlier - about $gcd(e, f)$ dividing the $gcd$ of the norms of $z$ and $w$. Could you please explain how you arrived at that condition? I tried to derive the statement "$z\cdot w$ is primitive" from "$\alpha z + \beta w = 1$ ($\alpha, \beta \in \mathbb{Z}[i]$)", but I got stuck.
– Art
Jun 20, 2020 at 15:55

The Gaussian integers $$\bf G$$ are the set of all $$a+bi$$ where $$a,b$$ are integers and $$i^2=-1$$. Here are some facts that are well-known and discussed in many Number Theory textbooks, so I'll present them without proof.

1. $$\bf G$$ is an integral domain.

2. The units in $$\bf G$$ (that is, the elements of $$\bf G$$ whose multiplicative inverses are also in $$\bf G$$) are $$\pm1$$ and $$\pm i$$.

3. Prime numbers one less than a multiple of four (e.g., $$3,7,11,19,23,31,\dots$$) are also primes in $$\bf G$$.

4. The prime number $$2$$ factors in $$\bf G$$ as $$2=(1+i)(1-i)$$, and those factors are irreducible in $$\bf G$$. The two factors are associates, that is, either one is a unit times the other: $$1+i=i(1-i)$$.

5. Prime numbers one more than a multiple of four (e.g., $$5,13,17,29,37,\dots$$) can be expressed as a sum of two integer squares (e.g., $$5=2^2+1^2$$, $$13=3^2+2^2$$, $$17=4^2+1^2$$, and so on) and therefore factor in $$\bf G$$; $$p=u^2+v^2=(u+vi)(u-vi)$$. The factors are primes in $$\bf G$$. Moreover, they are not associates, so they are relatively prime to each other.

6. $$\bf G$$ is a unique factorization domain; every nonzero element of $$\bf G$$ has a factorization into primes, unique up to associates.

Now, let $$z=a+bi$$, $$w=c+di$$, $$zw=e+fi$$, and assume $$zw$$ is not primitive. The case where $$e,f$$ are of the same parity was settled in the body of the question, so we assume $$\gcd(e,f)=r$$ is odd and exceeds $$1$$. Then there is an odd prime $$p$$ dividing both $$e$$ and $$f$$, so $$p$$ divides $$zw$$.

If $$p$$ is one less than a multiple of four, then $$p$$ is still prime in $$\bf G$$, so $$p$$ divides at least one of $$z,w$$, so $$z,w$$ aren't both primitive.

We're left with the case that $$p$$ is one more than a multiple of four, in which case $$p=(u+vi)(u-vi)$$ for some integers $$u,v$$, and $$u+vi,u-vi$$ are both primes in $$\bf G$$. Since $$p$$ divides $$zw$$, it follows that both $$u+vi$$ and $$u-vi$$ divide $$zw$$, and then by primality $$u+vi$$ divides at least one of $$z,w$$, and also $$u-vi$$ divides at least one of $$z,w$$.

If $$u+vi$$ and $$u-vi$$ divide the same number, then, since they are relatively prime to each other, their product divides the number. But their product is the integer $$p$$, so the number can't be primitive. Hence, we may assume $$u+vi$$ divides $$z$$, and $$u-vi$$ divides $$w$$. Now $$u-vi$$ divides $$w$$ if and only if $$u+vi$$ divides $$w'$$ (since $$(st)'=s't'$$), so $$\gcd(z,w')$$ is divisible by $$u+vi$$ and, in particular, is not $$1$$.

Summing up, if $$z,w$$ are primitive, then $$zw$$ is primitive if and only if $$\gcd(z,w')=1$$.

In practice, if you want to determine whether $$zw$$ is primitive, you have a choice between

(a) calculating $$zw=e+fi$$ and then (if $$e,f$$ are of different parity) calculating $$\gcd(e,f)$$, or

(b) just calculating $$\gcd(z,w')$$, which can be done by the Euclidean algorithm in $$\bf G$$.

It's not clear to me which is easier.

• I'm sorry for the delay in awarding the bounty. I assumed that the bounty automatically went to the accepted answer. Anyway, thanks for the insightful answer!
– Art
Jun 28, 2020 at 6:41