Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

4 Answers 4

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

share|improve this answer
1  
is $(a-c)(b-c)=c^2+1$ I guess –  user126154 Jul 28 at 11:49
    
@user126154 Thanks. Typo fixed. –  Krokop Jul 29 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.

share|improve this answer
    
@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 at 13:05
    
Sure, Sorry. I edited my question. –  Free X Jul 24 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.

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

$$(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}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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