Number Theory- Mathematical Proof

Question

I am trying to prove a theorem in my textbook using another theorem. What I need to show that

if a,b, and c are positive integers, show that the least positive integer linear combination of a and b equals the least positive integer linear combination of a+cb and b.

Any help would be great, I am new at proving things in mathematics.

Answer 1

Let the least positive linear combination of $a,b$ be $f$. You can write $f=da+eb$ Now show you can write $f$ as a linear combination of $a+cb, b$. You should be able to find explicit coefficients for the combination. To show this is minimum, assume you can write $g \lt f$ as a linear combination of $a+cb, b$. Show you can write $g$ as a linear combination of $a,b$ violating the assumption that $f$ is the minimum positive combination.

Answer 2

Hint. Show that the pairs $a + cb, b$ and $a, b$ have the same linear combinations.

That is, show that every linear combination of $a + cb$ and $b$ is a linear combination of $a$ and $b$. Conversely, show that every linear combination of $a$ and $b$ is a linear combination of $a + cb$ and $b$