Hence (this is because the multiplicative group is isomorphic to The result follows from the fact that
NB: The result also holds if one of and is equal to
let p and q be two distinct odd prime numbers, n=pq and let d=gcd(p-1,q-1). Then show that x^(ϕ(n)/d) ≡1 (mod n)
I know that ϕ(n)=(p-1)(q-1)
how can i show that???.
my answer is
x≡a1 (mod p)
x≡a2 (mod q)
we can write x^(p-1(q-1)/d ≡a1 ^ d((p-1)(q-1))/d ≡a1^(p-1)(q-1) ≡1 (mod p)
the same thing for mod q
so x^(ϕ(n)/d) ≡1 (mod pq)≡1 (mod n)
I hope this is correct.