Prove that there are infinitely many primes of the form $6n + 5$












6












$begingroup$


I know this is a duplicate but I had no idea what the other solution meant or how to go about approaching this problem. At first glance I thought about using Euclid's theorem that there are infinitely many primes and just doing proof by contradiction but I'm so confused right now. I'm horrible at math and I just want to understand how to approach this problem.
I've tried proof by contradiction: Assume that there are only a finite number of primes in the form of $6n+5$. But I'm just completely lost on what to do after this.



The original question: How do you prove that there are infinitely many primes of the form $5 + 6n$?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Please edit the question to include a link to the answer in the duplicate and explain to use just what you don't understand there. Without that information we would probably just suggest the same argument in an answer here.
    $endgroup$
    – Ethan Bolker
    Mar 1 '18 at 22:08










  • $begingroup$
    My apologies, I just updated the question to include the original solution.
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:11
















6












$begingroup$


I know this is a duplicate but I had no idea what the other solution meant or how to go about approaching this problem. At first glance I thought about using Euclid's theorem that there are infinitely many primes and just doing proof by contradiction but I'm so confused right now. I'm horrible at math and I just want to understand how to approach this problem.
I've tried proof by contradiction: Assume that there are only a finite number of primes in the form of $6n+5$. But I'm just completely lost on what to do after this.



The original question: How do you prove that there are infinitely many primes of the form $5 + 6n$?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Please edit the question to include a link to the answer in the duplicate and explain to use just what you don't understand there. Without that information we would probably just suggest the same argument in an answer here.
    $endgroup$
    – Ethan Bolker
    Mar 1 '18 at 22:08










  • $begingroup$
    My apologies, I just updated the question to include the original solution.
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:11














6












6








6


1



$begingroup$


I know this is a duplicate but I had no idea what the other solution meant or how to go about approaching this problem. At first glance I thought about using Euclid's theorem that there are infinitely many primes and just doing proof by contradiction but I'm so confused right now. I'm horrible at math and I just want to understand how to approach this problem.
I've tried proof by contradiction: Assume that there are only a finite number of primes in the form of $6n+5$. But I'm just completely lost on what to do after this.



The original question: How do you prove that there are infinitely many primes of the form $5 + 6n$?










share|cite|improve this question











$endgroup$




I know this is a duplicate but I had no idea what the other solution meant or how to go about approaching this problem. At first glance I thought about using Euclid's theorem that there are infinitely many primes and just doing proof by contradiction but I'm so confused right now. I'm horrible at math and I just want to understand how to approach this problem.
I've tried proof by contradiction: Assume that there are only a finite number of primes in the form of $6n+5$. But I'm just completely lost on what to do after this.



The original question: How do you prove that there are infinitely many primes of the form $5 + 6n$?







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








edited Mar 1 '18 at 22:11







notGoodAtMath

















asked Mar 1 '18 at 22:01









notGoodAtMathnotGoodAtMath

486




486












  • $begingroup$
    Please edit the question to include a link to the answer in the duplicate and explain to use just what you don't understand there. Without that information we would probably just suggest the same argument in an answer here.
    $endgroup$
    – Ethan Bolker
    Mar 1 '18 at 22:08










  • $begingroup$
    My apologies, I just updated the question to include the original solution.
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:11


















  • $begingroup$
    Please edit the question to include a link to the answer in the duplicate and explain to use just what you don't understand there. Without that information we would probably just suggest the same argument in an answer here.
    $endgroup$
    – Ethan Bolker
    Mar 1 '18 at 22:08










  • $begingroup$
    My apologies, I just updated the question to include the original solution.
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:11
















$begingroup$
Please edit the question to include a link to the answer in the duplicate and explain to use just what you don't understand there. Without that information we would probably just suggest the same argument in an answer here.
$endgroup$
– Ethan Bolker
Mar 1 '18 at 22:08




$begingroup$
Please edit the question to include a link to the answer in the duplicate and explain to use just what you don't understand there. Without that information we would probably just suggest the same argument in an answer here.
$endgroup$
– Ethan Bolker
Mar 1 '18 at 22:08












$begingroup$
My apologies, I just updated the question to include the original solution.
$endgroup$
– notGoodAtMath
Mar 1 '18 at 22:11




$begingroup$
My apologies, I just updated the question to include the original solution.
$endgroup$
– notGoodAtMath
Mar 1 '18 at 22:11










3 Answers
3






active

oldest

votes


















4












$begingroup$

First note that a prime of the form $6k+5$ is also of the form $6k-1$



