Results 1 to 5 of 5

Thread: Euler's totient function

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    41

    Euler's totient function

    If n=rs, r>2 and s>2, gcd(r,s)=1, show $\displaystyle a^{\phi(n)/2}$ ≡ 1 (mod n).

    I really have no ideas -- something with Euler's Criterion maybe? -- any help would be appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You should try using the Chinese Remainder Theorem.

    It will suffice to show that $\displaystyle a^{\varphi(n)/2}\equiv 1\pmod{r}$ and $\displaystyle a^{\varphi(n)/2}\equiv 1\pmod{s}$ simultaneously. Keep in mind that $\displaystyle \varphi(n)=\varphi(rs)=\varphi(r)\varphi(s)$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2010
    Posts
    41
    Quote Originally Posted by roninpro View Post
    You should try using the Chinese Remainder Theorem.

    It will suffice to show that $\displaystyle a^{\varphi(n)/2}\equiv 1\pmod{r}$ and $\displaystyle a^{\varphi(n)/2}\equiv 1\pmod{s}$ simultaneously. Keep in mind that $\displaystyle \varphi(n)=\varphi(rs)=\varphi(r)\varphi(s)$.
    Thank you! In trying the Chinese Remainder Theorem on those two congruences, if I set x = $\displaystyle a^{\varphi(n)/2} $, I get that N1 = rs/r = s and N2 = rs/s = r, and then I get stuck again at solving sx $\displaystyle \equiv$ 1 (mod r) and rx $\displaystyle \equiv$ 1 (mod s). Did I do something wrong here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Note that here $\displaystyle gcd(a,n)=1 $, and therefore $\displaystyle gcd(a,r)=gcd(a,s)=1$.

    Euler's Theorem implies that $\displaystyle a^{\phi(r)}\equiv1\bmod r$; also $\displaystyle \phi(r)$ is even since $\displaystyle r\geq3$. Hence $\displaystyle a^{(\phi(r)\cdot\phi(s))/2}=(a^{\phi(r)})^{\phi(s)/2}\equiv1^{\phi(s)/2}=1\bmod r$. In a similar way, we have the congruence $\displaystyle a^{(\phi(r)\cdot\phi(s))/2}\equiv1\bmod s$.

    By hypothesis $\displaystyle gcd(r,s)=1 $, so we can merge the main congruences to one that is equivalent, namely $\displaystyle a^{\phi(r)\cdot\phi(s))/2}\equiv1\bmod rs$. But $\displaystyle \phi(n)=\phi(r)\cdot\phi(s)$, so $\displaystyle a^{\phi(n)/2}\equiv1\bmod n$.
    Last edited by melese; Nov 5th 2010 at 12:53 AM. Reason: missed division by two
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2010
    Posts
    41
    Thank you so much! I think I understand it now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: Jul 12th 2010, 09:41 AM
  2. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 1st 2010, 09:33 AM
  3. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 28th 2009, 07:16 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 8th 2008, 08:53 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Mar 25th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum