Results 1 to 7 of 7

Math Help - Can someone help me understand these problems please? Should be fairly simple...

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    75

    Can someone help me understand these problems please? Should be fairly simple...

    Hello All,
    I am currently preparing for an upcoming test. I know most of the material but the problems below is what I got stuck on, any help will be greatly appreciated!



    A) Determine φ(77) *Euler Totient function for 77+. (The first step is finding the largest number that you can multiply to get 77, i believe which is 7 and 11).

    B) -55 Mod 7= 1 (<- I dont understand. I know that -7 mod 55 equals 48 but I can't understand how they got 1 from -55 mod 7).

    C)Find the value of x such that: 9 * x 1 mod 10 <- I have no clue
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by matthayzon89 View Post
    Hello All,
    I am currently preparing for an upcoming test. I know most of the material but the problems below is what I got stuck on, any help will be greatly appreciated!



    A) Determine φ(77) *Euler Totient function for 77+. (The first step is finding the largest number that you can multiply to get 77, i believe which is 7 and 11).

    B) -55 Mod 7= 1 (<- I dont understand. I know that -7 mod 55 equals 48 but I can't understand how they got 1 from -55 mod 7).

    C)Find the value of x such that: 9 * x 1 mod 10 <- I have no clue
    ]

    For (a) use that \phi(mn)=\phi(m)\phi(n) , whenever m,n are coprime.

    As for (b)-(c) check carefully the questions and check carefully what you write. As they appear in your OP they make no sense.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    Posts
    75
    Okay, thanks for your help...

    Can anyone help me figure out a way to compute 52^6 mod 73 = 27

    When I use a TI-83 to compute it, it gives me the answer in scientific notation and my answer ends up being incorrect due to rounding.

    Is there an easier way to make this number smaller somehow to get the correct remainder?

    Thanks...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    A) Determine φ(77) *Euler Totient function for 77+. (The first step is finding the largest number that you can multiply to get 77, i believe which is 7 and 11).
    From Wikipedia: "If p is prime, then for integer k\ge1, \varphi(p^{k}) = (p - 1)p^{k - 1}. Moreover, \varphi is a multiplicative function; if m and n are coprime then \varphi(mn) = \varphi(m) \varphi(n)." Therefore, \varphi(77)=\varphi(7^1\cdot 11^1)=(7-1)\cdot7^0\cdot(11-1)\cdot11^0=60.

    B) -55 Mod 7= 1 (<- I dont understand. I know that -7 mod 55 equals 48 but I can't understand how they got 1 from -55 mod 7).
    It's easy to understand why -55\equiv1\pmod{7}. Indeed, -55\equiv-55+7\cdot8\pmod{7}, and -55+7\cdot8=1.

    I am not sure how you defined -55 Mod 7. It may be defined as a function returning the remainder when -55 is divided by 7. Then the exact result depends heavily on the definition. I know that there are all kinds of similar functions in programming languages: some return only positive numbers, others return the same sign as the first argument (-6 in this case), etc.

    C)Find the value of x such that: 9 * x 1 mod 10
    One option is to search through all possible x from 0 to 9. It is easy to see that 9\cdot9\equiv1\pmod{10}.

    Another way relies on the Euclidean algorithm and its consequence, Bézout's identity. The latter says that, since gcd(9,10) = 1, there exist integers s and t such that 9s+10t = 1. In general, s and t can be found working backwards the computation of the Euclidean algorithm; here it is obvious that -1 * 9 + 1 * 10 = 1. Considering this equality modulo 10, we get -1\cdot 9\equiv1\pmod{10}. Now, -1\equiv 10-1\pmod{10}, so 9\cdot9\equiv1\pmod{10}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2010
    Posts
    75
    I still dont understand why -55 mod 7 = 1 where does 7*8 come in? it is not given....

    Also,
    52^6 mod 73 = 27 How would you determine this WITHOUT using a calculator? My calculator results in an incorrect answer due to rounding
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    52^6 mod 73 = 27 How would you determine this WITHOUT using a calculator? My calculator results in an incorrect answer due to rounding
    Get a more powerful calculator , like this one (it's a shame I could not find a better-looking one). Or use an interpreter for a programming language that handles arbitrary-precision arithmetic, such as Scheme. Here you can evaluate expression like (modulo (expt 52 6) 73) or (expt 2 1000).

    Seriously, note that in calculating the remainder of 52 * 52 * 52 * 52 * 52 * 52 and 73 you can perform multiplication and finding remainder in an arbitrary order. You could do all multiplications first and divide then, or could take remainders first, multiply, and find the remainder last (this would be no different in this case because 52 mod 73 = 52.) However, note also that 52 * 52 mod 73 = 3.

    I still dont understand why -55 mod 7 = 1 where does 7*8 come in? it is not given....
    We have n\equiv n+km\pmod{m} for any k. In other words, you can add or subtract m without changing the number modulo m.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,531
    Thanks
    1389
    Quote Originally Posted by matthayzon89 View Post
    Hello All,
    I am currently preparing for an upcoming test. I know most of the material but the problems below is what I got stuck on, any help will be greatly appreciated!



    A) Determine φ(77) *Euler Totient function for 77+. (The first step is finding the largest number that you can multiply to get 77, i believe which is 7 and 11).

    B) -55 Mod 7= 1 (<- I dont understand. I know that -7 mod 55 equals 48 but I can't understand how they got 1 from -55 mod 7).
    7 divides into 55 7 times with remainder 6: 55= 7(7)+ 6. Of course, 6= -1 (mod 7) (since 6= 7- 1) so 55 = -1 (mod 7). Now multiply the equation by -1.

    Another way to say that: -55= -8(7)+ 1

    C)Find the value of x such that: 9 * x 1 mod 10 <- I have no clue
    You are missing an "=" aren't you? Do you mean "solve 9x= 1 (mod 10)"?

    That means you are seeking a multiple of 9 that is 1 more than a multiple of 10. 9*9= 81.

    More formally, you are looking for x such that 9x- 10k= 1 for some number k.
    9 divides into 10 once with remainder 1: 1(10)- 1(9)= 1 (I bet you already knew that!!) which means that we can set x= -1, k= -1. x= -1= 9 (mod 10).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. gcd questions (fairly simple)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 29th 2010, 09:52 PM
  2. Fairly simple limit proof?
    Posted in the Calculus Forum
    Replies: 7
    Last Post: June 27th 2010, 05:28 PM
  3. Fairly simple limit, but tricky variables
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 12th 2010, 07:40 PM
  4. Help with fairly simple, quick problem.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 26th 2008, 05:44 PM
  5. I need help with a fairly simple question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 29th 2008, 02:52 AM

Search Tags


/mathhelpforum @mathhelpforum