Why is the list $1+N,1+2N, dots, 1+(n+1)N$ relatively prime?












1














I was reading:




Take $N in mathbf N$ such that $a_i leq N$ for all $i leq n$ and N
is a multiple of every prime number ≤ n. We claim that then 1 + N, 1 +
2N, . . . , 1 + nN, 1 + (n + 1)N are pairwise relatively prime. To see
this, suppose p is a prime number such that p | 1+iN and p | 1+jN (1 ≤
i < j ≤ n+ 1); then p divides their difference (j − i)N, but p ≡ 1 mod
N, so p does not divide N, hence p | j − i ≤ n. But all prime numbers
≤ n divide N, and we have a contradiction




however, it didn't really make sense to me.



My confusion is where:



$$p equiv 1 pmod N$$



came from and how it contributed to the proof. Why does it matter that that if $p equiv 1 mod N$ is true then $p$ doesn't divide $N$?



I feel this suppose to be a pretty elementary proof but it is escaping me. What is the simplest way to see this proof? Or what step is the proof skipping? I know this suppose to be easy but something is escaping me....





context:



https://faculty.math.illinois.edu/~vddries/main.pdf










share|cite|improve this question
























  • why is $p equiv 1 pmod N$ mentioned?
    – Pinocchio
    Nov 26 at 21:03


















1














I was reading:




Take $N in mathbf N$ such that $a_i leq N$ for all $i leq n$ and N
is a multiple of every prime number ≤ n. We claim that then 1 + N, 1 +
2N, . . . , 1 + nN, 1 + (n + 1)N are pairwise relatively prime. To see
this, suppose p is a prime number such that p | 1+iN and p | 1+jN (1 ≤
i < j ≤ n+ 1); then p divides their difference (j − i)N, but p ≡ 1 mod
N, so p does not divide N, hence p | j − i ≤ n. But all prime numbers
≤ n divide N, and we have a contradiction




however, it didn't really make sense to me.



My confusion is where:



$$p equiv 1 pmod N$$



came from and how it contributed to the proof. Why does it matter that that if $p equiv 1 mod N$ is true then $p$ doesn't divide $N$?



I feel this suppose to be a pretty elementary proof but it is escaping me. What is the simplest way to see this proof? Or what step is the proof skipping? I know this suppose to be easy but something is escaping me....





context:



https://faculty.math.illinois.edu/~vddries/main.pdf










share|cite|improve this question
























  • why is $p equiv 1 pmod N$ mentioned?
    – Pinocchio
    Nov 26 at 21:03
















1












1








1







I was reading:




Take $N in mathbf N$ such that $a_i leq N$ for all $i leq n$ and N
is a multiple of every prime number ≤ n. We claim that then 1 + N, 1 +
2N, . . . , 1 + nN, 1 + (n + 1)N are pairwise relatively prime. To see
this, suppose p is a prime number such that p | 1+iN and p | 1+jN (1 ≤
i < j ≤ n+ 1); then p divides their difference (j − i)N, but p ≡ 1 mod
N, so p does not divide N, hence p | j − i ≤ n. But all prime numbers
≤ n divide N, and we have a contradiction




however, it didn't really make sense to me.



My confusion is where:



$$p equiv 1 pmod N$$



came from and how it contributed to the proof. Why does it matter that that if $p equiv 1 mod N$ is true then $p$ doesn't divide $N$?



I feel this suppose to be a pretty elementary proof but it is escaping me. What is the simplest way to see this proof? Or what step is the proof skipping? I know this suppose to be easy but something is escaping me....





context:



https://faculty.math.illinois.edu/~vddries/main.pdf










share|cite|improve this question















I was reading:




Take $N in mathbf N$ such that $a_i leq N$ for all $i leq n$ and N
is a multiple of every prime number ≤ n. We claim that then 1 + N, 1 +
2N, . . . , 1 + nN, 1 + (n + 1)N are pairwise relatively prime. To see
this, suppose p is a prime number such that p | 1+iN and p | 1+jN (1 ≤
i < j ≤ n+ 1); then p divides their difference (j − i)N, but p ≡ 1 mod
N, so p does not divide N, hence p | j − i ≤ n. But all prime numbers
≤ n divide N, and we have a contradiction




