Suppose 1 ≤ k ≤ n − 1 and gcd(k, n) = 1. Prove that gcd(n − k, n) = 1Negative coefficients and Bezout's identityProof of Bezout's Lemma using Euclid's Algorithm backwardsUsing Bézout's Identity to prove that given $gcd$ of two numbers is really trueProve that if d is a common divisor of a and b, then $d=gcd(a,b)$ if and only if $gcd(a/d,b/d)=1$Why is it true that if $ax+by=d$ then $gcd(a,b)$ divides $d$?Prove if If $m in Z^+$, $a|m$, and $b|m$, then $mboxlcm(a,b) leq m$.Suggesting a good reference, & solving a linear diophantine equation in two variables with $gcd =1$.Proof involving gcdProof involving greatest common divisorsIf $gcd(a,b)=1$ then $gcd(a^n,b^n)=1$
Recommendations or Experiences on Archiving Mailing Data
The Sword in the Stone
Am I allowed to use personal conversation as a source?
Issue with Expansions of Nested Macros
How to politely refuse a startup's equity?
How to check what is edible on an alien world?
How do I explain an exponentially complex intuitively?
Why would a pilot use ailerons for countering asymmetric thrust in mid-flight?
Are the named pipe created by `mknod` and the FIFO created by `mkfifo` equivalent?
Correlation length anisotropy in the 2D Ising model
If a 2019 UA artificer has the Repeating Shot infusion on two hand crossbows, can they use two-weapon fighting?
How to apply the changes to my `.zshrc` file after edit?
Sea level static test of an upper stage possible?
Examples of simultaneous independent breakthroughs
Building a scene and readability
Sci fi story: Clever pigs that help a galaxy lawman
Why isn't there a serious attempt at creating a third mass-appeal party in the US?
How to get CPU-G to run on 18.04
To find islands of 1 and 0 in matrix
What is this spacecraft tethered to another spacecraft in LEO (vintage)
Why can't my huge trees be chopped down?
Sci-fi change: Too much or Not enough
What is the difference between position, displacement, and distance traveled?
How to judge a Ph.D. applicant that arrives "out of thin air"
Suppose 1 ≤ k ≤ n − 1 and gcd(k, n) = 1. Prove that gcd(n − k, n) = 1
Negative coefficients and Bezout's identityProof of Bezout's Lemma using Euclid's Algorithm backwardsUsing Bézout's Identity to prove that given $gcd$ of two numbers is really trueProve that if d is a common divisor of a and b, then $d=gcd(a,b)$ if and only if $gcd(a/d,b/d)=1$Why is it true that if $ax+by=d$ then $gcd(a,b)$ divides $d$?Prove if If $m in Z^+$, $a|m$, and $b|m$, then $mboxlcm(a,b) leq m$.Suggesting a good reference, & solving a linear diophantine equation in two variables with $gcd =1$.Proof involving gcdProof involving greatest common divisorsIf $gcd(a,b)=1$ then $gcd(a^n,b^n)=1$
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I wrote:
Since gcd(n-k, n)=1, we can use Bezout's Identity to say:
∃(x,y)∈Z such that (n-k)x+ny=1.
Distributing, nx-kx+ny=1.
One can then produce the equation: n(x+y)-kx=1.
I then stated about how because of that equation, it is proved that gcd(n-k, n)=1. I am almost certain that what I wrote is not the proper way to prove this statement so could someone please present their own version of the proof or explain to me where I messed up?
elementary-number-theory proof-writing
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
$endgroup$
add a comment |
$begingroup$
I wrote:
Since gcd(n-k, n)=1, we can use Bezout's Identity to say:
∃(x,y)∈Z such that (n-k)x+ny=1.
Distributing, nx-kx+ny=1.
One can then produce the equation: n(x+y)-kx=1.
I then stated about how because of that equation, it is proved that gcd(n-k, n)=1. I am almost certain that what I wrote is not the proper way to prove this statement so could someone please present their own version of the proof or explain to me where I messed up?
elementary-number-theory proof-writing
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
$endgroup$
add a comment |
$begingroup$
I wrote:
Since gcd(n-k, n)=1, we can use Bezout's Identity to say:
∃(x,y)∈Z such that (n-k)x+ny=1.
Distributing, nx-kx+ny=1.
One can then produce the equation: n(x+y)-kx=1.
I then stated about how because of that equation, it is proved that gcd(n-k, n)=1. I am almost certain that what I wrote is not the proper way to prove this statement so could someone please present their own version of the proof or explain to me where I messed up?
elementary-number-theory proof-writing
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
$endgroup$
I wrote:
Since gcd(n-k, n)=1, we can use Bezout's Identity to say:
∃(x,y)∈Z such that (n-k)x+ny=1.
Distributing, nx-kx+ny=1.
One can then produce the equation: n(x+y)-kx=1.
I then stated about how because of that equation, it is proved that gcd(n-k, n)=1. I am almost certain that what I wrote is not the proper way to prove this statement so could someone please present their own version of the proof or explain to me where I messed up?
elementary-number-theory proof-writing
elementary-number-theory proof-writing
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
asked Jul 17 at 23:52
ShaileshShailesh
384 bronze badges
384 bronze badges
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Note that Bézout's identity is used to prove an existence of an equation, but the existence of such an equation doesn't necessarily prove the reverse in terms of the factors or the gcd (e.g., there exists $x = -5$ and $y = 5$ such that $3x + 4y = 5$, but $gcd(3,4) = 1$ rather than $gcd(3,4) = 5$). However, as shown in Bill Dubuque's and steven gregory's answers, you can manipulate the resulting original equation to prove what you're asking.
Another way to prove it is to assume there is a $d gt 0$ with $d mid n - k$ and $d mid n$. Then $d mid n - (n-k) = k$. However, since $gcd(k,n) = 1$, this means $d = 1$, so $gcd(n-k,n) = 1$.
A similar, but perhaps a bit simpler, way to show this is to let $d = gcd(n-k,n)$, giving that $d mid n-k$ and $d mid n$, so $d mid n - (n-k) = k$. Once again, this leads to $d = 1$ and that $gcd(n-k,n) = 1$.
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
$endgroup$
add a comment |
$begingroup$
Yes, you can use Bezout: $ 1 = gcd(n,k) = an!+!bk = (a!color#c00+!b)n - b(n!-!k),Rightarrow,gcd(n,n!-!k)=1$
Or $ $ if $ dmid n $ then $ dmid k!iff! dmid n!-!k,,$ so $,n,k,$ and $,n,n!-!k,$ have the same set $S$ of common divisors $d$, so they have the same greatest common divisor $(= max S)$
Or $!bmod d!:: $ if $,nequiv 0 $ then $ kequiv 0!iff! kequiv n,,$ so $ ldots,$ (as above)
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
$endgroup$
add a comment |
$begingroup$
$gcd(x,y)=g$ if and only if $g$ is the smallest positive integer that can be expressed in the form
$g=ax+by$ where $a,b in mathbb Z$.
Since $gcd(k,n)=1$ is given, then you know that there exists integers $a$ and $b$ such that $ak+bn = 1$$
So
beginalign
1 &= ak + bn \
&= -a(-k) -an + an + bn \
&= -a(n-k) + (a+b)n \
&= (-a)(n-k) + (a+b)n
endalign
Since $1$ is the smallest possible positive integer, it follows that
$$gcd(n-k,n)=1$$
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3296239%2fsuppose-1-%25e2%2589%25a4-k-%25e2%2589%25a4-n-%25e2%2588%2592-1-and-gcdk-n-1-prove-that-gcdn-%25e2%2588%2592-k-n-1%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Note that Bézout's identity is used to prove an existence of an equation, but the existence of such an equation doesn't necessarily prove the reverse in terms of the factors or the gcd (e.g., there exists $x = -5$ and $y = 5$ such that $3x + 4y = 5$, but $gcd(3,4) = 1$ rather than $gcd(3,4) = 5$). However, as shown in Bill Dubuque's and steven gregory's answers, you can manipulate the resulting original equation to prove what you're asking.
Another way to prove it is to assume there is a $d gt 0$ with $d mid n - k$ and $d mid n$. Then $d mid n - (n-k) = k$. However, since $gcd(k,n) = 1$, this means $d = 1$, so $gcd(n-k,n) = 1$.
A similar, but perhaps a bit simpler, way to show this is to let $d = gcd(n-k,n)$, giving that $d mid n-k$ and $d mid n$, so $d mid n - (n-k) = k$. Once again, this leads to $d = 1$ and that $gcd(n-k,n) = 1$.
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
$endgroup$
add a comment |
$begingroup$
Note that Bézout's identity is used to prove an existence of an equation, but the existence of such an equation doesn't necessarily prove the reverse in terms of the factors or the gcd (e.g., there exists $x = -5$ and $y = 5$ such that $3x + 4y = 5$, but $gcd(3,4) = 1$ rather than $gcd(3,4) = 5$). However, as shown in Bill Dubuque's and steven gregory's answers, you can manipulate the resulting original equation to prove what you're asking.
Another way to prove it is to assume there is a $d gt 0$ with $d mid n - k$ and $d mid n$. Then $d mid n - (n-k) = k$. However, since $gcd(k,n) = 1$, this means $d = 1$, so $gcd(n-k,n) = 1$.
A similar, but perhaps a bit simpler, way to show this is to let $d = gcd(n-k,n)$, giving that $d mid n-k$ and $d mid n$, so $d mid n - (n-k) = k$. Once again, this leads to $d = 1$ and that $gcd(n-k,n) = 1$.
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
$endgroup$
add a comment |
$begingroup$
Note that Bézout's identity is used to prove an existence of an equation, but the existence of such an equation doesn't necessarily prove the reverse in terms of the factors or the gcd (e.g., there exists $x = -5$ and $y = 5$ such that $3x + 4y = 5$, but $gcd(3,4) = 1$ rather than $gcd(3,4) = 5$). However, as shown in Bill Dubuque's and steven gregory's answers, you can manipulate the resulting original equation to prove what you're asking.
Another way to prove it is to assume there is a $d gt 0$ with $d mid n - k$ and $d mid n$. Then $d mid n - (n-k) = k$. However, since $gcd(k,n) = 1$, this means $d = 1$, so $gcd(n-k,n) = 1$.
A similar, but perhaps a bit simpler, way to show this is to let $d = gcd(n-k,n)$, giving that $d mid n-k$ and $d mid n$, so $d mid n - (n-k) = k$. Once again, this leads to $d = 1$ and that $gcd(n-k,n) = 1$.
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
$endgroup$
Note that Bézout's identity is used to prove an existence of an equation, but the existence of such an equation doesn't necessarily prove the reverse in terms of the factors or the gcd (e.g., there exists $x = -5$ and $y = 5$ such that $3x + 4y = 5$, but $gcd(3,4) = 1$ rather than $gcd(3,4) = 5$). However, as shown in Bill Dubuque's and steven gregory's answers, you can manipulate the resulting original equation to prove what you're asking.
Another way to prove it is to assume there is a $d gt 0$ with $d mid n - k$ and $d mid n$. Then $d mid n - (n-k) = k$. However, since $gcd(k,n) = 1$, this means $d = 1$, so $gcd(n-k,n) = 1$.
A similar, but perhaps a bit simpler, way to show this is to let $d = gcd(n-k,n)$, giving that $d mid n-k$ and $d mid n$, so $d mid n - (n-k) = k$. Once again, this leads to $d = 1$ and that $gcd(n-k,n) = 1$.
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
edited Jul 18 at 1:08
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
answered Jul 18 at 0:01
John OmielanJohn Omielan
7,9202 gold badges3 silver badges25 bronze badges
7,9202 gold badges3 silver badges25 bronze badges
add a comment |
add a comment |
$begingroup$
Yes, you can use Bezout: $ 1 = gcd(n,k) = an!+!bk = (a!color#c00+!b)n - b(n!-!k),Rightarrow,gcd(n,n!-!k)=1$
Or $ $ if $ dmid n $ then $ dmid k!iff! dmid n!-!k,,$ so $,n,k,$ and $,n,n!-!k,$ have the same set $S$ of common divisors $d$, so they have the same greatest common divisor $(= max S)$
Or $!bmod d!:: $ if $,nequiv 0 $ then $ kequiv 0!iff! kequiv n,,$ so $ ldots,$ (as above)
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
$endgroup$
add a comment |
$begingroup$
Yes, you can use Bezout: $ 1 = gcd(n,k) = an!+!bk = (a!color#c00+!b)n - b(n!-!k),Rightarrow,gcd(n,n!-!k)=1$
Or $ $ if $ dmid n $ then $ dmid k!iff! dmid n!-!k,,$ so $,n,k,$ and $,n,n!-!k,$ have the same set $S$ of common divisors $d$, so they have the same greatest common divisor $(= max S)$
Or $!bmod d!:: $ if $,nequiv 0 $ then $ kequiv 0!iff! kequiv n,,$ so $ ldots,$ (as above)
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
$endgroup$
add a comment |
$begingroup$
Yes, you can use Bezout: $ 1 = gcd(n,k) = an!+!bk = (a!color#c00+!b)n - b(n!-!k),Rightarrow,gcd(n,n!-!k)=1$
Or $ $ if $ dmid n $ then $ dmid k!iff! dmid n!-!k,,$ so $,n,k,$ and $,n,n!-!k,$ have the same set $S$ of common divisors $d$, so they have the same greatest common divisor $(= max S)$
Or $!bmod d!:: $ if $,nequiv 0 $ then $ kequiv 0!iff! kequiv n,,$ so $ ldots,$ (as above)
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
$endgroup$
Yes, you can use Bezout: $ 1 = gcd(n,k) = an!+!bk = (a!color#c00+!b)n - b(n!-!k),Rightarrow,gcd(n,n!-!k)=1$
Or $ $ if $ dmid n $ then $ dmid k!iff! dmid n!-!k,,$ so $,n,k,$ and $,n,n!-!k,$ have the same set $S$ of common divisors $d$, so they have the same greatest common divisor $(= max S)$
Or $!bmod d!:: $ if $,nequiv 0 $ then $ kequiv 0!iff! kequiv n,,$ so $ ldots,$ (as above)
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
edited Jul 18 at 0:43
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
answered Jul 18 at 0:22
Bill DubuqueBill Dubuque
220k30 gold badges210 silver badges679 bronze badges
220k30 gold badges210 silver badges679 bronze badges
add a comment |
add a comment |
$begingroup$
$gcd(x,y)=g$ if and only if $g$ is the smallest positive integer that can be expressed in the form
$g=ax+by$ where $a,b in mathbb Z$.
Since $gcd(k,n)=1$ is given, then you know that there exists integers $a$ and $b$ such that $ak+bn = 1$$
So
beginalign
1 &= ak + bn \
&= -a(-k) -an + an + bn \
&= -a(n-k) + (a+b)n \
&= (-a)(n-k) + (a+b)n
endalign
Since $1$ is the smallest possible positive integer, it follows that
$$gcd(n-k,n)=1$$
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
$endgroup$
add a comment |
$begingroup$
$gcd(x,y)=g$ if and only if $g$ is the smallest positive integer that can be expressed in the form
$g=ax+by$ where $a,b in mathbb Z$.
Since $gcd(k,n)=1$ is given, then you know that there exists integers $a$ and $b$ such that $ak+bn = 1$$
So
beginalign
1 &= ak + bn \
&= -a(-k) -an + an + bn \
&= -a(n-k) + (a+b)n \
&= (-a)(n-k) + (a+b)n
endalign
Since $1$ is the smallest possible positive integer, it follows that
$$gcd(n-k,n)=1$$
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
$endgroup$
add a comment |
$begingroup$
$gcd(x,y)=g$ if and only if $g$ is the smallest positive integer that can be expressed in the form
$g=ax+by$ where $a,b in mathbb Z$.
Since $gcd(k,n)=1$ is given, then you know that there exists integers $a$ and $b$ such that $ak+bn = 1$$
So
beginalign
1 &= ak + bn \
&= -a(-k) -an + an + bn \
&= -a(n-k) + (a+b)n \
&= (-a)(n-k) + (a+b)n
endalign
Since $1$ is the smallest possible positive integer, it follows that
$$gcd(n-k,n)=1$$
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
$endgroup$
$gcd(x,y)=g$ if and only if $g$ is the smallest positive integer that can be expressed in the form
$g=ax+by$ where $a,b in mathbb Z$.
Since $gcd(k,n)=1$ is given, then you know that there exists integers $a$ and $b$ such that $ak+bn = 1$$
So
beginalign
1 &= ak + bn \
&= -a(-k) -an + an + bn \
&= -a(n-k) + (a+b)n \
&= (-a)(n-k) + (a+b)n
endalign
Since $1$ is the smallest possible positive integer, it follows that
$$gcd(n-k,n)=1$$
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
answered Jul 18 at 0:26
steven gregorysteven gregory
19.6k3 gold badges29 silver badges62 bronze badges
19.6k3 gold badges29 silver badges62 bronze badges
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3296239%2fsuppose-1-%25e2%2589%25a4-k-%25e2%2589%25a4-n-%25e2%2588%2592-1-and-gcdk-n-1-prove-that-gcdn-%25e2%2588%2592-k-n-1%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
