How to prove that if a number is divisible by two other numbers, then it is divisible by their product
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I would like to prove if $a mid n$ and $b mid n$ then $a cdot b mid n$ for $forall n ge a cdot b$ where $a, b, n in mathbbZ$
I'm stuck.
$n = a cdot k_1$
$n = b cdot k_2$
$therefore a cdot k_1 = b cdot k_2$
EDIT: so for fizzbuzz it wouldn't make sense to check to see if a number is divisible by 15 to see if it's divisible by both 3 and 5?
elementary-number-theory divisibility
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
asked May 2 '14 at 0:02
Celeritas
97311534
add a comment |Â
up vote
1
down vote
favorite
I would like to prove if $a mid n$ and $b mid n$ then $a cdot b mid n$ for $forall n ge a cdot b$ where $a, b, n in mathbbZ$
I'm stuck.
$n = a cdot k_1$
$n = b cdot k_2$
$therefore a cdot k_1 = b cdot k_2$
EDIT: so for fizzbuzz it wouldn't make sense to check to see if a number is divisible by 15 to see if it's divisible by both 3 and 5?
elementary-number-theory divisibility
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
asked May 2 '14 at 0:02
Celeritas
97311534
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime, then $abmid n$.
– David
May 2 '14 at 0:13
Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment.
– David
May 2 '14 at 0:16
@David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime?
– Celeritas
May 2 '14 at 2:43
It is a sufficient condition that $a,b$ are relatively prime.
– David
May 2 '14 at 3:00
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I would like to prove if $a mid n$ and $b mid n$ then $a cdot b mid n$ for $forall n ge a cdot b$ where $a, b, n in mathbbZ$
I'm stuck.
$n = a cdot k_1$
$n = b cdot k_2$
$therefore a cdot k_1 = b cdot k_2$
EDIT: so for fizzbuzz it wouldn't make sense to check to see if a number is divisible by 15 to see if it's divisible by both 3 and 5?
elementary-number-theory divisibility
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
asked May 2 '14 at 0:02
Celeritas
97311534
I would like to prove if $a mid n$ and $b mid n$ then $a cdot b mid n$ for $forall n ge a cdot b$ where $a, b, n in mathbbZ$
I'm stuck.
$n = a cdot k_1$
$n = b cdot k_2$
$therefore a cdot k_1 = b cdot k_2$
EDIT: so for fizzbuzz it wouldn't make sense to check to see if a number is divisible by 15 to see if it's divisible by both 3 and 5?
elementary-number-theory divisibility
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
asked May 2 '14 at 0:02
Celeritas
97311534
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
edited Aug 28 at 12:46
Sri Krishna Sahoo
571117
571117
asked May 2 '14 at 0:02
Celeritas
97311534
asked May 2 '14 at 0:02
Celeritas
97311534
asked May 2 '14 at 0:02
Celeritas
97311534
97311534
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime, then $abmid n$.
– David
May 2 '14 at 0:13
Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment.
– David
May 2 '14 at 0:16
@David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime?
– Celeritas
May 2 '14 at 2:43
It is a sufficient condition that $a,b$ are relatively prime.
– David
May 2 '14 at 3:00
add a comment |Â
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime, then $abmid n$.
– David
May 2 '14 at 0:13
Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment.
– David
May 2 '14 at 0:16
@David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime?
– Celeritas
May 2 '14 at 2:43
It is a sufficient condition that $a,b$ are relatively prime.
– David
May 2 '14 at 3:00
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime, then $abmid n$.
– David
May 2 '14 at 0:13
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime, then $abmid n$.
– David
May 2 '14 at 0:13
Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment.
– David
May 2 '14 at 0:16
Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment.
– David
May 2 '14 at 0:16
@David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime?
– Celeritas
May 2 '14 at 2:43
@David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime?
– Celeritas
May 2 '14 at 2:43
It is a sufficient condition that $a,b$ are relatively prime.
– David
May 2 '14 at 3:00
It is a sufficient condition that $a,b$ are relatively prime.
– David
May 2 '14 at 3:00
add a comment |Â
4 Answers
4
active
oldest
votes
up vote
2
down vote
accepted
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime (have no common factor except 1), then $abmid n$.
Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $bmid ak$; since $a,b$ are relatively prime this implies $bmid k$, so $k=bm$, so $n=abm$; therefore $abmid n$.
Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.
answered May 2 '14 at 0:22
David
66.2k663125
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
add a comment |Â
up vote
6
down vote
This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 times 6 < 30$.
answered May 2 '14 at 0:11
Xelvonar
1064
add a comment |Â
up vote
2
down vote
Updated: The edited version is still not true. At least two counterexamples in the comments below.
Prior counterexample: This is not true. $12|36$ and $9|36$, but $12cdot9 = 108 not | 36$.
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
1
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
 |Â
