# Is it possible to determine a $\gcd$ in a

non integral domain. For instance if we take the ring $\mathcal{Z}/9\mathcal{Z}=\{\bar0,\bar1,\bar2,\bar3,\bar4,\bar5,\bar6,\bar7,\bar8\}$. It's not an integral domain (indeed : $\bar3.\bar3=\bar0$ but $\bar3\neq \bar0$).

How can we determine $\gcd(\bar2,\bar7)$ ? Can we write a Bézout's relation ? I know that we can determine $(\mathcal{Z}/9\mathcal{Z})^{\times}$ using the congruences and Bézout which make the link between $\mathcal{Z}/9\mathcal{Z}$ and the ring $\mathcal{Z}$.

Moreover if we want to determine idempotent elements of this ring it can be a problem if we cannot use Bézout.

• The problem is with the g in $\gcd$. There is no ordering of your ring that makes sense. Oct 25, 2017 at 16:32
• @Arthur it means that the notion of $\gcd$ has no sense here ? Oct 25, 2017 at 16:36
• I think it does. See for instance the fact that this article exists: en.wikipedia.org/wiki/GCD_domain. That's specifically for integral domains, but still, the fact that the concept has its own Wikipedia article should point to the fact that not every ring or every ID has it. Oct 25, 2017 at 16:38
• @Arthur I have a hard time to reconcile your two comments.
– quid
Oct 25, 2017 at 16:40
• @quid Ahh, I meant "I think it does" as agreeing with "it means the notion of $\gcd$ has no sense here ?" I see now how that is ambiguous, but I still believe that my response is correct (the question is "it means [...]?", and my answer is affirmative). At any rate, it's too late to edit. Oct 25, 2017 at 16:55

The first thing you have to understand is that even if $\gcd(a, b)$ exists, it is not unique, strictly speaking. Even in $\mathbb{Z}$, for instance both $3$ and $-3$ are gcd's of $6$ and $15$. But the change of $\pm$ is the only thing that can happen in $\mathbb{Z}$, because $\pm 1$ are the only units of $\mathbb{Z}$.

Now quasi's answer is correct, and you should understand why in that example, all units of the ring are gcd's for your example. However, being all units, of course they are all associated (meaning: If $d$ and $e$ are gcd's of $a$ and $b$, then there is a unit $u$ such that $d\cdot u=e$).

In a domain, that would always be the case: If gcd's exist, they are associated.

That is also true in your ring $\mathbb{Z}/9$, as you can check by going through all cases (and noticing that $6 = -3$ in that ring), and it will be true for any $\mathbb{Z}/n$. But it is not true in general in rings with zero-divisors. Examples for this are a bit more complicated. Some are given in answers to this question: Two principal ideals coincide if and only if their generators are associated, and here.

By definition, in a commutative ring $R$, given two elements $a,b \in R$, an element $d \in R$ is a $\gcd$ of $a,b$, if

• $d|a$ and $d|b\;$(i.e., $d$ is a common divisor of $a,b$).$\\[4pt]$
• If $e \in R$ is such that $e|a$ and $e|b$, then $e|d$.

If all ideals of $R$ are principal (as is the case for $Z_9$), then any principal generator of the ideal $(a,b)$ is a $\gcd$ of $a,b$.

In particular, in the ring$Z_9$, the elements $2,7$ are units, so any unit is a $\gcd$ of $2,7$, For example, $1$ is a $\gcd$ of $2,7$.

• Thank you but the $\gcd$ should be $(a)+(b)$ ? Here we have $(\bar0), (\bar3)$ and $\mathcal{Z}/9\mathcal{Z}=(\bar1)$ as ideals Oct 25, 2017 at 17:34
• It seems to work like $\mathcal{Z}/p\mathcal{Z}$ with $p$ prime ? Oct 25, 2017 at 17:39
• If the ideal $(a,b)$ is a principal ideal, then any principal generator of the ideal $(a,b)$ is a $\gcd$ of $a,b$. Oct 25, 2017 at 17:41
• $(\bar{4},\bar6)$ $\subset$ $(\bar2)$ so the $\gcd(\bar4,\bar6)=(\bar2)$ Oct 25, 2017 at 17:43
• It's not "is in" that matters. If the ideal $(a,b)$ is principal, it's "is a principal generator" that matters. Oct 25, 2017 at 17:46