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$.
Clash 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
edited Aug 28 at 19:14
Shaun
7,45092972
asked Aug 28 at 18:34
Kai
242
add a comment |Â
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
edited Aug 28 at 19:14
Shaun
7,45092972
asked Aug 28 at 18:34
Kai
242
add a comment |Â
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
edited Aug 28 at 19:14
Shaun
7,45092972
asked Aug 28 at 18:34
Kai
242
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
edited Aug 28 at 19:14
Shaun
7,45092972
asked Aug 28 at 18:34
Kai
242
edited Aug 28 at 19:14
Shaun
7,45092972
edited Aug 28 at 19:14
Shaun
7,45092972
edited Aug 28 at 19:14
Shaun
7,45092972
7,45092972
asked Aug 28 at 18:34
Kai
242
asked Aug 28 at 18:34
Kai
242
asked Aug 28 at 18:34
Kai
242
242
add a comment |Â
add a comment |Â
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.
answered Aug 28 at 22:57
Fabio Lucchini
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
 |Â
show 6 more comments
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.
answered Aug 28 at 22:57
Fabio Lucchini
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
 |Â
show 6 more comments
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.
answered Aug 28 at 22:57
Fabio Lucchini
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
 |Â
show 6 more comments
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.
answered Aug 28 at 22:57
Fabio Lucchini
6,20911126
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.
answered Aug 28 at 22:57
Fabio Lucchini
6,20911126
edited Aug 29 at 7:17
answered Aug 28 at 22:57
Fabio Lucchini
6,20911126
answered Aug 28 at 22:57
Fabio Lucchini
6,20911126
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
 |Â
show 6 more comments
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
 |Â
show 6 more comments
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
