Maths Olympiad Prep

Library / /237 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Example 2 Let a,ba, b be coprime positive integers. Prove: the indeterminate equation
ax+by=ababa x+b y=a b-a-b

has no non-negative integer solutions.

Solution

If there exists a pair of non-negative integers (x0,y0)\left(x_{0}, y_{0}\right) satisfying (1), then
a(x0+1)+b(y0+1)=ab,a\left(x_{0}+1\right)+b\left(y_{0}+1\right)=a b,

then, we should have

and
thus
ab(y0+1)(a,b)=1ay0+1\begin{array}{l} a \mid b\left(y_{0}+1\right) \\ (a, b)=1 \\ a \mid y_{0}+1 \end{array}

Since aa and y0+1y_{0}+1 are both positive integers, we have ay0+1a \leqslant y_{0}+1.
Similarly, we can prove: bx0+1b \mid x_{0}+1, hence bx0+1b \leqslant x_{0}+1. But in this case, the left side of (2) ab+ba=\geqslant a b+b a= 2ab>2 a b> the right side of (2), which is a contradiction.

Therefore, (1) has no non-negative integer solutions.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.