Determine whether 271 is invertible modulo 2018, and if so find an inverse a.
up vote
1
down vote
favorite
Here is the question I'd greatly appreciate help on:
(a) Use the Euclidean Algorithm to compute gcd ($2018, 271$) and use that to find integers $x$ and $y$ so that gcd ($2018, 271$) =
$2018x + 271y$.
I've done this part. gcd($2018, 271$) = $1$ = $2018 * 56 + 271 * (-417)$
$(x = 56, y = -417)$
(I will edit in all of the algorithm's steps if needed!)
I'm having trouble with part (b):
(b) Use part (a) to determine whether $271$ is invertible modulo $2018$, and if it is invertible, find an inverse a of $271$ modulo
$2018$ so that $0 < a < 2018$. Explain why your answer is an inverse of $271$ modulo $2018$ using the definition of an inverse
modulo n.
I know that $271$ is invertible modulo $2018$ if and only if there exists an integer $t$ so that $271 * t ≡ 1 (mod 2018)$, and that t is an inverse of $271$ modulo $2018$.
However, I just got this from class lecture and don't really know what this means on a conceptual level, and how to apply it to this question.
Thank you.
discrete-mathematics modular-arithmetic
edited Nov 26 at 6:37
Akash Roy
1
asked Nov 26 at 5:43
Humdrum
134
add a comment |
up vote
1
down vote
favorite
Here is the question I'd greatly appreciate help on:
(a) Use the Euclidean Algorithm to compute gcd ($2018, 271$) and use that to find integers $x$ and $y$ so that gcd ($2018, 271$) =
$2018x + 271y$.
I've done this part. gcd($2018, 271$) = $1$ = $2018 * 56 + 271 * (-417)$
$(x = 56, y = -417)$
(I will edit in all of the algorithm's steps if needed!)
I'm having trouble with part (b):
(b) Use part (a) to determine whether $271$ is invertible modulo $2018$, and if it is invertible, find an inverse a of $271$ modulo
$2018$ so that $0 < a < 2018$. Explain why your answer is an inverse of $271$ modulo $2018$ using the definition of an inverse
modulo n.
I know that $271$ is invertible modulo $2018$ if and only if there exists an integer $t$ so that $271 * t ≡ 1 (mod 2018)$, and that t is an inverse of $271$ modulo $2018$.
However, I just got this from class lecture and don't really know what this means on a conceptual level, and how to apply it to this question.
Thank you.
discrete-mathematics modular-arithmetic
edited Nov 26 at 6:37
Akash Roy
1
asked Nov 26 at 5:43
Humdrum
134
You have already worked out the $a$ you need.
– Lord Shark the Unknown
Nov 26 at 5:46
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Here is the question I'd greatly appreciate help on:
(a) Use the Euclidean Algorithm to compute gcd ($2018, 271$) and use that to find integers $x$ and $y$ so that gcd ($2018, 271$) =
$2018x + 271y$.
I've done this part. gcd($2018, 271$) = $1$ = $2018 * 56 + 271 * (-417)$
$(x = 56, y = -417)$
(I will edit in all of the algorithm's steps if needed!)
I'm having trouble with part (b):
(b) Use part (a) to determine whether $271$ is invertible modulo $2018$, and if it is invertible, find an inverse a of $271$ modulo
$2018$ so that $0 < a < 2018$. Explain why your answer is an inverse of $271$ modulo $2018$ using the definition of an inverse
modulo n.
I know that $271$ is invertible modulo $2018$ if and only if there exists an integer $t$ so that $271 * t ≡ 1 (mod 2018)$, and that t is an inverse of $271$ modulo $2018$.
However, I just got this from class lecture and don't really know what this means on a conceptual level, and how to apply it to this question.
Thank you.
discrete-mathematics modular-arithmetic
edited Nov 26 at 6:37
Akash Roy
1
asked Nov 26 at 5:43
Humdrum
134
Here is the question I'd greatly appreciate help on:
(a) Use the Euclidean Algorithm to compute gcd ($2018, 271$) and use that to find integers $x$ and $y$ so that gcd ($2018, 271$) =
$2018x + 271y$.
I've done this part. gcd($2018, 271$) = $1$ = $2018 * 56 + 271 * (-417)$
$(x = 56, y = -417)$
(I will edit in all of the algorithm's steps if needed!)
I'm having trouble with part (b):
(b) Use part (a) to determine whether $271$ is invertible modulo $2018$, and if it is invertible, find an inverse a of $271$ modulo
$2018$ so that $0 < a < 2018$. Explain why your answer is an inverse of $271$ modulo $2018$ using the definition of an inverse
modulo n.
I know that $271$ is invertible modulo $2018$ if and only if there exists an integer $t$ so that $271 * t ≡ 1 (mod 2018)$, and that t is an inverse of $271$ modulo $2018$.
However, I just got this from class lecture and don't really know what this means on a conceptual level, and how to apply it to this question.
Thank you.
discrete-mathematics modular-arithmetic
discrete-mathematics modular-arithmetic
edited Nov 26 at 6:37
Akash Roy
1
asked Nov 26 at 5:43
Humdrum
134
edited Nov 26 at 6:37
Akash Roy
1
asked Nov 26 at 5:43
Humdrum
134
edited Nov 26 at 6:37
Akash Roy
1
edited Nov 26 at 6:37
Akash Roy
1
edited Nov 26 at 6:37
Akash Roy
1
1
asked Nov 26 at 5:43
Humdrum
134
asked Nov 26 at 5:43
Humdrum
134
asked Nov 26 at 5:43
Humdrum
134
134
You have already worked out the $a$ you need.
– Lord Shark the Unknown
Nov 26 at 5:46
add a comment |
You have already worked out the $a$ you need.
– Lord Shark the Unknown
Nov 26 at 5:46
You have already worked out the $a$ you need.
– Lord Shark the Unknown
Nov 26 at 5:46
You have already worked out the $a$ you need.
– Lord Shark the Unknown
Nov 26 at 5:46
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
We have $$1=2018(56)+271(-417)$$
Hence
$$1equiv 2018(56)+271(-417) pmod{2018}$$
$$1equiv 271(-417) pmod{2018}$$
Hence $-417 equiv 2018-417pmod{2018}$ is its inverse.
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
add a comment |
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',
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%2f3013897%2fdetermine-whether-271-is-invertible-modulo-2018-and-if-so-find-an-inverse-a%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
up vote
1
down vote
We have $$1=2018(56)+271(-417)$$
Hence
$$1equiv 2018(56)+271(-417) pmod{2018}$$
$$1equiv 271(-417) pmod{2018}$$
Hence $-417 equiv 2018-417pmod{2018}$ is its inverse.
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
add a comment |
up vote
1
down vote
We have $$1=2018(56)+271(-417)$$
Hence
$$1equiv 2018(56)+271(-417) pmod{2018}$$
$$1equiv 271(-417) pmod{2018}$$
Hence $-417 equiv 2018-417pmod{2018}$ is its inverse.
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
add a comment |
up vote
1
down vote
up vote
1
down vote
We have $$1=2018(56)+271(-417)$$
Hence
$$1equiv 2018(56)+271(-417) pmod{2018}$$
$$1equiv 271(-417) pmod{2018}$$
Hence $-417 equiv 2018-417pmod{2018}$ is its inverse.
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
We have $$1=2018(56)+271(-417)$$
Hence
$$1equiv 2018(56)+271(-417) pmod{2018}$$
$$1equiv 271(-417) pmod{2018}$$
Hence $-417 equiv 2018-417pmod{2018}$ is its inverse.
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
answered Nov 26 at 5:47
Siong Thye Goh
97.4k1463116
97.4k1463116
add a comment |
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3013897%2fdetermine-whether-271-is-invertible-modulo-2018-and-if-so-find-an-inverse-a%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
You have already worked out the $a$ you need.
– Lord Shark the Unknown
Nov 26 at 5:46