If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $gcd(a, pq)=1$ [duplicate]

5

$begingroup$

This question already has an answer here:

• 
  If $gcd(a,c)=1=gcd(b,c)$, then $gcd(ab,c)=1$
  
  3 answers
  
  

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $gcd(a, pq)=1$.

I want to show this using linear combinations, so that a linear combination of $a$, and $py$ will give $1$. So for some $x,y,x',y'$:

$ax+py = 1 = ax'+qy'$, and

$a(x-x')+py-qy'=1-ax'-qy'$.

Not sure where to go from here. Hints appreciated.

elementary-number-theory greatest-common-divisor

share|cite|improve this question

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

$endgroup$

marked as duplicate by Bill Dubuque 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();
}
);
});
});
Jan 26 at 18:31

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.

add a comment | 

5

$begingroup$

This question already has an answer here:

• 
  If $gcd(a,c)=1=gcd(b,c)$, then $gcd(ab,c)=1$
  
  3 answers
  
  

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $gcd(a, pq)=1$.

I want to show this using linear combinations, so that a linear combination of $a$, and $py$ will give $1$. So for some $x,y,x',y'$:

$ax+py = 1 = ax'+qy'$, and

$a(x-x')+py-qy'=1-ax'-qy'$.

Not sure where to go from here. Hints appreciated.

elementary-number-theory greatest-common-divisor

share|cite|improve this question

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

$endgroup$

marked as duplicate by Bill Dubuque 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();
}
);
});
});
Jan 26 at 18:31

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.

add a comment | 

5

5

5

$begingroup$

This question already has an answer here:

• 
  If $gcd(a,c)=1=gcd(b,c)$, then $gcd(ab,c)=1$
  
  3 answers
  
  

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $gcd(a, pq)=1$.

I want to show this using linear combinations, so that a linear combination of $a$, and $py$ will give $1$. So for some $x,y,x',y'$:

$ax+py = 1 = ax'+qy'$, and

$a(x-x')+py-qy'=1-ax'-qy'$.

Not sure where to go from here. Hints appreciated.

elementary-number-theory greatest-common-divisor

share|cite|improve this question

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

$endgroup$

This question already has an answer here:

• 
  If $gcd(a,c)=1=gcd(b,c)$, then $gcd(ab,c)=1$
  
  3 answers
  
  

If $p,q$ are distinct primes and $a$ is not divisible by $p$ or $q$, then $gcd(a, pq)=1$.

I want to show this using linear combinations, so that a linear combination of $a$, and $py$ will give $1$. So for some $x,y,x',y'$:

$ax+py = 1 = ax'+qy'$, and

$a(x-x')+py-qy'=1-ax'-qy'$.

Not sure where to go from here. Hints appreciated.

This question already has an answer here:

• 
  If $gcd(a,c)=1=gcd(b,c)$, then $gcd(ab,c)=1$
  
  3 answers
  
  

elementary-number-theory greatest-common-divisor

elementary-number-theory greatest-common-divisor

share|cite|improve this question

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

share|cite|improve this question

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

share|cite|improve this question

share|cite|improve this question

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

edited Jan 26 at 18:32

Bill Dubuque

212k29195654

212k29195654

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

asked Jan 26 at 18:14

IntegrateThisIntegrateThis

1,9441818

1,9441818

marked as duplicate by Bill Dubuque 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();
}
);
});
});
Jan 26 at 18:31

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 Bill Dubuque 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();
}
);
});
});
Jan 26 at 18:31

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.

add a comment | 

add a comment | 

2 Answers
2

active

oldest

votes

2

$begingroup$

