If n>4 is composite, then n divides (n-1) ?

[Math100]

Homework Statement

Establish the following statement:
If $n>4$ is composite, then $n$ divides $(n-1)!$.

Relevant Equations

None.

Proof:

Suppose $n>4$ is composite.
Then $n$ is either even or odd.
Now we consider these two cases separately.
Case #1: Let $n=2k$ for some $k\in\mathbb{Z}$.
Then we have $n\mid (n-1)! = 2k\mid (2k-1)!$.
Thus, $n$ divides $(n-1)!$.
Case #2: Let $n=2k+1$ for some $k\in\mathbb{Z}$.
Then we have $n\mid (n-1)! = (2k+1)\mid (2k+1-1)!$
= $(2k+1)\mid (2k)!$.
Thus, $n$ divides $(n-1)!$.
Therefore, if $n>4$ is composite, then $n$ divides $(n-1)!$.

 

[fresh_42]

Homework Statement:: Establish the following statement:
If $n>4$ is composite, then $n$ divides $(n-1)!$.
Relevant Equations:: None.

Proof:

Suppose $n>4$ is composite.
Then $n$ is either even or odd.
Now we consider these two cases separately.
Case #1: Let $n=2k$ for some $k\in\mathbb{Z}$.
Then we have $n\mid (n-1)! = 2k\mid (2k-1)!$.

You cannot use $n\mid (n-1)!$ since this is what you want to prove. So why do we have this?

Thus, $n$ divides $(n-1)!$.
Case #2: Let $n=2k+1$ for some $k\in\mathbb{Z}$.
Then we have $n\mid (n-1)! = (2k+1)\mid (2k+1-1)!$
= $(2k+1)\mid (2k)!$.
Thus, $n$ divides $(n-1)!$.
Therefore, if $n>4$ is composite, then $n$ divides $(n-1)!$.

Do you know what a proof by induction is?

 

[Math100]

I've heard of it, but how can mathematical induction be applied here? What would be the base case?

 

[fresh_42]

I've heard of it, but how can mathematical induction be applied here? What would be the base case?

I'm not sure whether this is the right way, it was just an idea.
The base case would be $n=6$. In this case, we have $(n-1)!=5!=120$ and $6\,|\,120.$
The induction step is the problem since either $n$ or $n+1$ could be a prime and we cannot use the induction hypothesis. Seems to be a bad idea, sorry.

If $n$ is square-free, i.e. its decomposition into primes is $n=p_1\cdot\ldots\cdot p_k$ and has only different primes all to the power $1$, then it is easy: Because $n$ is composite, we have $k>1.$ Then all primes are strictly smaller than $n$ and thus occur in the product $(n-1)!=1\cdot 2\cdot 3\cdot 4 \cdot \ldots \cdot (n-2)\cdot (n-1).$

But what if a prime factor of $n$ occurs twice or more times, e.g. $12=2^2\cdot 3$?

 

[PeroK]

The key here is to consider powers of primes that divide $n$.

 

[PeroK]

Hint: Consider each prime $p$ that divides $n$. There are two cases: $n = p^k$ and $n = m \times p^k$, where $m > 1$.

 

[nuuskur]

In general, for divisibility problems, induction is not a fruitful idea. The reason is that knowing something about the factors of $n$ tells you nothing about the factors of $n+1$. Moreover, this particular problem concerns composites. You have no way of predicting what the successor composite is during the induction step.

In your attempt, where are you invoking the fact that $n$ is composite? Clearly, compositeness is required, because $5\mid 4!$ does not hold, among others.

 

[Math100]

Proof:

The proof is by mathematical induction.
(1) When n=6, the statement is $6\mid (6-1)!$,
or $6\mid120$, which is true.
(2) Now assume the statement is true for some composite $n=k>4$, that is,
assume $k\mid(k-1)!$.
This means $(k-1)!=ka$ for some $a\in\mathbb{Z}$.
We need to show that $(k+1)\mid(k+1-1)!$.
Observe that $(k+1)\mid (k+1-1)!$ gives us $(k+1)\mid k!$.
Since $k!=k\cdot (k-1)!$, it follows that $(k+1)\mid k\cdot (k-1)!$.
Thus, $k\cdot (k-1)!=(k+1)a$ for some $a\in\mathbb{Z}$,
which implies that $ka+a=k\cdot (k-1)!$,
and so $ka=k\cdot (k-1)!-a$.
Therefore, if $n>4$ is composite, then $n$ divides $(n-1)!$.

 

[nuuskur]

Your induction is not conducted on $\{n\in\mathbb N \mid n>4\}$, but $\mathbb N\setminus (\mathbb P \cup \{1,2,3,4\})$. I don't know of any reasonable way to correctly do the step.

Your proof cannot be correct, because $6\mid 5!$ does not imply $7\mid 6!$, among others. I've already commented this in #7, please do not put symbols together in autopilot.

More precisely, this is where your argument fails:

Observe that $(k+1)\mid (k+1-1)!$ gives us $(k+1)\mid k!$.
Since $k!=k\cdot (k-1)!$, it follows that $(k+1)\mid k\cdot (k-1)!$.

$(k+1)\mid k!$ is something we need to show as you also pointed out earlier. Your proof is begging the question. Do not do that. In the terminology of @fresh_42 , you are not generating truth.

The following should work. Let $n>4$ be composite (obviously $4\mid 3!$ does not hold) and put $n=uv$, where $u\neq 1$ and $v\neq 1$. Then $u+v\leqslant n-1$, so it follows that
$$n=uv \mid u!v! \color{red}{\mid} (u+v)! \mid (n-1)!$$
The divisibility in red holds, because $\binom{u+v}{u}$ is an integer. Fill in the blanks.

Probably overkill with the binomials, a more elementary proof should be possible.

 

[PeroK]

Let's take an example to see what's happening. Suppose $n = 3^k\times 5^l$, where $k, l \ge 1$. We have: $3^k \le \frac n 5 < n -1$ and $5^l \le \frac n 3 < n-1$. Hence, both factors appear in $(n-1)!$ and $n \ | \ (n-1)!$.

That can be extended to any composite prime factorisation for $n$, leaving the case where $n = p^k$ for some prime $p$. Again, you could use $p = 3$ as an example to see how to prove that.

Note: somewhere in the proof $n = 2^2$ must emerge as an exception.

 

[PeroK]

What happened to this problem?

 

[nuuskur]

I think your approach is very clean-cut and elegant: $a\mid c, b\mid c$ implies $[a,b]\mid c$, where $[\, ,]$ denotes the least common multiple.

 

[PeroK]

I think your approach is very clean-cut and elegant: $a\mid c, b\mid c$ implies $[a,b]\mid c$, where $[\, ,]$ denotes the least common multiple.

I meant that the OP is now posting further problems and this one seems to have been forgotten!