2
$\begingroup$

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}$?

$\endgroup$
  • 11
    $\begingroup$ Hint: $\gcd(3,5)=1$. $\endgroup$ – Fimpellizieri May 18 '16 at 14:37
  • 4
    $\begingroup$ 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$. $\endgroup$ – JMoravitz May 18 '16 at 14:38
  • 2
    $\begingroup$ This is not (elementary-set-theory). This is elementary number theory. $\endgroup$ – GEdgar May 18 '16 at 14:41
  • 1
    $\begingroup$ @Fimpellizieri That is not a hint, that is the answer! $\endgroup$ – Jasper May 18 '16 at 14:41
  • 2
    $\begingroup$ @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)$. $\endgroup$ – user236182 May 18 '16 at 14:42
7
$\begingroup$

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}$.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – user236182 May 18 '16 at 14:41
  • 1
    $\begingroup$ To explain my downvote (which was perhaps slightly unfair) I think "Hint: Bezout's lemma" would have been a better answer.... $\endgroup$ – goblin May 18 '16 at 15:15
4
$\begingroup$

$ \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} $.

$\endgroup$
  • 5
    $\begingroup$ I would wager that the OP is not familiar with ideals. $\endgroup$ – user324795 May 18 '16 at 14:45
1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Perhaps you should delete your other answer? $\endgroup$ – Starfall May 18 '16 at 15:32
  • $\begingroup$ 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! $\endgroup$ – Jasper May 18 '16 at 15:42
  • $\begingroup$ You're welcome :) $\endgroup$ – Jasper May 18 '16 at 15:45
  • $\begingroup$ 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. $\endgroup$ – Jasper May 18 '16 at 15:48
  • 2
    $\begingroup$ 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. $\endgroup$ – Fimpellizieri May 18 '16 at 16:10
0
$\begingroup$

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

$\endgroup$

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.