Dividing Pairs

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Dividing Pairs

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Own

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

106 posts

#1 h Apr 13, 2025, 8:39 AM

Y by

Let $a$ and $b$ be positive integers.
Suppose that $a$ is a divisor of $b^2 + 1$ and $b$ is a divisor of $a^2 + 1$ .
Find all such pairs $(a, b)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

53 posts

ND_

#2 h Apr 13, 2025, 9:20 AM

Y by

$(F_{2n-1}, F_{2n+1})$ , where $F_n$ is the Fibonacci series

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

106 posts

#3 h Apr 24, 2025, 12:59 PM

Y by

Can you prove it?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ye3L101L201L401L701L100

3 posts

Ye3L101L201L401L701L100

#4 h Apr 27, 2025, 11:01 AM

Y by

IT'S MY FIRST POST
SO I WROTE THIS IN DETAIL
:-D

:-D

SORRY FOR THAT I CAN'T USE LATEX AND MY BAAAAAD ENGLISH

a | b^2 + 1
b | a^2 + 1
--> ab | (a^2 + 1) * (b^2 + 1)
--> ab | a^2 + b^2 + 1
IT IS VERY FAMOUS PROBLEM
--> IF (a^2 + b^2 + 1) / ab IS INTEGER, THE ONLY POSSIBLE VALUE IS 3
SO a^2 - 3ab + b^2 + 1 = 0

BY VIETA
IF (x, y) SATISFIES THE CONDITION, (y, 3y-x) ALSO SATISFIES THE CONDITION (OBVIOUSLY x < y < 3y-x)
(1,1) (= (F(-1), F(1)) ) SATISFIES THE CONDITION
(1,2) (= (F(1), F(3)) ) ALSO SATIS FIES THE CONDITION
WE KNOW F(N+4) = 3 * F(N+2) - F(N)
SO ( F(2N-1), F(2N+1) ) SATISFIES THE CONDITION

IF THERE IS ANOTHER PAIR THAT SATISFIES THE CONDITION,
WE CAN PERFORM THE REVERSE PROCESS ENOUGH TIMES TO REDUCE THE SMALLER NUMBER IN THE PAIR TO 1.
THE BIGGER NUMBER IN THE PAIR IS 1OR2
SO THERE IS NO ANOTHER PAIR

WE KNOW GCD ( F(2N-1), F(2N+1) ) = 1
LET a = F(2N-1), b = F(2N+1)
ab | a^2 + b^2 + 1
--> a | a^2 + b^2 + 1 --> a | b^2 +1
IN THE SAME WAY b | a^2 + 1
:-D

:-D

+) WE CAN SHOW DIRECTLY F(2N-1) | F(2N+1)^2 + 1 and F(2N+1) | F(2N-1)^2 + 1 BY MATHEMATICAL INDUCTION OR MANY OTHER METHODS :-)

:-)

END

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

106 posts

#5 h Apr 27, 2025, 2:24 PM

Y by

Thanks! I will write with LaTeX

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

106 posts

#6 h Apr 27, 2025, 2:26 PM

Y by

$a \mid b^2 + 1$ $b \mid a^2 + 1$ $\Rightarrow ab \mid (a^2 + 1)(b^2 + 1)$ $\Rightarrow ab \mid a^2 + b^2 + 1$

$\text{If } \frac{a^2 + b^2 + 1}{ab} \text{ is an integer, the only possible value is 3.}$
$a^2 - 3ab + b^2 + 1 = 0$
\textbf{BY VIETA}

$\text{If } (x, y) \text{ satisfies the condition, } (y, 3y - x) \text{ also satisfies the condition (obviously } x < y < 3y - x\text{).}$
$(1, 1) = (F(-1), F(1)) \text{ satisfies the condition.}$ $(1, 2) = (F(1), F(3)) \text{ also satisfies the condition.}$
$\text{We know } F(N+4) = 3F(N+2) - F(N).$
$\text{So } (F(2N-1), F(2N+1)) \text{ satisfies the condition.}$
\textit{If there is another pair that satisfies the condition,}

$\text{We can perform the reverse process enough times to reduce the smaller number in the pair to 1.}$ $\text{The bigger number in the pair is either 1 or 2.}$ $\text{So there is no other pair.}$
$\text{We know that } \gcd(F(2N-1), F(2N+1)) = 1.$
Let $a = F(2N-1), b = F(2N+1)$ , then:

$ab \mid a^2 + b^2 + 1$
$\Rightarrow a \mid a^2 + b^2 + 1 \Rightarrow a \mid b^2 + 1$
$\text{In the same way, } b \mid a^2 + 1$
$\text{:-D}$
$\text{+ We can show directly that } F(2N-1) \mid F(2N+1)^2 + 1 \text{ and } F(2N+1) \mid F(2N-1)^2 + 1 \text{ by mathematical induction or other methods.}$

This post has been edited 2 times. Last edited by Jackson0423, Apr 27, 2025, 2:28 PM
Reason: A

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a