Why is Bézout's identity considered an identity?Solving simple congruences by handProof of Bézout's identity - Cohn - CA p26Check proof of Bézout's identityConverse of Bézout's identityHow to formalize the notion of “context” and “arbitrary”? (In terms of “data types”?)A positive Bézout's identityProof by induction of Bézout's identity for $n$ integers with no common factorsBézout's identity and Extended Euclidean algorithm for polynomialsDoubt regarding the manipulation of Bézout's identityCounting integers related to Bézout's identityTerminology: naming different data-set computations / operations types
Signing using digital signatures?
How can I create ribbons like these in Microsoft word 2010?
Does ultrasonic bath cleaning damage laboratory volumetric glassware calibration?
“Faire” being used to mean “avoir l’air”?
Find smallest index that is identical to the value in an array
Was "I have the farts, again" broadcast from the Moon to the whole world?
Generate and graph the Recamán Sequence
Procedurally generate regions on island
Three column layout
The use of "I" and "we" used in the same sentence and other questions
If a high rpm motor is run at lower rpm, will it produce more torque?
Cross over of arrows in a complex diagram
Is there any set of 2-6 notes that doesn't have a chord name?
Would adding an external lens allow one area outside the focal plane to be in focus?
Do I have to roll to maintain concentration if a target other than me who is affected by my concentration spell takes damage?
Reverse of diffraction
Children's short story about material that accelerates away from gravity
Do 3D printers really reach 50 micron (0.050mm) accuracy?
Dual statement category theory
How do I find and plot the intersection of these three surfaces?
Zombie diet, why humans?
Why won't the ground take my seed?
Should I hide continue button until tasks are completed?
Anagram Within an Anagram!
Why is Bézout's identity considered an identity?
Solving simple congruences by handProof of Bézout's identity - Cohn - CA p26Check proof of Bézout's identityConverse of Bézout's identityHow to formalize the notion of “context” and “arbitrary”? (In terms of “data types”?)A positive Bézout's identityProof by induction of Bézout's identity for $n$ integers with no common factorsBézout's identity and Extended Euclidean algorithm for polynomialsDoubt regarding the manipulation of Bézout's identityCounting integers related to Bézout's identityTerminology: naming different data-set computations / operations types
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
In most cases, identities seem to take values and give outputs that are irrelevant to the input data.
example:
$(a + b)^2 = a^2 + 2ab + b^2$
$[cos(x)]^2 + [sin(x)]^2 = 1$
Yet Bézout's identity only seems to assert the existence of something, not a relation of the above kind.
Am I missing something, maybe a way to look at it?
[I know this isn't like a usual rigorous question, but something worth considering for those who enjoy mathematical literature]
Views even if undecisive would be appreciated.
elementary-number-theory discrete-mathematics terminology euclidean-algorithm
$endgroup$
add a comment |
$begingroup$
In most cases, identities seem to take values and give outputs that are irrelevant to the input data.
example:
$(a + b)^2 = a^2 + 2ab + b^2$
$[cos(x)]^2 + [sin(x)]^2 = 1$
Yet Bézout's identity only seems to assert the existence of something, not a relation of the above kind.
Am I missing something, maybe a way to look at it?
[I know this isn't like a usual rigorous question, but something worth considering for those who enjoy mathematical literature]
Views even if undecisive would be appreciated.
elementary-number-theory discrete-mathematics terminology euclidean-algorithm
$endgroup$
1
$begingroup$
The term identity is often used to describe an equality. For example, Euler's identity.
$endgroup$
– copper.hat
8 hours ago
$begingroup$
People are quirky and inconsistent in their language use. That's really all that can be said. I personally don't like the term "Bezout's Identity" for the exact reasons you state so I'd tell the world to stop using it. But apparently the world doesn't seem to revolve around me so ... no one pays attention when I do.
$endgroup$
– fleablood
2 hours ago
add a comment |
$begingroup$
In most cases, identities seem to take values and give outputs that are irrelevant to the input data.
example:
$(a + b)^2 = a^2 + 2ab + b^2$
$[cos(x)]^2 + [sin(x)]^2 = 1$
Yet Bézout's identity only seems to assert the existence of something, not a relation of the above kind.
Am I missing something, maybe a way to look at it?
[I know this isn't like a usual rigorous question, but something worth considering for those who enjoy mathematical literature]
Views even if undecisive would be appreciated.
elementary-number-theory discrete-mathematics terminology euclidean-algorithm
$endgroup$
In most cases, identities seem to take values and give outputs that are irrelevant to the input data.
example:
$(a + b)^2 = a^2 + 2ab + b^2$
$[cos(x)]^2 + [sin(x)]^2 = 1$
Yet Bézout's identity only seems to assert the existence of something, not a relation of the above kind.
Am I missing something, maybe a way to look at it?
[I know this isn't like a usual rigorous question, but something worth considering for those who enjoy mathematical literature]
Views even if undecisive would be appreciated.
elementary-number-theory discrete-mathematics terminology euclidean-algorithm
elementary-number-theory discrete-mathematics terminology euclidean-algorithm
edited 6 hours ago
Ethan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
51.2k5 gold badges60 silver badges130 bronze badges
asked 8 hours ago
John_NashJohn_Nash
192 bronze badges
192 bronze badges
1
$begingroup$
The term identity is often used to describe an equality. For example, Euler's identity.
$endgroup$
– copper.hat
8 hours ago
$begingroup$
People are quirky and inconsistent in their language use. That's really all that can be said. I personally don't like the term "Bezout's Identity" for the exact reasons you state so I'd tell the world to stop using it. But apparently the world doesn't seem to revolve around me so ... no one pays attention when I do.
$endgroup$
– fleablood
2 hours ago
add a comment |
1
$begingroup$
The term identity is often used to describe an equality. For example, Euler's identity.
$endgroup$
– copper.hat
8 hours ago
$begingroup$
People are quirky and inconsistent in their language use. That's really all that can be said. I personally don't like the term "Bezout's Identity" for the exact reasons you state so I'd tell the world to stop using it. But apparently the world doesn't seem to revolve around me so ... no one pays attention when I do.
$endgroup$
– fleablood
2 hours ago
1
1
$begingroup$
The term identity is often used to describe an equality. For example, Euler's identity.
$endgroup$
– copper.hat
8 hours ago
$begingroup$
The term identity is often used to describe an equality. For example, Euler's identity.
$endgroup$
– copper.hat
8 hours ago
$begingroup$
People are quirky and inconsistent in their language use. That's really all that can be said. I personally don't like the term "Bezout's Identity" for the exact reasons you state so I'd tell the world to stop using it. But apparently the world doesn't seem to revolve around me so ... no one pays attention when I do.
$endgroup$
– fleablood
2 hours ago
$begingroup$
People are quirky and inconsistent in their language use. That's really all that can be said. I personally don't like the term "Bezout's Identity" for the exact reasons you state so I'd tell the world to stop using it. But apparently the world doesn't seem to revolve around me so ... no one pays attention when I do.
$endgroup$
– fleablood
2 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
One way to view Bezout as an identity is to define functions $a_x,y, b_x,y,$ so that
$$ a_x,y x + b_x,y y, =, 1 rm for all coprime, x,yinBbb Z$$
Such functions implicitly exist in most extended Euclidean algorithm software. Compare
$$bmod xy!: bar a_x,y,x + bar b_x,y,y,equiv, 1 rm for all coprime, x,yinBbb Zqquadqquad $$
by using the functions $ bar a_x,y = x^-1bmod y,, bar b_x,y = y^-1bmod x,, $ see $ $ Inverse Reciprocity.
For Bezout we can put: $ a_x,y = x^-1bmod y,, b_x,y = (1-a_x,y,x)/y $ for example.
The general Bezout identity (for all $,x,yneq 0,0)$ reduces to the above by cancelling $gcd(x,y)$
Remark $ $ We introduced the functions $,a,,b,$ in order to eliminate the existential quatifiers in $, forall, x,y exists, a,b!: ax + b y = 1,,$ which leaves only universal quantifiers remaining, i.e. an "identity". The same idea works generally - see Skolemization.
A well known example is inverses: $,forall, x exists, y!: xy, = 1,,$ where we define the inverse function $,y_x = x^-1,$ which yields the identity $,forall x!: x,x^-1 = 1,$ in groups. Notice the close relationship with the modular example above, where the functions actually are (modular) inverses.
.
$endgroup$
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
1
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
add a comment |
$begingroup$
The Wikipedia article Bezout's identity states:
This article is about Bézout's theorem in arithmetic.
and also
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem:
Already, the result is called an identity, theorem, and lemma. The
terminology used in mathematics is not always precise and depends
on context. Usually, if there is an equation, then in some cases,
it can be called an identity, especially if it is true for all
values of the variables. Given any integers $,a,$
and $,b,$, then the Bezout equation
$, ax+by=d ,$ is true if $,d,$ is the GCD of $,a,$ and $,b,$
for some integers $,x,$ and $,y,$ which are not specified, but only
known to exist and not unique. They can be computed using the extended
Euclidean algorithm which is an efficient, effective algorithm. Perhaps
a better name would be Bezout's equation, but I have never seen that in
print.
What makes it somewhat peculiar is that, unlike the quadratic equation
which has a solution using the quadratic formula, there is no similar
formula for the solution of Bezout's equation. It would be a nice result
if there was a formula, but even though it is a linear equation, there are
two unknowns. At best, if we know the value of $,x,,$ then the formula
$,y = (d-ax)/b,$ gives the value of $,y,,$ and similarly if we
know the value of $,y,,$ then there is the formula
$, x = (d-by)/a,$ for the value of $,x.$
$endgroup$
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
1
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
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%2f3271922%2fwhy-is-b%25c3%25a9zouts-identity-considered-an-identity%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
One way to view Bezout as an identity is to define functions $a_x,y, b_x,y,$ so that
$$ a_x,y x + b_x,y y, =, 1 rm for all coprime, x,yinBbb Z$$
Such functions implicitly exist in most extended Euclidean algorithm software. Compare
$$bmod xy!: bar a_x,y,x + bar b_x,y,y,equiv, 1 rm for all coprime, x,yinBbb Zqquadqquad $$
by using the functions $ bar a_x,y = x^-1bmod y,, bar b_x,y = y^-1bmod x,, $ see $ $ Inverse Reciprocity.
For Bezout we can put: $ a_x,y = x^-1bmod y,, b_x,y = (1-a_x,y,x)/y $ for example.
The general Bezout identity (for all $,x,yneq 0,0)$ reduces to the above by cancelling $gcd(x,y)$
Remark $ $ We introduced the functions $,a,,b,$ in order to eliminate the existential quatifiers in $, forall, x,y exists, a,b!: ax + b y = 1,,$ which leaves only universal quantifiers remaining, i.e. an "identity". The same idea works generally - see Skolemization.
A well known example is inverses: $,forall, x exists, y!: xy, = 1,,$ where we define the inverse function $,y_x = x^-1,$ which yields the identity $,forall x!: x,x^-1 = 1,$ in groups. Notice the close relationship with the modular example above, where the functions actually are (modular) inverses.
.
$endgroup$
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
1
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
add a comment |
$begingroup$
One way to view Bezout as an identity is to define functions $a_x,y, b_x,y,$ so that
$$ a_x,y x + b_x,y y, =, 1 rm for all coprime, x,yinBbb Z$$
Such functions implicitly exist in most extended Euclidean algorithm software. Compare
$$bmod xy!: bar a_x,y,x + bar b_x,y,y,equiv, 1 rm for all coprime, x,yinBbb Zqquadqquad $$
by using the functions $ bar a_x,y = x^-1bmod y,, bar b_x,y = y^-1bmod x,, $ see $ $ Inverse Reciprocity.
For Bezout we can put: $ a_x,y = x^-1bmod y,, b_x,y = (1-a_x,y,x)/y $ for example.
The general Bezout identity (for all $,x,yneq 0,0)$ reduces to the above by cancelling $gcd(x,y)$
Remark $ $ We introduced the functions $,a,,b,$ in order to eliminate the existential quatifiers in $, forall, x,y exists, a,b!: ax + b y = 1,,$ which leaves only universal quantifiers remaining, i.e. an "identity". The same idea works generally - see Skolemization.
A well known example is inverses: $,forall, x exists, y!: xy, = 1,,$ where we define the inverse function $,y_x = x^-1,$ which yields the identity $,forall x!: x,x^-1 = 1,$ in groups. Notice the close relationship with the modular example above, where the functions actually are (modular) inverses.
.
$endgroup$
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
1
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
add a comment |
$begingroup$
One way to view Bezout as an identity is to define functions $a_x,y, b_x,y,$ so that
$$ a_x,y x + b_x,y y, =, 1 rm for all coprime, x,yinBbb Z$$
Such functions implicitly exist in most extended Euclidean algorithm software. Compare
$$bmod xy!: bar a_x,y,x + bar b_x,y,y,equiv, 1 rm for all coprime, x,yinBbb Zqquadqquad $$
by using the functions $ bar a_x,y = x^-1bmod y,, bar b_x,y = y^-1bmod x,, $ see $ $ Inverse Reciprocity.
For Bezout we can put: $ a_x,y = x^-1bmod y,, b_x,y = (1-a_x,y,x)/y $ for example.
The general Bezout identity (for all $,x,yneq 0,0)$ reduces to the above by cancelling $gcd(x,y)$
Remark $ $ We introduced the functions $,a,,b,$ in order to eliminate the existential quatifiers in $, forall, x,y exists, a,b!: ax + b y = 1,,$ which leaves only universal quantifiers remaining, i.e. an "identity". The same idea works generally - see Skolemization.
A well known example is inverses: $,forall, x exists, y!: xy, = 1,,$ where we define the inverse function $,y_x = x^-1,$ which yields the identity $,forall x!: x,x^-1 = 1,$ in groups. Notice the close relationship with the modular example above, where the functions actually are (modular) inverses.
.
$endgroup$
One way to view Bezout as an identity is to define functions $a_x,y, b_x,y,$ so that
$$ a_x,y x + b_x,y y, =, 1 rm for all coprime, x,yinBbb Z$$
Such functions implicitly exist in most extended Euclidean algorithm software. Compare
$$bmod xy!: bar a_x,y,x + bar b_x,y,y,equiv, 1 rm for all coprime, x,yinBbb Zqquadqquad $$
by using the functions $ bar a_x,y = x^-1bmod y,, bar b_x,y = y^-1bmod x,, $ see $ $ Inverse Reciprocity.
For Bezout we can put: $ a_x,y = x^-1bmod y,, b_x,y = (1-a_x,y,x)/y $ for example.
The general Bezout identity (for all $,x,yneq 0,0)$ reduces to the above by cancelling $gcd(x,y)$
Remark $ $ We introduced the functions $,a,,b,$ in order to eliminate the existential quatifiers in $, forall, x,y exists, a,b!: ax + b y = 1,,$ which leaves only universal quantifiers remaining, i.e. an "identity". The same idea works generally - see Skolemization.
A well known example is inverses: $,forall, x exists, y!: xy, = 1,,$ where we define the inverse function $,y_x = x^-1,$ which yields the identity $,forall x!: x,x^-1 = 1,$ in groups. Notice the close relationship with the modular example above, where the functions actually are (modular) inverses.
.
edited 5 hours ago
answered 8 hours ago
Bill DubuqueBill Dubuque
218k30 gold badges209 silver badges670 bronze badges
218k30 gold badges209 silver badges670 bronze badges
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
1
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
add a comment |
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
1
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
This needs something extra I think. Namely a specification of the representative for $x^-1 mod y$? For example, take $x = 2, y = 3$. Then $2^-1 equiv 2 mod 3$ and $3^-1 equiv 1 mod 2$. But $2 cdot 2 + 1 cdot 3 = 7$. Maybe I misunderstand your notation? Do you mean that there exists a representative such that the identity holds?
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
$begingroup$
I see you've made an edit. This makes more sense.
$endgroup$
– Ruben du Burck
8 hours ago
1
1
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@RubenduBurck Yes, was editing it while you were replying
$endgroup$
– Bill Dubuque
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@BillDubuque is this the usual modulo notation, a = b (mod n) implies n divides a-b ? if so, what does x(x inverse mod y) mean, just finished high school, would appreciate the extra time of yours I'm taking
$endgroup$
– John_Nash
8 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@John_Nash Yes, but I also use the binary operation mod (= remainder)
$endgroup$
– Bill Dubuque
7 hours ago
add a comment |
$begingroup$
The Wikipedia article Bezout's identity states:
This article is about Bézout's theorem in arithmetic.
and also
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem:
Already, the result is called an identity, theorem, and lemma. The
terminology used in mathematics is not always precise and depends
on context. Usually, if there is an equation, then in some cases,
it can be called an identity, especially if it is true for all
values of the variables. Given any integers $,a,$
and $,b,$, then the Bezout equation
$, ax+by=d ,$ is true if $,d,$ is the GCD of $,a,$ and $,b,$
for some integers $,x,$ and $,y,$ which are not specified, but only
known to exist and not unique. They can be computed using the extended
Euclidean algorithm which is an efficient, effective algorithm. Perhaps
a better name would be Bezout's equation, but I have never seen that in
print.
What makes it somewhat peculiar is that, unlike the quadratic equation
which has a solution using the quadratic formula, there is no similar
formula for the solution of Bezout's equation. It would be a nice result
if there was a formula, but even though it is a linear equation, there are
two unknowns. At best, if we know the value of $,x,,$ then the formula
$,y = (d-ax)/b,$ gives the value of $,y,,$ and similarly if we
know the value of $,y,,$ then there is the formula
$, x = (d-by)/a,$ for the value of $,x.$
$endgroup$
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
1
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
add a comment |
$begingroup$
The Wikipedia article Bezout's identity states:
This article is about Bézout's theorem in arithmetic.
and also
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem:
Already, the result is called an identity, theorem, and lemma. The
terminology used in mathematics is not always precise and depends
on context. Usually, if there is an equation, then in some cases,
it can be called an identity, especially if it is true for all
values of the variables. Given any integers $,a,$
and $,b,$, then the Bezout equation
$, ax+by=d ,$ is true if $,d,$ is the GCD of $,a,$ and $,b,$
for some integers $,x,$ and $,y,$ which are not specified, but only
known to exist and not unique. They can be computed using the extended
Euclidean algorithm which is an efficient, effective algorithm. Perhaps
a better name would be Bezout's equation, but I have never seen that in
print.
What makes it somewhat peculiar is that, unlike the quadratic equation
which has a solution using the quadratic formula, there is no similar
formula for the solution of Bezout's equation. It would be a nice result
if there was a formula, but even though it is a linear equation, there are
two unknowns. At best, if we know the value of $,x,,$ then the formula
$,y = (d-ax)/b,$ gives the value of $,y,,$ and similarly if we
know the value of $,y,,$ then there is the formula
$, x = (d-by)/a,$ for the value of $,x.$
$endgroup$
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
1
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
add a comment |
$begingroup$
The Wikipedia article Bezout's identity states:
This article is about Bézout's theorem in arithmetic.
and also
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem:
Already, the result is called an identity, theorem, and lemma. The
terminology used in mathematics is not always precise and depends
on context. Usually, if there is an equation, then in some cases,
it can be called an identity, especially if it is true for all
values of the variables. Given any integers $,a,$
and $,b,$, then the Bezout equation
$, ax+by=d ,$ is true if $,d,$ is the GCD of $,a,$ and $,b,$
for some integers $,x,$ and $,y,$ which are not specified, but only
known to exist and not unique. They can be computed using the extended
Euclidean algorithm which is an efficient, effective algorithm. Perhaps
a better name would be Bezout's equation, but I have never seen that in
print.
What makes it somewhat peculiar is that, unlike the quadratic equation
which has a solution using the quadratic formula, there is no similar
formula for the solution of Bezout's equation. It would be a nice result
if there was a formula, but even though it is a linear equation, there are
two unknowns. At best, if we know the value of $,x,,$ then the formula
$,y = (d-ax)/b,$ gives the value of $,y,,$ and similarly if we
know the value of $,y,,$ then there is the formula
$, x = (d-by)/a,$ for the value of $,x.$
$endgroup$
The Wikipedia article Bezout's identity states:
This article is about Bézout's theorem in arithmetic.
and also
In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem:
Already, the result is called an identity, theorem, and lemma. The
terminology used in mathematics is not always precise and depends
on context. Usually, if there is an equation, then in some cases,
it can be called an identity, especially if it is true for all
values of the variables. Given any integers $,a,$
and $,b,$, then the Bezout equation
$, ax+by=d ,$ is true if $,d,$ is the GCD of $,a,$ and $,b,$
for some integers $,x,$ and $,y,$ which are not specified, but only
known to exist and not unique. They can be computed using the extended
Euclidean algorithm which is an efficient, effective algorithm. Perhaps
a better name would be Bezout's equation, but I have never seen that in
print.
What makes it somewhat peculiar is that, unlike the quadratic equation
which has a solution using the quadratic formula, there is no similar
formula for the solution of Bezout's equation. It would be a nice result
if there was a formula, but even though it is a linear equation, there are
two unknowns. At best, if we know the value of $,x,,$ then the formula
$,y = (d-ax)/b,$ gives the value of $,y,,$ and similarly if we
know the value of $,y,,$ then there is the formula
$, x = (d-by)/a,$ for the value of $,x.$
edited 3 hours ago
answered 8 hours ago
SomosSomos
16.4k1 gold badge14 silver badges38 bronze badges
16.4k1 gold badge14 silver badges38 bronze badges
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
1
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
add a comment |
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
1
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
I agree that an explicit formula is missing. That is what makes it useful to Cryptography from what I've read.
$endgroup$
– John_Nash
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@John There are in fact formulas for the Bezout coefficients (in terms of modular inverses) - see the edit to my answer.
$endgroup$
– Bill Dubuque
7 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
$begingroup$
@BillDubuque Well, how is the modular inverse computed? My understanding is that Euclidean Algorithm is used as in Bezout's identity, and so it is a circular formula.
$endgroup$
– Somos
6 hours ago
1
1
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@Somos No,there are plenty of other ways to compute inverses without (explicitly) compting the Bezout identity, e.g. by Gauss's algorithm, or little Fermat and repeated squaring, etc. But we can easily compute one from the other, so they are equivalent in that sense.
$endgroup$
– Bill Dubuque
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
$begingroup$
@BillDubuque Thanks for that comment! I just did not immediately think about the other ways to compute inverses because I depend on CAS to do the calculations, although I knew about some of them.
$endgroup$
– Somos
6 hours ago
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%2f3271922%2fwhy-is-b%25c3%25a9zouts-identity-considered-an-identity%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
1
$begingroup$
The term identity is often used to describe an equality. For example, Euler's identity.
$endgroup$
– copper.hat
8 hours ago
$begingroup$
People are quirky and inconsistent in their language use. That's really all that can be said. I personally don't like the term "Bezout's Identity" for the exact reasons you state so I'd tell the world to stop using it. But apparently the world doesn't seem to revolve around me so ... no one pays attention when I do.
$endgroup$
– fleablood
2 hours ago