Results 1 to 3 of 3

Math Help - Euler's phi function

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Euler's phi function

    Use Euler;s Theorem to find all incongruent solutions of each congruence below.

    9x is congruent to 21 mod 25.


    OK, I know this is an easy computational but my anwser still does not math the books. can someone spot the error:

    1) i found the inverse of 9 modulo 25 to be 9^22. multiply both side and get

    2) x is congruent to 9^22 times 21 mod 25


    3) so then i get x is congruent to 7 mod 25.

    and i get the anwser of 4.


    I dont know where are my mistakes?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    1) i found the inverse of 9 modulo 25 to be 9^22. multiply both side and get
    false
    9^23 is not congruent to 1 mod 25

    2) x is congruent to 9^22 times 21 mod 25
    correct reasoning


    3) so then i get x is congruent to 7 mod 25.
    9^22 times 21 mod 25 is congruent to 1 mod 25

    ----------------------------
    Anyway, this looks naaasty ! In order to find the multiplicative inverse of the number, use the extended Euclidian algorithm.

    But first of all, let's play a little with the equation :
    9x \equiv 21 \bmod 25
    That is to say 9x-21=25k.
    3(3x-7)=25k
    Since 3 & 25 are coprime, 3x-7 divides 25, that is to say \boxed{3x \equiv 7 \bmod 25}.
    In further exercises, you can directly "simplify" by 3, since it divides 9x, 21, but not 25. If it were 24, you would have had to divide by 3 too.

    Now, find the inverse of 3 mod 25. Since 3 and 25 are coprime, there exists a such that 3a \equiv 1 \bmod 25. But since 3 and 25 are coprime, we can also say that their gcd is 1. And we know that at a moment, we'll get their gcd as a remainder in the Euclidian algorithm. So let's do it and you will see that thereafter.

    25=3*8+1 \implies 3*(-8)=1-25 \equiv 1 \bmod 25
    thus a \equiv -8 \bmod 25, a \equiv 17 \bmod 25.
    That is the inverse of 3.

    So x \equiv 17 \cdot 7 \bmod 25

    -----------------------------------
    Now, if you have to use Euler's totient function (phi) :

    \varphi(25)=\varphi(5^2)=5 \cdot (5-1)=20 (in general, if p is prime, then \varphi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)). Thus for any number coprime with 25, for example 9, we have 9^{20} \equiv 1 \bmod 25

    9^{20}=9 \cdot 9^{19}. Therefore 9^{19} is the inverse of 9 mod 25 !

    Does this help ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    There is an easy way to get the inverse.
    9x\equiv 1 ~ (25)
    If and only if,
    9x\equiv -24 ~ (25)
    If and only if,
    3x\equiv -8 ~ (25)
    If and only if,
    3x\equiv 42 ~ (25)
    If and only if,
    x\equiv 14 ~ (25)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler function
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2011, 09:53 AM
  2. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 07:29 AM
  3. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 8th 2010, 02:58 PM
  4. Euler's phi function
    Posted in the Advanced Math Topics Forum
    Replies: 12
    Last Post: January 12th 2010, 05:10 AM
  5. Euler phi-Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 11th 2009, 06:11 PM

Search Tags


/mathhelpforum @mathhelpforum