Divisibility of prime factorial











up vote
6
down vote

favorite
2












If $p>3$ is a prime number and $q$ is the next prime following $p$, is it always true that $p!$ is divisible by all $n<q$?










share|cite|improve this question


























    up vote
    6
    down vote

    favorite
    2












    If $p>3$ is a prime number and $q$ is the next prime following $p$, is it always true that $p!$ is divisible by all $n<q$?










    share|cite|improve this question
























      up vote
      6
      down vote

      favorite
      2









      up vote
      6
      down vote

      favorite
      2






      2





      If $p>3$ is a prime number and $q$ is the next prime following $p$, is it always true that $p!$ is divisible by all $n<q$?










      share|cite|improve this question













      If $p>3$ is a prime number and $q$ is the next prime following $p$, is it always true that $p!$ is divisible by all $n<q$?







      elementary-number-theory prime-numbers






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Nov 15 at 15:59









      Alex

      604




      604






















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          3
          down vote



          accepted










          The answer is that $n$ divides $p!$ if $p<n<q$.



          Let $p<n<q$ and assume that $r$ is a prime and $r^kmid n$. Our goal is to prove that $r^kmid p!$. Assume the contrary. First, note that in fact, we see that $r^k=n$. Indeed: if $n>r^k$ then $nge 2r^k$. On the other hand, Bertrand's postulate implies that $q<2p$ and we have
          $$r^klefrac n2<frac q2<p$$
          and then $r^kmid p!$.



          Moreover, $k>1$. Otherwise, $r^k$ would be a prime, a contradiction with the fact that $q$ is the least prime after $p$.



          Now we have
          $$k>sum_{j=1}^inftyleftlfloorfrac p{r^j}rightrfloor=sum_{j=1}^{k-1}leftlfloorfrac p{r^j}rightrfloorgesum_{j=1}^{k-1}leftlfloorfrac {r^{k-1}}{r^j}rightrfloor=sum_{j=0}^{k-2}r^jge1+2(k-2)=2k-3$$
          That is, $k<3$. This implies $k=2$.



          So we have now three primes $p,q,r$ such that $p<r^2<q$ such that $lfloor p/rrfloor<2$, that is, $p<2r$, and then $r^2<q<2p<4r$, so $r<4$. This leaves us with two options: $n=4$ and $n=9$. But $5le p<n$ and the last prime before $9$ is $7$, and $9mid 7!$.






          share|cite|improve this answer



















          • 1




            I'm wondering if there is a short proof without Bertrand's postulate.
            – ajotatxe
            Nov 15 at 17:37










          • I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
            – Sauhard Sharma
            Nov 15 at 17:45










          • $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
            – Keith Backman
            Nov 15 at 17:50












          • @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
            – Keith Backman
            Nov 15 at 18:22












          • @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
            – ajotatxe
            Nov 15 at 19:02


















          up vote
          1
          down vote













          Obviously $p!$ is divisible by any $n leq p$. So we need only concern ourselves with $p < n < q$.



          As you have stipulated that $q$ is the very next prime greater than $p$, it follows that the numbers between $p$ and $q$ are composite numbers divisible only by primes less than or equal to $p$.



          So $gcd(n, p!) geq 2$. Here's where your question gets interesting: it might be possible that one of these $n$ is divisible by some prime $r < p$ but with a higher exponent than in $p!$.



          The likeliest candidate for such a prime is 2. Since $p$ is odd, $p!$ has $$2^frac{p - 1}{2}$$ as a divisor.



          But let's not forget that multiples of 4 contribute at least twice as much as singly even numbers to 2's exponent in $p!$. So, assuming $p equiv 1 bmod 4$, the larger number $$2^{frac{p - 1}{2} + frac{p - 1}{4}}$$ is also a divisor of $p!$ (just a small tweak if $p equiv 3 bmod 4$ instead).



          So the best chance to accumulate enough exponents of 2 would be with the very first prime greater than a given power of 2, let's say $2^m$. But no even number between $2^m$ and $2^{m + 1}$ has a higher exponent for 2 than $m$.



          I guess this is the point where we must invoke Bertrand's postulate... or maybe it's the prime number theorem that we need instead? The fact $$frac{2^m}{log 2^m} < frac{2^{m + 1}}{log 2^{m + 1}}$$ by more than 2 for $m > 4$ suggests that there are at least two primes between $2^m$ and $2^{m + 1}$.



          Okay, so what if instead we choose the prime right below $2^m$? But thanks to 2 and $2^{m - 1}$, $p!$ has at least $m$ for 2's exponent in its factorization.



          Surely there are some gaps in the reasoning above, but I hope at least you find it illuminating.






          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: 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%2f2999871%2fdivisibility-of-prime-factorial%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            3
            down vote



            accepted










            The answer is that $n$ divides $p!$ if $p<n<q$.



            Let $p<n<q$ and assume that $r$ is a prime and $r^kmid n$. Our goal is to prove that $r^kmid p!$. Assume the contrary. First, note that in fact, we see that $r^k=n$. Indeed: if $n>r^k$ then $nge 2r^k$. On the other hand, Bertrand's postulate implies that $q<2p$ and we have
            $$r^klefrac n2<frac q2<p$$
            and then $r^kmid p!$.



            Moreover, $k>1$. Otherwise, $r^k$ would be a prime, a contradiction with the fact that $q$ is the least prime after $p$.



            Now we have
            $$k>sum_{j=1}^inftyleftlfloorfrac p{r^j}rightrfloor=sum_{j=1}^{k-1}leftlfloorfrac p{r^j}rightrfloorgesum_{j=1}^{k-1}leftlfloorfrac {r^{k-1}}{r^j}rightrfloor=sum_{j=0}^{k-2}r^jge1+2(k-2)=2k-3$$
            That is, $k<3$. This implies $k=2$.



            So we have now three primes $p,q,r$ such that $p<r^2<q$ such that $lfloor p/rrfloor<2$, that is, $p<2r$, and then $r^2<q<2p<4r$, so $r<4$. This leaves us with two options: $n=4$ and $n=9$. But $5le p<n$ and the last prime before $9$ is $7$, and $9mid 7!$.






            share|cite|improve this answer



















            • 1




              I'm wondering if there is a short proof without Bertrand's postulate.
              – ajotatxe
              Nov 15 at 17:37










            • I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
              – Sauhard Sharma
              Nov 15 at 17:45










            • $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
              – Keith Backman
              Nov 15 at 17:50












            • @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
              – Keith Backman
              Nov 15 at 18:22












            • @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
              – ajotatxe
              Nov 15 at 19:02















            up vote
            3
            down vote



            accepted










            The answer is that $n$ divides $p!$ if $p<n<q$.



            Let $p<n<q$ and assume that $r$ is a prime and $r^kmid n$. Our goal is to prove that $r^kmid p!$. Assume the contrary. First, note that in fact, we see that $r^k=n$. Indeed: if $n>r^k$ then $nge 2r^k$. On the other hand, Bertrand's postulate implies that $q<2p$ and we have
            $$r^klefrac n2<frac q2<p$$
            and then $r^kmid p!$.



            Moreover, $k>1$. Otherwise, $r^k$ would be a prime, a contradiction with the fact that $q$ is the least prime after $p$.



            Now we have
            $$k>sum_{j=1}^inftyleftlfloorfrac p{r^j}rightrfloor=sum_{j=1}^{k-1}leftlfloorfrac p{r^j}rightrfloorgesum_{j=1}^{k-1}leftlfloorfrac {r^{k-1}}{r^j}rightrfloor=sum_{j=0}^{k-2}r^jge1+2(k-2)=2k-3$$
            That is, $k<3$. This implies $k=2$.



            So we have now three primes $p,q,r$ such that $p<r^2<q$ such that $lfloor p/rrfloor<2$, that is, $p<2r$, and then $r^2<q<2p<4r$, so $r<4$. This leaves us with two options: $n=4$ and $n=9$. But $5le p<n$ and the last prime before $9$ is $7$, and $9mid 7!$.






            share|cite|improve this answer



















            • 1




              I'm wondering if there is a short proof without Bertrand's postulate.
              – ajotatxe
              Nov 15 at 17:37










            • I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
              – Sauhard Sharma
              Nov 15 at 17:45










            • $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
              – Keith Backman
              Nov 15 at 17:50












            • @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
              – Keith Backman
              Nov 15 at 18:22












            • @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
              – ajotatxe
              Nov 15 at 19:02













            up vote
            3
            down vote



            accepted







            up vote
            3
            down vote



            accepted






            The answer is that $n$ divides $p!$ if $p<n<q$.



            Let $p<n<q$ and assume that $r$ is a prime and $r^kmid n$. Our goal is to prove that $r^kmid p!$. Assume the contrary. First, note that in fact, we see that $r^k=n$. Indeed: if $n>r^k$ then $nge 2r^k$. On the other hand, Bertrand's postulate implies that $q<2p$ and we have
            $$r^klefrac n2<frac q2<p$$
            and then $r^kmid p!$.



            Moreover, $k>1$. Otherwise, $r^k$ would be a prime, a contradiction with the fact that $q$ is the least prime after $p$.



            Now we have
            $$k>sum_{j=1}^inftyleftlfloorfrac p{r^j}rightrfloor=sum_{j=1}^{k-1}leftlfloorfrac p{r^j}rightrfloorgesum_{j=1}^{k-1}leftlfloorfrac {r^{k-1}}{r^j}rightrfloor=sum_{j=0}^{k-2}r^jge1+2(k-2)=2k-3$$
            That is, $k<3$. This implies $k=2$.



            So we have now three primes $p,q,r$ such that $p<r^2<q$ such that $lfloor p/rrfloor<2$, that is, $p<2r$, and then $r^2<q<2p<4r$, so $r<4$. This leaves us with two options: $n=4$ and $n=9$. But $5le p<n$ and the last prime before $9$ is $7$, and $9mid 7!$.






            share|cite|improve this answer














            The answer is that $n$ divides $p!$ if $p<n<q$.



            Let $p<n<q$ and assume that $r$ is a prime and $r^kmid n$. Our goal is to prove that $r^kmid p!$. Assume the contrary. First, note that in fact, we see that $r^k=n$. Indeed: if $n>r^k$ then $nge 2r^k$. On the other hand, Bertrand's postulate implies that $q<2p$ and we have
            $$r^klefrac n2<frac q2<p$$
            and then $r^kmid p!$.



            Moreover, $k>1$. Otherwise, $r^k$ would be a prime, a contradiction with the fact that $q$ is the least prime after $p$.



            Now we have
            $$k>sum_{j=1}^inftyleftlfloorfrac p{r^j}rightrfloor=sum_{j=1}^{k-1}leftlfloorfrac p{r^j}rightrfloorgesum_{j=1}^{k-1}leftlfloorfrac {r^{k-1}}{r^j}rightrfloor=sum_{j=0}^{k-2}r^jge1+2(k-2)=2k-3$$
            That is, $k<3$. This implies $k=2$.



            So we have now three primes $p,q,r$ such that $p<r^2<q$ such that $lfloor p/rrfloor<2$, that is, $p<2r$, and then $r^2<q<2p<4r$, so $r<4$. This leaves us with two options: $n=4$ and $n=9$. But $5le p<n$ and the last prime before $9$ is $7$, and $9mid 7!$.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Nov 15 at 19:32

























            answered Nov 15 at 17:25









            ajotatxe

            52.1k23688




            52.1k23688








            • 1




              I'm wondering if there is a short proof without Bertrand's postulate.
              – ajotatxe
              Nov 15 at 17:37










            • I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
              – Sauhard Sharma
              Nov 15 at 17:45










            • $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
              – Keith Backman
              Nov 15 at 17:50












            • @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
              – Keith Backman
              Nov 15 at 18:22












            • @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
              – ajotatxe
              Nov 15 at 19:02














            • 1




              I'm wondering if there is a short proof without Bertrand's postulate.
              – ajotatxe
              Nov 15 at 17:37










            • I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
              – Sauhard Sharma
              Nov 15 at 17:45










            • $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
              – Keith Backman
              Nov 15 at 17:50












            • @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
              – Keith Backman
              Nov 15 at 18:22












            • @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
              – ajotatxe
              Nov 15 at 19:02








            1




            1




            I'm wondering if there is a short proof without Bertrand's postulate.
            – ajotatxe
            Nov 15 at 17:37




            I'm wondering if there is a short proof without Bertrand's postulate.
            – ajotatxe
            Nov 15 at 17:37












            I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
            – Sauhard Sharma
            Nov 15 at 17:45




            I know it might be a stupid question, but could you tell me what does $r^kmid n$ mean in the first line ?
            – Sauhard Sharma
            Nov 15 at 17:45












            $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
            – Keith Backman
            Nov 15 at 17:50






            $mid $ means 'evenly divides' as $2mid 6$. $r^k mid n$ means that $n=ccdot r^k$ where $c$ is an integer.
            – Keith Backman
            Nov 15 at 17:50














            @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
            – Keith Backman
            Nov 15 at 18:22






            @ajotatxe I'm not clear on how you can limit the exponent of $r$ to $2$. The question as posed can be seen to ask as a particular cases whether $128mid 127!$ or $27mid 23!$. But $128ne r^2$ and $27ne r^2$ for any integer $r$. Other examples of this kind are easy to generate by taking an odd power of a prime ($u=s^{2t+1}$) and asking if $u$ divides the factorial of the largest prime smaller than $u$.
            – Keith Backman
            Nov 15 at 18:22














            @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
            – ajotatxe
            Nov 15 at 19:02




            @KeithBackman It is proved in my answer that the exponent must be lesser than $3$.
            – ajotatxe
            Nov 15 at 19:02










            up vote
            1
            down vote













            Obviously $p!$ is divisible by any $n leq p$. So we need only concern ourselves with $p < n < q$.



            As you have stipulated that $q$ is the very next prime greater than $p$, it follows that the numbers between $p$ and $q$ are composite numbers divisible only by primes less than or equal to $p$.



            So $gcd(n, p!) geq 2$. Here's where your question gets interesting: it might be possible that one of these $n$ is divisible by some prime $r < p$ but with a higher exponent than in $p!$.



            The likeliest candidate for such a prime is 2. Since $p$ is odd, $p!$ has $$2^frac{p - 1}{2}$$ as a divisor.



            But let's not forget that multiples of 4 contribute at least twice as much as singly even numbers to 2's exponent in $p!$. So, assuming $p equiv 1 bmod 4$, the larger number $$2^{frac{p - 1}{2} + frac{p - 1}{4}}$$ is also a divisor of $p!$ (just a small tweak if $p equiv 3 bmod 4$ instead).



            So the best chance to accumulate enough exponents of 2 would be with the very first prime greater than a given power of 2, let's say $2^m$. But no even number between $2^m$ and $2^{m + 1}$ has a higher exponent for 2 than $m$.



            I guess this is the point where we must invoke Bertrand's postulate... or maybe it's the prime number theorem that we need instead? The fact $$frac{2^m}{log 2^m} < frac{2^{m + 1}}{log 2^{m + 1}}$$ by more than 2 for $m > 4$ suggests that there are at least two primes between $2^m$ and $2^{m + 1}$.



            Okay, so what if instead we choose the prime right below $2^m$? But thanks to 2 and $2^{m - 1}$, $p!$ has at least $m$ for 2's exponent in its factorization.



            Surely there are some gaps in the reasoning above, but I hope at least you find it illuminating.






            share|cite|improve this answer

























              up vote
              1
              down vote













              Obviously $p!$ is divisible by any $n leq p$. So we need only concern ourselves with $p < n < q$.



              As you have stipulated that $q$ is the very next prime greater than $p$, it follows that the numbers between $p$ and $q$ are composite numbers divisible only by primes less than or equal to $p$.



              So $gcd(n, p!) geq 2$. Here's where your question gets interesting: it might be possible that one of these $n$ is divisible by some prime $r < p$ but with a higher exponent than in $p!$.



              The likeliest candidate for such a prime is 2. Since $p$ is odd, $p!$ has $$2^frac{p - 1}{2}$$ as a divisor.



              But let's not forget that multiples of 4 contribute at least twice as much as singly even numbers to 2's exponent in $p!$. So, assuming $p equiv 1 bmod 4$, the larger number $$2^{frac{p - 1}{2} + frac{p - 1}{4}}$$ is also a divisor of $p!$ (just a small tweak if $p equiv 3 bmod 4$ instead).



              So the best chance to accumulate enough exponents of 2 would be with the very first prime greater than a given power of 2, let's say $2^m$. But no even number between $2^m$ and $2^{m + 1}$ has a higher exponent for 2 than $m$.



              I guess this is the point where we must invoke Bertrand's postulate... or maybe it's the prime number theorem that we need instead? The fact $$frac{2^m}{log 2^m} < frac{2^{m + 1}}{log 2^{m + 1}}$$ by more than 2 for $m > 4$ suggests that there are at least two primes between $2^m$ and $2^{m + 1}$.



              Okay, so what if instead we choose the prime right below $2^m$? But thanks to 2 and $2^{m - 1}$, $p!$ has at least $m$ for 2's exponent in its factorization.



              Surely there are some gaps in the reasoning above, but I hope at least you find it illuminating.






              share|cite|improve this answer























                up vote
                1
                down vote










                up vote
                1
                down vote









                Obviously $p!$ is divisible by any $n leq p$. So we need only concern ourselves with $p < n < q$.



                As you have stipulated that $q$ is the very next prime greater than $p$, it follows that the numbers between $p$ and $q$ are composite numbers divisible only by primes less than or equal to $p$.



                So $gcd(n, p!) geq 2$. Here's where your question gets interesting: it might be possible that one of these $n$ is divisible by some prime $r < p$ but with a higher exponent than in $p!$.



                The likeliest candidate for such a prime is 2. Since $p$ is odd, $p!$ has $$2^frac{p - 1}{2}$$ as a divisor.



                But let's not forget that multiples of 4 contribute at least twice as much as singly even numbers to 2's exponent in $p!$. So, assuming $p equiv 1 bmod 4$, the larger number $$2^{frac{p - 1}{2} + frac{p - 1}{4}}$$ is also a divisor of $p!$ (just a small tweak if $p equiv 3 bmod 4$ instead).



                So the best chance to accumulate enough exponents of 2 would be with the very first prime greater than a given power of 2, let's say $2^m$. But no even number between $2^m$ and $2^{m + 1}$ has a higher exponent for 2 than $m$.



                I guess this is the point where we must invoke Bertrand's postulate... or maybe it's the prime number theorem that we need instead? The fact $$frac{2^m}{log 2^m} < frac{2^{m + 1}}{log 2^{m + 1}}$$ by more than 2 for $m > 4$ suggests that there are at least two primes between $2^m$ and $2^{m + 1}$.



                Okay, so what if instead we choose the prime right below $2^m$? But thanks to 2 and $2^{m - 1}$, $p!$ has at least $m$ for 2's exponent in its factorization.



                Surely there are some gaps in the reasoning above, but I hope at least you find it illuminating.






                share|cite|improve this answer












                Obviously $p!$ is divisible by any $n leq p$. So we need only concern ourselves with $p < n < q$.



                As you have stipulated that $q$ is the very next prime greater than $p$, it follows that the numbers between $p$ and $q$ are composite numbers divisible only by primes less than or equal to $p$.



                So $gcd(n, p!) geq 2$. Here's where your question gets interesting: it might be possible that one of these $n$ is divisible by some prime $r < p$ but with a higher exponent than in $p!$.



                The likeliest candidate for such a prime is 2. Since $p$ is odd, $p!$ has $$2^frac{p - 1}{2}$$ as a divisor.



                But let's not forget that multiples of 4 contribute at least twice as much as singly even numbers to 2's exponent in $p!$. So, assuming $p equiv 1 bmod 4$, the larger number $$2^{frac{p - 1}{2} + frac{p - 1}{4}}$$ is also a divisor of $p!$ (just a small tweak if $p equiv 3 bmod 4$ instead).



                So the best chance to accumulate enough exponents of 2 would be with the very first prime greater than a given power of 2, let's say $2^m$. But no even number between $2^m$ and $2^{m + 1}$ has a higher exponent for 2 than $m$.



                I guess this is the point where we must invoke Bertrand's postulate... or maybe it's the prime number theorem that we need instead? The fact $$frac{2^m}{log 2^m} < frac{2^{m + 1}}{log 2^{m + 1}}$$ by more than 2 for $m > 4$ suggests that there are at least two primes between $2^m$ and $2^{m + 1}$.



                Okay, so what if instead we choose the prime right below $2^m$? But thanks to 2 and $2^{m - 1}$, $p!$ has at least $m$ for 2's exponent in its factorization.



                Surely there are some gaps in the reasoning above, but I hope at least you find it illuminating.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Nov 16 at 17:16









                Robert Soupe

                10.6k21949




                10.6k21949






























                     

                    draft saved


                    draft discarded



















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999871%2fdivisibility-of-prime-factorial%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

                    Plaza Victoria

                    Puebla de Zaragoza

                    Musa