Maths Olympiad Prep

Library / /18 of 37

Number theory Difficulty 8.0 Shortlist Find the answer

Find all pairs of positive integers (m,n) (m,n) such that mn 1\text{mn 1} divides (n 2 n 1) 2\text{(n 2 n 1) 2}.

Aaron Pixton.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To find all pairs of positive integers (m,n)(m, n) such that mn1mn - 1 divides (n2n+1)2(n^2 - n + 1)^2, we need to analyze the given condition and derive the solutions.

First, let's denote d=mn1d = mn - 1. We need dd to divide (n2n+1)2(n^2 - n + 1)^2. This implies:
d(n2n+1)2. d \mid (n^2 - n + 1)^2.

We start by considering the trivial solution (m,n)=(2,2)(m, n) = (2, 2):
221=3and(222+1)2=32=9, 2 \cdot 2 - 1 = 3 \quad \text{and} \quad (2^2 - 2 + 1)^2 = 3^2 = 9,
which satisfies 393 \mid 9.

Next, we explore other potential solutions. Suppose (m,n)(m, n) is a solution with 2<n<m2 < n < m. We need to find k<nk < n such that (n,k)(n, k) is also a solution. This requires:
(n2n+1)21(modn). (n^2 - n + 1)^2 \equiv -1 \pmod{n}.

We analyze the inequalities:
n21(n2n+1)2mn1(n2n+1)2n21. n^2 - 1 \leq \frac{(n^2 - n + 1)^2}{mn - 1} \leq \frac{(n^2 - n + 1)^2}{n^2 - 1}.

Simplifying, we get:
(n2n+1)2n21n21    n2n+1n21    n2. \frac{(n^2 - n + 1)^2}{n^2 - 1} \geq n^2 - 1 \implies n^2 - n + 1 \geq n^2 - 1 \implies n \leq 2.

This implies that the solutions are limited to specific cases. By fixing initial values a0a_0 and b0b_0 with b02b_0 \leq 2, we can generate all solutions using the recurrence relation:
(ai,bi)i=0whereai=bi+1,bi=1bi+1[(bi+12bi+1+1)2ai+1bi+11+1] iN. (a_i, b_i)_{i=0}^{\infty} \quad \text{where} \quad a_i = b_{i+1}, \quad b_i = \frac{1}{b_{i+1}} \left[ \frac{(b_{i+1}^2 - b_{i+1} + 1)^2}{a_{i+1} b_{i+1} - 1} + 1 \right] \quad \forall \ i \in \mathbb{N}^*.

By working through this recurrence, we find that the solutions are:
(m,n)=(2,2)and(m,n)=(b1,b), (b,b+1) N. (m, n) = (2, 2) \quad \text{and} \quad (m, n) = (b_{\ell-1}, b_{\ell}), \ (b_{\ell}, b_{\ell+1}) \quad \forall \ \ell \in \mathbb{N}^*.

Cleaning up the recurrence relation:
bi+2=bi+132bi+12+3bi+1+bi2bibi+11 iN,b0=2,b1=5, b_{i+2} = \frac{b_{i+1}^3 - 2b_{i+1}^2 + 3b_{i+1} + b_i - 2}{b_i b_{i+1} - 1} \quad \forall \ i \in \mathbb{N}^*, \quad b_0 = 2, \quad b_1 = 5,
we get the sequence:
(bi)i=0=2,5,10,17,, (b_i)_{i=0}^{\infty} = 2, 5, 10, 17, \ldots,
which can be generalized as:
bi=(i+1)2+1. b_i = (i + 1)^2 + 1.

Thus, the pairs (m,n)(m, n) that satisfy the condition are:
(m,n)=(2,2)and(m,n)=((i+1)2+1,(i+2)2+1) iN. (m, n) = (2, 2) \quad \text{and} \quad (m, n) = ((i+1)^2 + 1, (i+2)^2 + 1) \quad \forall \ i \in \mathbb{N}.

The answer is: (2,\boxed{(2,} 2) \text{} and } ((i+1)^2 + 1, (i+2)^2 + 1) \text{} for all } i N.{\in \mathbb{N}}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.