Show that if n is even and $n≥ 2$ then $phi(n)≤ n/2$












0












$begingroup$


I'm currently working in the following Euler's theorem exercise:




Show that if n is even and $n≥2$ then $phi(n)≤ n/2$




I'm starting from the point that if $n$ is even at least one of its factors is $2$ but still can't find a way to show the required fact, any help will be really appreciated.






elementary-number-theory modular-arithmetic







share|cite|improve this question











$endgroup$








  • 3




    $begingroup$
    Given that $n$ is even, are there any numbers you can say are definitely not coprime to $n$?
    $endgroup$
    – Gregory J. Puleo
    Feb 3 at 3:03
















0












$begingroup$


I'm currently working in the following Euler's theorem exercise:




Show that if n is even and $n≥2$ then $phi(n)≤ n/2$




I'm starting from the point that if $n$ is even at least one of its factors is $2$ but still can't find a way to show the required fact, any help will be really appreciated.






elementary-number-theory modular-arithmetic







share|cite|improve this question











$endgroup$








  • 3




    $begingroup$
    Given that $n$ is even, are there any numbers you can say are definitely not coprime to $n$?
    $endgroup$
    – Gregory J. Puleo
    Feb 3 at 3:03














0












0








0


0



$begingroup$


I'm currently working in the following Euler's theorem exercise:




Show that if n is even and $n≥2$ then $phi(n)≤ n/2$




I'm starting from the point that if $n$ is even at least one of its factors is $2$ but still can't find a way to show the required fact, any help will be really appreciated.






elementary-number-theory modular-arithmetic







share|cite|improve this question











$endgroup$




I'm currently working in the following Euler's theorem exercise:




Show that if n is even and $n≥2$ then $phi(n)≤ n/2$




I'm starting from the point that if $n$ is even at least one of its factors is $2$ but still can't find a way to show the required fact, any help will be really appreciated.






elementary-number-theory modular-arithmetic




elementary-number-theory modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 3 at 6:44









Jyrki Lahtonen

110k13172392




110k13172392










asked Feb 3 at 3:01









mrazmraz

452110




452110








  • 3




    $begingroup$
    Given that $n$ is even, are there any numbers you can say are definitely not coprime to $n$?
    $endgroup$
    – Gregory J. Puleo
    Feb 3 at 3:03














  • 3




    $begingroup$
    Given that $n$ is even, are there any numbers you can say are definitely not coprime to $n$?
    $endgroup$
    – Gregory J. Puleo
    Feb 3 at 3:03








3




3




$begingroup$
Given that $n$ is even, are there any numbers you can say are definitely not coprime to $n$?
$endgroup$
– Gregory J. Puleo
Feb 3 at 3:03




$begingroup$
Given that $n$ is even, are there any numbers you can say are definitely not coprime to $n$?
$endgroup$
– Gregory J. Puleo
Feb 3 at 3:03










3 Answers
3






active

oldest

votes


















4












$begingroup$

Since $n$ is even, any even number that's less than or equal $n$ is not coprime to $n$. There are $frac n2$ of them. The inequality follows.






share|cite|improve this answer









