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.

  • $\begingroup$ 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$. $\endgroup$ – NKS Jan 31 '12 at 3:56
  • $\begingroup$ yea you're right. I've edited it now. Thanks $\endgroup$ – WhiteBit Jan 31 '12 at 4:09
  • $\begingroup$ Still not right: do you want $S^*$ (and $T$) to be sets of pairs as well? $\endgroup$ – Arturo Magidin Jan 31 '12 at 4:30
  • $\begingroup$ 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. $\endgroup$ – Arturo Magidin Jan 31 '12 at 4:43
  • $\begingroup$ @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... $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.