How to calculate all possible values for $m$, where $m=i^k mod p$, $k,p$ are fixed?
up vote
1
down vote
favorite
For example, all possible values for $i^{10} mod 71$ is $1, 20, 30, 32, 37, 45, 48$. Is it possible to directly calculate these values without trying all possible $i$ from 1 to 71?
elementary-number-theory modular-arithmetic
asked Nov 15 at 7:41
Mayoi
183
add a comment |
up vote
1
down vote
favorite
For example, all possible values for $i^{10} mod 71$ is $1, 20, 30, 32, 37, 45, 48$. Is it possible to directly calculate these values without trying all possible $i$ from 1 to 71?
elementary-number-theory modular-arithmetic
asked Nov 15 at 7:41
Mayoi
183
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
For example, all possible values for $i^{10} mod 71$ is $1, 20, 30, 32, 37, 45, 48$. Is it possible to directly calculate these values without trying all possible $i$ from 1 to 71?
elementary-number-theory modular-arithmetic
asked Nov 15 at 7:41
Mayoi
183
For example, all possible values for $i^{10} mod 71$ is $1, 20, 30, 32, 37, 45, 48$. Is it possible to directly calculate these values without trying all possible $i$ from 1 to 71?
elementary-number-theory modular-arithmetic
elementary-number-theory modular-arithmetic
asked Nov 15 at 7:41
Mayoi
183
asked Nov 15 at 7:41
Mayoi
183
asked Nov 15 at 7:41
Mayoi
183
asked Nov 15 at 7:41
Mayoi
183
asked Nov 15 at 7:41
Mayoi
183
183
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
In this case $71-1=70$, so as the nonzero residues modulo $71$ form a cyclic
group of order $70$, the tenth powers form a cyclic group of order $7$.
So once you have one non-trivial value, say $10$, then $10^0$, $10^1$,
$10^2,ldots,10^6$ are all of them.
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
In this case $71-1=70$, so as the nonzero residues modulo $71$ form a cyclic
group of order $70$, the tenth powers form a cyclic group of order $7$.
So once you have one non-trivial value, say $10$, then $10^0$, $10^1$,
$10^2,ldots,10^6$ are all of them.
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
add a comment |
up vote
1
down vote
accepted
In this case $71-1=70$, so as the nonzero residues modulo $71$ form a cyclic
group of order $70$, the tenth powers form a cyclic group of order $7$.
So once you have one non-trivial value, say $10$, then $10^0$, $10^1$,
$10^2,ldots,10^6$ are all of them.
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
In this case $71-1=70$, so as the nonzero residues modulo $71$ form a cyclic
group of order $70$, the tenth powers form a cyclic group of order $7$.
So once you have one non-trivial value, say $10$, then $10^0$, $10^1$,
$10^2,ldots,10^6$ are all of them.
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
In this case $71-1=70$, so as the nonzero residues modulo $71$ form a cyclic
group of order $70$, the tenth powers form a cyclic group of order $7$.
So once you have one non-trivial value, say $10$, then $10^0$, $10^1$,
$10^2,ldots,10^6$ are all of them.
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
answered Nov 15 at 7:49
Lord Shark the Unknown
97.4k958128
97.4k958128
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
add a comment |
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
for $i^{374}mod 331$, the full answer is $1, 4, 16, 31, 64, 83, 124, 150, 165, 203, 256, 269, 299, 323, 329$. However, if we take $31$, $64$ to generate the list, only part of the answer can be obtained (of length 3 and 5, while the full answer has 15). Could you elaborate how to deal with this case? Thanks.
– Mayoi
Nov 15 at 9:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
using the primitive root works, never mind.
– Mayoi
Nov 15 at 10:09
add a comment |
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999380%2fhow-to-calculate-all-possible-values-for-m-where-m-ik-mod-p-k-p-are-fi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
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
