5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Jun 20, 2020 at 7:27
  • 1
    $\begingroup$ A condition is $\gcd(a+bi,c-di)=1$ but I don't know whether you consider that a useful condition. $\endgroup$ Jun 20, 2020 at 7:33
  • $\begingroup$ @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? $\endgroup$
    – Art
    Jun 20, 2020 at 8:57
  • 4
    $\begingroup$ 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. $\endgroup$ Jun 20, 2020 at 11:22
  • $\begingroup$ 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. $\endgroup$
    – Art
    Jun 20, 2020 at 15:55

1 Answer 1

5
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – Art
    Jun 28, 2020 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.