find all $k$ such that $k^5+3$ is divisible by $k^2+1$












2














That's it. I have a solution with substitutions, but it's tedious and not too generic. Is there a solution using some cool theorem for polynomials divisibility?










share|cite|improve this question



























    2














    That's it. I have a solution with substitutions, but it's tedious and not too generic. Is there a solution using some cool theorem for polynomials divisibility?










    share|cite|improve this question

























      2












      2








      2


      1





      That's it. I have a solution with substitutions, but it's tedious and not too generic. Is there a solution using some cool theorem for polynomials divisibility?










      share|cite|improve this question













      That's it. I have a solution with substitutions, but it's tedious and not too generic. Is there a solution using some cool theorem for polynomials divisibility?







      polynomials diophantine-equations






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Nov 29 '18 at 15:40









      kirilloidkirilloid

      1656




      1656






















          4 Answers
          4






          active

          oldest

          votes


















          3














          From $k^5+3=(k^2+1)(k^3-k)+k+3$ we see that $k^2+1mid k^5+3$ implies $k^2+1mid k+3$. If $k+3not=0$, we must have $k^2+1le|k+3|le|k|+3$, which can be rewritten as $|k|^2le|k|+2$. It's not hard to see that this implies $|k|le2$, at which point one can simply check the five possible values of $k$ (remembering to check $k=-3$ as well).



          Remark (added later): This approach extends to any pair of polynomials in $k$ (with integer coefficients): If the polynomial division of $Q(k)$ by $P(k)$ leaves a nonzero remainder $R(k)$ of degree less than the degree of $P$, then the set of $k$ for which $P(k)mid Q(k)$ is necessarily finite, limited to the integer roots of $R(k)$ and $k$'s satisfying the inequality $|P(k)|le|R(k)|$. In any given case there may be other (e.g., congruence) considerations that limit the search more efficiently; for example, $P(k)=k^2+k+2$ is always even while $Q(k)=k^5+k^3+1$ is always odd, so we don't have to search at all. It'd be nice to have an example where there are some solutions to search for that are cumbersome for this approach to find but are nonetheless easy to pinpoint by another approach.






          share|cite|improve this answer































            1














            Since $$k^2+1mid (k^2+1)(k^2-1)k = k^5-k$$ we have $$k^2+1mid (k^5+3)-(k^5-k) = k+3$$



            Now $$k^2+1mid (k+3)(k-3)=k^2-9$$



            So $$k^2+1mid (k^2+1)-(k^2-9) =10$$



            So $k^2+1in{1,2,5,10}$ so $kin{0,pm1,pm2,pm 3}$.






            share|cite|improve this answer





















            • -2 and 3 are not solutions, but OK, checking only some of them is not much
              – kirilloid
              Nov 29 '18 at 16:07












            • I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
              – kirilloid
              Nov 29 '18 at 16:20










            • Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
              – kirilloid
              Nov 29 '18 at 16:34





















            1














            $!bmod k^2!+!1!:, color{#c00}{k^2equiv-1},Rightarrow, k^4equiv 1, $ so $, color{#0a0}0equiv k(k^4)!+!3equiv color{#0a0}{k!+!3}$



            therefore $ color{#0a0}{0equiv (3!+!k)}(3!-!k)equiv 9-color{#c00}{k^2}equiv 10, $ so $, bbox[5px,border:1px solid red]{k^2!+!1mid 10}$



            Remark $ color{#c00}{k^2equiv -1},$ means $,k,$ behaves like $,i,$ so the above is essentially



            $qquadqquadqquadquadbegin{align} &0equiv z equiv 3!+!i^5 equiv 3!+!i\[.4em]
            Rightarrow &0 equiv zbar z equiv (3!+!i)(3!-!i) equiv 10end{align}$



            which has a natural interpretation in Gaussian integer arithmetic (or complex numbers).



            As for a "solution using polynomials", the above computation is generic and it translates to the following Euclidean gcd (or ideal) calculation with polynomials



            $qquadqquad(x^2!+!1,!overbrace{x^5!+!3!!!}^{largecolor{#c00}{x^2 equiv -1}}), =, (!overbrace{x^2!+!1}^{largecolor{#0a0}{x equiv -3}},,x!+!3), = ,(10,,x!+!3)$



            using Euclid's $, (a,,b) = (a,, bbmod a)., $ We could go further and extract the Bezout relation giving $10$ as a linear combination of $,x^2!+!1,,x^5!+!3,,$ but there is no need to do so for the problem at hand.






            share|cite|improve this answer























            • You wrote a solution which alrady exsist
              – greedoid
              Nov 29 '18 at 15:59










            • @greedoid I don't agree (and the other answers weren't there when I loaded this page)
              – Bill Dubuque
              Nov 29 '18 at 16:00












            • Why is that........?
              – greedoid
              Nov 29 '18 at 16:01






            • 1




              $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
              – kirilloid
              Nov 29 '18 at 16:26








            • 1




              @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
              – Bill Dubuque
              Nov 29 '18 at 16:49





















            0














            Solution with substitutions.



            If $k^5+3$ is divisible by $k^2+1$, it could be expressed as $(k^2+1)(k^3+n)$, which if expanded, leads us to $k^3+nk^2+n-3$.



            Now let's make another substitution by introducing another variable $a: k=-(n+a)$, which will get us $-an^2+(1-2a^2)n-(a^3+3)$. It is solvable for $n$ only when $Dge0$ or $-4a^2-12a+1ge0$.



            Roots of the last [expression turned into an] equation are $-3pmfrac{sqrt{10}}{2}$, and since we are looking only for integers, we need to check $ain{-3,-2,-1,0}$.



            Now we can start unrolling our substitutions. For all valid values of $a$, solve $-an^2+(1-2a^2)n-(a^3+3)$ for $n$, and get values of $k$ directly as $-(n+a)$



            $$begin {array} {r|r} equation & a & n & k\
            hline
            3n^2-17n+24=0 & -3 & 3 & 0 \
            3n^2-17n+24=0 & -3 & frac83 & - \
            2n^2-7n+5=0 & -2 & 1 & 1 \
            2n^2-7n+5=0 & -2 & 2.5 & - \
            n^2-n-2=0 & -1 & -1 & 2 \
            n^2-n-2=0 & -1 & 2 & -1 \
            n-3=0 & 0 & 3 & -3 \
            end {array}$$






            share|cite|improve this answer























              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%2f3018797%2ffind-all-k-such-that-k53-is-divisible-by-k21%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









              3














              From $k^5+3=(k^2+1)(k^3-k)+k+3$ we see that $k^2+1mid k^5+3$ implies $k^2+1mid k+3$. If $k+3not=0$, we must have $k^2+1le|k+3|le|k|+3$, which can be rewritten as $|k|^2le|k|+2$. It's not hard to see that this implies $|k|le2$, at which point one can simply check the five possible values of $k$ (remembering to check $k=-3$ as well).



              Remark (added later): This approach extends to any pair of polynomials in $k$ (with integer coefficients): If the polynomial division of $Q(k)$ by $P(k)$ leaves a nonzero remainder $R(k)$ of degree less than the degree of $P$, then the set of $k$ for which $P(k)mid Q(k)$ is necessarily finite, limited to the integer roots of $R(k)$ and $k$'s satisfying the inequality $|P(k)|le|R(k)|$. In any given case there may be other (e.g., congruence) considerations that limit the search more efficiently; for example, $P(k)=k^2+k+2$ is always even while $Q(k)=k^5+k^3+1$ is always odd, so we don't have to search at all. It'd be nice to have an example where there are some solutions to search for that are cumbersome for this approach to find but are nonetheless easy to pinpoint by another approach.






              share|cite|improve this answer




























                3














                From $k^5+3=(k^2+1)(k^3-k)+k+3$ we see that $k^2+1mid k^5+3$ implies $k^2+1mid k+3$. If $k+3not=0$, we must have $k^2+1le|k+3|le|k|+3$, which can be rewritten as $|k|^2le|k|+2$. It's not hard to see that this implies $|k|le2$, at which point one can simply check the five possible values of $k$ (remembering to check $k=-3$ as well).



                Remark (added later): This approach extends to any pair of polynomials in $k$ (with integer coefficients): If the polynomial division of $Q(k)$ by $P(k)$ leaves a nonzero remainder $R(k)$ of degree less than the degree of $P$, then the set of $k$ for which $P(k)mid Q(k)$ is necessarily finite, limited to the integer roots of $R(k)$ and $k$'s satisfying the inequality $|P(k)|le|R(k)|$. In any given case there may be other (e.g., congruence) considerations that limit the search more efficiently; for example, $P(k)=k^2+k+2$ is always even while $Q(k)=k^5+k^3+1$ is always odd, so we don't have to search at all. It'd be nice to have an example where there are some solutions to search for that are cumbersome for this approach to find but are nonetheless easy to pinpoint by another approach.






                share|cite|improve this answer


























                  3












                  3








                  3






                  From $k^5+3=(k^2+1)(k^3-k)+k+3$ we see that $k^2+1mid k^5+3$ implies $k^2+1mid k+3$. If $k+3not=0$, we must have $k^2+1le|k+3|le|k|+3$, which can be rewritten as $|k|^2le|k|+2$. It's not hard to see that this implies $|k|le2$, at which point one can simply check the five possible values of $k$ (remembering to check $k=-3$ as well).



                  Remark (added later): This approach extends to any pair of polynomials in $k$ (with integer coefficients): If the polynomial division of $Q(k)$ by $P(k)$ leaves a nonzero remainder $R(k)$ of degree less than the degree of $P$, then the set of $k$ for which $P(k)mid Q(k)$ is necessarily finite, limited to the integer roots of $R(k)$ and $k$'s satisfying the inequality $|P(k)|le|R(k)|$. In any given case there may be other (e.g., congruence) considerations that limit the search more efficiently; for example, $P(k)=k^2+k+2$ is always even while $Q(k)=k^5+k^3+1$ is always odd, so we don't have to search at all. It'd be nice to have an example where there are some solutions to search for that are cumbersome for this approach to find but are nonetheless easy to pinpoint by another approach.






                  share|cite|improve this answer














                  From $k^5+3=(k^2+1)(k^3-k)+k+3$ we see that $k^2+1mid k^5+3$ implies $k^2+1mid k+3$. If $k+3not=0$, we must have $k^2+1le|k+3|le|k|+3$, which can be rewritten as $|k|^2le|k|+2$. It's not hard to see that this implies $|k|le2$, at which point one can simply check the five possible values of $k$ (remembering to check $k=-3$ as well).



                  Remark (added later): This approach extends to any pair of polynomials in $k$ (with integer coefficients): If the polynomial division of $Q(k)$ by $P(k)$ leaves a nonzero remainder $R(k)$ of degree less than the degree of $P$, then the set of $k$ for which $P(k)mid Q(k)$ is necessarily finite, limited to the integer roots of $R(k)$ and $k$'s satisfying the inequality $|P(k)|le|R(k)|$. In any given case there may be other (e.g., congruence) considerations that limit the search more efficiently; for example, $P(k)=k^2+k+2$ is always even while $Q(k)=k^5+k^3+1$ is always odd, so we don't have to search at all. It'd be nice to have an example where there are some solutions to search for that are cumbersome for this approach to find but are nonetheless easy to pinpoint by another approach.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited Nov 29 '18 at 17:11

























                  answered Nov 29 '18 at 15:52









                  Barry CipraBarry Cipra

                  59.3k653125




                  59.3k653125























                      1














                      Since $$k^2+1mid (k^2+1)(k^2-1)k = k^5-k$$ we have $$k^2+1mid (k^5+3)-(k^5-k) = k+3$$



                      Now $$k^2+1mid (k+3)(k-3)=k^2-9$$



                      So $$k^2+1mid (k^2+1)-(k^2-9) =10$$



                      So $k^2+1in{1,2,5,10}$ so $kin{0,pm1,pm2,pm 3}$.






                      share|cite|improve this answer





















                      • -2 and 3 are not solutions, but OK, checking only some of them is not much
                        – kirilloid
                        Nov 29 '18 at 16:07












                      • I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
                        – kirilloid
                        Nov 29 '18 at 16:20










                      • Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
                        – kirilloid
                        Nov 29 '18 at 16:34


















                      1














                      Since $$k^2+1mid (k^2+1)(k^2-1)k = k^5-k$$ we have $$k^2+1mid (k^5+3)-(k^5-k) = k+3$$



                      Now $$k^2+1mid (k+3)(k-3)=k^2-9$$



                      So $$k^2+1mid (k^2+1)-(k^2-9) =10$$



                      So $k^2+1in{1,2,5,10}$ so $kin{0,pm1,pm2,pm 3}$.






                      share|cite|improve this answer





















                      • -2 and 3 are not solutions, but OK, checking only some of them is not much
                        – kirilloid
                        Nov 29 '18 at 16:07












                      • I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
                        – kirilloid
                        Nov 29 '18 at 16:20










                      • Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
                        – kirilloid
                        Nov 29 '18 at 16:34
















                      1












                      1








                      1






                      Since $$k^2+1mid (k^2+1)(k^2-1)k = k^5-k$$ we have $$k^2+1mid (k^5+3)-(k^5-k) = k+3$$



                      Now $$k^2+1mid (k+3)(k-3)=k^2-9$$



                      So $$k^2+1mid (k^2+1)-(k^2-9) =10$$



                      So $k^2+1in{1,2,5,10}$ so $kin{0,pm1,pm2,pm 3}$.






                      share|cite|improve this answer












                      Since $$k^2+1mid (k^2+1)(k^2-1)k = k^5-k$$ we have $$k^2+1mid (k^5+3)-(k^5-k) = k+3$$



                      Now $$k^2+1mid (k+3)(k-3)=k^2-9$$



                      So $$k^2+1mid (k^2+1)-(k^2-9) =10$$



                      So $k^2+1in{1,2,5,10}$ so $kin{0,pm1,pm2,pm 3}$.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Nov 29 '18 at 15:49









                      greedoidgreedoid

                      38.5k114797




                      38.5k114797












                      • -2 and 3 are not solutions, but OK, checking only some of them is not much
                        – kirilloid
                        Nov 29 '18 at 16:07












                      • I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
                        – kirilloid
                        Nov 29 '18 at 16:20










                      • Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
                        – kirilloid
                        Nov 29 '18 at 16:34




















                      • -2 and 3 are not solutions, but OK, checking only some of them is not much
                        – kirilloid
                        Nov 29 '18 at 16:07












                      • I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
                        – kirilloid
                        Nov 29 '18 at 16:20










                      • Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
                        – kirilloid
                        Nov 29 '18 at 16:34


















                      -2 and 3 are not solutions, but OK, checking only some of them is not much
                      – kirilloid
                      Nov 29 '18 at 16:07






                      -2 and 3 are not solutions, but OK, checking only some of them is not much
                      – kirilloid
                      Nov 29 '18 at 16:07














                      I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
                      – kirilloid
                      Nov 29 '18 at 16:20




                      I'm not sure I understand the last transition. You added $k^2+1$ and got a tautology $10=10$, where does $kin{1,2,5,10}$ come from?
                      – kirilloid
                      Nov 29 '18 at 16:20












                      Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
                      – kirilloid
                      Nov 29 '18 at 16:34






                      Nevermind, for get about tautology. How do we get $k^2+1in{1,2,5,10}$? $k^2+1 | 10 = 0$ so $10$ should be a multiple of $k^2+1$, let's check all divisors of $10$?
                      – kirilloid
                      Nov 29 '18 at 16:34













                      1














                      $!bmod k^2!+!1!:, color{#c00}{k^2equiv-1},Rightarrow, k^4equiv 1, $ so $, color{#0a0}0equiv k(k^4)!+!3equiv color{#0a0}{k!+!3}$



                      therefore $ color{#0a0}{0equiv (3!+!k)}(3!-!k)equiv 9-color{#c00}{k^2}equiv 10, $ so $, bbox[5px,border:1px solid red]{k^2!+!1mid 10}$



                      Remark $ color{#c00}{k^2equiv -1},$ means $,k,$ behaves like $,i,$ so the above is essentially



                      $qquadqquadqquadquadbegin{align} &0equiv z equiv 3!+!i^5 equiv 3!+!i\[.4em]
                      Rightarrow &0 equiv zbar z equiv (3!+!i)(3!-!i) equiv 10end{align}$



                      which has a natural interpretation in Gaussian integer arithmetic (or complex numbers).



                      As for a "solution using polynomials", the above computation is generic and it translates to the following Euclidean gcd (or ideal) calculation with polynomials



                      $qquadqquad(x^2!+!1,!overbrace{x^5!+!3!!!}^{largecolor{#c00}{x^2 equiv -1}}), =, (!overbrace{x^2!+!1}^{largecolor{#0a0}{x equiv -3}},,x!+!3), = ,(10,,x!+!3)$



                      using Euclid's $, (a,,b) = (a,, bbmod a)., $ We could go further and extract the Bezout relation giving $10$ as a linear combination of $,x^2!+!1,,x^5!+!3,,$ but there is no need to do so for the problem at hand.






                      share|cite|improve this answer























                      • You wrote a solution which alrady exsist
                        – greedoid
                        Nov 29 '18 at 15:59










                      • @greedoid I don't agree (and the other answers weren't there when I loaded this page)
                        – Bill Dubuque
                        Nov 29 '18 at 16:00












                      • Why is that........?
                        – greedoid
                        Nov 29 '18 at 16:01






                      • 1




                        $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
                        – kirilloid
                        Nov 29 '18 at 16:26








                      • 1




                        @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
                        – Bill Dubuque
                        Nov 29 '18 at 16:49


















                      1














                      $!bmod k^2!+!1!:, color{#c00}{k^2equiv-1},Rightarrow, k^4equiv 1, $ so $, color{#0a0}0equiv k(k^4)!+!3equiv color{#0a0}{k!+!3}$



                      therefore $ color{#0a0}{0equiv (3!+!k)}(3!-!k)equiv 9-color{#c00}{k^2}equiv 10, $ so $, bbox[5px,border:1px solid red]{k^2!+!1mid 10}$



                      Remark $ color{#c00}{k^2equiv -1},$ means $,k,$ behaves like $,i,$ so the above is essentially



                      $qquadqquadqquadquadbegin{align} &0equiv z equiv 3!+!i^5 equiv 3!+!i\[.4em]
                      Rightarrow &0 equiv zbar z equiv (3!+!i)(3!-!i) equiv 10end{align}$



                      which has a natural interpretation in Gaussian integer arithmetic (or complex numbers).



                      As for a "solution using polynomials", the above computation is generic and it translates to the following Euclidean gcd (or ideal) calculation with polynomials



                      $qquadqquad(x^2!+!1,!overbrace{x^5!+!3!!!}^{largecolor{#c00}{x^2 equiv -1}}), =, (!overbrace{x^2!+!1}^{largecolor{#0a0}{x equiv -3}},,x!+!3), = ,(10,,x!+!3)$



                      using Euclid's $, (a,,b) = (a,, bbmod a)., $ We could go further and extract the Bezout relation giving $10$ as a linear combination of $,x^2!+!1,,x^5!+!3,,$ but there is no need to do so for the problem at hand.






                      share|cite|improve this answer























                      • You wrote a solution which alrady exsist
                        – greedoid
                        Nov 29 '18 at 15:59










                      • @greedoid I don't agree (and the other answers weren't there when I loaded this page)
                        – Bill Dubuque
                        Nov 29 '18 at 16:00












                      • Why is that........?
                        – greedoid
                        Nov 29 '18 at 16:01






                      • 1




                        $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
                        – kirilloid
                        Nov 29 '18 at 16:26








                      • 1




                        @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
                        – Bill Dubuque
                        Nov 29 '18 at 16:49
















                      1












                      1








                      1






                      $!bmod k^2!+!1!:, color{#c00}{k^2equiv-1},Rightarrow, k^4equiv 1, $ so $, color{#0a0}0equiv k(k^4)!+!3equiv color{#0a0}{k!+!3}$



                      therefore $ color{#0a0}{0equiv (3!+!k)}(3!-!k)equiv 9-color{#c00}{k^2}equiv 10, $ so $, bbox[5px,border:1px solid red]{k^2!+!1mid 10}$



                      Remark $ color{#c00}{k^2equiv -1},$ means $,k,$ behaves like $,i,$ so the above is essentially



                      $qquadqquadqquadquadbegin{align} &0equiv z equiv 3!+!i^5 equiv 3!+!i\[.4em]
                      Rightarrow &0 equiv zbar z equiv (3!+!i)(3!-!i) equiv 10end{align}$



                      which has a natural interpretation in Gaussian integer arithmetic (or complex numbers).



                      As for a "solution using polynomials", the above computation is generic and it translates to the following Euclidean gcd (or ideal) calculation with polynomials



                      $qquadqquad(x^2!+!1,!overbrace{x^5!+!3!!!}^{largecolor{#c00}{x^2 equiv -1}}), =, (!overbrace{x^2!+!1}^{largecolor{#0a0}{x equiv -3}},,x!+!3), = ,(10,,x!+!3)$



                      using Euclid's $, (a,,b) = (a,, bbmod a)., $ We could go further and extract the Bezout relation giving $10$ as a linear combination of $,x^2!+!1,,x^5!+!3,,$ but there is no need to do so for the problem at hand.






                      share|cite|improve this answer














                      $!bmod k^2!+!1!:, color{#c00}{k^2equiv-1},Rightarrow, k^4equiv 1, $ so $, color{#0a0}0equiv k(k^4)!+!3equiv color{#0a0}{k!+!3}$



                      therefore $ color{#0a0}{0equiv (3!+!k)}(3!-!k)equiv 9-color{#c00}{k^2}equiv 10, $ so $, bbox[5px,border:1px solid red]{k^2!+!1mid 10}$



                      Remark $ color{#c00}{k^2equiv -1},$ means $,k,$ behaves like $,i,$ so the above is essentially



                      $qquadqquadqquadquadbegin{align} &0equiv z equiv 3!+!i^5 equiv 3!+!i\[.4em]
                      Rightarrow &0 equiv zbar z equiv (3!+!i)(3!-!i) equiv 10end{align}$



                      which has a natural interpretation in Gaussian integer arithmetic (or complex numbers).



                      As for a "solution using polynomials", the above computation is generic and it translates to the following Euclidean gcd (or ideal) calculation with polynomials



                      $qquadqquad(x^2!+!1,!overbrace{x^5!+!3!!!}^{largecolor{#c00}{x^2 equiv -1}}), =, (!overbrace{x^2!+!1}^{largecolor{#0a0}{x equiv -3}},,x!+!3), = ,(10,,x!+!3)$



                      using Euclid's $, (a,,b) = (a,, bbmod a)., $ We could go further and extract the Bezout relation giving $10$ as a linear combination of $,x^2!+!1,,x^5!+!3,,$ but there is no need to do so for the problem at hand.







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited Nov 30 '18 at 1:19

























                      answered Nov 29 '18 at 15:56









                      Bill DubuqueBill Dubuque

                      209k29190630




                      209k29190630












                      • You wrote a solution which alrady exsist
                        – greedoid
                        Nov 29 '18 at 15:59










                      • @greedoid I don't agree (and the other answers weren't there when I loaded this page)
                        – Bill Dubuque
                        Nov 29 '18 at 16:00












                      • Why is that........?
                        – greedoid
                        Nov 29 '18 at 16:01






                      • 1




                        $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
                        – kirilloid
                        Nov 29 '18 at 16:26








                      • 1




                        @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
                        – Bill Dubuque
                        Nov 29 '18 at 16:49




















                      • You wrote a solution which alrady exsist
                        – greedoid
                        Nov 29 '18 at 15:59










                      • @greedoid I don't agree (and the other answers weren't there when I loaded this page)
                        – Bill Dubuque
                        Nov 29 '18 at 16:00












                      • Why is that........?
                        – greedoid
                        Nov 29 '18 at 16:01






                      • 1




                        $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
                        – kirilloid
                        Nov 29 '18 at 16:26








                      • 1




                        @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
                        – Bill Dubuque
                        Nov 29 '18 at 16:49


















                      You wrote a solution which alrady exsist
                      – greedoid
                      Nov 29 '18 at 15:59




                      You wrote a solution which alrady exsist
                      – greedoid
                      Nov 29 '18 at 15:59












                      @greedoid I don't agree (and the other answers weren't there when I loaded this page)
                      – Bill Dubuque
                      Nov 29 '18 at 16:00






                      @greedoid I don't agree (and the other answers weren't there when I loaded this page)
                      – Bill Dubuque
                      Nov 29 '18 at 16:00














                      Why is that........?
                      – greedoid
                      Nov 29 '18 at 16:01




                      Why is that........?
                      – greedoid
                      Nov 29 '18 at 16:01




                      1




                      1




                      $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
                      – kirilloid
                      Nov 29 '18 at 16:26






                      $k^2equiv-1$ is really a neat idea, can this be generalized for divisibility by arbitrary 2-polynomials, not only this with almost trivial roots $pm i$?
                      – kirilloid
                      Nov 29 '18 at 16:26






                      1




                      1




                      @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
                      – Bill Dubuque
                      Nov 29 '18 at 16:49






                      @kirilloid Yes, $bmod x^2!-a,$ we can use $,x^2equiv a$ to reduce every polynomial $f(x)$ to a congruent linear polynomial $r(x)$. It's essentially an efficient what to compute the remainder $r(x)$ on dividing $f(x)$ by $,x^2!-a.,$ Since $,f(x) = q(x) (x^2!-a) + r(x),$ we have $,x^2!-amid f(x)iff x^2!-amid r(x),,$ so to test divisibility we need only the remainder (the quotient plays no role so it is a wasteful to compute it). The same works not only for $,x^2-a,$ but for any polynomial. But in the general case the modular arithmetic is more complicated.
                      – Bill Dubuque
                      Nov 29 '18 at 16:49













                      0














                      Solution with substitutions.



                      If $k^5+3$ is divisible by $k^2+1$, it could be expressed as $(k^2+1)(k^3+n)$, which if expanded, leads us to $k^3+nk^2+n-3$.



                      Now let's make another substitution by introducing another variable $a: k=-(n+a)$, which will get us $-an^2+(1-2a^2)n-(a^3+3)$. It is solvable for $n$ only when $Dge0$ or $-4a^2-12a+1ge0$.



                      Roots of the last [expression turned into an] equation are $-3pmfrac{sqrt{10}}{2}$, and since we are looking only for integers, we need to check $ain{-3,-2,-1,0}$.



                      Now we can start unrolling our substitutions. For all valid values of $a$, solve $-an^2+(1-2a^2)n-(a^3+3)$ for $n$, and get values of $k$ directly as $-(n+a)$



                      $$begin {array} {r|r} equation & a & n & k\
                      hline
                      3n^2-17n+24=0 & -3 & 3 & 0 \
                      3n^2-17n+24=0 & -3 & frac83 & - \
                      2n^2-7n+5=0 & -2 & 1 & 1 \
                      2n^2-7n+5=0 & -2 & 2.5 & - \
                      n^2-n-2=0 & -1 & -1 & 2 \
                      n^2-n-2=0 & -1 & 2 & -1 \
                      n-3=0 & 0 & 3 & -3 \
                      end {array}$$






                      share|cite|improve this answer




























                        0














                        Solution with substitutions.



                        If $k^5+3$ is divisible by $k^2+1$, it could be expressed as $(k^2+1)(k^3+n)$, which if expanded, leads us to $k^3+nk^2+n-3$.



                        Now let's make another substitution by introducing another variable $a: k=-(n+a)$, which will get us $-an^2+(1-2a^2)n-(a^3+3)$. It is solvable for $n$ only when $Dge0$ or $-4a^2-12a+1ge0$.



                        Roots of the last [expression turned into an] equation are $-3pmfrac{sqrt{10}}{2}$, and since we are looking only for integers, we need to check $ain{-3,-2,-1,0}$.



                        Now we can start unrolling our substitutions. For all valid values of $a$, solve $-an^2+(1-2a^2)n-(a^3+3)$ for $n$, and get values of $k$ directly as $-(n+a)$



                        $$begin {array} {r|r} equation & a & n & k\
                        hline
                        3n^2-17n+24=0 & -3 & 3 & 0 \
                        3n^2-17n+24=0 & -3 & frac83 & - \
                        2n^2-7n+5=0 & -2 & 1 & 1 \
                        2n^2-7n+5=0 & -2 & 2.5 & - \
                        n^2-n-2=0 & -1 & -1 & 2 \
                        n^2-n-2=0 & -1 & 2 & -1 \
                        n-3=0 & 0 & 3 & -3 \
                        end {array}$$






                        share|cite|improve this answer


























                          0












                          0








                          0






                          Solution with substitutions.



                          If $k^5+3$ is divisible by $k^2+1$, it could be expressed as $(k^2+1)(k^3+n)$, which if expanded, leads us to $k^3+nk^2+n-3$.



                          Now let's make another substitution by introducing another variable $a: k=-(n+a)$, which will get us $-an^2+(1-2a^2)n-(a^3+3)$. It is solvable for $n$ only when $Dge0$ or $-4a^2-12a+1ge0$.



                          Roots of the last [expression turned into an] equation are $-3pmfrac{sqrt{10}}{2}$, and since we are looking only for integers, we need to check $ain{-3,-2,-1,0}$.



                          Now we can start unrolling our substitutions. For all valid values of $a$, solve $-an^2+(1-2a^2)n-(a^3+3)$ for $n$, and get values of $k$ directly as $-(n+a)$



                          $$begin {array} {r|r} equation & a & n & k\
                          hline
                          3n^2-17n+24=0 & -3 & 3 & 0 \
                          3n^2-17n+24=0 & -3 & frac83 & - \
                          2n^2-7n+5=0 & -2 & 1 & 1 \
                          2n^2-7n+5=0 & -2 & 2.5 & - \
                          n^2-n-2=0 & -1 & -1 & 2 \
                          n^2-n-2=0 & -1 & 2 & -1 \
                          n-3=0 & 0 & 3 & -3 \
                          end {array}$$






                          share|cite|improve this answer














                          Solution with substitutions.



                          If $k^5+3$ is divisible by $k^2+1$, it could be expressed as $(k^2+1)(k^3+n)$, which if expanded, leads us to $k^3+nk^2+n-3$.



                          Now let's make another substitution by introducing another variable $a: k=-(n+a)$, which will get us $-an^2+(1-2a^2)n-(a^3+3)$. It is solvable for $n$ only when $Dge0$ or $-4a^2-12a+1ge0$.



                          Roots of the last [expression turned into an] equation are $-3pmfrac{sqrt{10}}{2}$, and since we are looking only for integers, we need to check $ain{-3,-2,-1,0}$.



                          Now we can start unrolling our substitutions. For all valid values of $a$, solve $-an^2+(1-2a^2)n-(a^3+3)$ for $n$, and get values of $k$ directly as $-(n+a)$



                          $$begin {array} {r|r} equation & a & n & k\
                          hline
                          3n^2-17n+24=0 & -3 & 3 & 0 \
                          3n^2-17n+24=0 & -3 & frac83 & - \
                          2n^2-7n+5=0 & -2 & 1 & 1 \
                          2n^2-7n+5=0 & -2 & 2.5 & - \
                          n^2-n-2=0 & -1 & -1 & 2 \
                          n^2-n-2=0 & -1 & 2 & -1 \
                          n-3=0 & 0 & 3 & -3 \
                          end {array}$$







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited Nov 29 '18 at 16:27

























                          answered Nov 29 '18 at 15:41









                          kirilloidkirilloid

                          1656




                          1656






























                              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.





                              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.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3018797%2ffind-all-k-such-that-k53-is-divisible-by-k21%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

                              Bundesstraße 106

                              Verónica Boquete

                              Ida-Boy-Ed-Garten