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

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

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

199年 目錄 大件事 到箇年出世嗰人 到箇年死嗰人 節慶、風俗習慣 導覽選單