# Linear Diophantine Set Proof

Let's say I have set S and T being the set of all integer solutions to $ax+by=c$ and $ax+by=nc$ respectively, and set S* might be the same as set T.

S* = $\{ (n x_0 + n y_0) | (x_0, y_0) \in S\}$

How would I prove that S* $\subseteq$ T for all values of a,b,c,n $\in \mathbb{Z}$

To be honest, I don't even understand the question. I know that $ax+by=c$ is a diophantine equation, and that there exists a complete integer solution where $x = x_0+ \frac{b}{d}n$, $y = y_0+ \frac{a}{d}n$ $\forall n \in\mathbb{Z}$. Sadly that's as far as I can go before asking for help.

-
I assume that you mean $(x_0,y_0) \in S$? These sets are collections of ordered pairs of solutions, so it doesn't make sense to say that $x_0 + y_0 \in S$. – NKS Jan 31 '12 at 3:56
yea you're right. I've edited it now. Thanks – WhiteBit Jan 31 '12 at 4:09
Still not right: do you want $S^*$ (and $T$) to be sets of pairs as well? – Arturo Magidin Jan 31 '12 at 4:30
The use of "for all values" is also confusing. You can show, easily, that for a particular fixed $a,b,c,n$, you have a certain inclusion (namely, if $(x_0,y_0)$ is a solution to $ax+by=c$, then $(nx_0,ny_0)$ is a solution to $ax+by=nc$); but talking about "for all values" suggests that you may place multiple conditions on an $(x_0,y_0)\in S$, which I suspect is not the case. – Arturo Magidin Jan 31 '12 at 4:43
@AndréNicolas: The post asks for a proof that $S^*$ is contained in $T$, not that it equals $T$. Though of course you are correct that in general it will not be the case that they are equal... – Arturo Magidin Jan 31 '12 at 4:44

The statement that $S^* \subseteq T$ is equivalent to showing that if $(x_0,y_0)$ is an integer solution to $ax+by=c$, then $(nx_0,ny_0)$ is an integer solution to $ax+by=nc$.
This is easy: if $ax_0+by_0 = c$, then $a(nx_0) + b(ny_0) = n(ax_0+by_0) = nc$. And of course, if $x_0$, $y_0$, and $n$ are integers, then so are $nx_0$ and $ny_0$.
However, it is not the case that every solution to $ax+by=nc$ is necessarily $n$ times a solution to $ax+by$, as André Nicolas shows in the comments with an explicit example.