Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I know $$17! = 17 \times16\times15...\times1$$ So I was thinking maybe go $$17mod(13)\equiv4 \space \space and \space 16mod(13)\equiv3 ...$$ add all that together but that is too much work so I went

17-13 = 4

$$4! mod 13 \equiv 4 mod(13) \space 3 mod(13)... etc$$

4+3+2+1 = 10

Is this correct? Edit: Is this at least a correct answer?

EDIT 2: I just checked google calc 17! mod 13 = 0, so what did i do wrong?

share|improve this question

3 Answers 3

up vote 16 down vote accepted

$17!=17\times 16\times \dots \times 13\times \dots 1$ .So $17!$ is divisible by $13$ implying that $17!\equiv 0\mod 13$.

Note: If $m\ge n$ then $m!\equiv 0\mod n$ .

share|improve this answer
    
So 13! mod 13 is 0 –  Ghozt Jun 17 '13 at 13:04
1  
Wait is it because 0 * all the others is 0 –  Ghozt Jun 17 '13 at 13:06
2  
Yes thats one way of explaining. But I think the easiest way to explain it is to see that $13|17!$ –  Abhra Abir Kundu Jun 17 '13 at 13:08
1  
Your statement is correct, but $m! \pmod n$ can be zero even if $m \lt n$ depending on the factorization of $n$. For example $4!=24 \equiv 0 \pmod 8$ –  Ross Millikan Jun 17 '13 at 13:08
1  
@RossMillikan whatever you have said is true but I just wanted to mean that if $m\ge n$ then $m!\equiv 0\mod n$ –  Abhra Abir Kundu Jun 17 '13 at 13:12

I try to answer the what did I do wrong part.

So I know $$17! = 17 \times16\times15...\times1$$ So I was thinking maybe go $$17mod(13)\equiv4 \space \space and \space 16mod(13)\equiv3 ...$$

Ok, this is a good start.

add all that together

That's your mistake. Three lines earlier you said that factorial is defined by a multiplication, and now you're talking of addition. Multiplying all that together would have given you the right answer which is 0.

17-13 = 4 $$4! mod 13 \equiv 4 mod(13) \space 3 mod(13)... etc$$ 4+3+2+1 = 10

Same here, lots of confusion between addition and multiplication.

share|improve this answer
    
Use \mod n to get $\mod n$ and \pmod n to get $\pmod n$. –  Pedro Tamaroff Jun 17 '13 at 19:30

Your first try would have been good if (1) you had said "multiply all that together" instead of "add all that together" and (2) you had continued for a few more steps, so you'd be multiplying 4 (coming from 17 mod 13) times 3 (coming from 16 mod 13) times 2 (coming from 15 mod 13) times 1 (coming from 14 mod 13) times 0 (coming from 13 times 13). And then you can stop, because now your product is zero and will remain zero no matter what else you multiply it by. (Sometimes, multiplying a lot of numbers is actually easier than adding them.)

Your second try seems to be based on a plausible idea, namely that 17 is congruent to 4 mod 13, so you expect 17! to be congruent to 4!. Unfortunately, this expectation is not correct.

Furthermore, the failure of this expectation can be very instructive (maybe not for you, if you already know the following, but then for other readers). Students often get bored with theorems like "If $a\equiv b\pmod n$ and $c\equiv d\pmod n$ then $a+c\equiv b+d\pmod n$" especially if the next theorem says the same thing with subtraction in place of addition (i.e., $a-c\equiv b-d\pmod n$), and the theorem after that says the same thing for multiplication. Why can't we just make a general rule that $\equiv\pmod n$ works like equality, so, just as we can replace equals by equals and get equal results, we should be able to replace "congruents" by "congruents" and get congruent results? Well, the theorems say this works fine as long as all you're doing is adding, subtracting, and multiplying. But, as you saw in this problem, it does not work when you do other things to your numbers, like taking factorials. So there really is some value in those boring theorems --- they tell you in which contexts congruence behaves like equality.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.