If $m$ is a divisor of $k$ and $n$ is a divisor of $k$ and $m$ and $n$ prime to each other then $mn$ is divisor of $k$. [duplicate]

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

This question already has an answer here:

• 
  Product of pairwise coprime integers divides $b$ if each integer divides $b$
  
  3 answers
  
  

If $m$ is a divisor of $k$ and $n$ is a divisor of $k$ and $m$ and $n$ prime to each other then $mn$ is divisor of $k$.

I tried but somehow I didnt manipulate.

As $m$ is divisor of $k$ then $k=mp$ for some $p$ and similarly $k=nq$ for some $q$ and as $gcd(m, n)=1$ there exist integer say $u$ and $v$ such that $mu+nv=1$

After that how I proceed?, Please help.

algebra-precalculus elementary-number-theory greatest-common-divisor

share|cite|improve this question

asked Jul 28 at 7:37

ram ram

816

marked as duplicate by José Carlos Santos, N. F. Taussig, Jyrki Lahtonen, amWhy algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

StackExchange.ready(function()
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();

);
);
);
Jul 29 at 0:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  As you said, $k = mp$. Then, $n$ must divide $mp$ and $m$ and $n$ share no factors, so $n$ must divide $p$.
  – Spencer
  Jul 28 at 7:40
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

This question already has an answer here:

• 
  Product of pairwise coprime integers divides $b$ if each integer divides $b$
  
  3 answers
  
  

If $m$ is a divisor of $k$ and $n$ is a divisor of $k$ and $m$ and $n$ prime to each other then $mn$ is divisor of $k$.

I tried but somehow I didnt manipulate.

As $m$ is divisor of $k$ then $k=mp$ for some $p$ and similarly $k=nq$ for some $q$ and as $gcd(m, n)=1$ there exist integer say $u$ and $v$ such that $mu+nv=1$

After that how I proceed?, Please help.

algebra-precalculus elementary-number-theory greatest-common-divisor

share|cite|improve this question

asked Jul 28 at 7:37

ram ram

816

marked as duplicate by José Carlos Santos, N. F. Taussig, Jyrki Lahtonen, amWhy algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

StackExchange.ready(function()
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();

);
);
);
Jul 29 at 0:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  As you said, $k = mp$. Then, $n$ must divide $mp$ and $m$ and $n$ share no factors, so $n$ must divide $p$.
  – Spencer
  Jul 28 at 7:40
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

This question already has an answer here:

• 
  Product of pairwise coprime integers divides $b$ if each integer divides $b$
  
  3 answers
  
  

If $m$ is a divisor of $k$ and $n$ is a divisor of $k$ and $m$ and $n$ prime to each other then $mn$ is divisor of $k$.

I tried but somehow I didnt manipulate.

As $m$ is divisor of $k$ then $k=mp$ for some $p$ and similarly $k=nq$ for some $q$ and as $gcd(m, n)=1$ there exist integer say $u$ and $v$ such that $mu+nv=1$

After that how I proceed?, Please help.

algebra-precalculus elementary-number-theory greatest-common-divisor

share|cite|improve this question

asked Jul 28 at 7:37

ram ram

816

This question already has an answer here:

• 
  Product of pairwise coprime integers divides $b$ if each integer divides $b$
  
  3 answers
  
  

If $m$ is a divisor of $k$ and $n$ is a divisor of $k$ and $m$ and $n$ prime to each other then $mn$ is divisor of $k$.

I tried but somehow I didnt manipulate.

As $m$ is divisor of $k$ then $k=mp$ for some $p$ and similarly $k=nq$ for some $q$ and as $gcd(m, n)=1$ there exist integer say $u$ and $v$ such that $mu+nv=1$

After that how I proceed?, Please help.

This question already has an answer here:

• 
  Product of pairwise coprime integers divides $b$ if each integer divides $b$
  
  3 answers
  
  

algebra-precalculus elementary-number-theory greatest-common-divisor

share|cite|improve this question

asked Jul 28 at 7:37

ram ram

816

share|cite|improve this question

share|cite|improve this question

asked Jul 28 at 7:37

ram ram

816

asked Jul 28 at 7:37

ram ram

816

asked Jul 28 at 7:37

ram ram

816

816

