6
$\begingroup$

Wilson's theorem asserts the following statement: $$(n-1)!\equiv -1\pmod n\Leftrightarrow n\text{ is prime.}\tag1$$ This means that $$\begin{align} n&{ \ \mid} \ \ (n-1)!+1 \\ \Leftrightarrow n&{ \ \mid} \ \ (n-1)!+1-n \\ &=(n-1)!-(n-1) \\ &= (n-1)\big((n-2)!-1\big) \\ \therefore n&{ \ \mid} \ \ (n-2)!-1 \\ \Leftrightarrow (n-2)!&\equiv 1\pmod n.\tag2\end{align}$$ Or, in the congruence, I could add $n$ to the right hand side, and then divide both sides by $n-1$, yeilding the same result.

I then asked myself, why wouldn't Wilson's theorem assert that $$(n-2)!\equiv 1\pmod n\Leftrightarrow n\text{ is prime,}$$ as opposed to $(1)$? It is more useful because $(n-2)! < (n-1)!$, so we can test this theorem with more primes without the factorial becoming too large as fast in $(1)$, and it is still just as interesting. However, I went here and found that it really is not that necessary to simplify the theorem.

Now, I have been trying to find some similar result for $(n-3)!$, and I found that $$(n-3)!\equiv \frac{n-1}{2}\pmod n\Leftrightarrow n\text{ is prime $> 2$.}$$

Main Question: If for some $k\in\mathbb{Z^+}$ and remainder $l_k\in\mathbb{Z}$, $$(n-k)!\equiv l_k\pmod n,\tag{$n$ is prime}$$ is there a pattern in the sequence $l_1, l_2, l_3,\ldots$?

Do there exist similar congruences for $(n-k)!$ such that $k > 3$?

Thank you in advance.


This post was inspired by this post.

$\endgroup$
  • $\begingroup$ Don't abuse notation. It is not true tbat $(n-1)!+1=(n-1)!-(n-1).$ $\endgroup$ – Thomas Andrews Apr 19 '18 at 2:35
  • 1
    $\begingroup$ $(n-1)!\equiv (-1)\cdot (n-2)!\pmod{n}$ all the time, so there really isn't a cost to computing $(n-1)!.$ It's just a multiplication of $-1\pmod{n}.$ $\endgroup$ – Thomas Andrews Apr 19 '18 at 2:37
  • $\begingroup$ @ThomasAndrews I know that. But it's just because of divisibility that we can cancel the $n$. If $n\mid a + n$ then of course $n\mid a$. That doesn't mean $a = a + n$. I know what u mean though $\endgroup$ – Feeds Apr 19 '18 at 4:45
  • 1
    $\begingroup$ It is a matter of taste whether residue $1$ is more useful than residue $-1$. Calculating $(n-2)!$ modulo $n$ is as difficult as calculating $(n-1)!$ modulo $n$ , so we still cannot find large primes with this criterion. And even if we calculate $(n-100)!$ modulo $n$ for very large $n$, it won't make a significant diffference in complexity. $\endgroup$ – Peter Apr 19 '18 at 19:13
1
+100
$\begingroup$

Note that since $n$ is prime, we can define the following: $$y \equiv \frac{a}{x} \pmod{m} \iff n \mid xy-a \space (x,y,a\neq 0) $$

We can use the same properties of congruence such as adding, subtracting, multiplying and dividing by relatively prime constants.

Now, to find $(n-2)! \pmod{n} \space$, we basically need to find $\frac{1}{n-1} \pmod{n}$. We can instead write $n-1 \pmod{n}$ as $-1 \pmod{n}$. Thus, we have $\frac{1}{-1} \equiv -1 \pmod{n} $ which gives you that $(n-2)! \equiv 1 \pmod{n}$ using Wilson's Theorem.

The same idea goes on for $(n-k)!$. We are to evaluate $\frac{1}{-k} \pmod{n}$. For $k=1$, we trivially get $-1$. For $k=2$, considering $n$ as an odd prime, we know that $2 \mid n+1$. Thus, $\frac{n+1}{2}$ is an integer from which we can derive $(n-3)! \pmod{n}$.

Unfortunately, this process can no longer continue. A prime can be any value modulo another odd prime less than it except $0$. Thus, we cannot detect any pattern.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer, but I had already figured this out. ‘Tis why I didn’t put a bounty on it, but I forgot to actually answer my own question.... however, your answer is nearly exactly the same as was my own, so I am gonna give you a tick. I’ll also give you a $+100$ bounty just because. Congratulations! $(+1)$ $\color{green}{\checkmark}$ $\endgroup$ – Feeds Sep 28 '18 at 5:02
  • 1
    $\begingroup$ Thank you. I'm glad I could be helpful. $\endgroup$ – Haran Sep 28 '18 at 7:50
  • 1
    $\begingroup$ It only took $5$ months, hahah :P (well, a "formal" answer, that is) $\endgroup$ – Feeds Sep 28 '18 at 7:51
  • 1
    $\begingroup$ If you are interested in understanding factorials modulo primes, there is a question I have asked regarding them. Any progress or insight would be appreciated. The question is: math.stackexchange.com/questions/2651733/… $\endgroup$ – Haran Sep 28 '18 at 7:55
  • 1
    $\begingroup$ Thanks. I will check it out :) $\endgroup$ – Feeds Sep 28 '18 at 7:55

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.