Modular Arithmetic: solving a quadratic equation with a variable in the modulus












0












$begingroup$


I am not an expert on modulus arithmetic and I am computer scientist looking to see if there is a better way to solve an equation in the form of



$$(x^2 + 43) mod (44-2x)=0$$



I am currently doing a linear search, I have other equations I am trying to solve other equations that are similar, but the search is becoming inefficient for large values. Any help would be appreciated.



The solutions to this equations are



$$x = -9,5,21,23$$










share|cite|improve this question











$endgroup$












  • $begingroup$
    Have you found any $x$ satisfying this so far?
    $endgroup$
    – ÍgjøgnumMeg
    Dec 29 '18 at 3:14










  • $begingroup$
    As a start, note that if $x$ is even, then $x^2+43$ is always odd and $44-2x$ is always even, and there is no multiple of an even number that results in an odd number, i.e. leaving a residue of $0$.
    $endgroup$
    – Keith Backman
    Dec 29 '18 at 3:15
















0












$begingroup$


I am not an expert on modulus arithmetic and I am computer scientist looking to see if there is a better way to solve an equation in the form of



$$(x^2 + 43) mod (44-2x)=0$$



I am currently doing a linear search, I have other equations I am trying to solve other equations that are similar, but the search is becoming inefficient for large values. Any help would be appreciated.



The solutions to this equations are



$$x = -9,5,21,23$$










share|cite|improve this question











$endgroup$












  • $begingroup$
    Have you found any $x$ satisfying this so far?
    $endgroup$
    – ÍgjøgnumMeg
    Dec 29 '18 at 3:14










  • $begingroup$
    As a start, note that if $x$ is even, then $x^2+43$ is always odd and $44-2x$ is always even, and there is no multiple of an even number that results in an odd number, i.e. leaving a residue of $0$.
    $endgroup$
    – Keith Backman
    Dec 29 '18 at 3:15














0












0








0





$begingroup$


I am not an expert on modulus arithmetic and I am computer scientist looking to see if there is a better way to solve an equation in the form of



$$(x^2 + 43) mod (44-2x)=0$$



I am currently doing a linear search, I have other equations I am trying to solve other equations that are similar, but the search is becoming inefficient for large values. Any help would be appreciated.



The solutions to this equations are



$$x = -9,5,21,23$$










share|cite|improve this question











$endgroup$




I am not an expert on modulus arithmetic and I am computer scientist looking to see if there is a better way to solve an equation in the form of



$$(x^2 + 43) mod (44-2x)=0$$



I am currently doing a linear search, I have other equations I am trying to solve other equations that are similar, but the search is becoming inefficient for large values. Any help would be appreciated.



The solutions to this equations are



$$x = -9,5,21,23$$







elementary-number-theory modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 29 '18 at 13:34









Moo

5,63131020




5,63131020










asked Dec 29 '18 at 2:59









Ryan ToppsRyan Topps

124




124












  • $begingroup$
    Have you found any $x$ satisfying this so far?
    $endgroup$
    – ÍgjøgnumMeg
    Dec 29 '18 at 3:14










  • $begingroup$
    As a start, note that if $x$ is even, then $x^2+43$ is always odd and $44-2x$ is always even, and there is no multiple of an even number that results in an odd number, i.e. leaving a residue of $0$.
    $endgroup$
    – Keith Backman
    Dec 29 '18 at 3:15


















  • $begingroup$
    Have you found any $x$ satisfying this so far?
    $endgroup$
    – ÍgjøgnumMeg
    Dec 29 '18 at 3:14










  • $begingroup$
    As a start, note that if $x$ is even, then $x^2+43$ is always odd and $44-2x$ is always even, and there is no multiple of an even number that results in an odd number, i.e. leaving a residue of $0$.
    $endgroup$
    – Keith Backman
    Dec 29 '18 at 3:15
















$begingroup$
Have you found any $x$ satisfying this so far?
$endgroup$
– ÍgjøgnumMeg
Dec 29 '18 at 3:14




$begingroup$
Have you found any $x$ satisfying this so far?
$endgroup$
– ÍgjøgnumMeg
Dec 29 '18 at 3:14