marked as duplicate by José Carlos Santos, N. F. Taussig, Jyrki Lahtonen, amWhy algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

StackExchange.ready(function()
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();

);
);
);
Jul 29 at 0:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

marked as duplicate by José Carlos Santos, N. F. Taussig, Jyrki Lahtonen, amWhy algebra-precalculus
Users with the  algebra-precalculus badge can single-handedly close algebra-precalculus questions as duplicates and reopen them as needed.

StackExchange.ready(function()
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function()
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function()
$hover.showInfoMessage('',
messageElement: $msg.clone().show(),
transient: false,
position: my: 'bottom left', at: 'top center', offsetTop: -7 ,
dismissable: false,
relativeToBody: true
);
,
function()
StackExchange.helpers.removeMessages();

);
);
);
Jul 29 at 0:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  As you said, $k = mp$. Then, $n$ must divide $mp$ and $m$ and $n$ share no factors, so $n$ must divide $p$.
  – Spencer
  Jul 28 at 7:40
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  As you said, $k = mp$. Then, $n$ must divide $mp$ and $m$ and $n$ share no factors, so $n$ must divide $p$.
  – Spencer
  Jul 28 at 7:40
  
  

  
  
  
  

1

1

As you said, $k = mp$. Then, $n$ must divide $mp$ and $m$ and $n$ share no factors, so $n$ must divide $p$.
– Spencer
Jul 28 at 7:40

As you said, $k = mp$. Then, $n$ must divide $mp$ and $m$ and $n$ share no factors, so $n$ must divide $p$.
– Spencer
Jul 28 at 7:40

add a comment | 

3 Answers
3

active

oldest

votes

up vote
1
down vote

Write $k=mq$. Since $gcd (m,n)=1$,by Gauß's lemma $nmid q$. So $q=rnimplies k=rmn$. Thus $mnmid k$.

Note: Thanks are due to @Bernard for enlightening me about Gauß's lemma...

share|cite|improve this answer

edited Jul 29 at 1:47

answered Jul 28 at 8:05

Chris Custer

5,2722622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You might more directly use Gauß'lemma.
  – Bernard
  Jul 28 at 8:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
  – Chris Custer
  Jul 28 at 9:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
  – Bernard
  Jul 28 at 9:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh ok. I was wondering. Thanks...
  – Chris Custer
  Jul 28 at 9:32
  

  
  
  
  

add a comment | 

up vote
0
down vote

Think of it in terms of the fundamental theorem of arithmetic. Let $m=prod p_i$. Since $mmid k, k=prod p_ir$. Similarly, $n=prod q_j$. But since $m$ and $n$ are relatively prime, $p_ineq q_j$ for all $i,j$. So to say that $nmid k$ is to say that $nmid r$.

So, $r=prod q_js$ and $k=prod p_i prod q_js$. This reduces to $k=mns$ which is plainly divisible by $mn$.

share|cite|improve this answer

answered Jul 28 at 18:19

Keith Backman

39227

add a comment | 

up vote
0
down vote

If $mmid k Rightarrow k=mt wedge nmid kRightarrow k=nl$. Using the Bezout's Identity $(m,n)=1Rightarrow mx_0+ny_0=1,$ with $x_0,y_0in mathbbZ$.

$mx_0+ny_0=1 Leftrightarrow mx_0k+ny_0k=k$

$Leftrightarrow mx_0(nl)+ny_0(mt)=k$

$Leftrightarrow mn(x_0l)+mn(y_0t)=k$

Therefore $mnmid k$

share|cite|improve this answer

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

add a comment | 

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

Write $k=mq$. Since $gcd (m,n)=1$,by Gauß's lemma $nmid q$. So $q=rnimplies k=rmn$. Thus $mnmid k$.

Note: Thanks are due to @Bernard for enlightening me about Gauß's lemma...

share|cite|improve this answer

edited Jul 29 at 1:47

answered Jul 28 at 8:05

Chris Custer

5,2722622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You might more directly use Gauß'lemma.
  – Bernard
  Jul 28 at 8:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
  – Chris Custer
  Jul 28 at 9:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
  – Bernard
  Jul 28 at 9:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh ok. I was wondering. Thanks...
  – Chris Custer
  Jul 28 at 9:32
  

  
  
  
  