however, it didn't really make sense to me.



My confusion is where:



$$p equiv 1 pmod N$$



came from and how it contributed to the proof. Why does it matter that that if $p equiv 1 mod N$ is true then $p$ doesn't divide $N$?



I feel this suppose to be a pretty elementary proof but it is escaping me. What is the simplest way to see this proof? Or what step is the proof skipping? I know this suppose to be easy but something is escaping me....





context:



https://faculty.math.illinois.edu/~vddries/main.pdf







elementary-number-theory proof-explanation






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 24 at 3:32

























asked Nov 24 at 1:47









Pinocchio

1,88021754




1,88021754












  • why is $p equiv 1 pmod N$ mentioned?
    – Pinocchio
    Nov 26 at 21:03




















  • why is $p equiv 1 pmod N$ mentioned?
    – Pinocchio
    Nov 26 at 21:03


















why is $p equiv 1 pmod N$ mentioned?
– Pinocchio
Nov 26 at 21:03






why is $p equiv 1 pmod N$ mentioned?
– Pinocchio
Nov 26 at 21:03












2 Answers
2






active

oldest

votes


















2














All you need is the conclusion that $p$ does not divide $N.$ It is enough to show that $gcd(p,N) = 1.$ Now, as there is an integer $t$ such that $pt = 1 + jN,$ we arrive at the Bezout expression
$$ pt - jN = 1 $$
which does the trick. See how, if $p|N,$ Bezout would force $p|1.$



Meanwhile, $N$ is divisible by all primes up to little $n.$ Since $p$ does not divide $N,$ we find that $$ p > n ; . $$
This leads to a contradiction when $p |(j-i) leq n$



I do not see any reason to conclude that $p equiv 1 pmod N.$ That sort of thing happens when $N$ divides something involving $p,$ not when $p $ divides something involving $N.$






share|cite|improve this answer























  • I still don't understand why they are coprime. How does your answer show that?
    – Pinocchio
    Nov 24 at 3:06










  • why is $gcd(p,N) = 1$ enough?
    – Pinocchio
    Nov 24 at 3:17










  • but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
    – Pinocchio
    Nov 24 at 3:23










  • why does the text mention $p equiv 1 pmod N$
    – Pinocchio
    Nov 24 at 3:24










  • @Pinocchio what text is this? Is it the main text or a solution section?
    – Will Jagy
    Nov 24 at 3:25



















0














We want to show:



$$ 1+N, 1+2N, dots, 1+(n+1)N$$



