Maths Olympiad Prep

Library / /437 of 520

Number theory Difficulty 6.1 National olympiad Prove it

198. Let pp and qq be two coprime natural numbers. A natural number nn will be called "good" if it can be represented as px+qyp x + q y, where xx and yy are non-negative integers, and "bad" otherwise.

a) Prove that there exists a number AA such that if the sum of two integers is equal to AA, then one of them is necessarily "good" and the other is "bad".

b) If the numbers pp and qq are given, how can one find the number of all possible "bad" natural numbers?

Solution

198. From the fact that pp and qq are coprime, using the Euclidean algorithm, it is established that any integer nn can be represented in the form:

n=px+qy, where x and y are integers.  n=p x+q y, \text { where } x \text { and } y \text { are integers. }

Indeed, let p>qp>q; then p=qd+rp=q d+r, where 0000 (since the number nn is positive). On the plane with coordinates x0,y0x_{0}, y_{0}, the lines x0=q,y0=0,px0+x_{0}=q, y_{0}=0, p x_{0}+ +qy0=0+q y_{0}=0 outline a shaded triangle as shown in Fig. 22; we need to find the number of "integer points" in this triangle. It is clear that this number is exactly half the number of "integer points" in the rectangle OABCO A B C (there are no "integer points" on the diagonal of the rectangle, since pp and qq are coprime). Since the number of "integer points" inside the rectangle is obviously (p1)(q1)(p-1) \cdot(q-1), we arrive at the same value of the desired number tt as above.

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.