Let $a\in\mathbb{N}$ be such that $1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{23}=\frac{a}{23!}$. Find $a$ mod 13.

My working:
By Wilson's Theorem, 23 is prime so $22!\equiv-1$ (mod 23) $\implies 23!\equiv0$ (mod 23).
13 is prime so $12!\equiv -1$ (mod 13) $\implies 13!\equiv0$ (mod 13)

I cannot find any other Theorem to use, and I am also struggling to relate 23 and 13. I also have little clue about how to work on fraction.

Can anybody please give some help? Thank you.

  • 2
    $\begingroup$ You don't need Wilson's theorem to prove that $n! \equiv 0 \pmod{n}$... that's trivial because $n! = \color{red}{n} \cdot (n-1) \dotsm 1$. $\endgroup$ – A.P. Nov 19 '15 at 11:19

Multiply the original equation through by $23!$. Then you have $a$ on the right and a number of integer terms on the left. All but one of the left-hand terms will be divisible by 13.

So all you have to find is $$ 1\cdot2\cdot3\cdots11\cdot12\cdot14\cdot15\cdots22\cdot23 \bmod 13 $$ This is the same as $$ \frac{(1\cdot2\cdot3\cdots11\cdot12)\cdot(14\cdot15\cdots24\cdot 25)}{24\cdot25} \bmod 13 $$ but even without Wilson's theorem, each factor in the 1-to-12 part of the numerator pairs up with its inverse modulo 13 in the 14-to-25 part, so this is the same as $$ \frac{1}{24\cdot 25} \equiv \frac1{(-2)(-1)} \equiv \frac12 \pmod{13} $$


$\Rightarrow \frac{2\cdot 3\cdot 4\cdot \cdot \cdot 22 \cdot 23+....+ 1 \cdot 2\cdot 3\cdot \cdot 20\cdot 21\cdot 22}{23!}=\frac{a}{23!}$

By comparison, we see that $a=2\cdot 3\cdot 4\cdot \cdot \cdot 22 \cdot 23+....+ 1 \cdot 2\cdot 3\cdot \cdot 20\cdot 21\cdot 22 = \frac{23!}{1}+\frac{23!}{2}+\frac{23!}{3}+\ldots+\frac{23!}{23}$

Now as we can see, $a \equiv \frac{23!}{13} \pmod {13}$

Rest can be simplified.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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