Why does the Euler's totient function $phi(n)$ give the minimum of exponent s.t. $a^{phi(n)}equiv 1pmod n$,...












1












$begingroup$


I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)



OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.






number-theory







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    See this answer for order algorithms.
    $endgroup$
    – Bill Dubuque
    Jan 7 at 19:40










  • $begingroup$
    Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
    $endgroup$
    – Erick Wong
    Jan 7 at 20:14










  • $begingroup$
    @ErickWong: for the given $a$, sorry for confusing.
    $endgroup$
    – user7813604
    Jan 8 at 1:48
















1












$begingroup$


I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)



OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.






number-theory







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    See this answer for order algorithms.
    $endgroup$
    – Bill Dubuque
    Jan 7 at 19:40










  • $begingroup$
    Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
    $endgroup$
    – Erick Wong
    Jan 7 at 20:14










  • $begingroup$
    @ErickWong: for the given $a$, sorry for confusing.
    $endgroup$
    – user7813604
    Jan 8 at 1:48














1












1








1





$begingroup$


I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)



OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.






number-theory







share|cite|improve this question











$endgroup$




I want to know whether it's possible that there would exist $1lt kltphi(n)$ s.t. $a^{phi(n)}equiv 1pmod n$, for a given $a$ and $n$? I need to prove/disprove it. I need some hints. (For title I meant minimum mod n.)



OK, seems it may be too easy for my question but may I also ask that how to find the minimum even if I know that $(a,n)=1$? i.e. I have to know the $k$ s.t. $a^kequiv 1pmod n,$ given $(a,n)=1$.






number-theory




number-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 8 at 2:54









kale

33




33










asked Jan 7 at 18:45









user7813604user7813604

15511




15511








  • 1




    $begingroup$
    See this answer for order algorithms.
    $endgroup$
    – Bill Dubuque
    Jan 7 at 19:40










  • $begingroup$
    Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
    $endgroup$
    – Erick Wong
    Jan 7 at 20:14










  • $begingroup$
    @ErickWong: for the given $a$, sorry for confusing.
    $endgroup$
    – user7813604
    Jan 8 at 1:48














  • 1




    $begingroup$
    See this answer for order algorithms.
    $endgroup$
    – Bill Dubuque
    Jan 7 at 19:40










  • $begingroup$
    Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
    $endgroup$
    – Erick Wong
    Jan 7 at 20:14










  • $begingroup$
    @ErickWong: for the given $a$, sorry for confusing.
    $endgroup$
    – user7813604
    Jan 8 at 1:48








1




1




$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40




$begingroup$
See this answer for order algorithms.
$endgroup$
– Bill Dubuque
Jan 7 at 19:40












$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14




$begingroup$
Please clarify whether you mean “minimum $k$ that works for all $a$” or for just a particular $a$.
$endgroup$
– Erick Wong
Jan 7 at 20:14












$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48




$begingroup$
@ErickWong: for the given $a$, sorry for confusing.
$endgroup$
– user7813604
Jan 8 at 1:48










3 Answers
3






active

oldest

votes


















2












$begingroup$

$phi(7)=6$ but $2^3equiv 1$(mod$7$).



Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
    $endgroup$
    – user7813604
    Jan 7 at 18:48












  • $begingroup$
    Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
    $endgroup$
    – user7813604
    Jan 7 at 18:56












  • $begingroup$
    So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
    $endgroup$
    – user7813604
    Jan 7 at 19:01








  • 1




    $begingroup$
    Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
    $endgroup$
    – Mark
    Jan 7 at 19:06






  • 1




    $begingroup$
    Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
    $endgroup$
    – Mark
    Jan 7 at 19:12



















3












$begingroup$

Hint 1:



If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.



Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.



Hint 2:



