double check my steps to find multiplicative inverse?Solving $ax equiv c pmod b$ efficiently when $a,b$ are not coprimeInverse modulo question?'Gauss's Algorithm' for computing modular fractions and inversesUsing Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse — Need some help understanding the solutions here.Solving congruence relations in Zp where p is very large.Find the multiplicative inverse of 23 in Z26Modular multiplicative inverse and coprime numbers needed.Fastest way to find modular multiplicative inverseFinding the Modular Multiplicative Inverse of a large numberMultiplicative inverse of polynomial modulus an integerModular Multiplicative Inverse / Euclidean AlgorithmFinding Modular Multiplicative Inverses (Quickly!)More than one modular multiplicative inverse possible?Finding inverse in multiplicative groupCalculation of modular multiplicative inverse of A mod B when A > B
Is there a problem with hiding "forgot password" until it's needed?
How can a function with a hole (removable discontinuity) equal a function with no hole?
Is HostGator storing my password in plaintext?
How to pronounce the slash sign
Is this apparent Class Action settlement a spam message?
Method to test if a number is a perfect power?
How to Reset Passwords on Multiple Websites Easily?
Implement the Thanos sorting algorithm
Customer Requests (Sometimes) Drive Me Bonkers!
Pre-amplifier input protection
Tiptoe or tiphoof? Adjusting words to better fit fantasy races
CREATE opcode: what does it really do?
Why, precisely, is argon used in neutrino experiments?
Is the destination of a commercial flight important for the pilot?
Where does the Z80 processor start executing from?
Integer addition + constant, is it a group?
Would a high gravity rocky planet be guaranteed to have an atmosphere?
Anatomically Correct Strange Women In Ponds Distributing Swords
How can I get through very long and very dry, but also very useful technical documents when learning a new tool?
Class Action - which options I have?
What happens if you roll doubles 3 times then land on "Go to jail?"
How do I find the solutions of the following equation?
Opposite of a diet
How can we prove that any integral in the set of non-elementary integrals cannot be expressed in the form of elementary functions?
double check my steps to find multiplicative inverse?
Solving $ax equiv c pmod b$ efficiently when $a,b$ are not coprimeInverse modulo question?'Gauss's Algorithm' for computing modular fractions and inversesUsing Fermat's Little Theorem or Euler's Theorem to find the Multiplicative Inverse — Need some help understanding the solutions here.Solving congruence relations in Zp where p is very large.Find the multiplicative inverse of 23 in Z26Modular multiplicative inverse and coprime numbers needed.Fastest way to find modular multiplicative inverseFinding the Modular Multiplicative Inverse of a large numberMultiplicative inverse of polynomial modulus an integerModular Multiplicative Inverse / Euclidean AlgorithmFinding Modular Multiplicative Inverses (Quickly!)More than one modular multiplicative inverse possible?Finding inverse in multiplicative groupCalculation of modular multiplicative inverse of A mod B when A > B
$begingroup$
assume we want to find the multiplicative inverse for $117$ in $Z337$.
i know that in order to find the the multiplicative inverse we use Euclidean and Extended Euclidean algorithm.
Eculidian:
$337 = 2*117 + 103$
$117 = 1*103 + 14$
$103 = 7*14 + 5$
$14 = 2*5 + 4$
$5 = 1*4 + 1$
Extended Euclidean:
not going to include the whole solution because i am pretty sure of it, i get:
$1=25*337-72*117$
Extended Euclidean gives us that the inverse is $-72$. but how come a calculator says the inverse is $265$ and so do the teacher. do i need to do anything more ? usually i only need to do Euclidean and Extended Euclidean to find the inverse.
elementary-number-theory modular-arithmetic
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
$endgroup$
|
show 1 more comment
$begingroup$
assume we want to find the multiplicative inverse for $117$ in $Z337$.
i know that in order to find the the multiplicative inverse we use Euclidean and Extended Euclidean algorithm.
Eculidian:
$337 = 2*117 + 103$
$117 = 1*103 + 14$
$103 = 7*14 + 5$
$14 = 2*5 + 4$
$5 = 1*4 + 1$
Extended Euclidean:
not going to include the whole solution because i am pretty sure of it, i get:
$1=25*337-72*117$
Extended Euclidean gives us that the inverse is $-72$. but how come a calculator says the inverse is $265$ and so do the teacher. do i need to do anything more ? usually i only need to do Euclidean and Extended Euclidean to find the inverse.
elementary-number-theory modular-arithmetic
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
$endgroup$
$begingroup$
$-72equiv 265 (textrm mod 337)$
$endgroup$
– King Ghidorah
Dec 11 '16 at 19:17
$begingroup$
ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:21
$begingroup$
If the final result is negative, then you need to add the order ($337$ in this case).
$endgroup$
– barak manos
Dec 11 '16 at 19:21
$begingroup$
I fixed some typos in your question (you had $177$ vs. $117) $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 20:14
$begingroup$
ops, sorry it should be 117. Thanks !
$endgroup$
– pabloBar
Dec 11 '16 at 20:16
|
show 1 more comment
$begingroup$
assume we want to find the multiplicative inverse for $117$ in $Z337$.
i know that in order to find the the multiplicative inverse we use Euclidean and Extended Euclidean algorithm.
Eculidian:
$337 = 2*117 + 103$
$117 = 1*103 + 14$
$103 = 7*14 + 5$
$14 = 2*5 + 4$
$5 = 1*4 + 1$
Extended Euclidean:
not going to include the whole solution because i am pretty sure of it, i get:
$1=25*337-72*117$
Extended Euclidean gives us that the inverse is $-72$. but how come a calculator says the inverse is $265$ and so do the teacher. do i need to do anything more ? usually i only need to do Euclidean and Extended Euclidean to find the inverse.
elementary-number-theory modular-arithmetic
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
$endgroup$
assume we want to find the multiplicative inverse for $117$ in $Z337$.
i know that in order to find the the multiplicative inverse we use Euclidean and Extended Euclidean algorithm.
Eculidian:
$337 = 2*117 + 103$
$117 = 1*103 + 14$
$103 = 7*14 + 5$
$14 = 2*5 + 4$
$5 = 1*4 + 1$
Extended Euclidean:
not going to include the whole solution because i am pretty sure of it, i get:
$1=25*337-72*117$
Extended Euclidean gives us that the inverse is $-72$. but how come a calculator says the inverse is $265$ and so do the teacher. do i need to do anything more ? usually i only need to do Euclidean and Extended Euclidean to find the inverse.
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
edited Dec 11 '16 at 20:14
Bill Dubuque
213k29195654
213k29195654
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
asked Dec 11 '16 at 19:08
pabloBarpabloBar
335
335
$begingroup$
$-72equiv 265 (textrm mod 337)$
$endgroup$
– King Ghidorah
Dec 11 '16 at 19:17
$begingroup$
ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:21
$begingroup$
If the final result is negative, then you need to add the order ($337$ in this case).
$endgroup$
– barak manos
Dec 11 '16 at 19:21
$begingroup$
I fixed some typos in your question (you had $177$ vs. $117) $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 20:14
$begingroup$
ops, sorry it should be 117. Thanks !
$endgroup$
– pabloBar
Dec 11 '16 at 20:16
|
show 1 more comment
$begingroup$
$-72equiv 265 (textrm mod 337)$
$endgroup$
– King Ghidorah
Dec 11 '16 at 19:17
$begingroup$
ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:21
$begingroup$
If the final result is negative, then you need to add the order ($337$ in this case).
$endgroup$
– barak manos
Dec 11 '16 at 19:21
$begingroup$
I fixed some typos in your question (you had $177$ vs. $117) $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 20:14
$begingroup$
ops, sorry it should be 117. Thanks !
$endgroup$
– pabloBar
Dec 11 '16 at 20:16
$begingroup$
$-72equiv 265 (textrm mod 337)$
$endgroup$
– King Ghidorah
Dec 11 '16 at 19:17
$begingroup$
$-72equiv 265 (textrm mod 337)$
$endgroup$
– King Ghidorah
Dec 11 '16 at 19:17
$begingroup$
ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:21
$begingroup$
ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:21
$begingroup$
If the final result is negative, then you need to add the order ($337$ in this case).
$endgroup$
– barak manos
Dec 11 '16 at 19:21
$begingroup$
If the final result is negative, then you need to add the order ($337$ in this case).
$endgroup$
– barak manos
Dec 11 '16 at 19:21
$begingroup$
I fixed some typos in your question (you had $177$ vs. $117) $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 20:14
$begingroup$
I fixed some typos in your question (you had $177$ vs. $117) $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 20:14
$begingroup$
ops, sorry it should be 117. Thanks !
$endgroup$
– pabloBar
Dec 11 '16 at 20:16
$begingroup$
ops, sorry it should be 117. Thanks !
$endgroup$
– pabloBar
Dec 11 '16 at 20:16
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
Either answer is correct since they are both congruent, i.e. $,rm mod, 337!: color#c00-72equiv 337-72equiv 265. $ Below is the complete calculation by a fractional form of the Extended Euclidean Algorithm
$rm mod 337!:, dfrac0337 oversetlargefrownequiv dfrac1117 oversetlargefrownequiv dfrac-3color#0a0-14 oversetlargefrownequiv dfrac-235 oversetlargefrownequivcolor#c00dfrac-72 1oversetlargefrownequivdfrac00,$ or, equivalently, without fractions
$qquad beginarrayrrl
[![1]!]!:!!!& 337,x!!!&equiv 0\
[![2]!]!:!!!& 117,x!!!&equiv 1\
[![1]!]-3[![2]!]=:[![3]!]!:!!!& color#0a0-14,x!!!&equiv -3\
[![2]!]+8[![3]!]=:[![4]!]!:!!!& 5,x!!! &equiv -23\
[![3]!]+3[![4]!]=:[![5]!]!:!!!& color#c001, x!!! &equiv color#c00-72
endarray$
Remark $ $ Allowing negative remainders (i.e. least magnitude reps) often simplifies calculations, e.g.$,10^nequiv (-1)^nequiv pm1pmod11 $ is used to calculate remainders mod $11$ as an alternating digit sums (casting out elevens). I did so above in $ color#0a0-14equiv 337pmod117,$ vs. $ 103 = (337bmod 117),$ as in your calculation. Using $-14,$ vs. $103$ simplifies subsequent calculations (it eliminates one step from your calculations, but generally it will save many steps in longer calculations).
See this answer for another worked example.
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
|
show 7 more comments
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
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%2f2054312%2fdouble-check-my-steps-to-find-multiplicative-inverse%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Either answer is correct since they are both congruent, i.e. $,rm mod, 337!: color#c00-72equiv 337-72equiv 265. $ Below is the complete calculation by a fractional form of the Extended Euclidean Algorithm
$rm mod 337!:, dfrac0337 oversetlargefrownequiv dfrac1117 oversetlargefrownequiv dfrac-3color#0a0-14 oversetlargefrownequiv dfrac-235 oversetlargefrownequivcolor#c00dfrac-72 1oversetlargefrownequivdfrac00,$ or, equivalently, without fractions
$qquad beginarrayrrl
[![1]!]!:!!!& 337,x!!!&equiv 0\
[![2]!]!:!!!& 117,x!!!&equiv 1\
[![1]!]-3[![2]!]=:[![3]!]!:!!!& color#0a0-14,x!!!&equiv -3\
[![2]!]+8[![3]!]=:[![4]!]!:!!!& 5,x!!! &equiv -23\
[![3]!]+3[![4]!]=:[![5]!]!:!!!& color#c001, x!!! &equiv color#c00-72
endarray$
Remark $ $ Allowing negative remainders (i.e. least magnitude reps) often simplifies calculations, e.g.$,10^nequiv (-1)^nequiv pm1pmod11 $ is used to calculate remainders mod $11$ as an alternating digit sums (casting out elevens). I did so above in $ color#0a0-14equiv 337pmod117,$ vs. $ 103 = (337bmod 117),$ as in your calculation. Using $-14,$ vs. $103$ simplifies subsequent calculations (it eliminates one step from your calculations, but generally it will save many steps in longer calculations).
See this answer for another worked example.
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
|
show 7 more comments
$begingroup$
Either answer is correct since they are both congruent, i.e. $,rm mod, 337!: color#c00-72equiv 337-72equiv 265. $ Below is the complete calculation by a fractional form of the Extended Euclidean Algorithm
$rm mod 337!:, dfrac0337 oversetlargefrownequiv dfrac1117 oversetlargefrownequiv dfrac-3color#0a0-14 oversetlargefrownequiv dfrac-235 oversetlargefrownequivcolor#c00dfrac-72 1oversetlargefrownequivdfrac00,$ or, equivalently, without fractions
$qquad beginarrayrrl
[![1]!]!:!!!& 337,x!!!&equiv 0\
[![2]!]!:!!!& 117,x!!!&equiv 1\
[![1]!]-3[![2]!]=:[![3]!]!:!!!& color#0a0-14,x!!!&equiv -3\
[![2]!]+8[![3]!]=:[![4]!]!:!!!& 5,x!!! &equiv -23\
[![3]!]+3[![4]!]=:[![5]!]!:!!!& color#c001, x!!! &equiv color#c00-72
endarray$
Remark $ $ Allowing negative remainders (i.e. least magnitude reps) often simplifies calculations, e.g.$,10^nequiv (-1)^nequiv pm1pmod11 $ is used to calculate remainders mod $11$ as an alternating digit sums (casting out elevens). I did so above in $ color#0a0-14equiv 337pmod117,$ vs. $ 103 = (337bmod 117),$ as in your calculation. Using $-14,$ vs. $103$ simplifies subsequent calculations (it eliminates one step from your calculations, but generally it will save many steps in longer calculations).
See this answer for another worked example.
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
|
show 7 more comments
$begingroup$
Either answer is correct since they are both congruent, i.e. $,rm mod, 337!: color#c00-72equiv 337-72equiv 265. $ Below is the complete calculation by a fractional form of the Extended Euclidean Algorithm
$rm mod 337!:, dfrac0337 oversetlargefrownequiv dfrac1117 oversetlargefrownequiv dfrac-3color#0a0-14 oversetlargefrownequiv dfrac-235 oversetlargefrownequivcolor#c00dfrac-72 1oversetlargefrownequivdfrac00,$ or, equivalently, without fractions
$qquad beginarrayrrl
[![1]!]!:!!!& 337,x!!!&equiv 0\
[![2]!]!:!!!& 117,x!!!&equiv 1\
[![1]!]-3[![2]!]=:[![3]!]!:!!!& color#0a0-14,x!!!&equiv -3\
[![2]!]+8[![3]!]=:[![4]!]!:!!!& 5,x!!! &equiv -23\
[![3]!]+3[![4]!]=:[![5]!]!:!!!& color#c001, x!!! &equiv color#c00-72
endarray$
Remark $ $ Allowing negative remainders (i.e. least magnitude reps) often simplifies calculations, e.g.$,10^nequiv (-1)^nequiv pm1pmod11 $ is used to calculate remainders mod $11$ as an alternating digit sums (casting out elevens). I did so above in $ color#0a0-14equiv 337pmod117,$ vs. $ 103 = (337bmod 117),$ as in your calculation. Using $-14,$ vs. $103$ simplifies subsequent calculations (it eliminates one step from your calculations, but generally it will save many steps in longer calculations).
See this answer for another worked example.
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
$endgroup$
Either answer is correct since they are both congruent, i.e. $,rm mod, 337!: color#c00-72equiv 337-72equiv 265. $ Below is the complete calculation by a fractional form of the Extended Euclidean Algorithm
$rm mod 337!:, dfrac0337 oversetlargefrownequiv dfrac1117 oversetlargefrownequiv dfrac-3color#0a0-14 oversetlargefrownequiv dfrac-235 oversetlargefrownequivcolor#c00dfrac-72 1oversetlargefrownequivdfrac00,$ or, equivalently, without fractions
$qquad beginarrayrrl
[![1]!]!:!!!& 337,x!!!&equiv 0\
[![2]!]!:!!!& 117,x!!!&equiv 1\
[![1]!]-3[![2]!]=:[![3]!]!:!!!& color#0a0-14,x!!!&equiv -3\
[![2]!]+8[![3]!]=:[![4]!]!:!!!& 5,x!!! &equiv -23\
[![3]!]+3[![4]!]=:[![5]!]!:!!!& color#c001, x!!! &equiv color#c00-72
endarray$
Remark $ $ Allowing negative remainders (i.e. least magnitude reps) often simplifies calculations, e.g.$,10^nequiv (-1)^nequiv pm1pmod11 $ is used to calculate remainders mod $11$ as an alternating digit sums (casting out elevens). I did so above in $ color#0a0-14equiv 337pmod117,$ vs. $ 103 = (337bmod 117),$ as in your calculation. Using $-14,$ vs. $103$ simplifies subsequent calculations (it eliminates one step from your calculations, but generally it will save many steps in longer calculations).
See this answer for another worked example.
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
edited Mar 17 at 20:15
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
answered Dec 11 '16 at 19:24
Bill DubuqueBill Dubuque
213k29195654
213k29195654
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
|
show 7 more comments
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
Thanks for the answer, but i wonder if its mathematically correct to say that $-72$ is the multiplicative inverse? is it ok if the multiplicative inverse is negative ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:30
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
In@pabloBar $ 117^-1equiv -72pmod337,$ is correct, but $, -72 = (117^-1bmod 337),$ is not correct. Do you understand the difference?
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:33
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
how would you translate these expressions in words?, sorry a bit bad when it comes the math expressions.
$endgroup$
– pabloBar
Dec 11 '16 at 19:36
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
@pabloBar $ aequiv bpmod n,$ means $,n,$ divides $,a-b,,$ but $, a = (bbmod n),$ means the same plus $, 0le a < n,,$ i.e. $,a,$ is the least nonnegative integer $equiv bpmod n,, $ i.e. the remainder left on dividing $,b,$ by $,n.$ $ $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 19:41
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
$begingroup$
on exam i would do the calculations above and then state with the exact words that "the multiplicative is $-72$", would my statement be correct in this case ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:47
|
show 7 more comments
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%2f2054312%2fdouble-check-my-steps-to-find-multiplicative-inverse%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
$begingroup$
$-72equiv 265 (textrm mod 337)$
$endgroup$
– King Ghidorah
Dec 11 '16 at 19:17
$begingroup$
ohh i see, is it wrong to say that $-72$ is the multiplicative inverse? is it enough to stop at $-72$ ?
$endgroup$
– pabloBar
Dec 11 '16 at 19:21
$begingroup$
If the final result is negative, then you need to add the order ($337$ in this case).
$endgroup$
– barak manos
Dec 11 '16 at 19:21
$begingroup$
I fixed some typos in your question (you had $177$ vs. $117) $
$endgroup$
– Bill Dubuque
Dec 11 '16 at 20:14
$begingroup$
ops, sorry it should be 117. Thanks !
$endgroup$
– pabloBar
Dec 11 '16 at 20:16