In other words,
16! divided by 17, remainder is 16.
12! divided by 13, remainder is 12
10! by 11, remainder is 10
and so on.
This has an interesting extrapolation. For any prime number 'p', (p-2)! divided by p leaves a remainder of 1.
15! divided by 17, remainder is 1.
11! divided by 13, remainder is 1
9! by 11, remainder is 1
and so on.
The proof for this theorem is interesting. If we take any prime 'p', we can have two interesting observations about it
1. For any number that leaves a remainder 'a' on division by p, we can find a unique remainder 'b' on division by p such that a*b leaves a remainder of 1 on division by p. (An extrapolation of Linear Congruence Theorem)
2. For any prime p, of there is a number n such that n^2 leaves a remainder 1 on division by p, then n has to leave a remainder either 1 or -1 on division by p. The proof for this is fairly simple.
If n^2 leaves a remainder of 1 on division by p, then n^2 = kp + 1. or (n -1) (n +1) should be a multiple of p. If p > 2, then either n -1 or n + 1 has to be a multiple of p. Or, n divided by p leaves a remainder of 1 or -1 on division by p.
So, if we take (p-1)!, this is nothing but 1 * 2 * 3 * 4 * ....(p-1). Of these let us remove 1 and (p-1), the remaining p - 3 numbers can be paired up as a * b such that a*b leaves a remainder of 1 on division by p. They will be ( p-3)/2 such pairs. The product of all these pairs multiplied together will leave a remainder of 1 on division by p.
So, 1 * 2 * 3 * ......(p-1), will effectively leave a remainder 1 * 1 * (p-1) = (p -1).
Fabulous theorem. But one can almost take it for granted that the CAT will not have a question based on this theorem in the exam. This will get slotted under the category of 'too tough to be tested in CAT'.
Similarly, Fermat's Little Theorem and Euler's Phi function would also be considered too tough for CAT.