'Gauss's Algorithm' for computing modular fractions and inverses
$begingroup$
There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the fractional form is essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801.
Now I have studied the article from the book, but I am not seeing the connection to the fractional form. What Gauss does is reducing $b$ via $p$ mod $b = p - qb$ and I do not see that happening in the fractional form nor do I see how it computes an inverse. I have already talked with Bill about this via comments, but decided to open a new question so he or anyone else can help me more intuitively understand what is going on here. This article is supposed to give an algorithm to compute inverses in a prime modulus, yet I have no idea how.
Edit:
Bill when you see this(I know you will :) ) please try to do this very detailed explaining everything. I am very new to number theory and there might be others so we thoroughly understand what exactly goes on here.
elementary-number-theory
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
$endgroup$
add a comment |
$begingroup$
There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the fractional form is essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801.
Now I have studied the article from the book, but I am not seeing the connection to the fractional form. What Gauss does is reducing $b$ via $p$ mod $b = p - qb$ and I do not see that happening in the fractional form nor do I see how it computes an inverse. I have already talked with Bill about this via comments, but decided to open a new question so he or anyone else can help me more intuitively understand what is going on here. This article is supposed to give an algorithm to compute inverses in a prime modulus, yet I have no idea how.
Edit:
Bill when you see this(I know you will :) ) please try to do this very detailed explaining everything. I am very new to number theory and there might be others so we thoroughly understand what exactly goes on here.
elementary-number-theory
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
$endgroup$
1
$begingroup$
I will answer later when I have more spare time. Others who may be interested in answering can learn the detailed context from the "via comments" link above.
$endgroup$
– Bill Dubuque
Jan 2 at 17:02
$begingroup$
Ok, though it might be best that you do it. You named the algorithm after all.
$endgroup$
– Michael Munta
Jan 3 at 9:57
$begingroup$
If you could do it this weekend please, I am really anxious to understand this :)
$endgroup$
– Michael Munta
Jan 4 at 10:25
add a comment |
$begingroup$
There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the fractional form is essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801.
Now I have studied the article from the book, but I am not seeing the connection to the fractional form. What Gauss does is reducing $b$ via $p$ mod $b = p - qb$ and I do not see that happening in the fractional form nor do I see how it computes an inverse. I have already talked with Bill about this via comments, but decided to open a new question so he or anyone else can help me more intuitively understand what is going on here. This article is supposed to give an algorithm to compute inverses in a prime modulus, yet I have no idea how.
Edit:
Bill when you see this(I know you will :) ) please try to do this very detailed explaining everything. I am very new to number theory and there might be others so we thoroughly understand what exactly goes on here.
elementary-number-theory
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
$endgroup$
There is an answer on the site for solving simple linear congruences via so called 'Gauss's Algorithm' presented in a fractional form. Answer was given by Bill Dubuque and it was said that the fractional form is essentially Gauss, Disquisitiones Arithmeticae, Art. 13, 1801.
Now I have studied the article from the book, but I am not seeing the connection to the fractional form. What Gauss does is reducing $b$ via $p$ mod $b = p - qb$ and I do not see that happening in the fractional form nor do I see how it computes an inverse. I have already talked with Bill about this via comments, but decided to open a new question so he or anyone else can help me more intuitively understand what is going on here. This article is supposed to give an algorithm to compute inverses in a prime modulus, yet I have no idea how.
Edit:
Bill when you see this(I know you will :) ) please try to do this very detailed explaining everything. I am very new to number theory and there might be others so we thoroughly understand what exactly goes on here.
elementary-number-theory
elementary-number-theory
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
edited Jan 2 at 17:01
Bill Dubuque
209k29191639
209k29191639
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
asked Jan 2 at 9:05
Michael MuntaMichael Munta
808
808
1
$begingroup$
I will answer later when I have more spare time. Others who may be interested in answering can learn the detailed context from the "via comments" link above.
$endgroup$
– Bill Dubuque
Jan 2 at 17:02
$begingroup$
Ok, though it might be best that you do it. You named the algorithm after all.
$endgroup$
– Michael Munta
Jan 3 at 9:57
$begingroup$
If you could do it this weekend please, I am really anxious to understand this :)
$endgroup$
– Michael Munta
Jan 4 at 10:25
add a comment |
1
$begingroup$
I will answer later when I have more spare time. Others who may be interested in answering can learn the detailed context from the "via comments" link above.
$endgroup$
– Bill Dubuque
Jan 2 at 17:02
$begingroup$
Ok, though it might be best that you do it. You named the algorithm after all.
$endgroup$
– Michael Munta
Jan 3 at 9:57
$begingroup$
If you could do it this weekend please, I am really anxious to understand this :)
$endgroup$
– Michael Munta
Jan 4 at 10:25
1
1
$begingroup$
I will answer later when I have more spare time. Others who may be interested in answering can learn the detailed context from the "via comments" link above.
$endgroup$
– Bill Dubuque
Jan 2 at 17:02
$begingroup$
I will answer later when I have more spare time. Others who may be interested in answering can learn the detailed context from the "via comments" link above.
$endgroup$
– Bill Dubuque
Jan 2 at 17:02
$begingroup$
Ok, though it might be best that you do it. You named the algorithm after all.
$endgroup$
– Michael Munta
Jan 3 at 9:57
$begingroup$
Ok, though it might be best that you do it. You named the algorithm after all.
$endgroup$
– Michael Munta
Jan 3 at 9:57
$begingroup$
If you could do it this weekend please, I am really anxious to understand this :)
$endgroup$
– Michael Munta
Jan 4 at 10:25
$begingroup$
If you could do it this weekend please, I am really anxious to understand this :)
$endgroup$
– Michael Munta
Jan 4 at 10:25
add a comment |
0
active
oldest
votes
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%2f3059260%2fgausss-algorithm-for-computing-modular-fractions-and-inverses%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3059260%2fgausss-algorithm-for-computing-modular-fractions-and-inverses%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I will answer later when I have more spare time. Others who may be interested in answering can learn the detailed context from the "via comments" link above.
$endgroup$
– Bill Dubuque
Jan 2 at 17:02
$begingroup$
Ok, though it might be best that you do it. You named the algorithm after all.
$endgroup$
– Michael Munta
Jan 3 at 9:57
$begingroup$
If you could do it this weekend please, I am really anxious to understand this :)
$endgroup$
– Michael Munta
Jan 4 at 10:25