# Is this graph connected

Define the following graph on the vertex set ${\mathbb N}_{\geq1}\>$:

Two numbers $a$, $b\in {\mathbb N}_{\geq1}$ are connected by an edge (written $a \ \mathcal{R} \ b)$ if and only if $a+b \ | \ ab-1$.

Clearly $1$ is isolated. Can we connect all integers greater than $2$ to $2$? For example: $$2014 \ \mathcal{R} \ 147 \ \mathcal{R} \ 4175 \ \mathcal{R} \ 3891 \ \mathcal{R} \ 142 \ \mathcal{R} \ 43 \ \mathcal{R} \ 7 \ \mathcal{R} \ 3 \ \mathcal{R} \ 2.$$ Therefore $2014$ can be connected to $2$ (written $2014\sim2$).

Question: Is this graph connected?

Motivation :

I worked on the Machin formula and I wondered if we had $$\arctan \frac{1}{a} + \arctan \frac{1}{b} = \arctan \frac{1}{c}$$ where $a,b,c$ are integers and this happens if $c=\frac{ab-1}{a+b}$ is an integer.

EDIT : My apologie I forgot to mention that the graph is restricted to positive integer.

• Do you think it is important that we know what $\mathcal{R}$ means? – Elchanan Solomon Jul 20 '14 at 12:14
• It's not an equivalence relation. It's not reflexive: $2$ is not related to $2$. It's also not transitive: $2 \mathcal{R} 3 \mathcal{R} 7$ but $2$ is not related to $7$. – Rebecca J. Stones Jul 20 '14 at 13:17
• Are you allowed to use negative integers, or is this graph only on positive integers? – Calvin Lin Jul 20 '14 at 13:26
• An equivalence relation satisfies three properties: reflexive, symmetric, transitive. $\mathcal{R}$ is symmetric, but is neither reflexive nor transitive, and thus is not an equivalence relation. – Rebecca J. Stones Jul 20 '14 at 13:27
• @RebeccaJ.Stones: Note that the OP asks about connectedness of a graph, apparently meaning one whose edges are between positive integers which satisfy $(a+b)|(ab-1)$. That this is a symmetric relation means the graph is undirected for this purpose, and the absence of self-edges or transitive "triangles" on adjacent edges is not an impediment to asking about the connected components of the graph. – hardmath Jul 20 '14 at 13:40

We have $a \sim b$ if and only if there exist a sequence of integers $a_1, \ldots, a_n$ such that $a \ \mathcal{R} \ a_1 \ \mathcal{R} \ \cdots \ \mathcal{R} \ a_n \ \mathcal{R} \ b$. The relation $ab-1 = c (a + b)$ can be written as $(a-c)(b-c)=c^2+1$ and can be solves $a=c+d$ and $b=c+ \dfrac{c ^ 2 + 1} d$ where d is a divisor of $c^ 2 +1$.

If $c$ is even: All divisors of $c^2+1$ are congruent to $1$ modulo $4$ then $a$ is congruent to $b$ modulo $4$.

If $c$ is odd: $d$ is congruent to $1$ modulo $4$ and $\dfrac{c^2}d+1$ is congruent to $2$ modulo 4 or vice versa. If $c=4k+1$ then $a$ is congruent to $2$ modulo $4$ and $b$ is congruent to $3$ modulo $4$ or vice versa. If $c = 4k +3$ then $a$ is congruent to $0$ modulo $4$ and $b$ to $1$ modulo $4$ or vice versa.

Therefore there is probably three components in the graph (but I did not prove this):

The first formed only by $1$, the second one formed by integer congruent to $0$ modulo $4$ or $1$, and the last by integer congruent to $2$ or $3$ modulo $4$.

• is $(a-c)(b-c)=c^2+1$ I guess – user126154 Jul 28 '14 at 11:49
• @user126154 Thanks. Typo fixed. – Krokop Jul 29 '14 at 19:08

I'm posting this as CW because my "clarification" as to positive integers vs. integers generally being the domain/nodes got edited out (perhaps accidentally), and I wanted to show that without the restriction to positive integers, $1$ is not "isolated" as the Q asserts.

Let $R(a,b)$ mean $(a+b)|(ab-1)$ for integers $a,b$. Then:

$$R(1,0) \text{ since } (1+0)|(0-1)$$

$$R(0,-1) \text{ since } (0-1)|(0-1)$$

$$R(2,-1) \text{ since } (2-1)|(-2-1)$$

So this evidence points to restricting the graph to edges between positive integers.

• @FreeX: You're obviously engaged with this Question, since you offered the bounty. Why not clarify the point, first raised above in Commenting on the Q by Calvin Line, whether the graph is restricted to positive integer nodes? – hardmath Jul 24 '14 at 13:05
• Sure, Sorry. I edited my question. – Free X Jul 24 '14 at 17:31

This isn't an answer, but the following reformulation may lead to some inspiration.

For given $a,b\in\mathbb{N}$ let $c=a+b$. Then adjacency between $a$ and $b$ may be written as $ab\equiv 1$ mod $c$. But $b\equiv -a$ mod $c$, so we also have $a^2=b^2=-1$ mod $c$. This suggests we should consider for what moduli we can solve $x^2=-1$ i.e. for which $-1$ is a quadratic residue.

If the modulus $p$ is an odd prime, then we have the classical result that $-1$ is a quadratic residue mod $p$ iff $p\equiv 1$ mod 4. If $p=1$ mod 8 there is no simple expression for $x$, but if $p=5$ mod 8 then $x=2^{(p-1)/4}$ solves the congruence. Therefore if we choose $a\equiv 2^{(p-1)/4}$ for $0\leq a<p$ then $a$ and $p-a$ adjacent.

Hence the primes that equal 5 mod 8 generate a family of such adjacencies. By recalling other properties of the square root of -1 for various moduli, we can presumably generate other such families of adjacencies, and (optimistically) classify all adjacencies in a systematic way.

If you told me to find for a given set. $c$ - integer of any sign.

Then for the equation. $$\frac{ab-1}{a+b}=c$$

using factorization. In the following manner.

$$(k-n)(k+n)=4(c^2+1)$$

Then the solutions are.

$$a=c+\frac{k+n}{2}$$

$$b=c+\frac{k-n}{2}$$

$$.........$$

$$a=c-\frac{k+n}{2}$$

$$b=c-\frac{k-n}{2}$$