why $ax + by$ can take any value if their gcd is $1$

Question

Given 2 integers $a$ and $b$ whose gcd is 1 (coprime). Now the value of $ax + by$ can be any multiple of gcd$(a, b)$, which is 1 in this case. So literally $ax + by$ can be any integer value. I have verified it for some small coprime numbers, but what is the mathematical reason behind this?

Answer 1

$\gcd(a,b)=1$ if and only if $a$ is a unit modulo $b$. Thus, there is some integer $p$ such that $ap\equiv 1 \pmod b$, which means that there is some integer $q$ such that $ap=1+bq$.

We can rewrite this as $ap-bq=1$. Then for any integer $k$ we have $(x,y)=(kp,-kq)$ as a solution to the equation $ax+by=k$.

Answer 2

This is, I think, pretty easy to see once one realizes that, for $a, b \in \Bbb Z$ with

$\gcd(a, b) = d, \tag 1$

there exist $x, y \in \Bbb Z$ with

$ax + by = d; \tag 2$

the easiest way I know to see this is to use the fact that $\Bbb Z$ is a principal ideal domain (or PID); that is, for any ideal

$J \subset \Bbb Z \tag 3$

there exists some $j \in \Bbb Z$ with

$J = (j) = j\Bbb Z; \tag 4$

given that $\Bbb Z$ is a PID, we examine the ideal generated by $a$ and $b$:

$(a, b) = \{am + bn \mid m, n \in \Bbb Z \}; \tag 5$

we then have

$(a, b) = (d) = d\Bbb Z, \tag 6$

for some $d \in \Bbb Z$, and thus there are $x, y \in \Bbb Z$ such that (2) binds. It follows from (4) and (6) that

$d \mid a, \; d \mid b; \tag 7$

thus, by definition,

$d \mid \gcd(a, b), \tag 8$

and since

$\gcd(a, b) \mid a, \; \gcd(a, b) \mid b, \tag 9$

we see via (2) that

$\gcd(a, b) \mid d; \tag{10}$

it follows from (8) and (10) that

$d = \gcd(a, b); \tag{11}$

therefore there are $x, y \in \Bbb Z$ with

$\gcd(a, b) = ax + by; \tag{12}$

now if

$\gcd(a, b) = 1, \tag{13}$

we have

$ax + by = 1, \tag{14}$

and thus for $z \in \Bbb Z$

$z = z(ax + by) = a(xz) + b(yz); \tag{15}$

therefore, for any $z \in \Bbb Z$ there exist $r, s \in \Bbb Z$ with

$z = ar + bt; \tag{16}$

the expression may take on any integer value; the essential mathematical reason is that $\Bbb Z$ is a PID.

Answer 3

If you want a mathematical reason, then you have to specify that you are working with integers.

Here $1$ is a generator of the integers $\mathbb Z$ as an additive group ($-1$ is the only other generator), and since you have expressed $1$ in terms of the elements $a$ and $b$ you have been given, these two elements together generate the whole group - ie every integer is included.

The arithmetic expression of $n$ in terms of $a$ and $b$ has been dealt with in another answer - that tells you how you can do it.

There are two things here which are worth noting:

First, the set of numbers $ax+by$ express every integer multiple of the gcd or $a$ and $b$ whatever that is - call it $d$. Then $d$ is the least possible positive value of $ax+by$ and every multiple of $d$ is expressible. Just multiply everything by $n$.

Second, when looking to see what subgroup (or other subobject) is generated by a set of elements, we might look to see the "simplest" elements formed from the set we have. If I can generate some element $z$ from the set I've been given, I can then generate everything I can make using $z$.