RMO Practice Problems - Number Theory #2

The given expression is equivalent to:

$\large\ a=23!+\frac { 23! }{ 2 } +\frac { 23! }{ 3 } +...+\frac { 23! }{ 23 }$

Observe that each term except $\large\ \frac { 23! }{ 13 }$ on the right hand side is divisible by $13$ .

Whence,

$\large\ a=\frac { 23! }{ 13 }$

$\large\ =12!14.15...23$

$\large\ =12!(1+13)(2+13)...(10+13)$

$\large\ \equiv 12!10! mod {13})$

Now, by Wilson Theorem we know that for any prime $p$ , we have $(p-1)! \equiv -1\pmod {p}$ .

Thus, $12! \equiv -1\pmod {13}) \equiv 12 \pmod {13}$ .

Hence,

$\large\ 11a\quad \equiv \quad 11\times 12\times 10!\quad (mod\quad 13)\\ \quad \quad \quad \quad \equiv \quad 12!\quad (mod\quad 13)\\ \quad \quad \quad \quad \equiv \quad -1\quad (mod\quad 13)$

Now,

$\large\ a\quad \equiv \quad 66a\quad (mod\quad 13)\quad \equiv \quad 6\times 11a\quad (mod\quad 13)\\ \quad \quad \equiv \quad -6\quad (mod\quad 13)\quad \equiv \quad 7\quad (mod\quad 13).$

and we are done.

So, Answer : $\boxed{7}$

Equivalent to $a \equiv \frac{23!}{13} \equiv 12! \cdot 10! \equiv \boxed{7} \text{ (mod 13)}$

This is an ARML question.

Alan Yan@ Your solution is very precise but I'd like u not to snub those who are having difficulty grasping it.

Use all sorts of ways to find that a/ 23! = 444316699/ 118982864

a = 23! 444316699/ 118982864 = 96538966652493066240000

Note that 2 x 5, 4 x 10, 6 x 15 and 8 x 20 give rise to ?0000, we can be confident that the a obtained is exact. 444316699 = 761 x 583859 is a result of addition for big prime number(s). (3^2) and (5) are cancelled between numerator and denominator of the big fraction.

96538966652493066240000 Mod 13 = 7

As others have stated, $a = \frac{23!}{13} \pmod {13}$ as all the other terms have a factor of $13$ in their factorial, so they equal $0$ modulo $13$ .

Modulo $13$ , this is just: $(1 \cdot 2 \cdot 3 \cdots 12) \cdot (14 \cdot 15 \cdots 23) \equiv 12! \cdot (1 \cdot 2 \cdots 10) \equiv 12! \cdot (1 \cdot 2 \cdots 10 \cdot 11 \cdot 12) \cdot 11^{-1} \cdot 12^{-1} \equiv 12! \cdot 12! \cdot 11^{-1} \cdot 12^{-1}.$

By Wilson's theorem, $12! \equiv -1 \pmod{13-1}$ since $13$ is prime. Also, if $a \equiv 12^{-1} \equiv (-1)^{-1} \pmod {13}$ , $(-1)a \equiv 1 \pmod {13} \Rightarrow a \equiv -1 \pmod {13}$ . Similarly, if $b \equiv 11^{-1} \equiv (-2)^{-1} \pmod {13}, -2b \equiv 1 \pmod {13} \Rightarrow b \equiv -7 \pmod {13}$ .

Altogether, we have that: $a \equiv -1 \cdot -1 \cdot -1 \cdot -7 \pmod {13} \Rightarrow a \equiv \boxed{7} \pmod {13}$ .