A number theory question: every integer n ≥ K can be written as n = xa + yb where a, b ∈ Z are nonnegative.

Question

I am an undergraduate math student who have meet a problem that confused me a lot.

Let x, y be positive integers such that gcd(x,y) = 1. Prove there is an integer K such that every integer n ≥ K can be written as n = xa + yb where a, b ∈ Z are nonnegative.

I have seen the answer such as

Show that every integer can be written in the form $5a + 7b$ for $a,b \in \mathbb{Z}$

but I am still quite confused. I had also noticed that the minimum of K could be (x-1)(y-1).

Sorry for all my typing mistakes and my bad written English. Thank you all for your help!

Answer 1

My thought process is to start with one of the $a,b$ as $0$, and then increase from there. So every $mx$ is expressible in the form $xa+y\cdot 0$. Next increase $b$ to one and make a new arithmetic progression as $mx+y$. Since gcd$(x,y)=1$, adding further $y$ will cycle through all the congruence classes modulo $x$, giving that at $K=(x-1)(y-1)$, every integer not less than $K$ will be a member of one of these arithmetic progressions.

Answer 2

Refer : https://en.m.wikipedia.org/wiki/Bézout%27s_identity See @above and you may multiply the expression by $k$ to arrive at $k$. i.e. Consider $$ax+by=1 \Rightarrow a(kx)+b(my)=k$$