1. Not finding help here? Sign up for a free 30min 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!

Finding remainder

  1. Jul 12, 2012 #1
    1. The problem statement, all variables and given/known data
    Find the remainder of [itex]\frac{25!}{29}[/itex]


    2. Relevant equations



    3. The attempt at a solution
    One of my friend asked me this question and i was clueless how should i start?
    (I am not sure that the question is correct.)

    Any help is appreciated!
     
  2. jcsd
  3. Jul 12, 2012 #2
    ??Find the remainder after you divide 25(Factorial) by 29.

    Do you know what a factorial is? (the ! symbol)
     
  4. Jul 12, 2012 #3
    I know what a factorial is. Wouldn't that be a difficult task, expanding 25! and dividing it by 29?
     
  5. Jul 12, 2012 #4
    Yea, I see your predicament. It's just a long number and would be a PITA to get at. But you take the nearest whole number from your result and multiply by 29. Subtract that from 25! and you'll get the remainder.
     
  6. Jul 12, 2012 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I believe Pranav-Arora is asking if there is a simpler way of calculating that since 29! is a huge number. And trying to use a calculator won't work because dividing by 29 will give a non-terminating decimal and you cannot get the remainder from the truncated decimal form.

    Unfortunately, since 29 is a prime number, I also do not see any way to simplify that.
     
  7. Jul 12, 2012 #6
    Yea the real problem that I see is most calculation software have their upper limit at around the 10^23 range...I know it was a big number, but I didn't think it was so large in my original post.
     
  8. Jul 12, 2012 #7
    Thanks for the effort HallsofIvy, i will see if the question is correct by confirming it from my friend. :smile:

    Btw, wolframalpha gives me this: http://www.wolframalpha.com/input/?i=remainder(25!/29)
     
  9. Jul 12, 2012 #8
    WolframAlpha gives the result as 5.

    Calculate 25!/9
    Truncate at the correct decimal place
    subtract 25! by the truncated result
    There ya go!
     
  10. Jul 12, 2012 #9

    Curious3141

    User Avatar
    Homework Helper

    The answer is 5.

    By Wilson's Theorem,

    28! = -1 (mod 29)

    25!(26)(27)(28) = -1 (mod 29)

    25!(-3)(-2)(-1) = -1(mod 29)

    25! = 6^(-1) (mod 29) = 5 (mod 29).

    The last step involved calculating the modular inverse of 6 (mod 29).
     
  11. Jul 12, 2012 #10
    Never heard of it, will check that out.

    I was afraid of this, i have never used the mod notation and i don't even know what that means. I think i will have to check that too. Thanks for the help Curious! :smile:
     
  12. Jul 12, 2012 #11
    Seems like mod is related to remainder.

    Can you tell me how did you replace 26,27 and 28 with -3,-2 and -1?

    I see at wikipedia that the congruence sign is used instead of equality sign.
     
  13. Jul 12, 2012 #12

    Curious3141

    User Avatar
    Homework Helper

    You may replace all the equals signs with congruence signs, I was just typing fast.

    26 = 29 - 3

    When you take everything modulo 29, on the RHS, you get: 29 = 0 (mod 29), so you're left with:

    26 = 0 + (-3) (mod 29) = -3 (mod 29)

    The same applies for the others.

    The most involved part is calculating the modular inverse of 6. For that, you can use any implementation of the Extended Euclidean Algorithm. I like the "magic box" method mentioned in wiki, it's very spinal and quick for small numbers.
     
  14. Jul 12, 2012 #13
    It is called modular arithmetic.

    It basically involves getting a remainder when a given number is divided by a certain integer. So when you have,

    [tex]a \equiv b (mod \ n)[/tex]

    a is the given number
    b is the remainder
    n is the divisor

    There are really interesting relations using this, and you can find them online. If you are still interested, look up Chinese remainder theorem, Fermat's little theorem, Wilson's theorem(which Curious used), and Euler's theorem.


    Edit : Seems I am late, but here is the post anyway.

    What is [tex]26 \equiv x(mod 29)[/tex] And so on...

    Take a look at this pdf file, too.
    http://aleph.math.louisville.edu/teaching/2011SP-311/notes-110209.pdf

    Do you see the property being used?
     
  15. Jul 12, 2012 #14
    I don't know much (or nothing) about modular arithmetic, most of the stuff is going off my head. I don't get it when you say take "modulo" on RHS. For example, in an equation, if we perform any action like multiplication, division etc on LHS, we do it the same on RHS, i don't know about this modulo thing, can we do it on one side of the equation?
     
  16. Jul 12, 2012 #15

    Curious3141

    User Avatar
    Homework Helper

    You're doing it on both sides because the statement [itex]a \equiv b \pmod n[/itex] is defining a congruence class modulo n. It's saying that a and b are equivalent in some way, specifically that they leave the same remainder when divided by n.

    I have to go to sleep now (past midnight here), but please read up on modular arithmetic in the meantime. :smile:
     
  17. Jul 12, 2012 #16
    Thanks for the help Curious! Good night, i will be studying about modular arithmetic and post some questions. :smile:

    @Infinitum: I am checking out the pdf file you linked to.

    [itex]26\equiv x\mod 29[/itex] means [itex]0\equiv(26-x)\mod29[/itex], am i right here? How can i calculate x from here?

    EDIT: Sorry that was a noob question. :tongue:
     
  18. Jul 12, 2012 #17
    That should be, [itex]0\equiv(x-26)\mod29[/itex]

    What remainder do you get when you divide 26 by 29? That's x.
     
  19. Jul 12, 2012 #18
    Why my expression is wrong?
    From my expression i can say that x=-3, because 26-(-3) mod 29=0.
     
  20. Jul 12, 2012 #19
    It isn't wrong. Saying the remainder is -3, as Curious explained in one of his above posts, is equivalent to saying that the remainder is 26. Its just intuitively easier to see a positive remainder over a negative one. Also, it comes with an advantage that you can see the numbers being 'subtracted' on both sides, just like in case of equality.
     
  21. Jul 12, 2012 #20
    Okay, i get it. You asked me what's the remainder when you divide 26 by 29. Shouldn't that be 26? This modular arithmetic is completely new thing to me. I have never dealt with negative remainders.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook