Mfcttrf

What adaptations would be advantageous given a regular, but extreme variation in climate?

How to engage Decker in the actual run?

RX vs TX operation in Software UART

Princesses covering an 8x8 chess board

Showing a homeless person that you care about their well-being

Response to referee after rejection

Would fantasy dwarves be able to invent and/or manufacture the radio?

Can someone interview their sibling?

Can a NATO member call Article 5 after being attacked outside its national borders?

What are the limits of religious freedom in the workplace?

How do I update sudo package version?

SpaceX Starship landing on Moon or Mars: why doesn't it fall over?

What is the purpose of polls published by the organization that they are asking about which have leading/confusing questions?

Can I reproduce this in Latex

Why do the Romance languages use definite articles, when Latin doesn't?

How can I increase the rate of regeneration in humans without the possibility of tumors developing?

Im on the Titanic, what should I do to survive?

Uses of に思う in this statement

Why are one-word titles so dominant in books, film, and games?

Are hit dice used to add damage?

Find the closest enemy

What (if any) replacement parts have been 3D printed on the ISS and then installed?

What's the origin of the trope that dragons used to be common but aren't any more?

How to delete music as it's being played

Euclid Algorithm to Find Muliplicative Inverse

How to use the Extended Euclidean Algorithm manually?Use Euclid's Algorithm to find the multiplicative inverseUsing the Euclidean Algorithm how to find the inverse of 41 in Z(131)Solving the congruence $7x + 3 = 1 mod 31$?Find the inverse modulo of a number - got a negative resultSolving $3xequiv 4pmod 7$Simultaneusly solving $2x equiv 11 pmod15$ and $3x equiv 6 pmod 8$$x^2 + 3x + 7 equiv 0 pmod 37$What is a modular inverse?What is $5^-1$ in $mathbb Z_11$?Proving Bezouts identity is equal to the modular multiplicative inverseFinding modular inverse (wrong approach)Prove if a (mod n) has a multiplicative inverse, then it's uniqueDecrypting an Affine Cipher $ e(m)=am+bpmod27$ knowing $e(8)equiv 14$ and $e(26)equiv 5$

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;

7

$begingroup$

Here I am trying to find the multiplicative inverse of 19 respect to 29.

$$19x equiv 1 pmod29 $$

What I tried

beginalign*
29 &= 1(19) + 10\
19 &= 1(10) + 9\
10 &= 1(9) + 1.
endalign*

From backtracking, I came up with the

beginalign*
1 &= 2(29) - 3(19)\
endalign*

However, 3 is not a multiplicative inverse of the 29. Where am I making a mistake?

I looked many answers including this answer; however, couldn't figure out my mistake.

elementary-number-theory modular-arithmetic euclidean-algorithm

share|cite|improve this question

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

New contributor

Emrah Sariboz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  The inerse is $-3$ here, which is congruent to $26$
  $endgroup$
  – Peter
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Instead of rote rule application to the Bezout identity you should remember its genesis, viz. reducing $, a n + b m = 1,$ modulo $n$ yields $,bmequiv 1,$ so $, mequiv b^-1pmod!n.,$ In your case $, b = -3,$ (you forgot to include the sign). Generally one should always strive to remember the conceptual heart of the matter vs. rote rules.
  $endgroup$
  – Bill Dubuque
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Btw, it is easier and far less error-prone to forward propagate the equations, e.g. see here and here.
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque Do you agree with my suggested choice of duplicate?
  $endgroup$
  – Jyrki Lahtonen
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  FWIW I haven't downvoted on the answers here even though I am tempted, and encourage the practice. A site this age has certainly covered all the nooks and corners of Euclid, so it behooves 20k+ users to search first. When they obviously don't, a downvote is A) a reminder, B) a gesture of strong disproval.
  $endgroup$
  – Jyrki Lahtonen
  2 days ago
  
  

  
  
  
  

 | 
show 2 more comments

7

$begingroup$

Here I am trying to find the multiplicative inverse of 19 respect to 29.

$$19x equiv 1 pmod29 $$

What I tried

beginalign*
29 &= 1(19) + 10\
19 &= 1(10) + 9\
10 &= 1(9) + 1.
endalign*

