# Connectedness of $\{(x,y,z)\ : \ x,y,z \in \mathbb Z, \gcd(x,y,z) = 1\}$ under the relation $\vec u \cdot \vec v = 1$

Let $$S = \{(x,y,z)\ : \ x,y,z \in \mathbb Z, \gcd(x,y,z) = 1\}$$, I would like to investigate the connectedness of $$S$$, considered as an (infinite) graph, where two vertices $$(x,y,z)$$ and $$(a,b,c)$$ are connected by an edge iff $$ax+by+cz = 1$$.

After some experiment I conjectured that $$S$$ is connected. My thoughts: let's start from $$(1,0,0)$$, and we can reach $$(1,a,b)$$ for all $$a,b\in\mathbb Z$$. From there we can proceed to $$(x, y, z)$$ for all $$\gcd(y,z)=1$$, by a simple application of Bézout's theorem on $$(y, z)$$. This is already quite close to our goal. But it gets much more complicated to proceed from here, since there is this strange constraint on $$y$$ and $$z$$. And even if we successfully characterize $$\{(a,b,c)\ : \ \exists x,y,z, \gcd(y,z)=1 \wedge ax+by+cz=1\}$$, there are still more work to do because it does not seem to cover the whole $$S$$.

On the other hand, maybe we could somehow start from an arbitrary element in $$S$$ and work our way back to $$(1,0,0)$$, by defining some strictly decreasing measure, but I can't think of a good way to proceed yet.

By the way, another subject of interest is the minimum number of steps it takes to get from $$(x,y,z)$$ to $$(1,0,0),(0,1,0)$$ or $$(0,0,1)$$ (i.e. the graph-theoretic distance). But it is not relevant here.

Any help is appreciated!

• Nice question! The interesting invariant to track of a triple $(a, b, c)$ seems to be $(\gcd(b, c), \gcd(a, c), \gcd(a, b))$, and the interesting case is when all of these are greater than $1$ (your argument shows that if any of them is equal to $1$ then we can connect to $(1, 0, 0), (0, 1, 0)$, or $(0, 0, 1)$ in two steps). Aug 29, 2020 at 23:26

Aha! In fact the interesting number to track turns out to be

$$m(a, b, c) = \text{min}(\gcd(b, c), \gcd(a, c), \gcd(a, b));$$

we can arrange for this to be strictly decreasing (in fact exponentially strictly decreasing), so it eventually hits $$1$$, and then your observation shows we hit $$(1, 0, 0), (0, 1, 0)$$, or $$(0, 0, 1)$$ (each of which is connected to, say, $$(1, 1, 1)$$) in two more steps. That is, every triple $$(a, b, c)$$ connects to $$(1, 1, 1)$$ in at most

$$\lfloor \log_2 m(a, b, c) \rfloor + 3$$

steps. As an easy upper bound note that we have $$m(a, b, c) \le \text{min}(a, b, c)$$, and with a little more effort we can show that $$m(a, b, c) \le \text{min}(\sqrt{a}, \sqrt{b}, \sqrt{c})$$, although this improves the bound by $$1$$ so it doesn't matter much.

We can see this as follows. Let's start with any triple $$(a, b, c)$$ whatsoever. WLOG let $$d = \gcd(b, c) = m(a, b, c)$$ be minimal. Then any triple $$(x, y, z)$$ this triple is connected to satisfies $$ax + by + cz = 1$$ by definition, hence $$d | ax - 1$$, or equivalently $$x \equiv a^{-1} \bmod d$$. This is actually the only constraint on $$x$$; given such an $$x$$ we can always find suitable $$y, z$$ by Bezout. Hence we can arrange for $$x$$ to be an integer congruent to $$a^{-1} \bmod d$$ between $$-\frac{d}{2}$$ and $$\frac{d}{2}$$ (which is unique if $$d$$ is odd and almost unique if $$d$$ is even); if we do so, then we've connected $$(a, b, c)$$ to a triple $$(x, y, z)$$ such that $$\gcd(x, y) \le |x| \le \frac{d}{2}$$, so $$m(x, y, z) \le \frac{d}{2}$$. Now we can repeat the same construction but in the third variable, etc. After logarithmically many steps we hit a triple with $$m(-, -, -) = 1$$.

Example. Consider the triple $$(15, 21, 35)$$, so that $$m(15, 21, 35) = \text{min}(7, 5, 3) = 3$$. The smallest gcd is $$\gcd(15, 21) = 3$$, so we expect to be able to connect this to a triple $$(x, y, z)$$ such that $$z \equiv 35^{-1} \equiv 2 \bmod 3$$; the unique such $$z$$ between $$-\frac{3}{2}$$ and $$\frac{3}{2}$$ is $$-1$$, so we can take $$z = -1$$ and now we need to find $$x, y$$ such that

$$15x + 21y - 35 = 1$$

or $$15x + 21y = 36$$ or $$5x + 7y = 12$$. Happily we can take $$x = y = 1$$ so this is clear. So $$(15, 21, 35) \to (1, 1, -1)$$ in one step.