Product of $k$ distinct positive integers is divisible by its sum

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite
3












Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?



It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.










share|cite|improve this question























  • Where did you find this problem?
    – Jam
    Aug 26 at 11:14










  • @Jam I don't know. Was it already asked in this community?
    – Mathwriter
    Aug 26 at 11:18






  • 1




    @quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
    – Jam
    Aug 26 at 13:02







  • 1




    $30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
    – Gerry Myerson
    Aug 26 at 13:07






  • 1




    Another one for $(k,n)=(2,3)$ is $15,30,60$.
    – quasi
    Aug 26 at 13:09














up vote
2
down vote

favorite
3












Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?



It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.










share|cite|improve this question























  • Where did you find this problem?
    – Jam
    Aug 26 at 11:14










  • @Jam I don't know. Was it already asked in this community?
    – Mathwriter
    Aug 26 at 11:18






  • 1




    @quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
    – Jam
    Aug 26 at 13:02







  • 1




    $30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
    – Gerry Myerson
    Aug 26 at 13:07






  • 1




    Another one for $(k,n)=(2,3)$ is $15,30,60$.
    – quasi
    Aug 26 at 13:09












up vote
2
down vote

favorite
3









up vote
2
down vote

favorite
3






3





Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?



It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.










share|cite|improve this question















Is it true that for every positive integer $k, n$ satisfying $2 leq k leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?



It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$),
however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.







combinatorics number-theory elementary-number-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Aug 26 at 14:31









Asaf Karagila♦

295k32410738




295k32410738










asked Aug 26 at 11:12









Mathwriter

395




395











  • Where did you find this problem?
    – Jam
    Aug 26 at 11:14










  • @Jam I don't know. Was it already asked in this community?
    – Mathwriter
    Aug 26 at 11:18






  • 1




    @quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
    – Jam
    Aug 26 at 13:02







  • 1




    $30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
    – Gerry Myerson
    Aug 26 at 13:07






  • 1




    Another one for $(k,n)=(2,3)$ is $15,30,60$.
    – quasi
    Aug 26 at 13:09
















  • Where did you find this problem?
    – Jam
    Aug 26 at 11:14










  • @Jam I don't know. Was it already asked in this community?
    – Mathwriter
    Aug 26 at 11:18






  • 1




    @quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
    – Jam
    Aug 26 at 13:02







  • 1




    $30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
    – Gerry Myerson
    Aug 26 at 13:07






  • 1




    Another one for $(k,n)=(2,3)$ is $15,30,60$.
    – quasi
    Aug 26 at 13:09















Where did you find this problem?
– Jam
Aug 26 at 11:14




Where did you find this problem?
– Jam
Aug 26 at 11:14












@Jam I don't know. Was it already asked in this community?
– Mathwriter
Aug 26 at 11:18




@Jam I don't know. Was it already asked in this community?
– Mathwriter
Aug 26 at 11:18




1




1




@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
– Jam
Aug 26 at 13:02





@quasi I'm not sure those solutions both work? $(3+12)nmid3cdot12$ and $(4+20)nmid4cdot20$.
– Jam
Aug 26 at 13:02





1




1




$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
– Gerry Myerson
Aug 26 at 13:07




$30,60,120$. $(30)(60)/(90)=20$, $(30)(120)/(150)=24$, $(60)(120)/(180)=40$.
– Gerry Myerson
Aug 26 at 13:07




1




1




Another one for $(k,n)=(2,3)$ is $15,30,60$.
– quasi
Aug 26 at 13:09




Another one for $(k,n)=(2,3)$ is $15,30,60$.
– quasi
Aug 26 at 13:09










2 Answers
2






active

oldest

votes

















up vote
5
down vote













Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.






share|cite|improve this answer
















  • 1




    (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
    – Jam
    Aug 26 at 14:03

















up vote
4
down vote













Fix positive integers $k,n$ with $2le k le n$.



Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.



Define $y_1,...,y_n$ by $y_i=ax_i$.



Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.






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',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    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%2f2894928%2fproduct-of-k-distinct-positive-integers-is-divisible-by-its-sum%23new-answer', 'question_page');

    );

    Post as a guest






























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    5
    down vote













    Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.






    share|cite|improve this answer
















    • 1




      (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
      – Jam
      Aug 26 at 14:03














    up vote
    5
    down vote













    Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.






    share|cite|improve this answer
















    • 1




      (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
      – Jam
      Aug 26 at 14:03












    up vote
    5
    down vote










    up vote
    5
    down vote









    Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.






    share|cite|improve this answer












    Suppose $a_1a_2cdots a_k$ is not divisible by $a_1+cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)cdots(a_kd)$ is divisible by $a_1d+cdots+a_kd=(a_1+cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Aug 26 at 13:14









    Gerry Myerson

    144k8145296




    144k8145296







    • 1




      (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
      – Jam
      Aug 26 at 14:03












    • 1




      (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
      – Jam
      Aug 26 at 14:03







    1




    1




    (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
    – Jam
    Aug 26 at 14:03




    (+1) As a side-note, if I'm not mistaken, you can transform this answer into @quasi's answer by defining $d=a_1+ldots+a_k$, for each subset $a_1ldots a_k$. This would fulfil your criteria. And then the product of each $d$ over all subsets would be @quasi's "$a$" or your "common multiple".
    – Jam
    Aug 26 at 14:03










    up vote
    4
    down vote













    Fix positive integers $k,n$ with $2le k le n$.



    Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.



    Define $y_1,...,y_n$ by $y_i=ax_i$.



    Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.






    share|cite|improve this answer
























      up vote
      4
      down vote













      Fix positive integers $k,n$ with $2le k le n$.



      Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.



      Define $y_1,...,y_n$ by $y_i=ax_i$.



      Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.






      share|cite|improve this answer






















        up vote
        4
        down vote










        up vote
        4
        down vote









        Fix positive integers $k,n$ with $2le k le n$.



        Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.



        Define $y_1,...,y_n$ by $y_i=ax_i$.



        Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.






        share|cite|improve this answer












        Fix positive integers $k,n$ with $2le k le n$.



        Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $x_1,...,x_n$.



        Define $y_1,...,y_n$ by $y_i=ax_i$.



        Then the product of any $k$ elements of $y_1,...,y_n$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Aug 26 at 13:21









        quasi

        34k22461




        34k22461



























             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2894928%2fproduct-of-k-distinct-positive-integers-is-divisible-by-its-sum%23new-answer', 'question_page');

            );

            Post as a guest













































































            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Displaying single band from multi-band raster using QGIS

            How many registers does an x86_64 CPU actually have?