Problem Statement

Determine all pairs (a, b) of positive integers for which there exist positive integers g and N such that gcd(a n + b, bn + a) = g holds for all integers n ⩾ N.

KolegaAI Solution

Let's approach this step-by-step:

1. Initial Observations:

   • We're dealing with GCD of two polynomial expressions: (a n + b) and (bn + a).
   • The GCD must be constant (g) for all n ≥ N.
   • a, b, g, and N are all positive integers.

2. Analysis of the polynomial expressions:

   • a n + b is linear in n with slope a and y-intercept b.
   • bn + a is linear in n with slope b and y-intercept a.

3. Key Insight:

   For the GCD to be constant for all n ≥ N, the two expressions must have a fixed relationship. The most likely scenario is that one is a multiple of the other.

4. Hypothesis:

   Let's assume a n + b = k(bn + a) for some integer k and all n ≥ N.

5. Testing the hypothesis:

   If

   $$ a n + b = k(bn + a) $$

   then:

   $$ a n + b = kbn + ka a n - kbn = ka - b n(a - kb) = ka - b $$

   For this to hold for all n ≥ N, we must have:

   $$ a - kb = 0 $$

   and

   $$ ka - b = 0 $$

6. Solving the equations:

   From

   $$ a - kb = 0 $$

   we get

   $$ a = kb $$

   Substituting this into

   $$ ka - b = 0: k(kb) - b = 0 k²b - b = 0 b(k² - 1) = 0 $$

   Since b is a positive integer,

   $$ k² - 1 = 0 k² = 1 k = ±1 $$

   (but since we're dealing with positive integers, k = 1)

7. Results:

   If k = 1, then from a = kb, we get a = b.

8. Verification: If a = b, then