Blogs, Mathematical Reasoning, MR Study Help

Integers written as 13x+10y

In the following posts, we will be looking more at how to prove different theorems. In some of these, we will have to determine if the theorem is true, then prove that our answer is correct. You can find more examples of proof writing in the Study Help category for mathematical reasoning. You can also view the available videos on YouTube.

\(\left\{13x+10y:x,y \in \mathbb{Z}\right\}=\mathbb{Z}\)

Prove or disprove that \(\left\{13x+10y:x,y \in \mathbb{Z}\right\}=\mathbb{Z}\).

Examples

As we start this problem, we want elements will be in each of the sets. While we know that \(\mathbb{Z}\) is all the integers, we would get that the terms in the other set would be things like \(0, 13, 10, 23, -13, -10, -3\). We see these by letting \((x,y)=(0,0),(1,0),(0,1),(1,1),(-1,0),(0,-1),(-1,1)\).

We can quickly see that every element in \(\left\{13x+10y:x,y \in \mathbb{Z}\right\}\) is also an integer. As we start to think about why, we realize that we are multiplying and adding integers, and therefore we should get out on an integer. On the other hand, we still need to determine if every integer can be written in the form \(13x+10y\).

We want to be able to write any integer in this form, so trying to write 1 in this form will be a good indicator of whether or not this would always be possible. With a little trial and error, we can see that \(13(-3)+10(4)=1\), so \(1 \in \left\{13x+10y: x,y \in \mathbb{Z}\right\}\). Now that we have 1, however, we can see that we can get any other integer by multiplying both and \(x\) and \(y\) by the integer we are trying to find. We are now ready to give our proof.

\(\left\{13x+10y:x,y \in \mathbb{Z}\right\} \subseteq \mathbb{Z}\)

In order to prove that the two sets are equal, recall that we will show that each set is a subset of the other. That is, we will show that every element in one, is also in the other.

Proof

Let \(a \in \left\{13x+10y:x,y \in \mathbb{Z}\right\}\). We then note that, since \(13 \in \mathbb{Z}\) and \(x \in \mathbb{Z}\), we must have that \(13x \in \mathbb{Z}\) since the integers are closed under multiplication. In a similar manner, \(10y \in \mathbb{Z}\). Now, since \(\mathbb{Z}\) is closed under addition, we have that \(a=13x+10y \in \mathbb{Z}\).

\(\mathbb{Z} \subseteq \left\{13x+10y:x,y \in \mathbb{Z}\right\}\).

Proof

Let \(k \in \mathbb{Z}\). We then note that
\begin{align*}
13(-3k)+10(4k)&=(13(-3)+10(4))k \\
&=1k=k.
\end{align*}
Therefore, by letting \(x=-3k\) and \(y=4k\), we get that \(k=13x+10y\).

Conclusion

In this situation we wanted to show that two sets were equal. While we were quickly able to see that the first was a subset of the second, more thought was required to show the other direction. By choosing helpful examples to work, we were able to find the theorem to be true while constructing a proof.

For more help with proofs, make sure to continue working on the other problems we have posted solutions for in Study Help. If you find these helpful, make sure to let other people know about them so that they can get help as well.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.