$endgroup$





















    2












    $begingroup$

    Given $n$ is even, all the even numbers less than or equal to $n$ must not be coprime to $n$. There are $frac n2$ such. $therefore phi(n)le n-frac n2=frac n2$.






    share|cite|improve this answer









    $endgroup$





















      2












      $begingroup$

      For $kge1,$



      $phi(2^km)=phi(2^k)phi(m)=?$ for odd $m$



      Now $phi(m)le m-1$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        Do you mean in the second line "for even $m$"?
        $endgroup$
        – mraz
        Feb 3 at 3:28






      • 1




        $begingroup$
        @mraz, No, I've used math.stackexchange.com/questions/192452/…
        $endgroup$
        – lab bhattacharjee
        Feb 3 at 3:40










      • $begingroup$
        Got it, thank you
        $endgroup$
        – mraz
        Feb 3 at 3:55












      Your Answer








      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%2f3098111%2fshow-that-if-n-is-even-and-n%25e2%2589%25a5-2-then-phin%25e2%2589%25a4-n-2%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$

      Since $n$ is even, any even number that's less than or equal $n$ is not coprime to $n$. There are $frac n2$ of them. The inequality follows.






      share|cite|improve this answer









      $endgroup$


















        4












        $begingroup$

        Since $n$ is even, any even number that's less than or equal $n$ is not coprime to $n$. There are $frac n2$ of them. The inequality follows.






        share|cite|improve this answer









        $endgroup$
















          4












          4








          4





          $begingroup$

          Since $n$ is even, any even number that's less than or equal $n$ is not coprime to $n$. There are $frac n2$ of them. The inequality follows.






          share|cite|improve this answer









          $endgroup$



          Since $n$ is even, any even number that's less than or equal $n$ is not coprime to $n$. There are $frac n2$ of them. The inequality follows.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Feb 3 at 3:09









          abc...abc...

          3,242739




          3,242739























              2












              $begingroup$

              Given $n$ is even, all the even numbers less than or equal to $n$ must not be coprime to $n$. There are $frac n2$ such. $therefore phi(n)le n-frac n2=frac n2$.






              share|cite|improve this answer









              $endgroup$


















                2












                $begingroup$

                Given $n$ is even, all the even numbers less than or equal to $n$ must not be coprime to $n$. There are $frac n2$ such. $therefore phi(n)le n-frac n2=frac n2$.






                share|cite|improve this answer









                $endgroup$
















                  2












                  2








                  2





                  $begingroup$

                  Given $n$ is even, all the even numbers less than or equal to $n$ must not be coprime to $n$. There are $frac n2$ such. $therefore phi(n)le n-frac n2=frac n2$.






                  share|cite|improve this answer









                  $endgroup$



                  Given $n$ is even, all the even numbers less than or equal to $n$ must not be coprime to $n$. There are $frac n2$ such. $therefore phi(n)le n-frac n2=frac n2$.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Feb 3 at 3:13









                  Chris CusterChris Custer

                  14.4k3827




                  14.4k3827























                      2












                      $begingroup$

                      For $kge1,$



                      $phi(2^km)=phi(2^k)phi(m)=?$ for odd $m$



                      Now $phi(m)le m-1$






                      share|cite|improve this answer









                      $endgroup$













                      • $begingroup$
                        Do you mean in the second line "for even $m$"?
                        $endgroup$
                        – mraz
                        Feb 3 at 3:28






                      • 1




                        $begingroup$
                        @mraz, No, I've used math.stackexchange.com/questions/192452/…
                        $endgroup$
                        – lab bhattacharjee
                        Feb 3 at 3:40










                      • $begingroup$
                        Got it, thank you
                        $endgroup$
                        – mraz
                        Feb 3 at 3:55
















                      2












                      $begingroup$

                      For $kge1,$



                      $phi(2^km)=phi(2^k)phi(m)=?$ for odd $m$



                      Now $phi(m)le m-1$






                      share|cite|improve this answer









                      $endgroup$













                      • $begingroup$
                        Do you mean in the second line "for even $m$"?
                        $endgroup$
                        – mraz
                        Feb 3 at 3:28






                      • 1




                        $begingroup$
                        @mraz, No, I've used math.stackexchange.com/questions/192452/…
                        $endgroup$
                        – lab bhattacharjee
                        Feb 3 at 3:40










                      • $begingroup$
                        Got it, thank you
                        $endgroup$
                        – mraz
                        Feb 3 at 3:55














                      2












                      2








                      2





                      $begingroup$

                      For $kge1,$



                      $phi(2^km)=phi(2^k)phi(m)=?$ for odd $m$



                      Now $phi(m)le m-1$






                      share|cite|improve this answer









                      $endgroup$



                      For $kge1,$



                      $phi(2^km)=phi(2^k)phi(m)=?$ for odd $m$



                      Now $phi(m)le m-1$







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Feb 3 at 3:23









                      lab bhattacharjeelab bhattacharjee

                      229k15159279




                      229k15159279












                      • $begingroup$
                        Do you mean in the second line "for even $m$"?
                        $endgroup$
                        – mraz
                        Feb 3 at 3:28






                      • 1




                        $begingroup$
                        @mraz, No, I've used math.stackexchange.com/questions/192452/…
                        $endgroup$
                        – lab bhattacharjee
                        Feb 3 at 3:40










                      • $begingroup$
                        Got it, thank you
                        $endgroup$
                        – mraz
                        Feb 3 at 3:55


















                      • $begingroup$
                        Do you mean in the second line "for even $m$"?
                        $endgroup$
                        – mraz
                        Feb 3 at 3:28






                      • 1




                        $begingroup$
                        @mraz, No, I've used math.stackexchange.com/questions/192452/…
                        $endgroup$
                        – lab bhattacharjee
                        Feb 3 at 3:40










                      • $begingroup$
                        Got it, thank you
                        $endgroup$
                        – mraz
                        Feb 3 at 3:55
















                      $begingroup$
                      Do you mean in the second line "for even $m$"?
                      $endgroup$
                      – mraz
                      Feb 3 at 3:28




                      $begingroup$
                      Do you mean in the second line "for even $m$"?
                      $endgroup$
                      – mraz
                      Feb 3 at 3:28




                      1




                      1




                      $begingroup$
                      @mraz, No, I've used math.stackexchange.com/questions/192452/…
                      $endgroup$
                      – lab bhattacharjee
                      Feb 3 at 3:40




                      $begingroup$
                      @mraz, No, I've used math.stackexchange.com/questions/192452/…
                      $endgroup$
                      – lab bhattacharjee
                      Feb 3 at 3:40












                      $begingroup$
                      Got it, thank you
                      $endgroup$
                      – mraz
                      Feb 3 at 3:55




                      $begingroup$
                      Got it, thank you
                      $endgroup$
                      – mraz
                      Feb 3 at 3:55


















                      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%2f3098111%2fshow-that-if-n-is-even-and-n%25e2%2589%25a5-2-then-phin%25e2%2589%25a4-n-2%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

                      MongoDB - Not Authorized To Execute Command

                      Image
                      .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
                      Read more

                      How to fix TextFormField cause rebuild widget in Flutter

                      Image
                      .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I've got the same issue at #9280. I tried all solutions from that topic with/without GlobalKey for Scaffold and Form but the problem wasn't fixed. I tried to build a authentication form with login and signup. But the keyboard doesn't show when I tap the TextFormField at the first time. Then I try to input some letter from physical keyboard, the widget is rebuilt. Like this: login screen Nothing to be log when I run flutter run --verbose, so I logged manually. Every tapping on field, the widget called dispose -> init -> build. [√] Flutter (Channel beta, v1.0.0, on Microsoft Windows [Version 10.0.17763.195], ...
                      Read more

                      in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith

                      Image
                      1 I tried to upgrade a yummy sandwich made of two test slices (@JsonTest and @JdbcTest in my case, crunchy test code in between) adding spring boot 2.1 flavour to it. But it seems it was not much of a success. I cannot annotate my tests with many @...Test since they are now each bringing their own XxxTestContextBootstrapper. It used to work when they all used same SpringBootTestContextBootstrapper. @RunWith(SpringRunner.class) @JdbcTest @JsonTest public class Test { @Test public void test() { System.out.printn("Hello, World !"); } } The error I get from BootstrapUtils is illegalStateException : Configuration error: found multiple declarations of @BootstrapWith for test class I understand I might be doing something wrong here but is there an easy way I could load both Json and Jdbc contex...
                      Read more