Hey there! Sign in to join this conversationNew here? Join for free
    • 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
    Offline

    13
    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
    Offline

    13
    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
    Offline

    13
    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
    Offline

    13
    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
    Offline

    13
    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.
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Would you rather give up salt or pepper?
    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
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • 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.