MathDB

ax+by=n, odd no. of non-negative integer solutions (x, y)

Source: INAMO Shortlist 2015 N5

May 14, 2019

number theoryDiophantine equationIntegers

Problem Statement

Given a prime number

n \ge 5

. Prove that for any natural number

a \le \frac{n}{2}

, we can search for natural number

b \le \frac{n}{2}

so the number of non-negative integer solutions

(x, y)

of the equation

ax+by=n

to be odd*.
Clarification: * For example when

n = 7, a = 3

, we can choose

b = 1

so that there number of solutions og

3x + y = 7

to be

3

(odd), namely:

(0, 7), (1, 4), (2, 1)

Back to Problems View on AoPS