5
$\begingroup$

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?

$\endgroup$

3 Answers 3

16
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ So 13! mod 13 is 0 $\endgroup$
    – Ghozt
    Jun 17, 2013 at 13:04
  • 1
    $\begingroup$ Wait is it because 0 * all the others is 0 $\endgroup$
    – Ghozt
    Jun 17, 2013 at 13:06
  • 2
    $\begingroup$ Yes thats one way of explaining. But I think the easiest way to explain it is to see that $13|17!$ $\endgroup$ Jun 17, 2013 at 13:08
  • 1
    $\begingroup$ 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$ $\endgroup$ Jun 17, 2013 at 13:08
  • 1
    $\begingroup$ @RossMillikan whatever you have said is true but I just wanted to mean that if $m\ge n$ then $m!\equiv 0\mod n$ $\endgroup$ Jun 17, 2013 at 13:12
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Use \mod n to get $\mod n$ and \pmod n to get $\pmod n$. $\endgroup$
    – Pedro
    Jun 17, 2013 at 19:30
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .