Let $p$ be prime and $nmid p-1$. Let $gcd(a,p)=1$, and $a^(p-1)/n equiv 1 mod p$. Show that there are $n$ solutions to $x^n equiv a mod p$.

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite













Let $p$ be prime and $n$ divide $p-1$. Let $gcd(a,p)=1$, and $a^(p-1)/n equiv 1 mod p$. Show that there are $n$ solutions to $x^n equiv a mod p$ for $x$ if $a$ is a constant.




For now I have come up with that there are $p-1$ solutions to $x^p-1 equiv 1 mod p$




number-theory prime-numbers




share|cite|improve this question


























    up vote
    1
    down vote

    favorite













    Let $p$ be prime and $n$ divide $p-1$. Let $gcd(a,p)=1$, and $a^(p-1)/n equiv 1 mod p$. Show that there are $n$ solutions to $x^n equiv a mod p$ for $x$ if $a$ is a constant.




    For now I have come up with that there are $p-1$ solutions to $x^p-1 equiv 1 mod p$




    number-theory prime-numbers




    share|cite|improve this question
























      up vote
      1
      down vote

      favorite









      up vote
      1
      down vote

      favorite












      Let $p$ be prime and $n$ divide $p-1$. Let $gcd(a,p)=1$, and $a^(p-1)/n equiv 1 mod p$. Show that there are $n$ solutions to $x^n equiv a mod p$ for $x$ if $a$ is a constant.




      For now I have come up with that there are $p-1$ solutions to $x^p-1 equiv 1 mod p$




      number-theory prime-numbers




      share|cite|improve this question















      Let $p$ be prime and $n$ divide $p-1$. Let $gcd(a,p)=1$, and $a^(p-1)/n equiv 1 mod p$. Show that there are $n$ solutions to $x^n equiv a mod p$ for $x$ if $a$ is a constant.




      For now I have come up with that there are $p-1$ solutions to $x^p-1 equiv 1 mod p$





      number-theory prime-numbers





      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Aug 28 at 19:14









      Shaun

      7,45092972




      7,45092972










      asked Aug 28 at 18:34









      Kai

      242




      242




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          2
          down vote













          Let $g $ be a primitive root modulo $p$ and $uinBbb Z $ such that $a=g^u $.



          By assumption, there exists an integer $m $ such that $p-1=nm $.



          From $a^mequiv 1pmod p $ follows $muequiv 0pmod mn $, hence there exists an integer $v $ such that $u=vn $.



          If $x=g^y $, then we have $x^nequiv apmod p $ if and only if $ynequiv upmod mn $, that's $yequiv vpmod m$.
          Consequently, $x^v+km $ for $0leq kleq n-1$ are the required $n $ solutions.






          share|cite|improve this answer






















          • What is Fxp? Thanks.
            – Kai
            Aug 29 at 2:05










          • Is a generator also called a primitive root?
            – Kai
            Aug 29 at 2:56










          • Fxp is the name of collection of generator units, right?
            – Kai
            Aug 29 at 2:58










          • @kai: I mean primitive root modulo $p $, I edit my answer.
            – Fabio Lucchini
            Aug 29 at 7:19







          • 1




            $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
            – Kai
            Sep 1 at 1:09










          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',
          convertImagesToLinks: true,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          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%2f2897558%2flet-p-be-prime-and-n-mid-p-1-let-gcda-p-1-and-ap-1-n-equiv-1-m%23new-answer', 'question_page');

          );

          Post as a guest

















          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          2
          down vote













          Let $g $ be a primitive root modulo $p$ and $uinBbb Z $ such that $a=g^u $.



          By assumption, there exists an integer $m $ such that $p-1=nm $.



          From $a^mequiv 1pmod p $ follows $muequiv 0pmod mn $, hence there exists an integer $v $ such that $u=vn $.



          If $x=g^y $, then we have $x^nequiv apmod p $ if and only if $ynequiv upmod mn $, that's $yequiv vpmod m$.
          Consequently, $x^v+km $ for $0leq kleq n-1$ are the required $n $ solutions.






          share|cite|improve this answer






















          • What is Fxp? Thanks.
            – Kai
            Aug 29 at 2:05










          • Is a generator also called a primitive root?
            – Kai
            Aug 29 at 2:56










          • Fxp is the name of collection of generator units, right?
            – Kai
            Aug 29 at 2:58










          • @kai: I mean primitive root modulo $p $, I edit my answer.
            – Fabio Lucchini
            Aug 29 at 7:19







          • 1




            $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
            – Kai
            Sep 1 at 1:09














          up vote
          2
          down vote













          Let $g $ be a primitive root modulo $p$ and $uinBbb Z $ such that $a=g^u $.



          By assumption, there exists an integer $m $ such that $p-1=nm $.



          From $a^mequiv 1pmod p $ follows $muequiv 0pmod mn $, hence there exists an integer $v $ such that $u=vn $.



          If $x=g^y $, then we have $x^nequiv apmod p $ if and only if $ynequiv upmod mn $, that's $yequiv vpmod m$.
          Consequently, $x^v+km $ for $0leq kleq n-1$ are the required $n $ solutions.






          share|cite|improve this answer






















          • What is Fxp? Thanks.
            – Kai
            Aug 29 at 2:05










          • Is a generator also called a primitive root?
            – Kai
            Aug 29 at 2:56










          • Fxp is the name of collection of generator units, right?
            – Kai
            Aug 29 at 2:58










          • @kai: I mean primitive root modulo $p $, I edit my answer.
            – Fabio Lucchini
            Aug 29 at 7:19







          • 1




            $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
            – Kai
            Sep 1 at 1:09












          up vote
          2
          down vote










          up vote
          2
          down vote









          Let $g $ be a primitive root modulo $p$ and $uinBbb Z $ such that $a=g^u $.



          By assumption, there exists an integer $m $ such that $p-1=nm $.



          From $a^mequiv 1pmod p $ follows $muequiv 0pmod mn $, hence there exists an integer $v $ such that $u=vn $.



          If $x=g^y $, then we have $x^nequiv apmod p $ if and only if $ynequiv upmod mn $, that's $yequiv vpmod m$.
          Consequently, $x^v+km $ for $0leq kleq n-1$ are the required $n $ solutions.






          share|cite|improve this answer














          Let $g $ be a primitive root modulo $p$ and $uinBbb Z $ such that $a=g^u $.



          By assumption, there exists an integer $m $ such that $p-1=nm $.



          From $a^mequiv 1pmod p $ follows $muequiv 0pmod mn $, hence there exists an integer $v $ such that $u=vn $.



          If $x=g^y $, then we have $x^nequiv apmod p $ if and only if $ynequiv upmod mn $, that's $yequiv vpmod m$.
          Consequently, $x^v+km $ for $0leq kleq n-1$ are the required $n $ solutions.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Aug 29 at 7:17

























          answered Aug 28 at 22:57









          Fabio Lucchini

          6,20911126




          6,20911126











          • What is Fxp? Thanks.
            – Kai
            Aug 29 at 2:05










          • Is a generator also called a primitive root?
            – Kai
            Aug 29 at 2:56










          • Fxp is the name of collection of generator units, right?
            – Kai
            Aug 29 at 2:58










          • @kai: I mean primitive root modulo $p $, I edit my answer.
            – Fabio Lucchini
            Aug 29 at 7:19







          • 1




            $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
            – Kai
            Sep 1 at 1:09
















          • What is Fxp? Thanks.
            – Kai
            Aug 29 at 2:05










          • Is a generator also called a primitive root?
            – Kai
            Aug 29 at 2:56










          • Fxp is the name of collection of generator units, right?
            – Kai
            Aug 29 at 2:58










          • @kai: I mean primitive root modulo $p $, I edit my answer.
            – Fabio Lucchini
            Aug 29 at 7:19







          • 1




            $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
            – Kai
            Sep 1 at 1:09















          What is Fxp? Thanks.
          – Kai
          Aug 29 at 2:05




          What is Fxp? Thanks.
          – Kai
          Aug 29 at 2:05












          Is a generator also called a primitive root?
          – Kai
          Aug 29 at 2:56




          Is a generator also called a primitive root?
          – Kai
          Aug 29 at 2:56












          Fxp is the name of collection of generator units, right?
          – Kai
          Aug 29 at 2:58




          Fxp is the name of collection of generator units, right?
          – Kai
          Aug 29 at 2:58












          @kai: I mean primitive root modulo $p $, I edit my answer.
          – Fabio Lucchini
          Aug 29 at 7:19





          @kai: I mean primitive root modulo $p $, I edit my answer.
          – Fabio Lucchini
          Aug 29 at 7:19





          1




          1




          $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
          – Kai
          Sep 1 at 1:09




          $(g^v+km)^n=g^nv+kmn=g^u+k(p-1)=g^u=a$ (mod p)
          – Kai
          Sep 1 at 1:09

















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2897558%2flet-p-be-prime-and-n-mid-p-1-let-gcda-p-1-and-ap-1-n-equiv-1-m%23new-answer', 'question_page');

          );

          Post as a guest
































































          -

          這個網誌中的熱門文章

          How to combine Bézier curves to a surface?

          圖片
          Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite My aim is to smooth the terrain in a video game. Therefore I contrived an algorithm that makes use of Bézier curves of different orders. But this algorithm is defined in a two dimensional space for now. To shift it into the third dimension I need to somehow combine the Bézier curves. Given two curves in each two dimensions, how can I combine them to build a surface? I thought about something like a curve of a curve. Or maybe I could multiply them somehow. How can I combine them to cause the wanted behavior? Is there a common approach? In the image you can see the input, on the left, and the output, on the right, of the algorithm that works in a two dimensional space. For the real application there is a three dimensional input. The algorithm relays only on the adjacent tiles. Given these it will define the control points of the mentioned Bézier curve. Additionally it marks one side of the curve as inside t
          閱讀完整內容

          Why am i infinitely getting the same tweet with the Twitter Search API?

          圖片
          up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia
          閱讀完整內容

          Is there any way to eliminate the singular point to solve this integral by hand or by approximations?

          圖片
          Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite 1 $$int_0^1 (1+(x^-p-1)^1-p)^frac1pdx, pin mathbbR, pge 1$$ I find that $x=0,1$ are singular points(discontinuous points of this integral), is there a way to eliminate those singular points to make sure that this integral can be calculated by hand or by Taylor approximations. In either cases, what are those steps of calculating the integral? calculus real-analysis analysis approximation share | cite | improve this question edited Sep 11 at 5:07 asked Sep 11 at 4:48 Mclalalala 126 8 1 What is $p$? Please give more information to make it complete. – xbh Sep 11 at 5:02 @xbh already fixed it, thanks for reminding. – Mclalalala Sep 11 at 5:10 Seems that $0$ is not singular here… [I might compute wrong] – xbh Sep 11 at 5:30 @xbh can you show me how to get the close formula for the integral above? – Mclalalala Sep 11 at 5:33
          閱讀完整內容