is coprime (i.e. share no common factors). It's sufficient to show they don't share a common prime factor (since all other factors are made of primes, since if its a factor of a specific number then that number can be turned to primes and those divide the number in question. So if the building blocks don't divide the number no other number does either).



Consider any pair $1 + iN,1+jN$ ($0 leq i,j leq n+1)$ and any prime $p$ less than either number in the pair. For the sake of contradiction suppose $p | 1+iN$ and $p | 1+Nj$. This means $1+Nj = p t_j$ and $1+Ni = p t_i$. We also have $p$ divides the difference:



$$ p | N (i-j) $$



so $p|N$ or $p|i-j$ (since $p$ is prime i.e. "atomic"). Notice from earlier facts that $1 = Nj - p t_j $ is true so if $p|N$ we'd get that $p$ divides $1$ which is absurd because $p$ is prime. So $p not mid N$. So $p | i - j$. Notice that $i,j$ are between 1 to n so their difference is less that $n$. So $p | i - j leq n$ which means $p$ must be less than $n$. But that can't be true either because $N$ is a multiple of all primes less than $n$ and if $p leq n$ and is prime, then it must divide $N$. So contradicts an earlier fact we derived. Thus, this sequence must be coprime $ 1+N, 1+2N, dots, 1+(n+1)N$ (share no common factors, especially a prime factor which is what we showed explicitly).






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%2f3011080%2fwhy-is-the-list-1n-12n-dots-1n1n-relatively-prime%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









    2














    All you need is the conclusion that $p$ does not divide $N.$ It is enough to show that $gcd(p,N) = 1.$ Now, as there is an integer $t$ such that $pt = 1 + jN,$ we arrive at the Bezout expression
    $$ pt - jN = 1 $$
    which does the trick. See how, if $p|N,$ Bezout would force $p|1.$



    Meanwhile, $N$ is divisible by all primes up to little $n.$ Since $p$ does not divide $N,$ we find that $$ p > n ; . $$
    This leads to a contradiction when $p |(j-i) leq n$



    I do not see any reason to conclude that $p equiv 1 pmod N.$ That sort of thing happens when $N$ divides something involving $p,$ not when $p $ divides something involving $N.$






    share|cite|improve this answer























    • I still don't understand why they are coprime. How does your answer show that?
      – Pinocchio
      Nov 24 at 3:06










    • why is $gcd(p,N) = 1$ enough?
      – Pinocchio
      Nov 24 at 3:17










    • but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
      – Pinocchio
      Nov 24 at 3:23










    • why does the text mention $p equiv 1 pmod N$
      – Pinocchio
      Nov 24 at 3:24










    • @Pinocchio what text is this? Is it the main text or a solution section?
      – Will Jagy
      Nov 24 at 3:25
















    2














    All you need is the conclusion that $p$ does not divide $N.$ It is enough to show that $gcd(p,N) = 1.$ Now, as there is an integer $t$ such that $pt = 1 + jN,$ we arrive at the Bezout expression
    $$ pt - jN = 1 $$
    which does the trick. See how, if $p|N,$ Bezout would force $p|1.$



    Meanwhile, $N$ is divisible by all primes up to little $n.$ Since $p$ does not divide $N,$ we find that $$ p > n ; . $$
    This leads to a contradiction when $p |(j-i) leq n$



    I do not see any reason to conclude that $p equiv 1 pmod N.$ That sort of thing happens when $N$ divides something involving $p,$ not when $p $ divides something involving $N.$






    share|cite|improve this answer























    • I still don't understand why they are coprime. How does your answer show that?
      – Pinocchio
      Nov 24 at 3:06










    • why is $gcd(p,N) = 1$ enough?
      – Pinocchio
      Nov 24 at 3:17










    • but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
      – Pinocchio
      Nov 24 at 3:23










    • why does the text mention $p equiv 1 pmod N$
      – Pinocchio
      Nov 24 at 3:24










    • @Pinocchio what text is this? Is it the main text or a solution section?
      – Will Jagy
      Nov 24 at 3:25














    2












    2








    2






    All you need is the conclusion that $p$ does not divide $N.$ It is enough to show that $gcd(p,N) = 1.$ Now, as there is an integer $t$ such that $pt = 1 + jN,$ we arrive at the Bezout expression
    $$ pt - jN = 1 $$
    which does the trick. See how, if $p|N,$ Bezout would force $p|1.$



    Meanwhile, $N$ is divisible by all primes up to little $n.$ Since $p$ does not divide $N,$ we find that $$ p > n ; . $$
    This leads to a contradiction when $p |(j-i) leq n$



    I do not see any reason to conclude that $p equiv 1 pmod N.$ That sort of thing happens when $N$ divides something involving $p,$ not when $p $ divides something involving $N.$






    share|cite|improve this answer














    All you need is the conclusion that $p$ does not divide $N.$ It is enough to show that $gcd(p,N) = 1.$ Now, as there is an integer $t$ such that $pt = 1 + jN,$ we arrive at the Bezout expression
    $$ pt - jN = 1 $$
    which does the trick. See how, if $p|N,$ Bezout would force $p|1.$



    Meanwhile, $N$ is divisible by all primes up to little $n.$ Since $p$ does not divide $N,$ we find that $$ p > n ; . $$
    This leads to a contradiction when $p |(j-i) leq n$



    I do not see any reason to conclude that $p equiv 1 pmod N.$ That sort of thing happens when $N$ divides something involving $p,$ not when $p $ divides something involving $N.$







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Nov 24 at 3:25

























    answered Nov 24 at 2:12









    Will Jagy

    101k599199




    101k599199












    • I still don't understand why they are coprime. How does your answer show that?
      – Pinocchio
      Nov 24 at 3:06










    • why is $gcd(p,N) = 1$ enough?
      – Pinocchio
      Nov 24 at 3:17










    • but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
      – Pinocchio
      Nov 24 at 3:23










    • why does the text mention $p equiv 1 pmod N$
      – Pinocchio
      Nov 24 at 3:24










    • @Pinocchio what text is this? Is it the main text or a solution section?
      – Will Jagy
      Nov 24 at 3:25


















    • I still don't understand why they are coprime. How does your answer show that?
      – Pinocchio
      Nov 24 at 3:06










    • why is $gcd(p,N) = 1$ enough?
      – Pinocchio
      Nov 24 at 3:17










    • but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
      – Pinocchio
      Nov 24 at 3:23










    • why does the text mention $p equiv 1 pmod N$
      – Pinocchio
      Nov 24 at 3:24










    • @Pinocchio what text is this? Is it the main text or a solution section?
      – Will Jagy
      Nov 24 at 3:25
















    I still don't understand why they are coprime. How does your answer show that?
    – Pinocchio
    Nov 24 at 3:06




    I still don't understand why they are coprime. How does your answer show that?
    – Pinocchio
    Nov 24 at 3:06












    why is $gcd(p,N) = 1$ enough?
    – Pinocchio
    Nov 24 at 3:17




    why is $gcd(p,N) = 1$ enough?
    – Pinocchio
    Nov 24 at 3:17












    but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
    – Pinocchio
    Nov 24 at 3:23




    but $N$ is a multiple of every prime $leq n$...shouldn't $p$ divide $N$?
    – Pinocchio
    Nov 24 at 3:23












    why does the text mention $p equiv 1 pmod N$
    – Pinocchio
    Nov 24 at 3:24




    why does the text mention $p equiv 1 pmod N$
    – Pinocchio
    Nov 24 at 3:24












    @Pinocchio what text is this? Is it the main text or a solution section?
    – Will Jagy
    Nov 24 at 3:25




    @Pinocchio what text is this? Is it the main text or a solution section?
    – Will Jagy
    Nov 24 at 3:25











    0














    We want to show:



    $$ 1+N, 1+2N, dots, 1+(n+1)N$$



    is coprime (i.e. share no common factors). It's sufficient to show they don't share a common prime factor (since all other factors are made of primes, since if its a factor of a specific number then that number can be turned to primes and those divide the number in question. So if the building blocks don't divide the number no other number does either).



    Consider any pair $1 + iN,1+jN$ ($0 leq i,j leq n+1)$ and any prime $p$ less than either number in the pair. For the sake of contradiction suppose $p | 1+iN$ and $p | 1+Nj$. This means $1+Nj = p t_j$ and $1+Ni = p t_i$. We also have $p$ divides the difference:



    $$ p | N (i-j) $$



    so $p|N$ or $p|i-j$ (since $p$ is prime i.e. "atomic"). Notice from earlier facts that $1 = Nj - p t_j $ is true so if $p|N$ we'd get that $p$ divides $1$ which is absurd because $p$ is prime. So $p not mid N$. So $p | i - j$. Notice that $i,j$ are between 1 to n so their difference is less that $n$. So $p | i - j leq n$ which means $p$ must be less than $n$. But that can't be true either because $N$ is a multiple of all primes less than $n$ and if $p leq n$ and is prime, then it must divide $N$. So contradicts an earlier fact we derived. Thus, this sequence must be coprime $ 1+N, 1+2N, dots, 1+(n+1)N$ (share no common factors, especially a prime factor which is what we showed explicitly).






    share|cite|improve this answer


























      0














      We want to show:



      $$ 1+N, 1+2N, dots, 1+(n+1)N$$



      is coprime (i.e. share no common factors). It's sufficient to show they don't share a common prime factor (since all other factors are made of primes, since if its a factor of a specific number then that number can be turned to primes and those divide the number in question. So if the building blocks don't divide the number no other number does either).



      Consider any pair $1 + iN,1+jN$ ($0 leq i,j leq n+1)$ and any prime $p$ less than either number in the pair. For the sake of contradiction suppose $p | 1+iN$ and $p | 1+Nj$. This means $1+Nj = p t_j$ and $1+Ni = p t_i$. We also have $p$ divides the difference:



      $$ p | N (i-j) $$



      so $p|N$ or $p|i-j$ (since $p$ is prime i.e. "atomic"). Notice from earlier facts that $1 = Nj - p t_j $ is true so if $p|N$ we'd get that $p$ divides $1$ which is absurd because $p$ is prime. So $p not mid N$. So $p | i - j$. Notice that $i,j$ are between 1 to n so their difference is less that $n$. So $p | i - j leq n$ which means $p$ must be less than $n$. But that can't be true either because $N$ is a multiple of all primes less than $n$ and if $p leq n$ and is prime, then it must divide $N$. So contradicts an earlier fact we derived. Thus, this sequence must be coprime $ 1+N, 1+2N, dots, 1+(n+1)N$ (share no common factors, especially a prime factor which is what we showed explicitly).






      share|cite|improve this answer
























        0












        0








        0






        We want to show:



        $$ 1+N, 1+2N, dots, 1+(n+1)N$$



        is coprime (i.e. share no common factors). It's sufficient to show they don't share a common prime factor (since all other factors are made of primes, since if its a factor of a specific number then that number can be turned to primes and those divide the number in question. So if the building blocks don't divide the number no other number does either).



        Consider any pair $1 + iN,1+jN$ ($0 leq i,j leq n+1)$ and any prime $p$ less than either number in the pair. For the sake of contradiction suppose $p | 1+iN$ and $p | 1+Nj$. This means $1+Nj = p t_j$ and $1+Ni = p t_i$. We also have $p$ divides the difference:



        $$ p | N (i-j) $$



        so $p|N$ or $p|i-j$ (since $p$ is prime i.e. "atomic"). Notice from earlier facts that $1 = Nj - p t_j $ is true so if $p|N$ we'd get that $p$ divides $1$ which is absurd because $p$ is prime. So $p not mid N$. So $p | i - j$. Notice that $i,j$ are between 1 to n so their difference is less that $n$. So $p | i - j leq n$ which means $p$ must be less than $n$. But that can't be true either because $N$ is a multiple of all primes less than $n$ and if $p leq n$ and is prime, then it must divide $N$. So contradicts an earlier fact we derived. Thus, this sequence must be coprime $ 1+N, 1+2N, dots, 1+(n+1)N$ (share no common factors, especially a prime factor which is what we showed explicitly).






        share|cite|improve this answer












        We want to show:



        $$ 1+N, 1+2N, dots, 1+(n+1)N$$



        is coprime (i.e. share no common factors). It's sufficient to show they don't share a common prime factor (since all other factors are made of primes, since if its a factor of a specific number then that number can be turned to primes and those divide the number in question. So if the building blocks don't divide the number no other number does either).



        Consider any pair $1 + iN,1+jN$ ($0 leq i,j leq n+1)$ and any prime $p$ less than either number in the pair. For the sake of contradiction suppose $p | 1+iN$ and $p | 1+Nj$. This means $1+Nj = p t_j$ and $1+Ni = p t_i$. We also have $p$ divides the difference:



        $$ p | N (i-j) $$



        so $p|N$ or $p|i-j$ (since $p$ is prime i.e. "atomic"). Notice from earlier facts that $1 = Nj - p t_j $ is true so if $p|N$ we'd get that $p$ divides $1$ which is absurd because $p$ is prime. So $p not mid N$. So $p | i - j$. Notice that $i,j$ are between 1 to n so their difference is less that $n$. So $p | i - j leq n$ which means $p$ must be less than $n$. But that can't be true either because $N$ is a multiple of all primes less than $n$ and if $p leq n$ and is prime, then it must divide $N$. So contradicts an earlier fact we derived. Thus, this sequence must be coprime $ 1+N, 1+2N, dots, 1+(n+1)N$ (share no common factors, especially a prime factor which is what we showed explicitly).







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 24 at 3:50









        Pinocchio

        1,88021754




        1,88021754






























            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%2f3011080%2fwhy-is-the-list-1n-12n-dots-1n1n-relatively-prime%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