$(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....



Hint 3:



$a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?



=====



Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!



Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.



One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.






share|cite|improve this answer











$endgroup$





















    2












    $begingroup$

    Hint:



    $$frac{10^3-1}{37}=27$$






    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%2f3065332%2fwhy-does-the-eulers-totient-function-phin-give-the-minimum-of-exponent-s-t%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









      2












      $begingroup$

      $phi(7)=6$ but $2^3equiv 1$(mod$7$).



      Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.






      share|cite|improve this answer











      $endgroup$













      • $begingroup$
        lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
        $endgroup$
        – user7813604
        Jan 7 at 18:48












      • $begingroup$
        Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
        $endgroup$
        – user7813604
        Jan 7 at 18:56












      • $begingroup$
        So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
        $endgroup$
        – user7813604
        Jan 7 at 19:01








      • 1




        $begingroup$
        Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
        $endgroup$
        – Mark
        Jan 7 at 19:06






      • 1




        $begingroup$
        Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
        $endgroup$
        – Mark
        Jan 7 at 19:12
















      2












      $begingroup$

      $phi(7)=6$ but $2^3equiv 1$(mod$7$).



      Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.






      share|cite|improve this answer











      $endgroup$













      • $begingroup$
        lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
        $endgroup$
        – user7813604
        Jan 7 at 18:48












      • $begingroup$
        Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
        $endgroup$
        – user7813604
        Jan 7 at 18:56












      • $begingroup$
        So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
        $endgroup$
        – user7813604
        Jan 7 at 19:01








      • 1




        $begingroup$
        Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
        $endgroup$
        – Mark
        Jan 7 at 19:06






      • 1




        $begingroup$
        Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
        $endgroup$
        – Mark
        Jan 7 at 19:12














      2












      2








      2





      $begingroup$

      $phi(7)=6$ but $2^3equiv 1$(mod$7$).



      Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.






      share|cite|improve this answer











      $endgroup$



      $phi(7)=6$ but $2^3equiv 1$(mod$7$).



      Edit: As I know there is no general algorithm to find the least integer $k$ such that $a^kequiv 1$(mod$n$). Though a fact that can help is that this $k$ must divide $phi(n)$. Even more than that, this $k$ divides every integer $m$ such that $a^mequiv 1$(mod $m$). You can try to prove it, that's a pretty easy exercise. So for example, given that we know that $phi(7)=6$ we know that the minimum cannot be $4$ or $5$. It must be an integer which divides $6$. So that gives us less options which makes it a bit easier.







      share|cite|improve this answer














      share|cite|improve this answer



      share|cite|improve this answer








      edited Jan 7 at 18:59

























      answered Jan 7 at 18:46









      MarkMark

      6,230416




      6,230416












      • $begingroup$
        lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
        $endgroup$
        – user7813604
        Jan 7 at 18:48












      • $begingroup$
        Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
        $endgroup$
        – user7813604
        Jan 7 at 18:56












      • $begingroup$
        So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
        $endgroup$
        – user7813604
        Jan 7 at 19:01








      • 1




        $begingroup$
        Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
        $endgroup$
        – Mark
        Jan 7 at 19:06






      • 1




        $begingroup$
        Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
        $endgroup$
        – Mark
        Jan 7 at 19:12


















      • $begingroup$
        lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
        $endgroup$
        – user7813604
        Jan 7 at 18:48












      • $begingroup$
        Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
        $endgroup$
        – user7813604
        Jan 7 at 18:56












      • $begingroup$
        So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
        $endgroup$
        – user7813604
        Jan 7 at 19:01








      • 1




        $begingroup$
        Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
        $endgroup$
        – Mark
        Jan 7 at 19:06






      • 1




        $begingroup$
        Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
        $endgroup$
        – Mark
        Jan 7 at 19:12
















      $begingroup$
      lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
      $endgroup$
      – user7813604
      Jan 7 at 18:48






      $begingroup$
      lol... Then my friend's answer is incorrect. I'm trying to understand her solution which using the formula.
      $endgroup$
      – user7813604
      Jan 7 at 18:48














      $begingroup$
      Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
      $endgroup$
      – user7813604
      Jan 7 at 18:56






      $begingroup$
      Could you also help me understand how to find the minimum, i.e. 3 in your example? Is there a general algorithm to calculate the exponent $k$ s.t. $a^kequiv 1pmod n$ and $k$ is minimum mod $n$?
      $endgroup$
      – user7813604
      Jan 7 at 18:56














      $begingroup$
      So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
      $endgroup$
      – user7813604
      Jan 7 at 19:01






      $begingroup$
      So I have a homework question which is just trying to waste my time solving a problem which can only be done by brute force trying...?
      $endgroup$
      – user7813604
      Jan 7 at 19:01






      1




      1




      $begingroup$
      Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
      $endgroup$
      – Mark
      Jan 7 at 19:06




      $begingroup$
      Well, in the example I gave you it is pretty fast. When it comes to big numbers it is obviously a very hard task. Even to find $phi(n)$ is very hard in general.
      $endgroup$
      – Mark
      Jan 7 at 19:06




      1




      1




      $begingroup$
      Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
      $endgroup$
      – Mark
      Jan 7 at 19:12




      $begingroup$
      Yes, exactly. And to find $phi(n)$ is hard because you need to find the prime factorization of $n$. And if the primes which are dividing $n$ are very big then the factorization might take years even for today's best computers. (maybe it might change in the future). So RSA is pretty safe.
      $endgroup$
      – Mark
      Jan 7 at 19:12











      3












      $begingroup$

      Hint 1:



      If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.



      Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.



      Hint 2:



      $(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....



      Hint 3:



      $a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?



      =====



      Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!



      Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.



      One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.






      share|cite|improve this answer











      $endgroup$


















        3












        $begingroup$

        Hint 1:



        If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.



        Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.



        Hint 2:



        $(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....



        Hint 3:



        $a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?



        =====



        Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!



        Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.



        One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.






        share|cite|improve this answer











        $endgroup$
















          3












          3








          3





          $begingroup$

          Hint 1:



          If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.



          Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.



          Hint 2:



          $(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....



          Hint 3:



          $a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?



          =====



          Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!



          Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.



          One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.






          share|cite|improve this answer











          $endgroup$



          Hint 1:



          If $a^{phi(n)}equiv 1 pmod n$ and $phi(n)$ is composite and $k|phi(n)$ then Let $b = a^k$.



          Then $b^{frac {phi(n)}k} = (a^k)^{frac {phi(n)}k}=a^{phi(n)} equiv 1 pmod n$.



          Hint 2:



          $(-1)^2 equiv 1 pmod n$. So if $phi(n) ne 2$....



          Hint 3:



          $a^3 equiv 1 pmod {a^3 -1}$. Can you find any $a^3 -1$ so that $phi(a^3 -1) > 3$?



          =====



          Euler's Theorem was never actually meant to be a way of finding the order of an element, least not directly. The fact that $a^{phi(n)} equiv 1 pmod n$ for $a$ relatively prime to $n$ in no way means that $phi(n)$ is the smallest order that such is true. In general, it rarely is!



          Indeed, as $(a^k)^{frac {phi(n)}k}=a^k$ and $phi(n)$ is never prime for $phi(n) > 2$ for every element where $phi(n)$ is the smallest power there are $a^k; k|phi(n)$ where it isnt.



          One useful tidbit. If $a^kequiv 1 pmod n$ then $k|phi(n)$. That is useful for finding an order.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Jan 8 at 3:18

























          answered Jan 8 at 2:38









          fleabloodfleablood

          68.7k22685




          68.7k22685























              2












              $begingroup$

              Hint:



              $$frac{10^3-1}{37}=27$$






              share|cite|improve this answer









              $endgroup$


















                2












                $begingroup$

                Hint:



                $$frac{10^3-1}{37}=27$$






                share|cite|improve this answer









                $endgroup$
















                  2












                  2








                  2





                  $begingroup$

                  Hint:



                  $$frac{10^3-1}{37}=27$$






                  share|cite|improve this answer









                  $endgroup$



                  Hint:



                  $$frac{10^3-1}{37}=27$$







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Jan 7 at 18:48









                  ajotatxeajotatxe

                  53.7k23890




                  53.7k23890






























                      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%2f3065332%2fwhy-does-the-eulers-totient-function-phin-give-the-minimum-of-exponent-s-t%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

                      Mario Kart Wii

                      Image
                      Please consider supporting The Cutting Room Floor on Patreon. Thanks for all your support! Mario Kart Wii From The Cutting Room Floor Jump to: navigation, search Mario Kart Wii Developer : Nintendo Publisher : Nintendo Platform : Wii Released in JP : April 10, 2008 Released in US : April 27, 2008 Released in EU : April 11, 2008 Released in AU : April 24, 2008 Released in KR : April 30, 2009 This game has unused animations. This game has unused areas. This game has unused code. This game has unused objects. This game has unused modes / minigames. This game has unused graphics. This game has unused models. This game has unused items. This game has unused music. This game has regional differences. This game has a notes page This game has a prerelease article Mario Kart Wii is the sixth game in the series (not counting Arcade editions), which intro...
                      Read more

                      Understanding the size os this class of aleatory events

                      Image
                      0 1 $begingroup$ Hi I am having problems to understand this: I have: $Omega = [0,1]$ , $Lambda =$ all subsets with defined length Let $A_{0}$ = {A $subset$ [0,1]: A is finite union of intervals} 1º: My doubt is that $A_{0}$ is a algebra but its not a sigma algebra. Why? Also, A = $(0,1/2) cup (1/2,3/4) cup (3/4,7/8) cup ... cup(1-1/2^{n},1-1/2^{n+1})...$ 2º: So the class of aleatory events would be bigger than $A_{0}$ . Why? How the set A is greater than $A_{0}$ ? measure-theory share | cite | improve this question asked Jan 8 at 19:17 Diogo Bastos Diogo Bastos 116 6 ...
                      Read more

                      Partial Derivative Guidance.

                      Image
                      0 $begingroup$ I was given this tricky problem in which I'm confuse on how to solve it and I would like some help: Let $v(x,y)$ be continuously differentiable function. Let the function $u(s,t)$ be given by $u(s,t) = sin(s)*v(s-2t,t^2)$ . Compute $du/ds$ and $du/dt$ in terms of $v$ and it's partial derivatives. My attempt (which is wrong): Using chain rule: $du/ds=(du/dx)(dx/ds) + (du/dy)(dy/ds)$ $du/dt=(du/dx)(dx/dt) + (du/dx)(dy/dt)$ So, $du/ds = sin(s)*v(x,y)*s + sin(s)*v(x,y)*0$ $du/dt = 2t*sin(s)*v(x,y) - 2*sin(s)*v(x,y)$ Thanks, calculus multivariable-calculus share | cite | improve this question edited Jan 19 at 19:38...
                      Read more