Counting lattice points with relatively prime coordinates The Next CEO of Stack...

Can this transistor (2N2222) take 6 V on emitter-base? Am I reading the datasheet incorrectly?

How to unfasten electrical subpanel attached with ramset

How seriously should I take size and weight limits of hand luggage?

Is it possible to create a QR code using text?

Compensation for working overtime on Saturdays

logical reads on global temp table, but not on session-level temp table

Salesforce opportunity stages

How dangerous is XSS

What difference does it make matching a word with/without a trailing whitespace?

Finitely generated matrix groups whose eigenvalues are all algebraic

Is it a bad idea to plug the other end of ESD strap to wall ground?

How should I connect my cat5 cable to connectors having an orange-green line?

Is it okay to majorly distort historical facts while writing a fiction story?

My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?

Direct Implications Between USA and UK in Event of No-Deal Brexit

How does a dynamic QR code work?

Does Germany produce more waste than the US?

How to pronounce fünf in 45

Why can't we say "I have been having a dog"?

Man transported from Alternate World into ours by a Neutrino Detector

Why doesn't Shulchan Aruch include the laws of destroying fruit trees?

What did the word "leisure" mean in late 18th Century usage?

Is it correct to say moon starry nights?

How can the PCs determine if an item is a phylactery?



Counting lattice points with relatively prime coordinates



The Next CEO of Stack OverflowCounting Lattice Points with Ehrhart PolynomialsFinding a set of subsets such that for each such subset in the set, there exists another subset in the same set which is non-disjointConcise proof that every common divisor divides GCD without Bezout's identity?counting lattice paths with turnsFind the condition for a center of a circle with exactly one lattice point on its circumferenceUnderstanding the proof of unique natural divisorConditions for $(I+K)cap (J+K) = Icap J +K $ to hold for ideals of ring $R$Probabilistic/combinatoric proof of $sum_{k=0}^{n}binom{tk+r}{k}binom{t(n-k)+s}{n-k}frac{r}{tk+r}=binom{tn+r+s}{n}$A proof of a simple combinatorial lemmaCounting Lattice Points












2












$begingroup$


My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.




Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
, : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
$$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
gcd(x,y) = 1, text{ and } x+y > n}$$ Then, we have $|S| = |R| + 1$.




Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$



We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.



Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$






combinatorics elementary-number-theory







share|cite|improve this question











