Coprime numbers

Question

Why is it true that if $a, b$ are coprime then there exists an $N$ such that for all $n> N,$ $n$ can be expressed as $n= ca+db$ where $c, d$ are non-negative?

Thanks.

Answer 1

By Bézout's identity there exists $p,q \in \mathbb{Z}$ such that $ 1 = pa + qb $ so we write $n = np a + nq b.$

We have $ n = (np+kb)a + (nq -ka)b$ for all $ k\in \mathbb{Z}.$

For both these coefficients to be positive we need $\displaystyle - \frac{np}{b} < k < \frac{nq}{a} $ and for sufficiently large $n$ this interval is large enough so that we can pick an integer from that range.

Answer 2

There is a proof on page 3 of this PDF.