Associated Topics || Dr. Math Home || Search Dr. Math

### Pairs of Integers

```
Date: 08/16/97 at 07:08:39
From: pal sandip
Subject: Number theory

Show that there are infinitely many pairs of integers(x,y) such
that x|y**2+m and y|x**2+m where m is any chosen integer.

Moreover, gcd(x,y) = 1.
```

```
Date: 08/21/97 at 09:01:46
From: Doctor Rob
Subject: Re: Number theory

This is certainly false if m = 0, since then x|y^2 and (x,y) = 1 =>
x = 1 or -1, and similarly y = 1 or -1, so there are just four pairs.

For m = -a^2, this is easy:  (y-a,y) and (y+a,y) with (y,a) = 1 are
two infinite families, and (a,a*z) is another (although not relatively
prime unless a = 1).

For m = 1, the sequence of values which works is:

(1,2), (2,5), (5,13), (13,34), (34,89), (89,233), (233,610), ...

which are the Fibonacci numbers (F[2*k-1], F[2*k+1]). The appropriate
identity is F[2*j-1]*F[2*j+3] = F[2*j+1]^2 + 1 applied with j = k and
with j = k - 1. The recursion satisfied by the x-values (and by the
y-values) is x[n+1] = 3*x[n] - x[n-1].

For m = 2, the sequence of values which works is:

(1,3), (3,11), (11,41), (41,153), (153,571), (571,2131), ...

The recursion satisfied by the x-values (and by the y-values) is
x[n+1] = 4*x[n] - x[n-1].  There is the identity
x[j-1]*x[j+1] = x[j]^2 + 2, which is applied with j = n and j = n-1.

For m = 3, there are two infinite sequences of the same sort:

(1,2), (2,7), (7,26), (26,97), (97, 362), (362, 1351), ...
(1,4), (4,19), (19,91), (91,436), (436,2089), ...

The first satisfies x[n+1] = 4*x[n] - x[n-1], which we treated in the
preceding paragraph, and the second satisfies x[n+1] = 5*x[n] - x[n-
1]. Presumably there is an associated identity which works here, too.

For m = 4, there is one sequence:

(1,5), (5,29), (29,169), (169,985), ...

which satisfies x[n+1] = 6*x[n] - x[n-1].  Presumably there is an
associated identity which works here, too.

Do you detect a pattern?

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search