MathDB
gcd(n^a + 1, n^b + 1) <= n^{gcd(a,b)} + 1

Source: 2008 Indonesia TST stage 2 test 3 p3

December 15, 2020
GCDgreatest common divisornumber theory

Problem Statement

Let nn be an arbitrary positive integer. (a) For every positive integers aa and bb, show that gcd(na+1,nb+1)≤ngcd(a,b)+1gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1. (b) Show that there exist infinitely many composite pairs (a,b)a, b), such that each of them is not a multiply of the other number and equality holds in (a).
Back to ProblemsView on AoPS