7
$\begingroup$

I need to show that if $(n-2)! \equiv 1 \pmod n$ then $n$ is prime.
I think that if $n$ is composite, then we'll have every factor of $n$ in $(n-2)!$, and it would yield that $(n-2)! \equiv 0 \pmod n$.
However, I didn't use the fact that it specifically congruent to $1 \bmod n$, so I think I'm getting something fundamental wrong. Is my solution correct? Why do we demand congruence to $1 \bmod n$?

$\endgroup$
  • 6
    $\begingroup$ $(4-2)!\not\equiv 0\pmod{4}$, but for $n>4$ you are correct that if $n$ is composite then $(n-2)!\equiv 0\pmod{n}$. $\endgroup$ – Thomas Andrews Feb 1 '17 at 21:01
  • 6
    $\begingroup$ A superior reference for Wilson's theorem: mathworld.wolfram.com/WilsonsTheorem.html $\endgroup$ – David R. Feb 1 '17 at 21:29
  • 4
    $\begingroup$ Is proving Wilson's theorem earlier or later in your syllabus? $\endgroup$ – Robert Soupe Feb 6 '17 at 20:25
  • 3
    $\begingroup$ @RobertSoupe My guess would be earlier. $\endgroup$ – Mr. Brooks Feb 6 '17 at 22:15
  • 5
    $\begingroup$ @Mr.Brooks My guess would be later. Or whatever is worse from a pedagogical point of view, now that Betsy DeVos is Secretary of Education. Mwahahaha! $\endgroup$ – The Short One Feb 8 '17 at 21:47
4
$\begingroup$

Your solution is correct aside from the small detail of 4!, which has already been pointed out in the comments. 4 is somewhat special, being the first composite number, and the square of the "oddest" prime. So I don't think this little mistake is at all "fundamental."

Still, I think it's better to use the fact of $1 \bmod n$, since it guarantees that $\gcd((n! - 2), n) = 1$. The least prime factor of $n$, if $n$ is not itself prime, is less than or equal to $\sqrt n$, and $\sqrt n < (n - 2)$ for all $n > 4$. Therefore, if $n$ is composite, then $(n - 2)!$ is divisible by the least prime factor of $n$, making $(n - 2)! \equiv 1 \bmod n$ impossible.

Yet another way you can go about it is this: If $n$ is even and composite, then $n - 2$ is also even and therefore $(n - 2)! \equiv 2k \bmod n$, where $k$ is some nonnegative integer we don't care too much about. But 1 is not even, proving $n$ is not an even composite number. If $n$ is odd and composite, it is divisible by some odd prime $p \leq \sqrt n$. And since $p \leq \sqrt n < (n - 2)$, it follows that $p \mid (n - 2)!$ and $(n - 2)! \equiv pk \bmod n$. And $pk \neq 1$, proving $n$ is not an odd composite number.

And yet another way is to use Wilson's theorem, but then I would be merely restating one or two of the other answers.

$\endgroup$
2
$\begingroup$

If $n=p^2$ where $p>2$ is a prime number, $(n-2)!$ contains $p$ and $2p$ inside it, so it is $0$ modulo $p^2$. If $n=2^2$, then $(n-2)!\equiv 2$. In all other cases it is easy to see that composite $n=ab$ where $a\ne b$, and then $(n-2)!$ contains both $a$ and $b$ and is $0$ modulo $n$. If $p$ is prime, then $(-1)(n-2)!\equiv(n-1)!\equiv -1$ by Wilson's theorem and so $(n-2)!\equiv 1$.

So generally you use the fact that $(n-2)!$ is not $0$ or $2$, it is not necessary to know that it is exactly $1$. Just cause it cannot be anything except $0,1,2$.

$\endgroup$
  • $\begingroup$ "1 does not divide p"???? $\endgroup$ – fleablood Feb 1 '17 at 21:26
  • $\begingroup$ Thanks, I meant other way around. $\endgroup$ – Wolfram Feb 1 '17 at 21:27
  • $\begingroup$ if $n=3^2$ then $(9-2)! \equiv 0 \text{ }mod9$ $\endgroup$ – sel Feb 1 '17 at 21:28
  • $\begingroup$ I don't quite understand how you get (p^2 -2)! \equiv 1 mod p^2 means p|1. $\endgroup$ – fleablood Feb 1 '17 at 21:29
  • $\begingroup$ Ok, I'm just wrong then. Of course, 2p is also in $(n-2)!$ when $p>2$. $\endgroup$ – Wolfram Feb 1 '17 at 21:29
2
$\begingroup$

As $\mathbb{Z}_n$ is a commutative unitary ring, all we need to prove is that every element has inverse, so it'd be a field and then $n$'d be prime. Is easy to see from the hypothesis than for any $k\leq n-2$ we have the inverse. Then we just note that $-(n-2)!\mod n$ is the inverse of $(n-1)$, 'cause: $$-(n-1)(n-2)!=-(n-1)\dot{}1=1\mod n$$

$\endgroup$
1
$\begingroup$

Let $n = a*b; n > 4$ and neither $b$ nor $a$ is $1$.

First off: both $b$ and $a$ are less than $n-2$. This should be clear when you consider if $b \ge n-2$ then $a = \frac nb \le \frac n{n-2} < \frac n{n- \frac 12 n} = 2$ so $a < 2$ which contradicts our hypothesis. (Note: we need $n > 4$ to know that $n- 2 > n- (\frac 12 n)$)

If $a \ne b$ then $(n-2)! = \prod_{k \le n-2;k \in \mathbb N} k$ and $\frac {(n-2)!}{ab} = \prod_{k \le n-2;k \ne a; k\ne b;e \in \mathbb N}k \in \mathbb Z$ so $(n-2)! \equiv 0 \mod ab = n$.

If $a = b$ and $n = a*b$ is the only possible factorization then $n = a^2$ and $a$ is prime.

But as $n > 4$ we have $a > 2$ so we have $a < 2a < a^2 - 2 < a^2$ so $\frac{(a^2 - 2)!}{a^2} = 2*\prod_{k\le a^2 -2; k \ne a; k \ne 2a k \in \mathbb N}k$.

So $(n-2)! \equiv 0 \mod n$ if $n$ is composite.

So if $(n-2)! \not \equiv 0 \mod n$ for $n > 4$ then $n$ must be prime.

Of course, we haven't proven that $(p-2)! \ne 0 \mod p$ (although that's obvious) or that there are any $(p-2)! \equiv 1 \mod p$ (not as obvious).

$\endgroup$

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.