6
$\begingroup$

Find the remainder when $ 12!^{14!} +1 $ is divided by $13$

I faced this problem in one of my recent exam. It is reminiscent of Wilson's theorem. So, I was convinced that $12! \equiv -1 \pmod {13} $ after this I did some test on the exponent and it seems like $12!^{n!} +1\equiv 2\pmod {13}\forall n \in \mathbb{N}$.

After I came back home I ran some more test and I noticed that if $p$ is prime then $(p-1)!^{n!} +1\equiv 2\pmod {p}\forall n \in \mathbb{N}$.

I was wondering if this result is true, if yes how to prove it? If not what is the formal way for solving the mother problem.

  • 0
    Note that your 'for all' quantifier needs the caveat that $n\gt 1$; if $n=1$ then the sums are $0\bmod p$, not $2$.2012-06-07

2 Answers 2

7

By Wilson's Theorem, $12!\equiv -1\pmod{13}$. So for any non-negative even integer $m$, $(12!)^m+1\equiv (-1)^m+1\equiv 2\pmod{13}$. Since $0\le 2\lt 13$, it follows that $2$ is the remainder when $(12!)^m+1$ is divided by $13$.

If $m$ is odd, the same reasoning shows that $(12!)^m+1\equiv 0\pmod{13}$.

And $13$ is not particularly lucky or unlucky. The same result, with the same proof, holds if $13$ is replaced by any odd prime $p$, and $12$ is replaced by $p-1$.

The prime $2$ is slightly different. Whether $m$ is odd or even, $(1)^m +1\equiv 2\pmod{2}$, but the remainder is $0$, not $2$.

  • 0
    Aha that helps! Thanks a lot Andre :)2012-06-07
2

Hint $\ $ Unifying little Fermat and Wilson: $\rm C\:\!!^{\:\!C}\!\equiv 1\ mod\:\ C\!+\!1\:$ prime. Take your pick for a proof.