$begingroup$
As a start, note that if $x$ is even, then $x^2+43$ is always odd and $44-2x$ is always even, and there is no multiple of an even number that results in an odd number, i.e. leaving a residue of $0$.
$endgroup$
– Keith Backman
Dec 29 '18 at 3:15




$begingroup$
As a start, note that if $x$ is even, then $x^2+43$ is always odd and $44-2x$ is always even, and there is no multiple of an even number that results in an odd number, i.e. leaving a residue of $0$.
$endgroup$
– Keith Backman
Dec 29 '18 at 3:15










4 Answers
4






active

oldest

votes


















0












$begingroup$

I assume that you're looking to solve the equation over the integers.



First notice that when $x$ is even, then $x^2+43$ is odd, but the modulus is even. (The modulus is always even.) Therefore in order for $x$ to be a solution, $x$ must be odd. Let $x=2k+1$ then, for some integer $k$. Let's see if that simplifies things.



We now have
$$4k^2+4k+44 equiv 0 pmod{2(2k-21)}.$$



Cancelling a $2$ from the equation and the modulus at the same time, we now have
$$2k^2+2k+22 equiv 0 pmod{2k-21},$$
which is much nicer.



The reason it's much nicer is that $2k-21$ has leading coefficient 2, which divides the leading coefficient of $2k^2+2k+22$. Thus, we can subtract the equation $(2k-21)k=2k^2-21kequiv 0$ to get
$$23k + 22 equiv 0 pmod{2k-21},$$
and now we can subtract $11(2k-21)= 22k-231equiv 0$
to get the equation
$$k+253equiv 0 pmod{2k-21}.$$



Now we rewrite this. We want to find for which $k$ there exist $q$ such that $k+253 = q(2k-21)$.



Rearranging, we have $(2q-1)k = 253+21q$



Thus, $k$ is a solution if and only if $k$ can be written as $frac{21q+253}{2q-1}=10+frac{q+263}{2q-1}$.



Thus we have reduced the question to figuring out when $frac{q+263}{2q-1}$ is an integer.



This is kind of a pain, so let's solve the much easier question of when it is an integer or a half integer, which we can solve by noting that in that case,
$$frac{2(q+263)}{2q-1}=frac{2q+526}{2q-1}=1+frac{527}{2q-1}$$ will be an integer. Thus $2q-1$ will be a factor of $527$.



Note that $527$ is odd, so that $527/(2q-1)$ will always be odd, so that the resulting integer will always be even. This means that no value of $q$ gave a half integer solution, so every possible value of $q$ gives a value of $x$.
The factors of 527 are $pm 1$,$pm 17$,$pm 31$, and $pm 527$,
corresponding to values for $q$ of $1,0,9,-8,16,-15$, $264$, and $-263$.



These give values of $k$ of $11,10,19,2,26,-5,274$, and $-253$.
Thus we get solutions for $x$ of $23,21,39,5,53,-9,549$, and $-505$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
    $endgroup$
    – Ryan Topps
    Dec 29 '18 at 4:07










  • $begingroup$
    @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
    $endgroup$
    – jgon
    Dec 29 '18 at 4:10










  • $begingroup$
    I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
    $endgroup$
    – Ryan Topps
    Dec 29 '18 at 4:21










  • $begingroup$
    @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
    $endgroup$
    – Bill Dubuque
    Dec 29 '18 at 5:28



















1












$begingroup$

Hint $, x!-!22mid x^2!+!43-(x!-!22)(x!+!22) = 527= 17cdot 31,$ so $,x, =, 22pm{1,17,31,527}$






share|cite|improve this answer











