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
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
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
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 yesterday
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.
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
yesterday
using the primitive root works, never mind.
– Mayoi
23 hours ago
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.
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
yesterday
using the primitive root works, never mind.
– Mayoi
23 hours ago
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.
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
yesterday
using the primitive root works, never mind.
– Mayoi
23 hours ago
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.
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 yesterday
Lord Shark the Unknown
96.5k958128
96.5k958128
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
yesterday
using the primitive root works, never mind.
– Mayoi
23 hours ago
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
yesterday
using the primitive root works, never mind.
– Mayoi
23 hours ago
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
yesterday
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
yesterday
using the primitive root works, never mind.
– Mayoi
23 hours ago
using the primitive root works, never mind.
– Mayoi
23 hours ago
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