Turn on thread page Beta
    • Thread Starter
    Offline

    16
    ReputationRep:
    How would you use Euler's theorem to compute the remainder of A^n + B^m when divided be C.

    I'm guessing the division by C means the answer will be the remainder is congruent to something modulo C?

    I don't really know how to work this out. Also as A and B are different it makes it harder - I think lol.


    Can you help me please?

    Thank you
    • Study Helper
    Online

    15
    Study Helper
    (Original post by claret_n_blue)
    How would you use Euler's theorem to compute the remainder of A^n + B^m when divided be C.

    I'm guessing the division by C means the answer will be the remainder is congruent to something modulo C?

    I don't really know how to work this out. Also as A and B are different it makes it harder - I think lol.


    Can you help me please?

    Thank you
    Do you have specific values in mind?

    You could reduce them both separately then add the two results.
    • Thread Starter
    Offline

    16
    ReputationRep:
    (Original post by ghostwalker)
    Do you have specific values in mind?

    You could reduce them both separately then add the two results.
    C = 143
    A^n = 5^124
    B^m = 6^242
    • Study Helper
    Online

    15
    Study Helper
    (Original post by claret_n_blue)
    C = 143
    A^n = 5^124
    B^m = 6^242
    You have the necesary conditions to apply Euler's theorem to each of the terms. What's causing the problem?
    • Thread Starter
    Offline

    16
    ReputationRep:
    (Original post by ghostwalker)
    You have the necesary conditions to apply Euler's theorem to each of the terms. What's causing the problem?
    So the fact that I'm adding them doesn't change anything? Do I still use the theorem seperately on all the terms? Also, I don't get what I would have to do to find the remainder. If I wrote the answers a = b mod n, then would the remainder simply be 'b'?
    • Study Helper
    Online

    15
    Study Helper
    (Original post by claret_n_blue)
    So the fact that I'm adding them doesn't change anything? Do I still use the theorem seperately on all the terms? Also, I don't get what I would have to do to find the remainder. If I wrote the answers a = b mod n, then would the remainder simply be 'b'?
    It's basically modular arithmetic and you are looking for the value of the expression mod(143).

    Applying Euler's theorem to each of the terms in turn will reduce them to manageable size which you can then work out manually, then add, and finally the division by 143 to get the remainder.

    And your answer would just be "Remainder is..."
    Offline

    3
    ReputationRep:
    THis is my answer

    Spoiler:
    Show

    143 = 11 x 13

    \varphi(143)=(11-1) \times (13-1) = 120


    (5^124+6^242)mod 143 = R

    (5^120 x 5^4 )mod 143 = (1 x 5^4) mod 143 = 53
    (6^240 x 6^2 )mod 143 = (1 x 6^2) mod 143 = 36


    R = 53+36 = 89

    • Thread Starter
    Offline

    16
    ReputationRep:
    (Original post by noobynoo)
    THis is my answer

    Spoiler:
    Show

    143 = 11 x 13

    \varphi(143)=(11-1) \times (13-1) = 120


    (5^124+6^242)mod 143 = R

    (5^120 x 5^4 )mod 143 = (1 x 5^4) mod 143 = 53
    (6^240 x 6^2 )mod 143 = (1 x 6^2) mod 143 = 36


    R = 53+36 = 89


    Why does 5^120 become 1 and how do you get the answer 53 from 5^4 mod 143?

    I'm guessing it's the same for the second one as well.
    • Study Helper
    Online

    15
    Study Helper
    (Original post by claret_n_blue)
    Why does 5^120 become 1 and how do you get the answer 53 from 5^4 mod 143?

    I'm guessing it's the same for the second one as well.
    \varphi(143)=120

    And since 5 is coprime to 143, then by Euler's theorem 5^{120}\equiv 1 (mod 143)


    5^4=625 and when you divide it by 143, the remainder is 53.

    Edit: You could have added the two terms and then divided by 143 (which is what I was suggesting), or this way dividing by 143, and then adding the two. Either is fine.
    • Thread Starter
    Offline

    16
    ReputationRep:
    (Original post by ghostwalker)
    \varphi(143)=120

    And since 5 is coprime to 143, then by Euler's theorem 5^{120}\equiv 1 (mod 143)


    5^4=625 and when you divide it by 143, the remainder is 53.

    Edit: You could have added the two terms and then divided by 143 (which is what I was suggesting), or this way dividing by 143, and then adding the two. Either is fine.
    And is the second simply 36 because there is no remainder when you divide 36 by 143?
    • Study Helper
    Online

    15
    Study Helper
    (Original post by claret_n_blue)
    And is the second simply 36 because there is no remainder when you divide 36 by 143?
    36 is the remainder. It's less than 143 already, so you don't need to try and divide 143 into it.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: March 20, 2011

University open days

  1. University of Bradford
    University-wide Postgraduate
    Wed, 25 Jul '18
  2. University of Buckingham
    Psychology Taster Tutorial Undergraduate
    Wed, 25 Jul '18
  3. Bournemouth University
    Clearing Campus Visit Undergraduate
    Wed, 1 Aug '18
Poll
How are you feeling in the run-up to Results Day 2018?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.