Is it true that (k,n+k)=d if and only if (k,n)=d? [duplicate] Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Why $gcd(qb+r,b)=gcd(b,r)$?If $3$ divides $a^2 + b^2$, then $3$ divides $a$ and $3$ divides $b$A couple of problems involving divisibility and congruenceHow to prove that for all positive integers $a,b$, if $a|b$ , then $gcd(a,b) = a$?Is this a true theorem?How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?Element of that $mathbb Q[sqrt2]$ have a square root in $mathbb Q[sqrt2]$Prove that $gcd(3^n-2,2^n-3)=1$ if and only if $gcd(6^n-4,2^n-3)=1$Which of the following statements are true for all such $a$ and $b$? Prove the statement or give a counterexample.Prove that $x$ is congruent to $y pmod m$ if and only if $x = km + y$Example of an assertion which is not true for any positive integer, yet for which the induction step holds.
Is the address of a local variable a constexpr?
Center align columns in table ignoring minus signs?
Determinant is linear as a function of each of the rows of the matrix.
If Jon Snow became King of the Seven Kingdoms what would his regnal number be?
How can players work together to take actions that are otherwise impossible?
Is the Standard Deduction better than Itemized when both are the same amount?
Why constant symbols in a language?
What is the musical term for a note that continously plays through a melody?
How to motivate offshore teams and trust them to deliver?
Is there a concise way to say "all of the X, one of each"?
What happens to sewage if there is no river near by?
How to find all the available tools in macOS terminal?
Does accepting a pardon have any bearing on trying that person for the same crime in a sovereign jurisdiction?
Why don't the Weasley twins use magic outside of school if the Trace can only find the location of spells cast?
What is the longest distance a 13th-level monk can jump while attacking on the same turn?
What does the "x" in "x86" represent?
Bonus calculation: Am I making a mountain out of a molehill?
Withdrew £2800, but only £2000 shows as withdrawn on online banking; what are my obligations?
What is a Meta algorithm?
Gastric acid as a weapon
Should I call the interviewer directly, if HR aren't responding?
I am not a queen, who am I?
What do you call a plan that's an alternative plan in case your initial plan fails?
Did Xerox really develop the first LAN?
Is it true that (k,n+k)=d if and only if (k,n)=d? [duplicate]
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Why $gcd(qb+r,b)=gcd(b,r)$?If $3$ divides $a^2 + b^2$, then $3$ divides $a$ and $3$ divides $b$A couple of problems involving divisibility and congruenceHow to prove that for all positive integers $a,b$, if $a|b$ , then $gcd(a,b) = a$?Is this a true theorem?How to select the right modulus to prove that there do not exist integers $a$ and $b$ such that $a^2+b^2=1234567$?Element of that $mathbb Q[sqrt2]$ have a square root in $mathbb Q[sqrt2]$Prove that $gcd(3^n-2,2^n-3)=1$ if and only if $gcd(6^n-4,2^n-3)=1$Which of the following statements are true for all such $a$ and $b$? Prove the statement or give a counterexample.Prove that $x$ is congruent to $y pmod m$ if and only if $x = km + y$Example of an assertion which is not true for any positive integer, yet for which the induction step holds.
$begingroup$
This question already has an answer here:
Why $gcd(qb+r,b)=gcd(b,r)$?
8 answers
Is it true that (k,n+k)=d if and only if (k,n)=d?
I solved "Prove that (k,n+k)=1 if and only if (k,n)=1"
but I cannot solve "Is it true that (k,n+k)=d if and only if (k,n)=d?"
I think it is False but I don't know why it is
elementary-number-theory greatest-common-divisor
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
asked Apr 1 at 0:49
SKYYYSKYYY
1
$endgroup$
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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();
);
);
);
Apr 1 at 19:58
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 |
$begingroup$
This question already has an answer here:
Why $gcd(qb+r,b)=gcd(b,r)$?
8 answers
Is it true that (k,n+k)=d if and only if (k,n)=d?
I solved "Prove that (k,n+k)=1 if and only if (k,n)=1"
but I cannot solve "Is it true that (k,n+k)=d if and only if (k,n)=d?"
I think it is False but I don't know why it is
elementary-number-theory greatest-common-divisor
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
asked Apr 1 at 0:49
SKYYYSKYYY
1
$endgroup$
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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();
);
);
);
Apr 1 at 19:58
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.
3
$begingroup$
If m is any integer, then gcd(k,n + mk) = gcd(k, n). How did you solve (k,n)=1?
$endgroup$
– J. W. Tanner
Apr 1 at 0:57
add a comment |
$begingroup$
This question already has an answer here:
Why $gcd(qb+r,b)=gcd(b,r)$?
8 answers
Is it true that (k,n+k)=d if and only if (k,n)=d?
I solved "Prove that (k,n+k)=1 if and only if (k,n)=1"
but I cannot solve "Is it true that (k,n+k)=d if and only if (k,n)=d?"
I think it is False but I don't know why it is
elementary-number-theory greatest-common-divisor
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
asked Apr 1 at 0:49
SKYYYSKYYY
1
$endgroup$
This question already has an answer here:
Why $gcd(qb+r,b)=gcd(b,r)$?
8 answers
Is it true that (k,n+k)=d if and only if (k,n)=d?
I solved "Prove that (k,n+k)=1 if and only if (k,n)=1"
but I cannot solve "Is it true that (k,n+k)=d if and only if (k,n)=d?"
I think it is False but I don't know why it is
This question already has an answer here:
Why $gcd(qb+r,b)=gcd(b,r)$?
8 answers
elementary-number-theory greatest-common-divisor
elementary-number-theory greatest-common-divisor
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
asked Apr 1 at 0:49
SKYYYSKYYY
1
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
asked Apr 1 at 0:49
SKYYYSKYYY
1
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
edited Apr 1 at 5:29
J. W. Tanner
4,8471420
4,8471420
asked Apr 1 at 0:49
SKYYYSKYYY
1
asked Apr 1 at 0:49
SKYYYSKYYY
1
asked Apr 1 at 0:49
SKYYYSKYYY
1
1
marked as duplicate by Bill Dubuque elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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();
);
);
);
Apr 1 at 19:58
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 elementary-number-theory
Users with the elementary-number-theory badge can single-handedly close elementary-number-theory 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();
);
);
);
Apr 1 at 19:58
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.
3
$begingroup$
If m is any integer, then gcd(k,n + mk) = gcd(k, n). How did you solve (k,n)=1?
$endgroup$
– J. W. Tanner
Apr 1 at 0:57
add a comment |
3
$begingroup$
If m is any integer, then gcd(k,n + mk) = gcd(k, n). How did you solve (k,n)=1?
$endgroup$
– J. W. Tanner
Apr 1 at 0:57
3
3
$begingroup$
If m is any integer, then gcd(k,n + mk) = gcd(k, n). How did you solve (k,n)=1?
$endgroup$
– J. W. Tanner
Apr 1 at 0:57
$begingroup$
If m is any integer, then gcd(k,n + mk) = gcd(k, n). How did you solve (k,n)=1?
$endgroup$
– J. W. Tanner
Apr 1 at 0:57
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $d=(k,n)$. Then $d$ divides $k$ and $n,$ so $d$ is a divisor of $n+k$ $(k=da, n=db, n+k=d(b+a)).$
On the other hand, if $e$ divides $k$ and $n+k$ then $e$ divides $n$ ($k=ec, n+k=ef, n=e(f-c)$),
so $e$ divides $d=(k,n)$. Thus, $d=(k,n+k)$.
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $d=(k,n)$. Then $d$ divides $k$ and $n,$ so $d$ is a divisor of $n+k$ $(k=da, n=db, n+k=d(b+a)).$
On the other hand, if $e$ divides $k$ and $n+k$ then $e$ divides $n$ ($k=ec, n+k=ef, n=e(f-c)$),
so $e$ divides $d=(k,n)$. Thus, $d=(k,n+k)$.
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
$endgroup$
add a comment |
$begingroup$
Let $d=(k,n)$. Then $d$ divides $k$ and $n,$ so $d$ is a divisor of $n+k$ $(k=da, n=db, n+k=d(b+a)).$
On the other hand, if $e$ divides $k$ and $n+k$ then $e$ divides $n$ ($k=ec, n+k=ef, n=e(f-c)$),
so $e$ divides $d=(k,n)$. Thus, $d=(k,n+k)$.
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
$endgroup$
add a comment |
$begingroup$
Let $d=(k,n)$. Then $d$ divides $k$ and $n,$ so $d$ is a divisor of $n+k$ $(k=da, n=db, n+k=d(b+a)).$
On the other hand, if $e$ divides $k$ and $n+k$ then $e$ divides $n$ ($k=ec, n+k=ef, n=e(f-c)$),
so $e$ divides $d=(k,n)$. Thus, $d=(k,n+k)$.
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
$endgroup$
Let $d=(k,n)$. Then $d$ divides $k$ and $n,$ so $d$ is a divisor of $n+k$ $(k=da, n=db, n+k=d(b+a)).$
On the other hand, if $e$ divides $k$ and $n+k$ then $e$ divides $n$ ($k=ec, n+k=ef, n=e(f-c)$),
so $e$ divides $d=(k,n)$. Thus, $d=(k,n+k)$.
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
answered Apr 1 at 2:58
J. W. TannerJ. W. Tanner
4,8471420
4,8471420
add a comment |
add a comment |
3
$begingroup$
If m is any integer, then gcd(k,n + mk) = gcd(k, n). How did you solve (k,n)=1?
$endgroup$
– J. W. Tanner
Apr 1 at 0:57