Mixing
Multiplicative inverse of polynomial modulus an integer
$begingroup$
How do you calculate the multiplicative inverse of a polynomial mod a monomial/integer?The specific questions are:
Find the multiplicative inverse of
1) x+1 mod 3
2) x^2+x-1 mod 3
3) x^2+x-1 mod 32
I understand that you need to use the Extended Euclidean algorithm to solve it. For integer mod integer (e.g. 11 mod 26) and polynomial mod polynomial, its clear.But how to solve x+1 mod 3?
modular-arithmetic inverse
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
$endgroup$
add a comment |
$begingroup$
How do you calculate the multiplicative inverse of a polynomial mod a monomial/integer?The specific questions are:
Find the multiplicative inverse of
1) x+1 mod 3
2) x^2+x-1 mod 3
3) x^2+x-1 mod 32
I understand that you need to use the Extended Euclidean algorithm to solve it. For integer mod integer (e.g. 11 mod 26) and polynomial mod polynomial, its clear.But how to solve x+1 mod 3?
modular-arithmetic inverse
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
$endgroup$
add a comment |
$begingroup$
How do you calculate the multiplicative inverse of a polynomial mod a monomial/integer?The specific questions are:
Find the multiplicative inverse of
1) x+1 mod 3
2) x^2+x-1 mod 3
3) x^2+x-1 mod 32
I understand that you need to use the Extended Euclidean algorithm to solve it. For integer mod integer (e.g. 11 mod 26) and polynomial mod polynomial, its clear.But how to solve x+1 mod 3?
modular-arithmetic inverse
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
$endgroup$
How do you calculate the multiplicative inverse of a polynomial mod a monomial/integer?The specific questions are:
Find the multiplicative inverse of
1) x+1 mod 3
2) x^2+x-1 mod 3
3) x^2+x-1 mod 32
I understand that you need to use the Extended Euclidean algorithm to solve it. For integer mod integer (e.g. 11 mod 26) and polynomial mod polynomial, its clear.But how to solve x+1 mod 3?
modular-arithmetic inverse
modular-arithmetic inverse
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
asked Jul 14 '15 at 13:40
jaynjaynjaynjayn
1
1
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Neither $x+1$ nor $x^2+x-1$ are invertible modulo $3$, i.e. in the polynomial ring $mathbf Z/3mathbf Z[x]$, which is a polynomial ring over a field, because in such a case, for any polynomials $f,g$ we have $deg fg=deg f+deg g gedeg f,deg g$, which is not compatible with $fg=1$ unless $f$ and $g$ are constants.
If the quotient ring is not a field, this may not be true. However $x^2+x-1$ invertible in $ is impossible since its dominant coefficient is $1$, hence $deg f(x)(x^2+x-1)=deg f+2$.
For an example with coefficients in $mathbf Z/32mathbf Z$ you can check that $;(16x^2-4x+1)(4x+1)=1$.
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
$endgroup$
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
do you mean that for a polynomialfto have a multiplicative inversemod gthen inlinedeg fg=deg f+deg g ≥deg f,deg g? If that is the case thenx+1 mod 3meets the criteria becausedeg ((x+1)3)=1' anddeg f=1` anddeg g=0. Kindly explain
$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
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',
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%2f1360722%2fmultiplicative-inverse-of-polynomial-modulus-an-integer%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$
Neither $x+1$ nor $x^2+x-1$ are invertible modulo $3$, i.e. in the polynomial ring $mathbf Z/3mathbf Z[x]$, which is a polynomial ring over a field, because in such a case, for any polynomials $f,g$ we have $deg fg=deg f+deg g gedeg f,deg g$, which is not compatible with $fg=1$ unless $f$ and $g$ are constants.
If the quotient ring is not a field, this may not be true. However $x^2+x-1$ invertible in $ is impossible since its dominant coefficient is $1$, hence $deg f(x)(x^2+x-1)=deg f+2$.
For an example with coefficients in $mathbf Z/32mathbf Z$ you can check that $;(16x^2-4x+1)(4x+1)=1$.
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
$endgroup$
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
do you mean that for a polynomialfto have a multiplicative inversemod gthen inlinedeg fg=deg f+deg g ≥deg f,deg g? If that is the case thenx+1 mod 3meets the criteria becausedeg ((x+1)3)=1' anddeg f=1` anddeg g=0. Kindly explain
$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
add a comment |
$begingroup$
Neither $x+1$ nor $x^2+x-1$ are invertible modulo $3$, i.e. in the polynomial ring $mathbf Z/3mathbf Z[x]$, which is a polynomial ring over a field, because in such a case, for any polynomials $f,g$ we have $deg fg=deg f+deg g gedeg f,deg g$, which is not compatible with $fg=1$ unless $f$ and $g$ are constants.
If the quotient ring is not a field, this may not be true. However $x^2+x-1$ invertible in $ is impossible since its dominant coefficient is $1$, hence $deg f(x)(x^2+x-1)=deg f+2$.
For an example with coefficients in $mathbf Z/32mathbf Z$ you can check that $;(16x^2-4x+1)(4x+1)=1$.
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
$endgroup$
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
do you mean that for a polynomialfto have a multiplicative inversemod gthen inlinedeg fg=deg f+deg g ≥deg f,deg g? If that is the case thenx+1 mod 3meets the criteria becausedeg ((x+1)3)=1' anddeg f=1` anddeg g=0. Kindly explain
$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
add a comment |
$begingroup$
Neither $x+1$ nor $x^2+x-1$ are invertible modulo $3$, i.e. in the polynomial ring $mathbf Z/3mathbf Z[x]$, which is a polynomial ring over a field, because in such a case, for any polynomials $f,g$ we have $deg fg=deg f+deg g gedeg f,deg g$, which is not compatible with $fg=1$ unless $f$ and $g$ are constants.
If the quotient ring is not a field, this may not be true. However $x^2+x-1$ invertible in $ is impossible since its dominant coefficient is $1$, hence $deg f(x)(x^2+x-1)=deg f+2$.
For an example with coefficients in $mathbf Z/32mathbf Z$ you can check that $;(16x^2-4x+1)(4x+1)=1$.
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
$endgroup$
Neither $x+1$ nor $x^2+x-1$ are invertible modulo $3$, i.e. in the polynomial ring $mathbf Z/3mathbf Z[x]$, which is a polynomial ring over a field, because in such a case, for any polynomials $f,g$ we have $deg fg=deg f+deg g gedeg f,deg g$, which is not compatible with $fg=1$ unless $f$ and $g$ are constants.
If the quotient ring is not a field, this may not be true. However $x^2+x-1$ invertible in $ is impossible since its dominant coefficient is $1$, hence $deg f(x)(x^2+x-1)=deg f+2$.
For an example with coefficients in $mathbf Z/32mathbf Z$ you can check that $;(16x^2-4x+1)(4x+1)=1$.
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
answered Jul 14 '15 at 14:13
BernardBernard
122k741116
122k741116
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
do you mean that for a polynomialfto have a multiplicative inversemod gthen inlinedeg fg=deg f+deg g ≥deg f,deg g? If that is the case thenx+1 mod 3meets the criteria becausedeg ((x+1)3)=1' anddeg f=1` anddeg g=0. Kindly explain
$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
add a comment |
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
do you mean that for a polynomialfto have a multiplicative inversemod gthen inlinedeg fg=deg f+deg g ≥deg f,deg g? If that is the case thenx+1 mod 3meets the criteria becausedeg ((x+1)3)=1' anddeg f=1` anddeg g=0. Kindly explain
$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
Thank you for the response.
$endgroup$
– jaynjayn
Jul 14 '15 at 16:06
$begingroup$
do you mean that for a polynomial
f to have a multiplicative inverse mod g then inlinedeg fg=deg f+deg g ≥deg f,deg g ? If that is the case then x+1 mod 3 meets the criteria because deg ((x+1)3)=1' and deg f=1` and deg g=0 . Kindly explain$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
do you mean that for a polynomial
f to have a multiplicative inverse mod g then inlinedeg fg=deg f+deg g ≥deg f,deg g ? If that is the case then x+1 mod 3 meets the criteria because deg ((x+1)3)=1' and deg f=1` and deg g=0 . Kindly explain$endgroup$
– jaynjayn
Jul 15 '15 at 7:03
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
$begingroup$
If $fg=1$, we must have $deg f+deg g=deg 1=0$, whence $deg f=deg g=0$, i. e. $f$ and $g$ must be non-zero constants.
$endgroup$
– Bernard
Jul 15 '15 at 7:29
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.
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%2f1360722%2fmultiplicative-inverse-of-polynomial-modulus-an-integer%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
