Show that for any integer $n$ which is relatively prime to $N$, it can be written as $a^k \pmod N$ for some integer $0 < k < (p−1)(q−1)$

Asked Sep 29 '17 at 05:27

Active Sep 29 '17 at 05:29

Viewed 197 times

Assume $a^{(p−1)(q−1)} \equiv 1 \pmod N$, and for any positive integer k where $0 < k < (p−1)(q−1)$, $a^k \neq 1 \pmod N$.

Show that for any integer s which is relatively prime to N, s can be written as $a^k \pmod\ N$ for some integer $0 \leq k < (p−1)(q−1)$.

Any hints on this?

edited Sep 29 '17 at 05:29

Siong Thye Goh

asked Sep 29 '17 at 05:27

John

1

What are $p,q?$ What's their relation to $N?$ If $N=pq$ with $p,q$ different odd primes, have look at the Carmichael function. – gammatester Sep 29 '17 at 07:21

0 Answers0