add a comment | 

up vote
1
down vote

Write $k=mq$. Since $gcd (m,n)=1$,by Gauß's lemma $nmid q$. So $q=rnimplies k=rmn$. Thus $mnmid k$.

Note: Thanks are due to @Bernard for enlightening me about Gauß's lemma...

share|cite|improve this answer

edited Jul 29 at 1:47

answered Jul 28 at 8:05

Chris Custer

5,2722622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You might more directly use Gauß'lemma.
  – Bernard
  Jul 28 at 8:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
  – Chris Custer
  Jul 28 at 9:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
  – Bernard
  Jul 28 at 9:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh ok. I was wondering. Thanks...
  – Chris Custer
  Jul 28 at 9:32
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

Write $k=mq$. Since $gcd (m,n)=1$,by Gauß's lemma $nmid q$. So $q=rnimplies k=rmn$. Thus $mnmid k$.

Note: Thanks are due to @Bernard for enlightening me about Gauß's lemma...

share|cite|improve this answer

edited Jul 29 at 1:47

answered Jul 28 at 8:05

Chris Custer

5,2722622

Write $k=mq$. Since $gcd (m,n)=1$,by Gauß's lemma $nmid q$. So $q=rnimplies k=rmn$. Thus $mnmid k$.

Note: Thanks are due to @Bernard for enlightening me about Gauß's lemma...

share|cite|improve this answer

edited Jul 29 at 1:47

answered Jul 28 at 8:05

Chris Custer

5,2722622

share|cite|improve this answer

share|cite|improve this answer

edited Jul 29 at 1:47

edited Jul 29 at 1:47

edited Jul 29 at 1:47

answered Jul 28 at 8:05

Chris Custer

5,2722622

answered Jul 28 at 8:05

Chris Custer

5,2722622

answered Jul 28 at 8:05

Chris Custer

5,2722622

5,2722622

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You might more directly use Gauß'lemma.
  – Bernard
  Jul 28 at 8:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
  – Chris Custer
  Jul 28 at 9:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
  – Bernard
  Jul 28 at 9:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh ok. I was wondering. Thanks...
  – Chris Custer
  Jul 28 at 9:32
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You might more directly use Gauß'lemma.
  – Bernard
  Jul 28 at 8:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
  – Chris Custer
  Jul 28 at 9:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
  – Bernard
  Jul 28 at 9:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Oh ok. I was wondering. Thanks...
  – Chris Custer
  Jul 28 at 9:32
  

  
  
  
  

You might more directly use Gauß'lemma.
– Bernard
Jul 28 at 8:54

You might more directly use Gauß'lemma.
– Bernard
Jul 28 at 8:54

Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
– Chris Custer
Jul 28 at 9:18

Hmm. Don't immediately see how to do it... I admit my experience with, say, the Legendre symbol, is still pretty limited. Perhaps you could clue me in...
– Chris Custer
Jul 28 at 9:18

There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
– Bernard
Jul 28 at 9:27

There are several Gauß'lemmas actually. I mean, the extension of Euclid's lemma which says that if $m$ divides $ab$, and $m$ and $a$ are coprime, then $m$ divides $b$. Needless to use prime factorisation.
– Bernard
Jul 28 at 9:27

Oh ok. I was wondering. Thanks...
– Chris Custer
Jul 28 at 9:32

Oh ok. I was wondering. Thanks...
– Chris Custer
Jul 28 at 9:32

add a comment | 

up vote
0
down vote

Think of it in terms of the fundamental theorem of arithmetic. Let $m=prod p_i$. Since $mmid k, k=prod p_ir$. Similarly, $n=prod q_j$. But since $m$ and $n$ are relatively prime, $p_ineq q_j$ for all $i,j$. So to say that $nmid k$ is to say that $nmid r$.

So, $r=prod q_js$ and $k=prod p_i prod q_js$. This reduces to $k=mns$ which is plainly divisible by $mn$.

share|cite|improve this answer

answered Jul 28 at 18:19

Keith Backman

39227

add a comment | 

up vote
0
down vote

Think of it in terms of the fundamental theorem of arithmetic. Let $m=prod p_i$. Since $mmid k, k=prod p_ir$. Similarly, $n=prod q_j$. But since $m$ and $n$ are relatively prime, $p_ineq q_j$ for all $i,j$. So to say that $nmid k$ is to say that $nmid r$.