From backtracking, I came up with the

beginalign*
1 &= 2(29) - 3(19)\
endalign*

However, 3 is not a multiplicative inverse of the 29. Where am I making a mistake?

I looked many answers including this answer; however, couldn't figure out my mistake.

elementary-number-theory modular-arithmetic euclidean-algorithm

share|cite|improve this question

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

New contributor

Emrah Sariboz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  $begingroup$
  The inerse is $-3$ here, which is congruent to $26$
  $endgroup$
  – Peter
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Instead of rote rule application to the Bezout identity you should remember its genesis, viz. reducing $, a n + b m = 1,$ modulo $n$ yields $,bmequiv 1,$ so $, mequiv b^-1pmod!n.,$ In your case $, b = -3,$ (you forgot to include the sign). Generally one should always strive to remember the conceptual heart of the matter vs. rote rules.
  $endgroup$
  – Bill Dubuque
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Btw, it is easier and far less error-prone to forward propagate the equations, e.g. see here and here.
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque Do you agree with my suggested choice of duplicate?
  $endgroup$
  – Jyrki Lahtonen
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  FWIW I haven't downvoted on the answers here even though I am tempted, and encourage the practice. A site this age has certainly covered all the nooks and corners of Euclid, so it behooves 20k+ users to search first. When they obviously don't, a downvote is A) a reminder, B) a gesture of strong disproval.
  $endgroup$
  – Jyrki Lahtonen
  2 days ago
  
  

  
  
  
  

 | 
show 2 more comments

$begingroup$

Here I am trying to find the multiplicative inverse of 19 respect to 29.

$$19x equiv 1 pmod29 $$

What I tried

beginalign*
29 &= 1(19) + 10\
19 &= 1(10) + 9\
10 &= 1(9) + 1.
endalign*

From backtracking, I came up with the

beginalign*
1 &= 2(29) - 3(19)\
endalign*

However, 3 is not a multiplicative inverse of the 29. Where am I making a mistake?

I looked many answers including this answer; however, couldn't figure out my mistake.

elementary-number-theory modular-arithmetic euclidean-algorithm

share|cite|improve this question

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

New contributor

Emrah Sariboz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

New contributor

Emrah Sariboz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

New contributor

Emrah Sariboz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

New contributor

Emrah Sariboz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 2 days ago

Emrah SaribozEmrah Sariboz

3833 bronze badges

3 Answers
3

active

oldest

votes

3

$begingroup$

What you have found indeed is that $-3equiv 26$ is the multiplicative inverse of $19$ $mod 29$.

share|cite|improve this answer

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Since this is the first answer, I want to give a credit to this one. I have only one question. Why $-3equiv 26$
  $endgroup$
  – Emrah Sariboz
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 Because $,29,$ divides $,-3-26 $
  $endgroup$
  – Bill Dubuque
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 Because $-3+29=26$
  $endgroup$
  – user
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  sorry still not clear. What you mean 29 divides -3?
  $endgroup$
  – Emrah Sariboz
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 $ -3-26 = -29 $ is divisible by $29. $ Recall $ aequiv bpmod n $ means $a-b$ is divisible by $n $
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  

 | 
show 2 more comments

3

$begingroup$

You're almost there! Multiply both sides by $-3$ and you have $$-57xequiv -3pmod 29\xequiv-3equiv26pmod29$$

share|cite|improve this answer

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

$endgroup$

add a comment
 | 

3

$begingroup$

Reducing your backtracking result modulo $29$, it becomes
$$
1equiv -3cdot 19pmod29
$$
Which is to say, the multiplicative inverse of $19$ is $-3$.

share|cite|improve this answer

edited 2 days ago

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is a correct explanation, so why was it downvoted?
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque The ways of the downvote fairies are ineffable. But yeah, I'm wondering that too. I mean, there are other correct answers here, but I feel my approach is at least a tiny bit distinct.
  $endgroup$
  – Arthur
  2 days ago
  

  
  
  
  

add a comment
 | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.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
);



);

Emrah Sariboz is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3390808%2feuclid-algorithm-to-find-muliplicative-inverse%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

What you have found indeed is that $-3equiv 26$ is the multiplicative inverse of $19$ $mod 29$.

