SOLUTION: 2.Which of the following is divisible by 13? a) 12! + 1 b)15! - 1 c) 14! + 1 d) none of these

Algebra ->  Divisibility and Prime Numbers -> SOLUTION: 2.Which of the following is divisible by 13? a) 12! + 1 b)15! - 1 c) 14! + 1 d) none of these       Log On


   

Question 1038874: 2.Which of the following is divisible by 13?
a) 12! + 1 b)15! - 1 c) 14! + 1 d) none of these

Found 2 solutions by ikleyn, jim_thompson5910:
Answer by ikleyn(52817) About Me  (Show Source):
You can put this solution on YOUR website!
.
2. Which of the following is divisible by 13? 

a) 12! + 1	     <--- This is divisible - I checked it in Excel.

b)15! - 1	     <--- This is not.

c) 14! + 1           <--- This is not.	

d) none of these


Answer by jim_thompson5910(35256) About Me  (Show Source):
You can put this solution on YOUR website!
Using modular arithmetic, we can find that
12 = -1 (mod 13)
11 = -2 (mod 13)
10 = -3 (mod 13)
9 = -4 (mod 13)
8 = -5 (mod 13)
7 = -6 (mod 13)


720 = 72*10 (mod 13)
720 = 7*10 (mod 13)
720 = 70 (mod 13)
720 = 5 (mod 13)

--------------------------------------------

Using those facts above, we can then do this


12! = 12*11*10*9*8*7*6*5*4*3*2*1

12! = (12*11*10*9*8*7)*(6*5*4*3*2*1)

12! = ((-1)*(-2)*(-3)*(-4)*(-5)*(-6))*(6*5*4*3*2*1) (mod 13)

12! = 720*720 (mod 13)

12! = 5*5 (mod 13)

12! = 25 (mod 13)

12! = -1 (mod 13)

-----------------------------------

Since 12! = -1 (mod 13), we can say

12! + 1 = -1 + 1 (mod 13)

12! + 1 = 0 (mod 13)

The 0 on the right side proves that 12!+1 is divisible by 13.

Put another way (12!+1)/13 is a whole number

So the answer is choice A

-------------------------------------

Side Note: the other terms have 13 in the factorial

eg: 15! = 15*14*13*12*...*3*2*1
so 15! is a multiple of 13 since 13 is a factor of 15!
adding or subtracting 1 from this will land you on a number that is NOT a multiple of 13. So that's why choice B is out. Choice C is very similar to choice B so it is eliminated for similar reasons.

Choice D is not true because choice A is true which contradicts choice D.

-------------------------------------

Once again, the final answer is a) 12! + 1