Assume , there are only a finite many prime numbers of the form $6k-1$ and multiply them all together. The product must have residue $1$ or $5$ modulo $6$. If the residue is $1$, then subtract $2$. If the residue is $5$, then subtract $6$.



The resulting number is then greater than $1$ and of the form $6k+5$



It is easy to see that the resulting number cannot be divisible by $2$ or $3$, hence it must have prime factors of the form $6kpm1$. If all prime factors were of the form $6k+1$, the number would be congruent to $1$ modulo $6$, which is not the case.



Hence, there must be a prime of the form $6k+5$ dividing the number, but because of the subtraction of $2$ or $6$ it cannot be one of the primes in the product. This gives you the desired contradiction.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:22






  • 2




    $begingroup$
    $6k+5=6k+6-1=6(k+1)-1$
    $endgroup$
    – Peter
    Mar 1 '18 at 22:23



















3












$begingroup$

Note that the only primes not of the form $6npm 1$ are $2$ and $3$. A number of the form $6n+5$ is not divisible by $2$ or $3$.



Now note that the product $(6n+1)(6m+1)=36nm+6n+6m+1=6(6mn+m+n)+1$, and you can show by induction that any product of integers of the form $6n+1$ has the same form.



Any number of the form $6n+5=6(n+1)-1$ therefore has at least one prime factor of the form $6r+5$.



If you had a finite number of primes $p_i$ of the form $6r+5$ consider $n=4+prod p_i^2$



You should be able to prove that this is of the form $6m+5$ and is not divisible by any of the $p_i$ (or by $2$ or $3$), but it is divisible by a prime of the form $6k+5$.



The essential step is showing that you can find a number of the form $6m+5$ which is not divisible by any of the $p_i$.






share|cite|improve this answer









