How to: $f(x)$ congruent to $a pmod{b^n}$
$begingroup$
I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class.
The specific question is solve $x^2 =-3pmod{13^3}$.
As far as I can figure out I need to let $f(x) = (x^2)+3$ and then try to solve $f(x)= 0 pmod{13^3}$. Beyond that I can't really understand what is going on.
All of the questions are of the form $f(x)= a pmod{b^n}$. I've only been able to find help on questions where $b^n$ doesn't only have one prime factor and you split the question into two or more equations and solve, and as far as I have seen solving for $x^2 = -3pmod{13^3}$ gives incorrect answers or leaves some out.
Any help would be much appreciated!
number-theory elementary-number-theory modular-arithmetic problem-solving
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
asked Dec 9 '18 at 15:52
MaxMax
31
$endgroup$
add a comment |
$begingroup$
I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class.
The specific question is solve $x^2 =-3pmod{13^3}$.
As far as I can figure out I need to let $f(x) = (x^2)+3$ and then try to solve $f(x)= 0 pmod{13^3}$. Beyond that I can't really understand what is going on.
All of the questions are of the form $f(x)= a pmod{b^n}$. I've only been able to find help on questions where $b^n$ doesn't only have one prime factor and you split the question into two or more equations and solve, and as far as I have seen solving for $x^2 = -3pmod{13^3}$ gives incorrect answers or leaves some out.
Any help would be much appreciated!
number-theory elementary-number-theory modular-arithmetic problem-solving
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
asked Dec 9 '18 at 15:52
MaxMax
31
$endgroup$
1
$begingroup$
Are you familiar with Hensel lifitng or Newton iteration?
$endgroup$
– Bill Dubuque
Dec 9 '18 at 15:54
$begingroup$
e.g. see this answer and other answers there. Search on "Hensel" for more.
$endgroup$
– Bill Dubuque
Dec 9 '18 at 16:01
add a comment |
$begingroup$
I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class.
The specific question is solve $x^2 =-3pmod{13^3}$.
As far as I can figure out I need to let $f(x) = (x^2)+3$ and then try to solve $f(x)= 0 pmod{13^3}$. Beyond that I can't really understand what is going on.
All of the questions are of the form $f(x)= a pmod{b^n}$. I've only been able to find help on questions where $b^n$ doesn't only have one prime factor and you split the question into two or more equations and solve, and as far as I have seen solving for $x^2 = -3pmod{13^3}$ gives incorrect answers or leaves some out.
Any help would be much appreciated!
number-theory elementary-number-theory modular-arithmetic problem-solving
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
asked Dec 9 '18 at 15:52
MaxMax
31
$endgroup$
I'm failing to understand the notes we've been given and have struggled to find something on the internet in the form of help. I'm currently stuck on a question for a class.
The specific question is solve $x^2 =-3pmod{13^3}$.
As far as I can figure out I need to let $f(x) = (x^2)+3$ and then try to solve $f(x)= 0 pmod{13^3}$. Beyond that I can't really understand what is going on.
All of the questions are of the form $f(x)= a pmod{b^n}$. I've only been able to find help on questions where $b^n$ doesn't only have one prime factor and you split the question into two or more equations and solve, and as far as I have seen solving for $x^2 = -3pmod{13^3}$ gives incorrect answers or leaves some out.
Any help would be much appreciated!
number-theory elementary-number-theory modular-arithmetic problem-solving
number-theory elementary-number-theory modular-arithmetic problem-solving
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
asked Dec 9 '18 at 15:52
MaxMax
31
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
asked Dec 9 '18 at 15:52
MaxMax
31
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
edited Dec 9 '18 at 16:01
Andreas Caranti
56.6k34395
56.6k34395
asked Dec 9 '18 at 15:52
MaxMax
31
asked Dec 9 '18 at 15:52
MaxMax
31
asked Dec 9 '18 at 15:52
MaxMax
31
31
1
$begingroup$
Are you familiar with Hensel lifitng or Newton iteration?
$endgroup$
– Bill Dubuque
Dec 9 '18 at 15:54
$begingroup$
e.g. see this answer and other answers there. Search on "Hensel" for more.
$endgroup$
– Bill Dubuque
Dec 9 '18 at 16:01
add a comment |
1
$begingroup$
Are you familiar with Hensel lifitng or Newton iteration?
$endgroup$
– Bill Dubuque
Dec 9 '18 at 15:54
$begingroup$
e.g. see this answer and other answers there. Search on "Hensel" for more.
$endgroup$
– Bill Dubuque
Dec 9 '18 at 16:01
1
1
$begingroup$
Are you familiar with Hensel lifitng or Newton iteration?
$endgroup$
– Bill Dubuque
Dec 9 '18 at 15:54
$begingroup$
Are you familiar with Hensel lifitng or Newton iteration?
$endgroup$
– Bill Dubuque
Dec 9 '18 at 15:54
$begingroup$
e.g. see this answer and other answers there. Search on "Hensel" for more.
$endgroup$
– Bill Dubuque
Dec 9 '18 at 16:01
$begingroup$
e.g. see this answer and other answers there. Search on "Hensel" for more.
$endgroup$
– Bill Dubuque
Dec 9 '18 at 16:01
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You must first solve the congruence $x^2equiv -3pmod{13}$. To do this note that $x_oequiv 6pmod{13}$ and $x_1equiv 7pmod{13}$ are solutions as $x_o^2=6^2=36equiv -3pmod{13}$ and $x_1^2=7^2=49equiv -3pmod{13}$. Now like you mentioned define the function $f$ such that $f(x)=x^2+3$ and $f'(x)=2x$. Note that $f'(x_o)=f'(6)=2*6=12notequiv 0 pmod{13^2}$ and $f'(x_1)=f'(7)=2*7=14notequiv 0 pmod{13^2}$. Thus by Hensel's Lemma a unique lift exists for both solutions and they are given by the formula $$x_k=x_{k-1}-f(x_{k-1})overline{f'(x_{k-1})}$$
After you find these two solutions to the congruence $x^2equiv -3pmod{13^2}$ use Hensel's Lemma again to find the solutions to $x^2equiv -3pmod{13^3}$. Hope this helps!
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
$endgroup$
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%2f3032531%2fhow-to-fx-congruent-to-a-pmodbn%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$
You must first solve the congruence $x^2equiv -3pmod{13}$. To do this note that $x_oequiv 6pmod{13}$ and $x_1equiv 7pmod{13}$ are solutions as $x_o^2=6^2=36equiv -3pmod{13}$ and $x_1^2=7^2=49equiv -3pmod{13}$. Now like you mentioned define the function $f$ such that $f(x)=x^2+3$ and $f'(x)=2x$. Note that $f'(x_o)=f'(6)=2*6=12notequiv 0 pmod{13^2}$ and $f'(x_1)=f'(7)=2*7=14notequiv 0 pmod{13^2}$. Thus by Hensel's Lemma a unique lift exists for both solutions and they are given by the formula $$x_k=x_{k-1}-f(x_{k-1})overline{f'(x_{k-1})}$$
After you find these two solutions to the congruence $x^2equiv -3pmod{13^2}$ use Hensel's Lemma again to find the solutions to $x^2equiv -3pmod{13^3}$. Hope this helps!
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
$endgroup$
add a comment |
$begingroup$
You must first solve the congruence $x^2equiv -3pmod{13}$. To do this note that $x_oequiv 6pmod{13}$ and $x_1equiv 7pmod{13}$ are solutions as $x_o^2=6^2=36equiv -3pmod{13}$ and $x_1^2=7^2=49equiv -3pmod{13}$. Now like you mentioned define the function $f$ such that $f(x)=x^2+3$ and $f'(x)=2x$. Note that $f'(x_o)=f'(6)=2*6=12notequiv 0 pmod{13^2}$ and $f'(x_1)=f'(7)=2*7=14notequiv 0 pmod{13^2}$. Thus by Hensel's Lemma a unique lift exists for both solutions and they are given by the formula $$x_k=x_{k-1}-f(x_{k-1})overline{f'(x_{k-1})}$$
After you find these two solutions to the congruence $x^2equiv -3pmod{13^2}$ use Hensel's Lemma again to find the solutions to $x^2equiv -3pmod{13^3}$. Hope this helps!
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
$endgroup$
add a comment |
$begingroup$
You must first solve the congruence $x^2equiv -3pmod{13}$. To do this note that $x_oequiv 6pmod{13}$ and $x_1equiv 7pmod{13}$ are solutions as $x_o^2=6^2=36equiv -3pmod{13}$ and $x_1^2=7^2=49equiv -3pmod{13}$. Now like you mentioned define the function $f$ such that $f(x)=x^2+3$ and $f'(x)=2x$. Note that $f'(x_o)=f'(6)=2*6=12notequiv 0 pmod{13^2}$ and $f'(x_1)=f'(7)=2*7=14notequiv 0 pmod{13^2}$. Thus by Hensel's Lemma a unique lift exists for both solutions and they are given by the formula $$x_k=x_{k-1}-f(x_{k-1})overline{f'(x_{k-1})}$$
After you find these two solutions to the congruence $x^2equiv -3pmod{13^2}$ use Hensel's Lemma again to find the solutions to $x^2equiv -3pmod{13^3}$. Hope this helps!
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
$endgroup$
You must first solve the congruence $x^2equiv -3pmod{13}$. To do this note that $x_oequiv 6pmod{13}$ and $x_1equiv 7pmod{13}$ are solutions as $x_o^2=6^2=36equiv -3pmod{13}$ and $x_1^2=7^2=49equiv -3pmod{13}$. Now like you mentioned define the function $f$ such that $f(x)=x^2+3$ and $f'(x)=2x$. Note that $f'(x_o)=f'(6)=2*6=12notequiv 0 pmod{13^2}$ and $f'(x_1)=f'(7)=2*7=14notequiv 0 pmod{13^2}$. Thus by Hensel's Lemma a unique lift exists for both solutions and they are given by the formula $$x_k=x_{k-1}-f(x_{k-1})overline{f'(x_{k-1})}$$
After you find these two solutions to the congruence $x^2equiv -3pmod{13^2}$ use Hensel's Lemma again to find the solutions to $x^2equiv -3pmod{13^3}$. Hope this helps!
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
answered Dec 10 '18 at 10:13
mjosephmjoseph
929
929
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.
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%2f3032531%2fhow-to-fx-congruent-to-a-pmodbn%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$
Are you familiar with Hensel lifitng or Newton iteration?
$endgroup$
– Bill Dubuque
Dec 9 '18 at 15:54
$begingroup$
e.g. see this answer and other answers there. Search on "Hensel" for more.
$endgroup$
– Bill Dubuque
Dec 9 '18 at 16:01