1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What would be the remainder?

  1. Jun 25, 2011 #1
    1. The problem statement, all variables and given/known data
    Hi!!
    This is not a homework question but it came in my test.
    What is the remainder when 4101 is divided by 101?


    2. Relevant equations
    (1+x)n-1 is always divisible by x.


    3. The attempt at a solution
    Only the equation given above came in my mind but i wasn't able to bring it in that form. I am not able to devise other way to solve it. :confused:

    Thanks!!
     
  2. jcsd
  3. Jun 25, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi Pranav-Arora! :smile:

    The easiest way to do this, is with Fermat's little theorem or Euler's theorem (see wiki).

    Most applicable here is Fermat's little theorem that says:
    For any prime p holds: [itex]a^p \equiv a \mod p[/itex]

    (Do you already know about this notation or should I explain? :wink:)


    Btw, is this IIT stuff or something?
     
    Last edited: Jun 25, 2011
  4. Jun 25, 2011 #3
    Hi I Like Serena!! :smile:

    Sorry!! But i don't know about Fermat's little theorem or Euler's theorem. :frown:
    And yes, it may be from the IIT previous year question papers because most of the time my teacher try to make us solve IIT paper like questions. :wink:
     
  5. Jun 25, 2011 #4
    It would be much appreciated if you explain me the notation. :smile:
     
  6. Jun 25, 2011 #5

    I like Serena

    User Avatar
    Homework Helper

    Well, I don't know what is expected from you here.
    Or whether you should know about these theorems already.
    Typically it would be first year university mathematics material (algebra).

    Actually there is an alternate way to do this for which you do not need to know these theorems. It's just more work.

    If we take for instance 43 and divide it by 10, we can also take the remainder of 42 divided by 10, multiply it by 4 and take the remainder again.
    The remainder of 42=16 is 6, multiplied by 4 is 24, and the remainder of 24 is 4.


    [itex]a \equiv b \mod c[/itex] is about the remainders in divisions.

    For instance [itex]10 \equiv 1 \mod 3[/itex] means that if you divide 10 by 3, the remainder is 1.
    And it is actually more generic, because you can also say [itex]10 \equiv 4 \mod 3[/itex], mearning that the remainders of 10 resp. 4 when divided by 3 are the same.



    I guess I shouldn't explain the theorems as they are probably out of scope for your current class material.
    Still, if you're interested, here goes:

    Wiki also states Fermat's little theorem without this notation: "Fermat's little theorem states that if p is a prime number, then for any integer a, ap − a will be evenly divisible by p. "

    101 is a prime, meaning that it is only divisible by 1 and by itself.

    Since 101 is a prime, this means that 4101 - 4 divided by 101 has remainder 0.
     
    Last edited: Jun 26, 2011
  7. Jun 26, 2011 #6
    Thanks for your explanation!! :smile:
    So if i do it like this, subtract and add 4 to 4101, what i get is this:-
    4101-4+4
    As you said that 4101-4 is completely divisible by 101, so here +4 is left. Therefore the remainder is 4.
    Am i right..?
     
  8. Jun 26, 2011 #7

    I like Serena

    User Avatar
    Homework Helper

    Yep! :smile:
     
  9. Jun 26, 2011 #8
    Thanks!!:smile:
    I would also like to know where this Fermat's little theorem is applicable. Would you please tell me? :smile:
     
  10. Jun 26, 2011 #9

    I like Serena

    User Avatar
    Homework Helper

    It's applicable whenever you have a problem with numbers involving remainders and exponentiation! :smile:

    Application in real life is typically in cryptography.
    It is used (actually the generalization Euler's theorem) in the RSA encryption technique (http://en.wikipedia.org/wiki/RSA).
    This encryption scheme is used world wide for all secure communication across the internet.
     
  11. Jun 26, 2011 #10
    When i checked wikipedia, it isn't stated anywhere that "Fermat's little theorem states that if p is a prime number, then for any integer a, ap − a will be evenly divisible by p. " Rather it is stated "if p is a prime and a is an integer coprime to p, then ap−1 − 1 will be evenly divisible by p." :confused:
     
  12. Jun 26, 2011 #11

    I like Serena

    User Avatar
    Homework Helper

    Are you looking at the same page I did?
    http://en.wikipedia.org/wiki/Fermat's_little_theorem

    What you mention is the alternate form, which is mentioned in the wiki page right after the text I quoted.
    I prefer the version I quoted, since it does not put a constraint on "a".
    (And I didn't have to explain what "coprime" means.) :smile:
     
  13. Jun 26, 2011 #12
    Yes, i am looking at the same page. When i tried to solve using this statement " if p is a prime and a is an integer coprime to p, then a p−1 − 1 will be evenly divisible by p." then too i got the remainder 4. :smile:

    Oops!! I didn't noticed it!! :biggrin:

    And yes i know what a coprime is. :biggrin:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What would be the remainder?
Loading...