Results 1 to 2 of 2

Thread: please help

  1. #1
    Junior Member
    Sep 2009

    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.
    Last edited by koko2009; Oct 21st 2009 at 04:49 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Oct 2009
    We have

    x^{p-1}\equiv1\pmod p


    x^{q-1}\equiv1\pmod q

    Hence x^{\mathrm{lcm}(p-1,q-1)}\equiv1\pmod n (this is because the multiplicative group \mathbb Z_n^\times is isomorphic to \mathbb Z_p^\times\times\mathbb Z_q^\times). The result follows from the fact that


    NB: The result also holds if one of p and q is equal to 2.
    Follow Math Help Forum on Facebook and Google+

/mathhelpforum @mathhelpforum