$endgroup$





















    -1












    $begingroup$

    If we cross out from sequence of positive integers all numbers divisible by 2 and all numbers divisible by 3, then all remaining numbers will be in one of two forms:



    $S1(n)=6n-1=5,11,17,...$ or $S2(n)=6n+1=7,13,19,$....$n=1, 2, 3,...$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.
    See link






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      [link](planet-source-code.com/vb/scripts/…) "download code"
      $endgroup$
      – Boris Sklyar
      Mar 15 at 14:45














    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%2f2672794%2fprove-that-there-are-infinitely-many-primes-of-the-form-6n-5%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    4












    $begingroup$

    First note that a prime of the form $6k+5$ is also of the form $6k-1$



    Assume , there are only a finite many prime numbers of the form $6k-1$ and multiply them all together. The product must have residue $1$ or $5$ modulo $6$. If the residue is $1$, then subtract $2$. If the residue is $5$, then subtract $6$.



    The resulting number is then greater than $1$ and of the form $6k+5$



    It is easy to see that the resulting number cannot be divisible by $2$ or $3$, hence it must have prime factors of the form $6kpm1$. If all prime factors were of the form $6k+1$, the number would be congruent to $1$ modulo $6$, which is not the case.



    Hence, there must be a prime of the form $6k+5$ dividing the number, but because of the subtraction of $2$ or $6$ it cannot be one of the primes in the product. This gives you the desired contradiction.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
      $endgroup$
      – notGoodAtMath
      Mar 1 '18 at 22:22






    • 2




      $begingroup$
      $6k+5=6k+6-1=6(k+1)-1$
      $endgroup$
      – Peter
      Mar 1 '18 at 22:23
















    4












    $begingroup$

    First note that a prime of the form $6k+5$ is also of the form $6k-1$



    Assume , there are only a finite many prime numbers of the form $6k-1$ and multiply them all together. The product must have residue $1$ or $5$ modulo $6$. If the residue is $1$, then subtract $2$. If the residue is $5$, then subtract $6$.



    The resulting number is then greater than $1$ and of the form $6k+5$



    It is easy to see that the resulting number cannot be divisible by $2$ or $3$, hence it must have prime factors of the form $6kpm1$. If all prime factors were of the form $6k+1$, the number would be congruent to $1$ modulo $6$, which is not the case.



    Hence, there must be a prime of the form $6k+5$ dividing the number, but because of the subtraction of $2$ or $6$ it cannot be one of the primes in the product. This gives you the desired contradiction.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
      $endgroup$
      – notGoodAtMath
      Mar 1 '18 at 22:22






    • 2




      $begingroup$
      $6k+5=6k+6-1=6(k+1)-1$
      $endgroup$
      – Peter
      Mar 1 '18 at 22:23














    4












    4








    4





    $begingroup$

    First note that a prime of the form $6k+5$ is also of the form $6k-1$



    Assume , there are only a finite many prime numbers of the form $6k-1$ and multiply them all together. The product must have residue $1$ or $5$ modulo $6$. If the residue is $1$, then subtract $2$. If the residue is $5$, then subtract $6$.



    The resulting number is then greater than $1$ and of the form $6k+5$



    It is easy to see that the resulting number cannot be divisible by $2$ or $3$, hence it must have prime factors of the form $6kpm1$. If all prime factors were of the form $6k+1$, the number would be congruent to $1$ modulo $6$, which is not the case.



    Hence, there must be a prime of the form $6k+5$ dividing the number, but because of the subtraction of $2$ or $6$ it cannot be one of the primes in the product. This gives you the desired contradiction.






    share|cite|improve this answer











    $endgroup$



    First note that a prime of the form $6k+5$ is also of the form $6k-1$



    Assume , there are only a finite many prime numbers of the form $6k-1$ and multiply them all together. The product must have residue $1$ or $5$ modulo $6$. If the residue is $1$, then subtract $2$. If the residue is $5$, then subtract $6$.



    The resulting number is then greater than $1$ and of the form $6k+5$



    It is easy to see that the resulting number cannot be divisible by $2$ or $3$, hence it must have prime factors of the form $6kpm1$. If all prime factors were of the form $6k+1$, the number would be congruent to $1$ modulo $6$, which is not the case.



    Hence, there must be a prime of the form $6k+5$ dividing the number, but because of the subtraction of $2$ or $6$ it cannot be one of the primes in the product. This gives you the desired contradiction.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Mar 1 '18 at 22:15

























    answered Mar 1 '18 at 22:09









    PeterPeter

    48.8k1240137




    48.8k1240137












    • $begingroup$
      I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
      $endgroup$
      – notGoodAtMath
      Mar 1 '18 at 22:22






    • 2




      $begingroup$
      $6k+5=6k+6-1=6(k+1)-1$
      $endgroup$
      – Peter
      Mar 1 '18 at 22:23


















    • $begingroup$
      I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
      $endgroup$
      – notGoodAtMath
      Mar 1 '18 at 22:22






    • 2




      $begingroup$
      $6k+5=6k+6-1=6(k+1)-1$
      $endgroup$
      – Peter
      Mar 1 '18 at 22:23
















    $begingroup$
    I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:22




    $begingroup$
    I'm afraid I'll be asking a stupid question, but why is a prime of the form 6k+5 also of the form 6k-1? Is this due to some fundamental theorems I'm missing or am I just overthinking things?
    $endgroup$
    – notGoodAtMath
    Mar 1 '18 at 22:22




    2




    2




    $begingroup$
    $6k+5=6k+6-1=6(k+1)-1$
    $endgroup$
    – Peter
    Mar 1 '18 at 22:23




    $begingroup$
    $6k+5=6k+6-1=6(k+1)-1$
    $endgroup$
    – Peter
    Mar 1 '18 at 22:23











    3












    $begingroup$

    Note that the only primes not of the form $6npm 1$ are $2$ and $3$. A number of the form $6n+5$ is not divisible by $2$ or $3$.



    Now note that the product $(6n+1)(6m+1)=36nm+6n+6m+1=6(6mn+m+n)+1$, and you can show by induction that any product of integers of the form $6n+1$ has the same form.



    Any number of the form $6n+5=6(n+1)-1$ therefore has at least one prime factor of the form $6r+5$.



    If you had a finite number of primes $p_i$ of the form $6r+5$ consider $n=4+prod p_i^2$



    You should be able to prove that this is of the form $6m+5$ and is not divisible by any of the $p_i$ (or by $2$ or $3$), but it is divisible by a prime of the form $6k+5$.



    The essential step is showing that you can find a number of the form $6m+5$ which is not divisible by any of the $p_i$.






    share|cite|improve this answer









    $endgroup$


















      3












      $begingroup$

      Note that the only primes not of the form $6npm 1$ are $2$ and $3$. A number of the form $6n+5$ is not divisible by $2$ or $3$.



      Now note that the product $(6n+1)(6m+1)=36nm+6n+6m+1=6(6mn+m+n)+1$, and you can show by induction that any product of integers of the form $6n+1$ has the same form.



      Any number of the form $6n+5=6(n+1)-1$ therefore has at least one prime factor of the form $6r+5$.



      If you had a finite number of primes $p_i$ of the form $6r+5$ consider $n=4+prod p_i^2$



      You should be able to prove that this is of the form $6m+5$ and is not divisible by any of the $p_i$ (or by $2$ or $3$), but it is divisible by a prime of the form $6k+5$.



      The essential step is showing that you can find a number of the form $6m+5$ which is not divisible by any of the $p_i$.






      share|cite|improve this answer









      $endgroup$
















        3












        3








        3





        $begingroup$

        Note that the only primes not of the form $6npm 1$ are $2$ and $3$. A number of the form $6n+5$ is not divisible by $2$ or $3$.



        Now note that the product $(6n+1)(6m+1)=36nm+6n+6m+1=6(6mn+m+n)+1$, and you can show by induction that any product of integers of the form $6n+1$ has the same form.



        Any number of the form $6n+5=6(n+1)-1$ therefore has at least one prime factor of the form $6r+5$.



        If you had a finite number of primes $p_i$ of the form $6r+5$ consider $n=4+prod p_i^2$



        You should be able to prove that this is of the form $6m+5$ and is not divisible by any of the $p_i$ (or by $2$ or $3$), but it is divisible by a prime of the form $6k+5$.



        The essential step is showing that you can find a number of the form $6m+5$ which is not divisible by any of the $p_i$.






        share|cite|improve this answer









        $endgroup$



        Note that the only primes not of the form $6npm 1$ are $2$ and $3$. A number of the form $6n+5$ is not divisible by $2$ or $3$.



        Now note that the product $(6n+1)(6m+1)=36nm+6n+6m+1=6(6mn+m+n)+1$, and you can show by induction that any product of integers of the form $6n+1$ has the same form.



        Any number of the form $6n+5=6(n+1)-1$ therefore has at least one prime factor of the form $6r+5$.



        If you had a finite number of primes $p_i$ of the form $6r+5$ consider $n=4+prod p_i^2$



        You should be able to prove that this is of the form $6m+5$ and is not divisible by any of the $p_i$ (or by $2$ or $3$), but it is divisible by a prime of the form $6k+5$.



        The essential step is showing that you can find a number of the form $6m+5$ which is not divisible by any of the $p_i$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Mar 1 '18 at 22:13









        Mark BennetMark Bennet

        81.9k984183




        81.9k984183























            -1












            $begingroup$

            If we cross out from sequence of positive integers all numbers divisible by 2 and all numbers divisible by 3, then all remaining numbers will be in one of two forms:



            $S1(n)=6n-1=5,11,17,...$ or $S2(n)=6n+1=7,13,19,$....$n=1, 2, 3,...$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.
            See link






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              [link](planet-source-code.com/vb/scripts/…) "download code"
              $endgroup$
              – Boris Sklyar
              Mar 15 at 14:45


















            -1












            $begingroup$

            If we cross out from sequence of positive integers all numbers divisible by 2 and all numbers divisible by 3, then all remaining numbers will be in one of two forms:



            $S1(n)=6n-1=5,11,17,...$ or $S2(n)=6n+1=7,13,19,$....$n=1, 2, 3,...$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.
            See link






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              [link](planet-source-code.com/vb/scripts/…) "download code"
              $endgroup$
              – Boris Sklyar
              Mar 15 at 14:45
















            -1












            -1








            -1





            $begingroup$

            If we cross out from sequence of positive integers all numbers divisible by 2 and all numbers divisible by 3, then all remaining numbers will be in one of two forms:



            $S1(n)=6n-1=5,11,17,...$ or $S2(n)=6n+1=7,13,19,$....$n=1, 2, 3,...$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.
            See link






            share|cite|improve this answer











            $endgroup$



            If we cross out from sequence of positive integers all numbers divisible by 2 and all numbers divisible by 3, then all remaining numbers will be in one of two forms:



            $S1(n)=6n-1=5,11,17,...$ or $S2(n)=6n+1=7,13,19,$....$n=1, 2, 3,...$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $S1(n)$ to number of primes in the sequence $S2(n)$ tends to be $1$.
            See link







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Mar 15 at 14:44

























            answered Mar 15 at 14:10









            Boris SklyarBoris Sklyar

            2715




            2715












            • $begingroup$
              [link](planet-source-code.com/vb/scripts/…) "download code"
              $endgroup$
              – Boris Sklyar
              Mar 15 at 14:45




















            • $begingroup$
              [link](planet-source-code.com/vb/scripts/…) "download code"
              $endgroup$
              – Boris Sklyar
              Mar 15 at 14:45


















            $begingroup$
            [link](planet-source-code.com/vb/scripts/…) "download code"
            $endgroup$
            – Boris Sklyar
            Mar 15 at 14:45






            $begingroup$
            [link](planet-source-code.com/vb/scripts/…) "download code"
            $endgroup$
            – Boris Sklyar
            Mar 15 at 14:45




















            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2672794%2fprove-that-there-are-infinitely-many-primes-of-the-form-6n-5%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

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

            Aardman Animations

            Are they similar matrix