Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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