We have

and

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

Results 1 to 2 of 2

- October 21st 2009, 02:55 PM #1

- Joined
- Sep 2009
- Posts
- 35

## please help

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.

- October 22nd 2009, 06:06 AM #2

- Joined
- Oct 2009
- Posts
- 68