1
$\begingroup$

(1) How can you preconceive to prove by contradiction?

Prove by contradiction. Suppose $n$ is composite. This means there exists a divisor $d|n$ such that $1<d<n$. We are given that $(n-1)!\equiv-1(mod\ n)$ which means $n|[(n-1)!+1]$. Since $d|n$ so

$d|[(n-1)!+1]$ which gives $dk=\color{seagreen}{ (n-1)! }+1$ for some integer $k$.

From the first line, and independently from the above paragraph, we have $1 < d < n$. Therefore $d|(n-1) ! \implies \color{seagreen}{dm=(n-1)}$ ! for some integer $m$.

(2) How can you preconceive to consider $1 < d < n$ alone and separately, in the middle of the proof?

(3) Why $d|(n - 1)!$ ? By reason of $1 < d < n \iff 2 \le d \le n - 1$?

Substitute $dm$ into $dk$, $dk=dm+1 \iff d(k-m)=1 \iff d$ divides 1.

Origin — p4 — better than Jones p82 Question 4.20

$\endgroup$
1
  • 2
    $\begingroup$ The proof by contradiction comes after one finds out what's happenin' when $n$ is composite. Minor fooling around with a couple of numerical examples shows that in that case $(n-1)!$ will have stuff in common with $n$. Then one writes up a tight argument that pins it down. If you don't want to mention contradiction, you can write a non-contradiction proof that if $n$ is composite, then $(n-1)!$ and $n$ have a common divisor $d\gt 1$. $\endgroup$ May 10 '14 at 20:46
1
$\begingroup$

(1) How can you preconceive to prove by contradiction?

Consider a few examples. $3! = 6$, $4! = 24$, $5! = 120$. These are highly divisible numbers, and in particular $(n-1)!$ contains every number up to $n-1$. You therefore expect that if $n$ is not prime, then $(n-1)!$ will be divisible by $n$. Hence, prove by contrapositive, or alternately proof contradiction will do the trick. (Note: $n = 4$ is the only exception where $(n-1)!$ is not divisible by $n$, but it still has some of the same factors.)

Beyond that, note that proof by contradiction, in general, is easier than both a normal proof and a proof by contrapositive, because you get to assume twice as many things. Thus, when stuck, always try a proof by contradiction.

(2) How can you preconceive to consider $1 < d < n$ alone and separately, in the middle of the proof?

You essentially want to show that $(n-1)!$ has some of the same factors as $n$. Thus naturally you find some $d$ which should be in the expansion of $(n-1)!$. So you need $1 < d < n$.

(3) Why $d|(n - 1)!$ ? By reason of $1 < d < n \iff 2 \le d \le n - 1$?

Any positive integer less than $n$ is included in the expansion $$ (n-1)! = (n-1)(n-2) \cdots (2)(1). $$ In particular for $d$ to be in this expansion, we need $2 \le d \le n-1$. So yes, that is the correct reason.

$\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.