So, $r=prod q_js$ and $k=prod p_i prod q_js$. This reduces to $k=mns$ which is plainly divisible by $mn$.

share|cite|improve this answer

answered Jul 28 at 18:19

Keith Backman

39227

add a comment | 

up vote
0
down vote

up vote
0
down vote

Think of it in terms of the fundamental theorem of arithmetic. Let $m=prod p_i$. Since $mmid k, k=prod p_ir$. Similarly, $n=prod q_j$. But since $m$ and $n$ are relatively prime, $p_ineq q_j$ for all $i,j$. So to say that $nmid k$ is to say that $nmid r$.

So, $r=prod q_js$ and $k=prod p_i prod q_js$. This reduces to $k=mns$ which is plainly divisible by $mn$.

share|cite|improve this answer

answered Jul 28 at 18:19

Keith Backman

39227

Think of it in terms of the fundamental theorem of arithmetic. Let $m=prod p_i$. Since $mmid k, k=prod p_ir$. Similarly, $n=prod q_j$. But since $m$ and $n$ are relatively prime, $p_ineq q_j$ for all $i,j$. So to say that $nmid k$ is to say that $nmid r$.

So, $r=prod q_js$ and $k=prod p_i prod q_js$. This reduces to $k=mns$ which is plainly divisible by $mn$.

share|cite|improve this answer

answered Jul 28 at 18:19

Keith Backman

39227

share|cite|improve this answer

share|cite|improve this answer

answered Jul 28 at 18:19

Keith Backman

39227

answered Jul 28 at 18:19

Keith Backman

39227

answered Jul 28 at 18:19

Keith Backman

39227

39227

add a comment | 

add a comment | 

up vote
0
down vote

If $mmid k Rightarrow k=mt wedge nmid kRightarrow k=nl$. Using the Bezout's Identity $(m,n)=1Rightarrow mx_0+ny_0=1,$ with $x_0,y_0in mathbbZ$.

$mx_0+ny_0=1 Leftrightarrow mx_0k+ny_0k=k$

$Leftrightarrow mx_0(nl)+ny_0(mt)=k$

$Leftrightarrow mn(x_0l)+mn(y_0t)=k$

Therefore $mnmid k$

share|cite|improve this answer

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

add a comment | 

up vote
0
down vote

If $mmid k Rightarrow k=mt wedge nmid kRightarrow k=nl$. Using the Bezout's Identity $(m,n)=1Rightarrow mx_0+ny_0=1,$ with $x_0,y_0in mathbbZ$.

$mx_0+ny_0=1 Leftrightarrow mx_0k+ny_0k=k$

$Leftrightarrow mx_0(nl)+ny_0(mt)=k$

$Leftrightarrow mn(x_0l)+mn(y_0t)=k$

Therefore $mnmid k$

share|cite|improve this answer

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

add a comment | 

up vote
0
down vote

up vote
0
down vote

If $mmid k Rightarrow k=mt wedge nmid kRightarrow k=nl$. Using the Bezout's Identity $(m,n)=1Rightarrow mx_0+ny_0=1,$ with $x_0,y_0in mathbbZ$.

$mx_0+ny_0=1 Leftrightarrow mx_0k+ny_0k=k$

$Leftrightarrow mx_0(nl)+ny_0(mt)=k$

$Leftrightarrow mn(x_0l)+mn(y_0t)=k$

Therefore $mnmid k$

share|cite|improve this answer

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

If $mmid k Rightarrow k=mt wedge nmid kRightarrow k=nl$. Using the Bezout's Identity $(m,n)=1Rightarrow mx_0+ny_0=1,$ with $x_0,y_0in mathbbZ$.

$mx_0+ny_0=1 Leftrightarrow mx_0k+ny_0k=k$

$Leftrightarrow mx_0(nl)+ny_0(mt)=k$

$Leftrightarrow mn(x_0l)+mn(y_0t)=k$

Therefore $mnmid k$

share|cite|improve this answer

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

share|cite|improve this answer

share|cite|improve this answer

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

answered Jul 28 at 19:09

Julio Trujillo Gonzalez

575

575

add a comment | 

add a comment |