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;








2












$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.










share|cite|improve this question











$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

















2












$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.










share|cite|improve this question











$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













2












2








2





$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.










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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












  • 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










2 Answers
2






active

oldest

votes


















3












$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.



.






share|cite|improve this answer











$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


















2












$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.$






share|cite|improve this answer











$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













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
);



);













draft saved

draft discarded


















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









3












$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.



.






share|cite|improve this answer











$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















3












$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.



.






share|cite|improve this answer











$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













3












3








3





$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.



.






share|cite|improve this answer











$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.



.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








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
















  • $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













2












$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.$






share|cite|improve this answer











$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















2












$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.$






share|cite|improve this answer











$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













2












2








2





$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.$






share|cite|improve this answer











$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.$







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








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
















  • $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

















draft saved

draft discarded
















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Invision Community Contents History See also References External links Navigation menuProprietaryinvisioncommunity.comIPS Community ForumsIPS Community Forumsthis blog entry"License Changes, IP.Board 3.4, and the Future""Interview -- Matt Mecham of Ibforums""CEO Invision Power Board, Matt Mecham Is a Liar, Thief!"IPB License Explanation 1.3, 1.3.1, 2.0, and 2.1ArchivedSecurity Fixes, Updates And Enhancements For IPB 1.3.1Archived"New Demo Accounts - Invision Power Services"the original"New Default Skin"the original"Invision Power Board 3.0.0 and Applications Released"the original"Archived copy"the original"Perpetual licenses being done away with""Release Notes - Invision Power Services""Introducing: IPS Community Suite 4!"Invision Community Release Notes

Canceling a color specificationRandomly assigning color to Graphics3D objects?Default color for Filling in Mathematica 9Coloring specific elements of sets with a prime modified order in an array plotHow to pick a color differing significantly from the colors already in a given color list?Detection of the text colorColor numbers based on their valueCan color schemes for use with ColorData include opacity specification?My dynamic color schemes

Tom Holland Mục lục Đầu đời và giáo dục | Sự nghiệp | Cuộc sống cá nhân | Phim tham gia | Giải thưởng và đề cử | Chú thích | Liên kết ngoài | Trình đơn chuyển hướngProfile“Person Details for Thomas Stanley Holland, "England and Wales Birth Registration Index, 1837-2008" — FamilySearch.org”"Meet Tom Holland... the 16-year-old star of The Impossible""Schoolboy actor Tom Holland finds himself in Oscar contention for role in tsunami drama"“Naomi Watts on the Prince William and Harry's reaction to her film about the late Princess Diana”lưu trữ"Holland and Pflueger Are West End's Two New 'Billy Elliots'""I'm so envious of my son, the movie star! British writer Dominic Holland's spent 20 years trying to crack Hollywood - but he's been beaten to it by a very unlikely rival"“Richard and Margaret Povey of Jersey, Channel Islands, UK: Information about Thomas Stanley Holland”"Tom Holland to play Billy Elliot""New Billy Elliot leaving the garage"Billy Elliot the Musical - Tom Holland - Billy"A Tale of four Billys: Tom Holland""The Feel Good Factor""Thames Christian College schoolboys join Myleene Klass for The Feelgood Factor""Government launches £600,000 arts bursaries pilot""BILLY's Chapman, Holland, Gardner & Jackson-Keen Visit Prime Minister""Elton John 'blown away' by Billy Elliot fifth birthday" (video with John's interview and fragments of Holland's performance)"First News interviews Arrietty's Tom Holland"“33rd Critics' Circle Film Awards winners”“National Board of Review Current Awards”Bản gốc"Ron Howard Whaling Tale 'In The Heart Of The Sea' Casts Tom Holland"“'Spider-Man' Finds Tom Holland to Star as New Web-Slinger”lưu trữ“Captain America: Civil War (2016)”“Film Review: ‘Captain America: Civil War’”lưu trữ“‘Captain America: Civil War’ review: Choose your own avenger”lưu trữ“The Lost City of Z reviews”“Sony Pictures and Marvel Studios Find Their 'Spider-Man' Star and Director”“‘Mary Magdalene’, ‘Current War’ & ‘Wind River’ Get 2017 Release Dates From Weinstein”“Lionsgate Unleashing Daisy Ridley & Tom Holland Starrer ‘Chaos Walking’ In Cannes”“PTA's 'Master' Leads Chicago Film Critics Nominations, UPDATED: Houston and Indiana Critics Nominations”“Nominaciones Goya 2013 Telecinco Cinema – ENG”“Jameson Empire Film Awards: Martin Freeman wins best actor for performance in The Hobbit”“34th Annual Young Artist Awards”Bản gốc“Teen Choice Awards 2016—Captain America: Civil War Leads Second Wave of Nominations”“BAFTA Film Award Nominations: ‘La La Land’ Leads Race”“Saturn Awards Nominations 2017: 'Rogue One,' 'Walking Dead' Lead”Tom HollandTom HollandTom HollandTom Hollandmedia.gettyimages.comWorldCat Identities300279794no20130442900000 0004 0355 42791085670554170004732cb16706349t(data)XX5557367