show 2 more comments
up vote
0
down vote
Hint $, a,bmid niff rm lcm(a,b)mid n!!!overset large times, (a,b)iff abmid n(a,b),, $ which is not equivalent to $,abmid n $
answered May 2 '14 at 1:21
Number
1
add a comment |Â
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime (have no common factor except 1), then $abmid n$.
Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $bmid ak$; since $a,b$ are relatively prime this implies $bmid k$, so $k=bm$, so $n=abm$; therefore $abmid n$.
Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.
answered May 2 '14 at 0:22
David
66.2k663125
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
add a comment |Â
up vote
2
down vote
accepted
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime (have no common factor except 1), then $abmid n$.
Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $bmid ak$; since $a,b$ are relatively prime this implies $bmid k$, so $k=bm$, so $n=abm$; therefore $abmid n$.
Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.
answered May 2 '14 at 0:22
David
66.2k663125
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime (have no common factor except 1), then $abmid n$.
Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $bmid ak$; since $a,b$ are relatively prime this implies $bmid k$, so $k=bm$, so $n=abm$; therefore $abmid n$.
Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.
answered May 2 '14 at 0:22
David
66.2k663125
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime (have no common factor except 1), then $abmid n$.
Proof. We have $n=ak$ and $n=bl$ for some integers $k,l$. Therefore $bmid ak$; since $a,b$ are relatively prime this implies $bmid k$, so $k=bm$, so $n=abm$; therefore $abmid n$.
Re: edit, yes this would make sense because $3$ and $5$ are relatively prime.
answered May 2 '14 at 0:22
David
66.2k663125
answered May 2 '14 at 0:22
David
66.2k663125
answered May 2 '14 at 0:22
David
66.2k663125
answered May 2 '14 at 0:22
David
66.2k663125
66.2k663125
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
add a comment |Â
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
how do you know b | ak ?
– Celeritas
May 2 '14 at 2:45
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
Because $n=ak$, see the first equation in the proof.
– David
May 2 '14 at 2:56
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
How to formally prove that: b∣ak; since a,b are relatively prime this implies b∣k?
– user394691
Oct 10 '17 at 21:43
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
@user394691 Since $a,b$ are relatively prime we have $ax+by=1$ for some integers $x,y$. Hence $akx+bky=k$; and $bmid akx$ (because $bmid ak$) and $bmid bky$ (obviously); so $bmid akx+bky$, that is, $bmid k$.
– David
Nov 5 '17 at 23:30
add a comment |Â
up vote
6
down vote
This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 times 6 < 30$.
answered May 2 '14 at 0:11
Xelvonar
1064
add a comment |Â
up vote
6
down vote
This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 times 6 < 30$.
answered May 2 '14 at 0:11
Xelvonar
1064
add a comment |Â
up vote
6
down vote
up vote
6
down vote
This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 times 6 < 30$.
answered May 2 '14 at 0:11
Xelvonar
1064
This is false. For example, 3 | 30 and 6 | 30, but their product, 18, does not divide 30 even though $3 times 6 < 30$.
answered May 2 '14 at 0:11
Xelvonar
1064
edited May 2 '14 at 0:48
answered May 2 '14 at 0:11
Xelvonar
1064
answered May 2 '14 at 0:11
Xelvonar
1064
answered May 2 '14 at 0:11
Xelvonar
1064
1064
add a comment |Â
add a comment |Â
up vote
2
down vote
Updated: The edited version is still not true. At least two counterexamples in the comments below.
Prior counterexample: This is not true. $12|36$ and $9|36$, but $12cdot9 = 108 not | 36$.
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
1
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
 |Â
