N5

Part of 2015 Indonesia MO Shortlist

Problems(1)

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

Source: INAMO Shortlist 2015 N5

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

b = 1

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

3

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

number theoryDiophantine equationIntegers