Competition problem — Number theory

Library / /113 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

Example 6 If $(a, b)=1$ , then any integer $n$ can be expressed as $n=a x+b y, \quad x, y$ are integers.

Solution

From $(a, b)=1$ and Theorem 8, we know that there exist $x_{0}, y_{0}$ such that $a x_{0}+b y_{0}=1$ . Therefore, taking $x=$ $n x_{0}, y=n y_{0}$ satisfies the requirement.

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.