$endgroup$





















    0












    $begingroup$

    For $x=21$, $44-2x=2$ and the residue of any even number is $0mod 2$.



    $21^2+43$ is even.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Yes I am was more concerned with finding the x values of -9,5,21,23
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 3:26












    • $begingroup$
      The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
      $endgroup$
      – Keith Backman
      Dec 29 '18 at 3:38



















    0












    $begingroup$

    Note that if



    $$x^2 + 43 equiv 0 pmod{44 - 2x} tag{1}label{eq1}$$



    then multiplying by $-2$ gives



    $$-2x^2 - 86 equiv 0 pmod{44 - 2x} tag{2}label{eq2}$$



    Also, dividing $44 - 2x$ into $-2x^2 - 86$ gives



    $$-2x^2 - 86 = left(x + 22right) left(44 - 2xright) - 1054 tag{3}label{eq3}$$



    Thus, your original equation can be simplified to just look for cases where



    $$-1054 equiv 0 pmod{44 - 2x} tag{4}label{eq4}$$



    As such, you only need to check cases where $44 - 2x$ is a factor of $1054 = 2 * 31 * 17$, in particular, $pm 1, pm 2, pm 31, pm 17, pm 62, pm 34, pm 527, pm 1054$. For each value $n$ among these factors, you can then solve for $x$ by using $x = 22 - frac{n}{2}$. As such, for integral values of $x$, the factor must be even, giving the results of $x = 21, 23, -9, 53, 5, 39, -505, 549$.



    Also, if you wish to avoid using negative modulus values, then you need to have $44 - 2x gt 0$, so $x lt 22$, giving the results of just $x = -505, -9, 5, 21$.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 3:45












    • $begingroup$
      @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
      $endgroup$
      – John Omielan
      Dec 29 '18 at 3:49










    • $begingroup$
      I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 3:56










    • $begingroup$
      @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
      $endgroup$
      – John Omielan
      Dec 29 '18 at 3:57











    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
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3055496%2fmodular-arithmetic-solving-a-quadratic-equation-with-a-variable-in-the-modulus%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    4 Answers
    4






    active

    oldest

    votes








    4 Answers
    4






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    I assume that you're looking to solve the equation over the integers.



    First notice that when $x$ is even, then $x^2+43$ is odd, but the modulus is even. (The modulus is always even.) Therefore in order for $x$ to be a solution, $x$ must be odd. Let $x=2k+1$ then, for some integer $k$. Let's see if that simplifies things.



    We now have
    $$4k^2+4k+44 equiv 0 pmod{2(2k-21)}.$$



    Cancelling a $2$ from the equation and the modulus at the same time, we now have
    $$2k^2+2k+22 equiv 0 pmod{2k-21},$$
    which is much nicer.



    The reason it's much nicer is that $2k-21$ has leading coefficient 2, which divides the leading coefficient of $2k^2+2k+22$. Thus, we can subtract the equation $(2k-21)k=2k^2-21kequiv 0$ to get
    $$23k + 22 equiv 0 pmod{2k-21},$$
    and now we can subtract $11(2k-21)= 22k-231equiv 0$
    to get the equation
    $$k+253equiv 0 pmod{2k-21}.$$



    Now we rewrite this. We want to find for which $k$ there exist $q$ such that $k+253 = q(2k-21)$.



    Rearranging, we have $(2q-1)k = 253+21q$



    Thus, $k$ is a solution if and only if $k$ can be written as $frac{21q+253}{2q-1}=10+frac{q+263}{2q-1}$.



    Thus we have reduced the question to figuring out when $frac{q+263}{2q-1}$ is an integer.



    This is kind of a pain, so let's solve the much easier question of when it is an integer or a half integer, which we can solve by noting that in that case,
    $$frac{2(q+263)}{2q-1}=frac{2q+526}{2q-1}=1+frac{527}{2q-1}$$ will be an integer. Thus $2q-1$ will be a factor of $527$.



    Note that $527$ is odd, so that $527/(2q-1)$ will always be odd, so that the resulting integer will always be even. This means that no value of $q$ gave a half integer solution, so every possible value of $q$ gives a value of $x$.
    The factors of 527 are $pm 1$,$pm 17$,$pm 31$, and $pm 527$,
    corresponding to values for $q$ of $1,0,9,-8,16,-15$, $264$, and $-263$.



    These give values of $k$ of $11,10,19,2,26,-5,274$, and $-253$.
    Thus we get solutions for $x$ of $23,21,39,5,53,-9,549$, and $-505$.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:07










    • $begingroup$
      @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
      $endgroup$
      – jgon
      Dec 29 '18 at 4:10










    • $begingroup$
      I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:21










    • $begingroup$
      @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
      $endgroup$
      – Bill Dubuque
      Dec 29 '18 at 5:28
















    0












    $begingroup$

    I assume that you're looking to solve the equation over the integers.



    First notice that when $x$ is even, then $x^2+43$ is odd, but the modulus is even. (The modulus is always even.) Therefore in order for $x$ to be a solution, $x$ must be odd. Let $x=2k+1$ then, for some integer $k$. Let's see if that simplifies things.



    We now have
    $$4k^2+4k+44 equiv 0 pmod{2(2k-21)}.$$



    Cancelling a $2$ from the equation and the modulus at the same time, we now have
    $$2k^2+2k+22 equiv 0 pmod{2k-21},$$
    which is much nicer.



    The reason it's much nicer is that $2k-21$ has leading coefficient 2, which divides the leading coefficient of $2k^2+2k+22$. Thus, we can subtract the equation $(2k-21)k=2k^2-21kequiv 0$ to get
    $$23k + 22 equiv 0 pmod{2k-21},$$
    and now we can subtract $11(2k-21)= 22k-231equiv 0$
    to get the equation
    $$k+253equiv 0 pmod{2k-21}.$$



    Now we rewrite this. We want to find for which $k$ there exist $q$ such that $k+253 = q(2k-21)$.



    Rearranging, we have $(2q-1)k = 253+21q$



    Thus, $k$ is a solution if and only if $k$ can be written as $frac{21q+253}{2q-1}=10+frac{q+263}{2q-1}$.



    Thus we have reduced the question to figuring out when $frac{q+263}{2q-1}$ is an integer.



    This is kind of a pain, so let's solve the much easier question of when it is an integer or a half integer, which we can solve by noting that in that case,
    $$frac{2(q+263)}{2q-1}=frac{2q+526}{2q-1}=1+frac{527}{2q-1}$$ will be an integer. Thus $2q-1$ will be a factor of $527$.



    Note that $527$ is odd, so that $527/(2q-1)$ will always be odd, so that the resulting integer will always be even. This means that no value of $q$ gave a half integer solution, so every possible value of $q$ gives a value of $x$.
    The factors of 527 are $pm 1$,$pm 17$,$pm 31$, and $pm 527$,
    corresponding to values for $q$ of $1,0,9,-8,16,-15$, $264$, and $-263$.



    These give values of $k$ of $11,10,19,2,26,-5,274$, and $-253$.
    Thus we get solutions for $x$ of $23,21,39,5,53,-9,549$, and $-505$.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:07










    • $begingroup$
      @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
      $endgroup$
      – jgon
      Dec 29 '18 at 4:10










    • $begingroup$
      I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:21










    • $begingroup$
      @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
      $endgroup$
      – Bill Dubuque
      Dec 29 '18 at 5:28














    0












    0








    0





    $begingroup$

    I assume that you're looking to solve the equation over the integers.



    First notice that when $x$ is even, then $x^2+43$ is odd, but the modulus is even. (The modulus is always even.) Therefore in order for $x$ to be a solution, $x$ must be odd. Let $x=2k+1$ then, for some integer $k$. Let's see if that simplifies things.



    We now have
    $$4k^2+4k+44 equiv 0 pmod{2(2k-21)}.$$



    Cancelling a $2$ from the equation and the modulus at the same time, we now have
    $$2k^2+2k+22 equiv 0 pmod{2k-21},$$
    which is much nicer.



    The reason it's much nicer is that $2k-21$ has leading coefficient 2, which divides the leading coefficient of $2k^2+2k+22$. Thus, we can subtract the equation $(2k-21)k=2k^2-21kequiv 0$ to get
    $$23k + 22 equiv 0 pmod{2k-21},$$
    and now we can subtract $11(2k-21)= 22k-231equiv 0$
    to get the equation
    $$k+253equiv 0 pmod{2k-21}.$$



    Now we rewrite this. We want to find for which $k$ there exist $q$ such that $k+253 = q(2k-21)$.



    Rearranging, we have $(2q-1)k = 253+21q$



    Thus, $k$ is a solution if and only if $k$ can be written as $frac{21q+253}{2q-1}=10+frac{q+263}{2q-1}$.



    Thus we have reduced the question to figuring out when $frac{q+263}{2q-1}$ is an integer.



    This is kind of a pain, so let's solve the much easier question of when it is an integer or a half integer, which we can solve by noting that in that case,
    $$frac{2(q+263)}{2q-1}=frac{2q+526}{2q-1}=1+frac{527}{2q-1}$$ will be an integer. Thus $2q-1$ will be a factor of $527$.



    Note that $527$ is odd, so that $527/(2q-1)$ will always be odd, so that the resulting integer will always be even. This means that no value of $q$ gave a half integer solution, so every possible value of $q$ gives a value of $x$.
    The factors of 527 are $pm 1$,$pm 17$,$pm 31$, and $pm 527$,
    corresponding to values for $q$ of $1,0,9,-8,16,-15$, $264$, and $-263$.



    These give values of $k$ of $11,10,19,2,26,-5,274$, and $-253$.
    Thus we get solutions for $x$ of $23,21,39,5,53,-9,549$, and $-505$.






    share|cite|improve this answer









    $endgroup$



    I assume that you're looking to solve the equation over the integers.



    First notice that when $x$ is even, then $x^2+43$ is odd, but the modulus is even. (The modulus is always even.) Therefore in order for $x$ to be a solution, $x$ must be odd. Let $x=2k+1$ then, for some integer $k$. Let's see if that simplifies things.



    We now have
    $$4k^2+4k+44 equiv 0 pmod{2(2k-21)}.$$



    Cancelling a $2$ from the equation and the modulus at the same time, we now have
    $$2k^2+2k+22 equiv 0 pmod{2k-21},$$
    which is much nicer.



    The reason it's much nicer is that $2k-21$ has leading coefficient 2, which divides the leading coefficient of $2k^2+2k+22$. Thus, we can subtract the equation $(2k-21)k=2k^2-21kequiv 0$ to get
    $$23k + 22 equiv 0 pmod{2k-21},$$
    and now we can subtract $11(2k-21)= 22k-231equiv 0$
    to get the equation
    $$k+253equiv 0 pmod{2k-21}.$$



    Now we rewrite this. We want to find for which $k$ there exist $q$ such that $k+253 = q(2k-21)$.



    Rearranging, we have $(2q-1)k = 253+21q$



    Thus, $k$ is a solution if and only if $k$ can be written as $frac{21q+253}{2q-1}=10+frac{q+263}{2q-1}$.



    Thus we have reduced the question to figuring out when $frac{q+263}{2q-1}$ is an integer.



    This is kind of a pain, so let's solve the much easier question of when it is an integer or a half integer, which we can solve by noting that in that case,
    $$frac{2(q+263)}{2q-1}=frac{2q+526}{2q-1}=1+frac{527}{2q-1}$$ will be an integer. Thus $2q-1$ will be a factor of $527$.



    Note that $527$ is odd, so that $527/(2q-1)$ will always be odd, so that the resulting integer will always be even. This means that no value of $q$ gave a half integer solution, so every possible value of $q$ gives a value of $x$.
    The factors of 527 are $pm 1$,$pm 17$,$pm 31$, and $pm 527$,
    corresponding to values for $q$ of $1,0,9,-8,16,-15$, $264$, and $-263$.



    These give values of $k$ of $11,10,19,2,26,-5,274$, and $-253$.
    Thus we get solutions for $x$ of $23,21,39,5,53,-9,549$, and $-505$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Dec 29 '18 at 3:53









    jgonjgon

    15.7k32143




    15.7k32143












    • $begingroup$
      Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:07










    • $begingroup$
      @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
      $endgroup$
      – jgon
      Dec 29 '18 at 4:10










    • $begingroup$
      I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:21










    • $begingroup$
      @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
      $endgroup$
      – Bill Dubuque
      Dec 29 '18 at 5:28


















    • $begingroup$
      Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:07










    • $begingroup$
      @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
      $endgroup$
      – jgon
      Dec 29 '18 at 4:10










    • $begingroup$
      I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
      $endgroup$
      – Ryan Topps
      Dec 29 '18 at 4:21










    • $begingroup$
      @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
      $endgroup$
      – Bill Dubuque
      Dec 29 '18 at 5:28
















    $begingroup$
    Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
    $endgroup$
    – Ryan Topps
    Dec 29 '18 at 4:07




    $begingroup$
    Could explain where you get the form for the k solutions as $21q+2532/q−1=10+q+2632/q−1$
    $endgroup$
    – Ryan Topps
    Dec 29 '18 at 4:07












    $begingroup$
    @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
    $endgroup$
    – jgon
    Dec 29 '18 at 4:10




    $begingroup$
    @RyanTopps, to get the first thing, I took the equation on the line above and divided by $2q-1$, then I simplified by doing polynomial long division of the numerator by the denominator. Try finding a common denominator on the right hand side to check that the lhs and rhs are equal.
    $endgroup$
    – jgon
    Dec 29 '18 at 4:10












    $begingroup$
    I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
    $endgroup$
    – Ryan Topps
    Dec 29 '18 at 4:21




    $begingroup$
    I appreciate the effort. Unfortunately getting prime factors will be even harder than a search at large values, but your replacements showed me how to scan more effectively so thank you.
    $endgroup$
    – Ryan Topps
    Dec 29 '18 at 4:21












    $begingroup$
    @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
    $endgroup$
    – Bill Dubuque
    Dec 29 '18 at 5:28




    $begingroup$
    @Ryan Prime factorization is required to solve such problems, but we can do the rest more quickly - see my answer.
    $endgroup$
    – Bill Dubuque
    Dec 29 '18 at 5:28











    1












    $begingroup$

    Hint $, x!-!22mid x^2!+!43-(x!-!22)(x!+!22) = 527= 17cdot 31,$ so $,x, =, 22pm{1,17,31,527}$






    share|cite|improve this answer











    $endgroup$


















      1












      $begingroup$

      Hint $, x!-!22mid x^2!+!43-(x!-!22)(x!+!22) = 527= 17cdot 31,$ so $,x, =, 22pm{1,17,31,527}$






      share|cite|improve this answer











      $endgroup$
















        1












        1








        1





        $begingroup$

        Hint $, x!-!22mid x^2!+!43-(x!-!22)(x!+!22) = 527= 17cdot 31,$ so $,x, =, 22pm{1,17,31,527}$






        share|cite|improve this answer











        $endgroup$



        Hint $, x!-!22mid x^2!+!43-(x!-!22)(x!+!22) = 527= 17cdot 31,$ so $,x, =, 22pm{1,17,31,527}$







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 29 '18 at 5:10

























        answered Dec 29 '18 at 5:02









        Bill DubuqueBill Dubuque

        212k29195654




        212k29195654























            0












            $begingroup$

            For $x=21$, $44-2x=2$ and the residue of any even number is $0mod 2$.



            $21^2+43$ is even.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Yes I am was more concerned with finding the x values of -9,5,21,23
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:26












            • $begingroup$
              The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
              $endgroup$
              – Keith Backman
              Dec 29 '18 at 3:38
















            0












            $begingroup$

            For $x=21$, $44-2x=2$ and the residue of any even number is $0mod 2$.



            $21^2+43$ is even.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Yes I am was more concerned with finding the x values of -9,5,21,23
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:26












            • $begingroup$
              The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
              $endgroup$
              – Keith Backman
              Dec 29 '18 at 3:38














            0












            0








            0





            $begingroup$

            For $x=21$, $44-2x=2$ and the residue of any even number is $0mod 2$.



            $21^2+43$ is even.






            share|cite|improve this answer









            $endgroup$



            For $x=21$, $44-2x=2$ and the residue of any even number is $0mod 2$.



            $21^2+43$ is even.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Dec 29 '18 at 3:20









            Keith BackmanKeith Backman

            1,4741812




            1,4741812












            • $begingroup$
              Yes I am was more concerned with finding the x values of -9,5,21,23
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:26












            • $begingroup$
              The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
              $endgroup$
              – Keith Backman
              Dec 29 '18 at 3:38


















            • $begingroup$
              Yes I am was more concerned with finding the x values of -9,5,21,23
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:26












            • $begingroup$
              The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
              $endgroup$
              – Keith Backman
              Dec 29 '18 at 3:38
















            $begingroup$
            Yes I am was more concerned with finding the x values of -9,5,21,23
            $endgroup$
            – Ryan Topps
            Dec 29 '18 at 3:26






            $begingroup$
            Yes I am was more concerned with finding the x values of -9,5,21,23
            $endgroup$
            – Ryan Topps
            Dec 29 '18 at 3:26














            $begingroup$
            The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
            $endgroup$
            – Keith Backman
            Dec 29 '18 at 3:38




            $begingroup$
            The value $23$ results in a negative modulus $(-2)$ which is a highly unusual usage.
            $endgroup$
            – Keith Backman
            Dec 29 '18 at 3:38











            0












            $begingroup$

            Note that if



            $$x^2 + 43 equiv 0 pmod{44 - 2x} tag{1}label{eq1}$$



            then multiplying by $-2$ gives



            $$-2x^2 - 86 equiv 0 pmod{44 - 2x} tag{2}label{eq2}$$



            Also, dividing $44 - 2x$ into $-2x^2 - 86$ gives



            $$-2x^2 - 86 = left(x + 22right) left(44 - 2xright) - 1054 tag{3}label{eq3}$$



            Thus, your original equation can be simplified to just look for cases where



            $$-1054 equiv 0 pmod{44 - 2x} tag{4}label{eq4}$$



            As such, you only need to check cases where $44 - 2x$ is a factor of $1054 = 2 * 31 * 17$, in particular, $pm 1, pm 2, pm 31, pm 17, pm 62, pm 34, pm 527, pm 1054$. For each value $n$ among these factors, you can then solve for $x$ by using $x = 22 - frac{n}{2}$. As such, for integral values of $x$, the factor must be even, giving the results of $x = 21, 23, -9, 53, 5, 39, -505, 549$.



            Also, if you wish to avoid using negative modulus values, then you need to have $44 - 2x gt 0$, so $x lt 22$, giving the results of just $x = -505, -9, 5, 21$.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:45












            • $begingroup$
              @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:49










            • $begingroup$
              I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:56










            • $begingroup$
              @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:57
















            0












            $begingroup$

            Note that if



            $$x^2 + 43 equiv 0 pmod{44 - 2x} tag{1}label{eq1}$$



            then multiplying by $-2$ gives



            $$-2x^2 - 86 equiv 0 pmod{44 - 2x} tag{2}label{eq2}$$



            Also, dividing $44 - 2x$ into $-2x^2 - 86$ gives



            $$-2x^2 - 86 = left(x + 22right) left(44 - 2xright) - 1054 tag{3}label{eq3}$$



            Thus, your original equation can be simplified to just look for cases where



            $$-1054 equiv 0 pmod{44 - 2x} tag{4}label{eq4}$$



            As such, you only need to check cases where $44 - 2x$ is a factor of $1054 = 2 * 31 * 17$, in particular, $pm 1, pm 2, pm 31, pm 17, pm 62, pm 34, pm 527, pm 1054$. For each value $n$ among these factors, you can then solve for $x$ by using $x = 22 - frac{n}{2}$. As such, for integral values of $x$, the factor must be even, giving the results of $x = 21, 23, -9, 53, 5, 39, -505, 549$.



            Also, if you wish to avoid using negative modulus values, then you need to have $44 - 2x gt 0$, so $x lt 22$, giving the results of just $x = -505, -9, 5, 21$.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:45












            • $begingroup$
              @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:49










            • $begingroup$
              I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:56










            • $begingroup$
              @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:57














            0












            0








            0





            $begingroup$

            Note that if



            $$x^2 + 43 equiv 0 pmod{44 - 2x} tag{1}label{eq1}$$



            then multiplying by $-2$ gives



            $$-2x^2 - 86 equiv 0 pmod{44 - 2x} tag{2}label{eq2}$$



            Also, dividing $44 - 2x$ into $-2x^2 - 86$ gives



            $$-2x^2 - 86 = left(x + 22right) left(44 - 2xright) - 1054 tag{3}label{eq3}$$



            Thus, your original equation can be simplified to just look for cases where



            $$-1054 equiv 0 pmod{44 - 2x} tag{4}label{eq4}$$



            As such, you only need to check cases where $44 - 2x$ is a factor of $1054 = 2 * 31 * 17$, in particular, $pm 1, pm 2, pm 31, pm 17, pm 62, pm 34, pm 527, pm 1054$. For each value $n$ among these factors, you can then solve for $x$ by using $x = 22 - frac{n}{2}$. As such, for integral values of $x$, the factor must be even, giving the results of $x = 21, 23, -9, 53, 5, 39, -505, 549$.



            Also, if you wish to avoid using negative modulus values, then you need to have $44 - 2x gt 0$, so $x lt 22$, giving the results of just $x = -505, -9, 5, 21$.






            share|cite|improve this answer











            $endgroup$



            Note that if



            $$x^2 + 43 equiv 0 pmod{44 - 2x} tag{1}label{eq1}$$



            then multiplying by $-2$ gives



            $$-2x^2 - 86 equiv 0 pmod{44 - 2x} tag{2}label{eq2}$$



            Also, dividing $44 - 2x$ into $-2x^2 - 86$ gives



            $$-2x^2 - 86 = left(x + 22right) left(44 - 2xright) - 1054 tag{3}label{eq3}$$



            Thus, your original equation can be simplified to just look for cases where



            $$-1054 equiv 0 pmod{44 - 2x} tag{4}label{eq4}$$



            As such, you only need to check cases where $44 - 2x$ is a factor of $1054 = 2 * 31 * 17$, in particular, $pm 1, pm 2, pm 31, pm 17, pm 62, pm 34, pm 527, pm 1054$. For each value $n$ among these factors, you can then solve for $x$ by using $x = 22 - frac{n}{2}$. As such, for integral values of $x$, the factor must be even, giving the results of $x = 21, 23, -9, 53, 5, 39, -505, 549$.



            Also, if you wish to avoid using negative modulus values, then you need to have $44 - 2x gt 0$, so $x lt 22$, giving the results of just $x = -505, -9, 5, 21$.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Dec 29 '18 at 4:00

























            answered Dec 29 '18 at 3:25









            John OmielanJohn Omielan

            4,1251215




            4,1251215












            • $begingroup$
              What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:45












            • $begingroup$
              @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:49










            • $begingroup$
              I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:56










            • $begingroup$
              @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:57


















            • $begingroup$
              What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:45












            • $begingroup$
              @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:49










            • $begingroup$
              I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
              $endgroup$
              – Ryan Topps
              Dec 29 '18 at 3:56










            • $begingroup$
              @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
              $endgroup$
              – John Omielan
              Dec 29 '18 at 3:57
















            $begingroup$
            What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
            $endgroup$
            – Ryan Topps
            Dec 29 '18 at 3:45






            $begingroup$
            What you showed me with this that all answers comes in pairs where their sum is 44, which is a quite interesting approach.
            $endgroup$
            – Ryan Topps
            Dec 29 '18 at 3:45














            $begingroup$
            @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
            $endgroup$
            – John Omielan
            Dec 29 '18 at 3:49




            $begingroup$
            @RyanTopps In general, I am showing here that if you have a quadratic equation of a square term and a constant on the left, and a linear equation as the modulus, you can simplify it to just a constant, as I have shown here. I could have done it for a more general case, but I thought it would be simpler, and possibly more useful, to show the specific case you asked for. I hope you can see how this technique works so you can apply it in any other similar situations.
            $endgroup$
            – John Omielan
            Dec 29 '18 at 3:49












            $begingroup$
            I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
            $endgroup$
            – Ryan Topps
            Dec 29 '18 at 3:56




            $begingroup$
            I appreciate it, its just to find prime factors is not an easy solution in programming. I am merely looking a way for me to "cheat" so to say so I do not have to scan from 0 to 44. Basically calculating the modulus is one of the fastest operations.
            $endgroup$
            – Ryan Topps
            Dec 29 '18 at 3:56












            $begingroup$
            @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
            $endgroup$
            – John Omielan
            Dec 29 '18 at 3:57




            $begingroup$
            @RyanTopps Note that your solution doesn't include the answer of $-505$. If you plug it into your original equation, the the modulus becomes $1054$, with the left side becomes $255068 = 242 times 1054$.
            $endgroup$
            – John Omielan
            Dec 29 '18 at 3:57


















            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3055496%2fmodular-arithmetic-solving-a-quadratic-equation-with-a-variable-in-the-modulus%23new-answer', 'question_page');
            }
            );

            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







            Popular posts from this blog

            Probability when a professor distributes a quiz and homework assignment to a class of n students.

            Aardman Animations

            Are they similar matrix