share|cite|improve this answer

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Since this is the first answer, I want to give a credit to this one. I have only one question. Why $-3equiv 26$
  $endgroup$
  – Emrah Sariboz
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 Because $,29,$ divides $,-3-26 $
  $endgroup$
  – Bill Dubuque
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 Because $-3+29=26$
  $endgroup$
  – user
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  sorry still not clear. What you mean 29 divides -3?
  $endgroup$
  – Emrah Sariboz
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 $ -3-26 = -29 $ is divisible by $29. $ Recall $ aequiv bpmod n $ means $a-b$ is divisible by $n $
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  

 | 
show 2 more comments

3

$begingroup$

What you have found indeed is that $-3equiv 26$ is the multiplicative inverse of $19$ $mod 29$.

share|cite|improve this answer

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Since this is the first answer, I want to give a credit to this one. I have only one question. Why $-3equiv 26$
  $endgroup$
  – Emrah Sariboz
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 Because $,29,$ divides $,-3-26 $
  $endgroup$
  – Bill Dubuque
  2 days ago
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 Because $-3+29=26$
  $endgroup$
  – user
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  sorry still not clear. What you mean 29 divides -3?
  $endgroup$
  – Emrah Sariboz
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @user109067 $ -3-26 = -29 $ is divisible by $29. $ Recall $ aequiv bpmod n $ means $a-b$ is divisible by $n $
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  

 | 
show 2 more comments

$begingroup$

What you have found indeed is that $-3equiv 26$ is the multiplicative inverse of $19$ $mod 29$.

share|cite|improve this answer

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

$endgroup$

share|cite|improve this answer

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

answered 2 days ago

useruser

98.6k99 gold badges4747 silver badges9797 bronze badges

3

$begingroup$

You're almost there! Multiply both sides by $-3$ and you have $$-57xequiv -3pmod 29\xequiv-3equiv26pmod29$$

share|cite|improve this answer

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

$endgroup$

add a comment
 | 

3

$begingroup$

You're almost there! Multiply both sides by $-3$ and you have $$-57xequiv -3pmod 29\xequiv-3equiv26pmod29$$

share|cite|improve this answer

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

You're almost there! Multiply both sides by $-3$ and you have $$-57xequiv -3pmod 29\xequiv-3equiv26pmod29$$

share|cite|improve this answer

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

$endgroup$

share|cite|improve this answer

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

answered 2 days ago

Matthew DalyMatthew Daly

7,27511 gold badge1111 silver badges3131 bronze badges

3

$begingroup$

Reducing your backtracking result modulo $29$, it becomes
$$
1equiv -3cdot 19pmod29
$$
Which is to say, the multiplicative inverse of $19$ is $-3$.

share|cite|improve this answer

edited 2 days ago

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is a correct explanation, so why was it downvoted?
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque The ways of the downvote fairies are ineffable. But yeah, I'm wondering that too. I mean, there are other correct answers here, but I feel my approach is at least a tiny bit distinct.
  $endgroup$
  – Arthur
  2 days ago
  

  
  
  
  

add a comment
 | 

3

$begingroup$

Reducing your backtracking result modulo $29$, it becomes
$$
1equiv -3cdot 19pmod29
$$
Which is to say, the multiplicative inverse of $19$ is $-3$.

share|cite|improve this answer

edited 2 days ago

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is a correct explanation, so why was it downvoted?
  $endgroup$
  – Bill Dubuque
  2 days ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BillDubuque The ways of the downvote fairies are ineffable. But yeah, I'm wondering that too. I mean, there are other correct answers here, but I feel my approach is at least a tiny bit distinct.
  $endgroup$
  – Arthur
  2 days ago
  

  
  
  
  

add a comment
 | 

$begingroup$

Reducing your backtracking result modulo $29$, it becomes
$$
1equiv -3cdot 19pmod29
$$
Which is to say, the multiplicative inverse of $19$ is $-3$.

share|cite|improve this answer

edited 2 days ago

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges

$endgroup$

share|cite|improve this answer

edited 2 days ago

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges

answered 2 days ago

ArthurArthur

142k99 gold badges131131 silver badges229229 bronze badges