$ax+py = 1$ and $ ax'+qy'=1$. Rearranging, we have
$py = 1-ax$ and $qy'=1-ax'$. Multiplying, we get $$pyqy'=(1-ax)(1-ax')=1-a (x+x')+a^2xx'.$$

Hence $$pq(yy')+a (x+x'-axx')=1. $$

share|cite|improve this answer

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

$endgroup$

add a comment | 

4

$begingroup$

If $a$ is not divisible by $p$ or $q$ then indeed there exist integers $x$, $x'$, $y$, and $y'$ such that
$$ax+py=1qquadtext{ and }qquad ax'+qy'=1.$$
Now isolate $py$ from the first and $qy'$ from the second equation, and multiply the two results together. Can you finish from here?

share|cite|improve this answer

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

$endgroup$

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

2

$begingroup$

$ax+py = 1$ and $ ax'+qy'=1$. Rearranging, we have
$py = 1-ax$ and $qy'=1-ax'$. Multiplying, we get $$pyqy'=(1-ax)(1-ax')=1-a (x+x')+a^2xx'.$$

Hence $$pq(yy')+a (x+x'-axx')=1. $$

share|cite|improve this answer

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

$endgroup$

add a comment | 

2

$begingroup$

$ax+py = 1$ and $ ax'+qy'=1$. Rearranging, we have
$py = 1-ax$ and $qy'=1-ax'$. Multiplying, we get $$pyqy'=(1-ax)(1-ax')=1-a (x+x')+a^2xx'.$$

Hence $$pq(yy')+a (x+x'-axx')=1. $$

share|cite|improve this answer

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

$endgroup$

add a comment | 

2

2

2

$begingroup$

$ax+py = 1$ and $ ax'+qy'=1$. Rearranging, we have
$py = 1-ax$ and $qy'=1-ax'$. Multiplying, we get $$pyqy'=(1-ax)(1-ax')=1-a (x+x')+a^2xx'.$$

Hence $$pq(yy')+a (x+x'-axx')=1. $$

share|cite|improve this answer

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

$endgroup$

$ax+py = 1$ and $ ax'+qy'=1$. Rearranging, we have
$py = 1-ax$ and $qy'=1-ax'$. Multiplying, we get $$pyqy'=(1-ax)(1-ax')=1-a (x+x')+a^2xx'.$$

Hence $$pq(yy')+a (x+x'-axx')=1. $$

share|cite|improve this answer

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

share|cite|improve this answer

share|cite|improve this answer

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

answered Jan 26 at 18:22

Thomas ShelbyThomas Shelby

4,3042726

4,3042726

add a comment | 

add a comment | 

4

$begingroup$

If $a$ is not divisible by $p$ or $q$ then indeed there exist integers $x$, $x'$, $y$, and $y'$ such that
$$ax+py=1qquadtext{ and }qquad ax'+qy'=1.$$
Now isolate $py$ from the first and $qy'$ from the second equation, and multiply the two results together. Can you finish from here?

share|cite|improve this answer

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

$endgroup$

add a comment | 

4

$begingroup$

If $a$ is not divisible by $p$ or $q$ then indeed there exist integers $x$, $x'$, $y$, and $y'$ such that
$$ax+py=1qquadtext{ and }qquad ax'+qy'=1.$$
Now isolate $py$ from the first and $qy'$ from the second equation, and multiply the two results together. Can you finish from here?

share|cite|improve this answer

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

$endgroup$

add a comment | 

4

4

4

$begingroup$

If $a$ is not divisible by $p$ or $q$ then indeed there exist integers $x$, $x'$, $y$, and $y'$ such that
$$ax+py=1qquadtext{ and }qquad ax'+qy'=1.$$
Now isolate $py$ from the first and $qy'$ from the second equation, and multiply the two results together. Can you finish from here?

share|cite|improve this answer

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

$endgroup$

If $a$ is not divisible by $p$ or $q$ then indeed there exist integers $x$, $x'$, $y$, and $y'$ such that
$$ax+py=1qquadtext{ and }qquad ax'+qy'=1.$$
Now isolate $py$ from the first and $qy'$ from the second equation, and multiply the two results together. Can you finish from here?

share|cite|improve this answer

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

share|cite|improve this answer

share|cite|improve this answer

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

answered Jan 26 at 18:16

ServaesServaes

28.5k34099

28.5k34099

add a comment | 

add a comment | 

This page is only for reference, If you need detailed information, please check here