$endgroup$

















    2












    $begingroup$


    My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.




    Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
    , : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
    $$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
    gcd(x,y) = 1, text{ and } x+y > n}$$     Then, we have $|S| = |R| + 1$.




    Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$



    We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.



    Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$






    combinatorics elementary-number-theory







    share|cite|improve this question











    $endgroup$















      2












      2








      2


      1



      $begingroup$


      My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.




      Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
      , : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
      $$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
      gcd(x,y) = 1, text{ and } x+y > n}$$       Then, we have $|S| = |R| + 1$.




      Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$



      We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.



      Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$






      combinatorics elementary-number-theory







      share|cite|improve this question











      $endgroup$




      My Question: Here is a fact, and a proof of said fact. I am wondering if someone can provide a cleaner/less convoluted argument, as it seems to me like a fact that ought to possess a very simple proof. Actually, it would be nice to see any substantially different proof.




      Fact: Consider the sets of lattice points $$R = {(x,y) in mathbb{N}^{2}
      , : , 1le x, y le n , , gcd(x,y) = 1, text{ and } x+yleq n}$$
      $$S = {(x,y) in mathbb{N}^{2} , : , 1le x, y le n , ,
      gcd(x,y) = 1, text{ and } x+y > n}$$       Then, we have $|S| = |R| + 1$.




      Proof: For each $k in mathbb{N}$, we have the sets $$S_{k} = left{(x,y) in S , : , k le frac{x}{y} < k+1right}$$ $$R_{k, <} = left{(x,y) in R , : , kle frac{n-x}{y} < k+1 , ,, x<yright}$$



      We have a map $f_k : S_k to R_{k,<}$ sending $(x,y) mapsto (x-ky, y)$, which is in fact a bijection for $kneq n$, with inverse $(x,y) mapsto (x+ky, y)$. When $k = n$, it is almost a bijection, i.e. $f_n$ is a bijection from $S_n setminus {(n,1)}$ onto $R_{n, <}$.



      Since we have disjoint unions $$bigcup_{kge 1} R_{k,<} = R cap {x<y}$$ $$bigcup_{kge 1} S_k = S cap {xge y}$$ it follows that $|R cap {x<y}| = |S cap {xge y}| - 1$. Noting that $|R cap {x<y}| = |R cap {x>y}|$ via the map $(x,y) mapsto (y,x)$, and similarly $|S cap {xge y}| = |S cap {x < y}|$, it follows that (taking care not to forget $(1,1) in R$) we have $$|R| = 1+ 2|R cap {x<y}| = 1+2(|Scap {xge y}| - 1) = |S| - 1$$ as desired. $blacksquare$






      combinatorics elementary-number-theory




      combinatorics elementary-number-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Mar 18 at 2:09







      Sameer Kailasa

















      asked Mar 18 at 1:32









      Sameer KailasaSameer Kailasa

      5,59321843




      5,59321843






















          1 Answer
          1






          active

          oldest

          votes


















          0












          $begingroup$

          A heuristic start:



          Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.






          share|cite|improve this answer









          $endgroup$














            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%2f3152297%2fcounting-lattice-points-with-relatively-prime-coordinates%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            0












            $begingroup$

            A heuristic start:



            Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.






            share|cite|improve this answer









            $endgroup$


















              0












              $begingroup$

              A heuristic start:



              Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.






              share|cite|improve this answer









              $endgroup$
















                0












                0








                0





                $begingroup$

                A heuristic start:



                Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.






                share|cite|improve this answer









                $endgroup$



                A heuristic start:



                Note, that you form a diagonal line with the equals of the first set. This line has $frac{n(n-1)}{2}$ points, on or below it. The total lattice has $n^2$ so in theory $n^2-n(n-1)=1$ but that's false (it's actually n). What we failed to consider, is coprimality that will decrease the numbers.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Mar 18 at 13:15









                Roddy MacPheeRoddy MacPhee

                629118




                629118






























                    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%2f3152297%2fcounting-lattice-points-with-relatively-prime-coordinates%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

                    Nidaros erkebispedøme

                    Image
                    For det lutherske bispedømet, sjå Nidaros bispedøme. Nidaros erkebispedøme var eit katolsk erkebispedøme med sete i Nidaros. Det vart oppretta av kong Olav Kyrre mellom 1070 og 1080 som bispedøme. Bispedømet vart opphøgd til erkebispedøme i 1153. Erkebispedømet vart innstifta av pave Anastasius IV i 1154, og var i funksjon fram til reformasjonen i 1537. Erkebiskopen sitt hovudsete var Erkebispegarden, rett ved domkyrkja Nidarosdomen. Frå 1152 til 1154 var Nicholas Breakspear i Skandinavia som paveleg utsending, og organiserte opprettinga av erkesetet. Innhaldsliste 1 Utbreiing og jurisdiksjon 2 Overhyrdar 2.1 Lydbiskopar 3 Biskopar 3.1 Biskopar 3.2 Erkebiskopar Utbreiing og jurisdiksjon | Kart over den nordiske kyrkjeprovinsen (1153-1387) Erkebispedømet omfatta i tillegg til Noreg øyane i vest i Noregsveldet. Nidaros var eit metropolitanerkebispedøme med fylgjande underliggjande bispedøme suffraganar: Bj...
                    Read more

                    Birsay

                    Image
                    Tettstaden Birsay på Orknøyane. Ruinane av jarleplasset om lag midt i biletet. (Fotografi frå 2012) Utsikt mot Birsay og Brough of Brisay (fotografi frå 2009) Birsay er ein tettstad i eit sokn (parish) med same namn, nordvest på øya Mainland [Note 1] på Orknøyane, om lag 31 km frå Kirkwall. Staden er omtala fleire stader i Orknøyingasoga [1] , der han er kalla «Byrgesherad» (norrønt: Birgisherað ). Namnet skriv seg truleg frå elvenamnet Birgisá [2] . Innhaldsliste 1 Den gamle hovudstaden 2 Bispesetet 3 Jarlepalasset 4 Kjelder og utfyllande opplysningar 4.1 Notar 4.2 Fotnotar 4.3 Bakgrunnsstoff Den gamle hovudstaden | Hovudartikkelen for dette emnet er Torfinn Sigurdsson . Soknet er i dag i hovudsak ei jordbrukskommune men er mest kjend for dei mange kulturminna i området. Tettstaden Birsay blir gjerne omtala som «den gamle hovudstaden på Orknøyane» [3] , og ein viser d...
                    Read more

                    Was Woodrow Wilson really a Liberal?Was World War I a war of liberals against authoritarians?Founding Fathers...

                    Image
                    Do VLANs within a subnet need to have their own subnet for router on a stick? What are the differences between the usage of 'it' and 'they'? Dragon forelimb placement How do we improve the relationship with a client software team that performs poorly and is becoming less collaborative? What typically incentivizes a professor to change jobs to a lower ranking university? How to write a macro that is braces sensitive? Modeling an IPv4 Address Writing rule stating superpower from different root cause is bad writing Can I ask the recruiters in my resume to put the reason why I am rejected? Approximately how much travel t...
                    Read more