# Show that $5\mathbb{Z}+3\mathbb{Z}=\mathbb{Z}$

I showed this: $5\mathbb{Z}+5\mathbb{Z}=5\mathbb{Z}$.

i.e., $5\mathbb{Z}+5\mathbb{Z}=5(\mathbb{Z}+\mathbb{Z})$. So, since we know $\mathbb{Z}+\mathbb{Z}=\mathbb{Z}$, $5\mathbb{Z}+5\mathbb{Z}=5(\mathbb{Z}+\mathbb{Z})=5\mathbb{Z}$.

So, how can I prove $5\mathbb{Z}+3\mathbb{Z}=\mathbb{Z}$?

• Hint: $\gcd(3,5)=1$. – Fimpellizieri May 18 '16 at 14:37
• The notation above is slightly messy, but it sounds like you are asking to show that every integer can be written as a sum of two integers, one of which a multiple of five, and one of which a multiple of three. As Fimpellizieri points out, $\gcd(5,3)=1$. As a more explicit hint, $1=-1\cdot 5 + 2\cdot 3$. – JMoravitz May 18 '16 at 14:38
• This is not (elementary-set-theory). This is elementary number theory. – GEdgar May 18 '16 at 14:41
• @Fimpellizieri That is not a hint, that is the answer! – Jasper May 18 '16 at 14:41
• @Jasper You also need to know the corollary of Bézout's lemma. Or notice that $3(2)+5(-1)=1$. Here the extended Euclidean algorithm can help to find the $(2), (-1)$. – user236182 May 18 '16 at 14:42

Clearly $5\mathbb{Z}+3\mathbb{Z}\subset \mathbb{Z}$. For the reverse inclusion, suppose $x\in\mathbb{Z}$. Since $\gcd(3,5)=1$, there exist integers $a,b$ such that $3a+5b=1$. Hence, $x=3(ax)+5(bx)\in3\mathbb{Z}+5\mathbb{Z}$.

• The fact that there exist such $a,b\in\mathbb Z$ follows from Bézout's lemma. Or simply by noticing $3(2)+5(-1)=1$. You can find the $a,b\in\mathbb Z$ using, e.g., the extended Euclidean algorithm. – user236182 May 18 '16 at 14:41
• To explain my downvote (which was perhaps slightly unfair) I think "Hint: Bezout's lemma" would have been a better answer.... – goblin May 18 '16 at 15:15

$\mathbb{Z}$ is a principal ideal domain, which means that the ideal $J = 5\mathbb{Z} + 3\mathbb{Z}$ is principal, say $J = (a)$. But $5 \in J$ and $3 \in J$, which means that $a$ divides both $5$ and $3$, from which it follows that $a = 1$ and $J = (1) = \mathbb{Z}$.

• I would wager that the OP is not familiar with ideals. – user324795 May 18 '16 at 14:45

Let $m,n\in\mathbb{Z}$. So, we have $5m+3n=1$ by the Bezout's lemma. Let $k\in\mathbb{Z}$. Then, $5(mk)+3(nk)=k$. So, we know $mk$ and $nk$ are in $\mathbb{Z}$. Hence, $k=5(mk)+3(nk)\in 5\mathbb{Z}+3\mathbb{Z}$. Therefore, $5\mathbb{Z}+3\mathbb{Z}=\mathbb{Z}$.

Now, is it enough and clear?

• Perhaps you should delete your other answer? – Starfall May 18 '16 at 15:32
• Add $3\mathbb{Z} + 5\mathbb{Z} = \{ 3n + 5m ~:~ m,n\in \mathbb{Z} \}$, and that $\gcd(3,5)=1$ to it, and I think it's sufficiently clear in my opinion! – Jasper May 18 '16 at 15:42
• You're welcome :) – Jasper May 18 '16 at 15:45
• I just notice one thing. Strictly speaking you prove that $3\mathbb{Z} + 5\mathbb{Z} \supset \mathbb{Z}$, so it's still possible that for example $3\mathbb{Z} + 5\mathbb{Z} = \frac{1}{2}\mathbb{Z}$. Adding a remark that $5\mathbb{Z} + 3\mathbb{Z} \subset \mathbb{Z}$ holds is for this reason of importance, yet you can also "whipe-it-off" as something that is trivial. – Jasper May 18 '16 at 15:48
• As written, it is still 'wrong'. Instead, try something like this: Because $\gcd(3,5)=1$, by Bezout's lemma there are $m,n \in \mathbb{Z}$ with $5m + 3n = 1$. Now, if $k \in \mathbb{Z}$, $5(mk)+3(nk)=k$, so $k \in 5\mathbb{Z}+3\mathbb{Z}$; in other words, $\mathbb{Z} \subset 5\mathbb{Z}+3\mathbb{Z}$. The other inclusion, that $5\mathbb{Z}+3\mathbb{Z} \subset \mathbb{Z}$, is trivial and equality follows. – Fimpellizieri May 18 '16 at 16:10

5(-1)+ 3(2)= 1. Thus 5(-n)+3(2n)=n.