show 2 more comments
up vote
2
down vote
Updated: The edited version is still not true. At least two counterexamples in the comments below.
Prior counterexample: This is not true. $12|36$ and $9|36$, but $12cdot9 = 108 not | 36$.
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
1
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
 |Â
show 2 more comments
up vote
2
down vote
up vote
2
down vote
Updated: The edited version is still not true. At least two counterexamples in the comments below.
Prior counterexample: This is not true. $12|36$ and $9|36$, but $12cdot9 = 108 not | 36$.
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
Updated: The edited version is still not true. At least two counterexamples in the comments below.
Prior counterexample: This is not true. $12|36$ and $9|36$, but $12cdot9 = 108 not | 36$.
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
edited May 2 '14 at 1:37
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
answered May 2 '14 at 0:04
Eric Towers
30.6k22264
30.6k22264
1
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
 |Â
show 2 more comments
1
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
1
1
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
We misread the question this isn't a counter example.
– Git Gud
May 2 '14 at 0:07
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
@GitGud . . . however, replacing $36$ by $36+12times9$, that is, $144$, does give a counterexample.
– David
May 2 '14 at 0:10
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
Or $(a,b,n)=(4,6,36)$. It's hard to believe someone up voted this when my comment says this isn't a counter example.
– Git Gud
May 2 '14 at 0:13
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@GitGud: So, ..., I reread and reread the problem. (1) it has not changed and (2) it still claims a falsehood.
– Eric Towers
May 2 '14 at 1:30
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
@EricTowers Yes and your answer still isn't a counter example to statement in the OP's question.
– Git Gud
May 2 '14 at 1:32
 |Â
show 2 more comments
up vote
0
down vote
Hint $, a,bmid niff rm lcm(a,b)mid n!!!overset large times, (a,b)iff abmid n(a,b),, $ which is not equivalent to $,abmid n $
answered May 2 '14 at 1:21
Number
1
add a comment |Â
up vote
0
down vote
Hint $, a,bmid niff rm lcm(a,b)mid n!!!overset large times, (a,b)iff abmid n(a,b),, $ which is not equivalent to $,abmid n $
answered May 2 '14 at 1:21
Number
1
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Hint $, a,bmid niff rm lcm(a,b)mid n!!!overset large times, (a,b)iff abmid n(a,b),, $ which is not equivalent to $,abmid n $
answered May 2 '14 at 1:21
Number
1
Hint $, a,bmid niff rm lcm(a,b)mid n!!!overset large times, (a,b)iff abmid n(a,b),, $ which is not equivalent to $,abmid n $
answered May 2 '14 at 1:21
Number
1
answered May 2 '14 at 1:21
Number
1
answered May 2 '14 at 1:21
Number
1
answered May 2 '14 at 1:21
Number
1
1
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f777691%2fhow-to-prove-that-if-a-number-is-divisible-by-two-other-numbers-then-it-is-divi%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You are possibly thinking of the following: if $amid n$ and $bmid n$ and $a,b$ are relatively prime, then $abmid n$.
– David
May 2 '14 at 0:13
Re: edit, yes it would make sense because $3$ and $5$ are relatively prime (have no common factor except $1$). See my previous comment.
– David
May 2 '14 at 0:16
@David ya that's what I was thinking of. so it needs to be a condition a and b are relatively prime?
– Celeritas
May 2 '14 at 2:43
It is a sufficient condition that $a,b$ are relatively prime.
– David
May 2 '14 at 3:00