Results 1 to 2 of 2

Math Help - please help

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

  2. #2
    Junior Member
    Joined
    Oct 2009
    Posts
    68
    We have

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

    and

    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

    \mathrm{lcm}(p-1,q-1)=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}=\frac{\varphi(n)}{d}

    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