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 03:49 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Oct 2009
    We have

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


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

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

    $\displaystyle \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 $\displaystyle p$ and $\displaystyle q$ is equal to $\displaystyle 2.$
    Follow Math Help Forum on Facebook and Google+

/mathhelpforum @mathhelpforum