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.

  • 3
    $\begingroup$ Do you think it is important that we know what $\mathcal{R}$ means? $\endgroup$ – Elchanan Solomon Jul 20 '14 at 12:14
  • 3
    $\begingroup$ 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$. $\endgroup$ – Rebecca J. Stones Jul 20 '14 at 13:17
  • 1
    $\begingroup$ Are you allowed to use negative integers, or is this graph only on positive integers? $\endgroup$ – Calvin Lin Jul 20 '14 at 13:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Rebecca J. Stones Jul 20 '14 at 13:27
  • 2
    $\begingroup$ @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. $\endgroup$ – hardmath Jul 20 '14 at 13:40

A partial answer :

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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ is $(a-c)(b-c)=c^2+1$ I guess $\endgroup$ – user126154 Jul 28 '14 at 11:49
  • $\begingroup$ @user126154 Thanks. Typo fixed. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ @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? $\endgroup$ – hardmath Jul 24 '14 at 13:05
  • $\begingroup$ Sure, Sorry. I edited my question. $\endgroup$ – 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.

| cite | improve this answer | |

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.


Then the solutions are.






| cite | improve this answer | |

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.