If ## n>1 ##, show that ## n ## is never a perfect square

[Math100]

Homework Statement

If $n>1$, show that $n!$ is never a perfect square.

Relevant Equations

None.

Proof:

Let $n>1$ be an integer.
By definition of factorial, $n!=n\times (n-1)\times \dotsb \times 1$.
Now we consider two cases.
Case #1: Suppose $n$ is odd.
Then $n=2k+1$ for $k\geq 1$.
Note that $n!=(2k+1)!=(2k+1)\times (2k+1-1)\times \dotsb \times 1\implies (2k+1)\times (2k)\times \dotsb \times 1$.
Thus, $n!$ is not a perfect square.
Case #2: Suppose $n$ is even.
Then $n=2k$ for $k\geq 1$.
Note that $n!=2k\times (2k-1)\times \dotsb \times 1$.
Thus, $n!$ is not a perfect square.
Therefore, $n!$ is never a perfect square.

 

[SammyS]

Homework Statement:: If $n>1$, show that $n!$ is never a perfect square.
Relevant Equations:: None.

Proof:

Let $n>1$ be an integer.
By definition of factorial, $n!=n\times (n-1)\times \dotsb \times 1$.
Now we consider two cases.
Case #1: Suppose $n$ is odd.
Then $n=2k+1$ for $k\geq 1$.
Note that $n!=(2k+1)!=(2k+1)\times (2k+1-1)\times \dotsb \times 1\implies (2k+1)\times (2k)\times \dotsb \times 1$.
Thus, $n!$ is not a perfect square.
Case #2: Suppose $n$ is even.
Then $n=2k$ for $k\geq 1$.
Note that $n!=2k\times (2k-1)\times \dotsb \times 1$.
Thus, $n!$ is not a perfect square.
Therefore, $n!$ is never a perfect square.

That is not convincing.

You might consider prime factors. - in particular, the largest prime factor. Can it appear more than once, i.e. can it appear as a squared factor?

 

[valenumr]

This has been asked here before:

Spoiler on link.

https://www.physicsforums.com/threa...ares-of-natural-numbers.1011489/#post-6590665

Formally proving it might be non-intuitive, but the starting point is that every factorial will have a factor that is a unique prime. Once you understand that concept, it shouldn't too difficult.

 

[nuuskur]

Start from definitions. A number $N$ is a perfect square if and only if every prime factor of $N$ has even power.

Note that $n!=2k\times (2k-1)\times \dotsb \times 1$.
Thus, $n!$ is not a perfect square.

The terms in $n!=\prod _{k\leqslant n} k$ are not all prime, so the conclusion you claim is not immediate.

 

[pbuk]

Yet again you write a lot that is irrelevant but do not write anything that actually proves the desired result. You don't need any of this:

Let $n>1$ be an integer.
By definition of factorial, $n!=n\times (n-1)\times \dotsb \times 1$.
Now we consider two cases.
Case #1: Suppose $n$ is odd.
Then $n=2k+1$ for $k\geq 1$.

Instead, your attempt at a proof can be written as below. The statements coloured red are of course inadequate as part of a proof (if we could see immediately that $2k\times (2k-1)\times \dotsb \times 1$ is not a perfect square then we wouldn't have to prove the hypothesis in the question).

1. If $n$ is odd, $n!=(2k+1)!=(2k+1)\times (2k+1-1)\times \dotsb \times 1\implies (2k+1)\times (2k)\times \dotsb \times 1$, which is not a perfect square.
2. If $n$ is even, $n!=2k\times (2k-1)\times \dotsb \times 1$, which is not a perfect square.
3. Therefore, $n!$ is never a perfect square.

 

[Math100]

How about using/applying the Bertrand conjecture? Will that work? I know that the Bertrand conjecture states for $n>1$, there exists a prime $p$ such that $n<p<2n$. But then how can we use/apply this conjecture in here?

 

[SammyS]

How about using/applying the Bertrand conjecture? Will that work? I know that the Bertrand conjecture states for $n>1$, there exists a prime $p$ such that $n<p<2n$. But then how can we use/apply this conjecture in here?

Yes, Bertrand's conjecture (Bertrand–Chebyshev theorem) will work nicely here.

Since the variable, $n$ is used in the statement of this exercise, use some other variable name, such as $k$ when invoking Bertrand, where $2k = n$ or $2k =n+1$ depending on $n$'s being even or being odd.

 

[Math100]

But what can I do with these two cases of $n$? I know that $n=2k+1$ for odd and $n=2k$ for even. How should I apply/use that for $k<p<2k$, the Bertrand's conjecture?

 

[Orodruin]

But what can I do with these two cases of $n$? I know that $n=2k+1$ for odd and $n=2k$ for even. How should I apply/use that for $k<p<2k$, the Bertrand's conjecture?

You don’t need to split this into cases.

 

[Math100]

You don’t need to split this into cases.

But what can we do with the Bertrand's conjecture, given that $n<p<2n$ for some prime $p$?

 

[Orodruin]

But what can we do with the Bertrand's conjecture, given that $n<p<2n$ for some prime $p$?

Take the largest prime factor in your number. How many times does it appear in the product?

 

[SammyS]

But what can we do with the Bertrand's conjecture, given that $n<p<2n$ for some prime $p$?

Answering @Orodruin's question is the key here.

Just keep in mind that you want to apply Bertrand for some integer, $k$, so that if $k<p<2k$,
then $p\le n$ and $n<2p$ .

 

[Math100]

Suppose for the sake of contradiction that $n!$ is a perfect square.
Let $p$ denote the largest prime such that $p\leq n$.
Then $p\mid n!$.
Since $n!$ is a perfect square,
it follows that $p^2\mid n!\implies p\mid (\frac{n!}{p})$.
Note that $\frac{n!}{p}=1\cdot 2\cdot 3\dotsb (p-1)(p+1)\dotsb n$
where $\frac{n!}{p}$ must have $2p$ as its factor.
Thus $n<2p$, so $p\mid n!$ but $p^2\nmid n!$, which is a contradiction.
Therefore, if $n>1$, show that $n!$ is never a perfect square.

 

[fresh_42]

Suppose for the sake of contradiction that $n!$ is a perfect square.
Let $p$ denote the largest prime such that $p\leq n$.
Then $p\mid n!$.
Since $n!$ is a perfect square,
it follows that $p^2\mid n!\implies p\mid (\frac{n!}{p})$.
Note that $\frac{n!}{p}=1\cdot 2\cdot 3\dotsb (p-1)(p+1)\dotsb n$
where $\frac{n!}{p}$ must have $2p$ as its factor.

Yes, $\dfrac{n!}{p}=(2p)\cdot( 3\dotsb (p-1)(p+1)\dotsb \dfrac n p)$

Thus $n<2p$, ...

Why? What if $n=p^4$ for example?

... so $p\mid n!$ but $p^2\nmid n!$, which is a contradiction.
Therefore, if $n>1$, show that $n!$ is never a perfect square.

Maybe @SammyS can give us another hint. I share your problems to see the solution. I suppose it is one of these examples where I cannot see the obvious. Happens.

 

[Math100]

Yes, $\dfrac{n!}{p}=(2p)\cdot( 3\dotsb (p-1)(p+1)\dotsb \dfrac n p)$


Why? What if $n=p^4$ for example?Maybe @SammyS can give us another hint. I share your problems to see the solution. I suppose it is one of these examples where I cannot see the obvious. Happens.

From $p\leq n<2p$.

 

[Math100]

$n\neq p^4$

 

[Math100]

Given the fact that $p\leq n$.

 

[fresh_42]

Given the fact that $p\leq n$.

Say $n=83521.$ Why is $83521!$ not a perfect square?

 

[Math100]

Because there exists a prime $p$ in the prime factorization of the integer 83521 only once, thus $p^2\nmid 83521!$.

 

[fresh_42]

Because there exists a prime $p$ in the prime factorization of the integer 83521 only once, thus $p^2\nmid 83521!$.

No. $83521=17^4.$ The largest and only prime factor is $17$ and $n \not\lt 2\cdot 17.$ So your proof does not work in this case. I do not see why $83521!$ shouldn't be a square.

 

[Math100]

I am surprised yet puzzled. Then why is the problem asking us to prove if $n>1$, show that $n!$ is never a perfect square? We have a counterexample then. Since when $n=83521$, it fails to prove that $n!$ is never a perfect square.

 

[fresh_42]

I am surprised yet puzzled. Then why is the problem asking us to prove if $n>1$, show that $n!$ is never a perfect square? We have a counterexample then. Since when $n=83521$, it fails to prove that $n!$ is never a perfect square.

This is no counterexample because $83521!$ isn't a perfect square.

 

[Math100]

Because $p^2\nmid 83521$ when $p=17$.

 

[Math100]

But since $n\nless 2p$, how should I correct my proof, knowing that my proof doesn't work in this case.

 

[fresh_42]

But since $n\nless 2p$, how should I correct my proof, knowing that my proof doesn't work in this case.

In my example, we have $p=83497$ which divides $n!=83521!$ This $p$ is too big to occur twice in the prime factorization of $n!$ So the question is: how can we make sure, that such a big prime always exists?

 

[Math100]

$p\leq n$

 

[fresh_42]

Think of it from behind with my example in mind. All prime factors of $n!$ are smaller than or equal $n$. If $n!$ is a perfect square then all primes occur even times. Now what if we could find a prime factor of $n!$ that is bigger than $\sqrt{n}$ but still smaller than $n$.

a) Would this prime do the job?
b) How can we guarantee its existence?

 

[SammyS]

Maybe @SammyS can give us another hint. I share your problems to see the solution. I suppose it is one of these examples where I cannot see the obvious. Happens.

The idea is not to do a complete prime factorization of $n!$ . It's only to find one prime number in the factorization of $n!$ which occurs only "once", i.e. find a prime factor of $n!$ with multiplicity of 1 .

Simply think of the factors of $n!$ as a list of the integers in increasing order from $1$ through $n$. Choose $k$ to be halfway through the list, such that $2k\ge n$.

 

[fresh_42]

The idea is not to do a complete prime factorization of $n!$ . It's only to find one prime number in the factorization of $n!$ which occurs only "once", i.e. find a prime factor of $n!$ with multiplicity of 1 .

Simply think the factors of as a list of the integers in increasing order from $1$ through $n$. Choose $k$ to be halfway through the list, such that $2k\ge n$.

Thanks. I think I got it now. See post #27. My version applies Bertrand to $\sqrt{n}$ and $2\sqrt{n}.$

 

[SammyS]

In my example, we have $p=83497$ which divides $n!=83521!$ This $p$ is too big to occur twice in the prime factorization of $n!$ So the question is: how can we make sure, that such a big prime always exists?

Define some number, I've called it $k$ such that $k$ is the quotient defined by Euclidean division for $n/2$ .

In the example, $n!=83521!$, we have that $k=41760$ , so that $2k=83520$. So, if there is a prime number, $p_B~,$ such that $41760<p_B<83520$ , then what can be stated about $2p_B$?

We technically have that $p_B\ge41761$ , so that $2p_B\ge83522>83521=n$.

 

[Math100]

Define some number, I've called it $k$ such that $k$ is the quotient defined by Euclidean division for $n/2$ .

In the example, $n!=83521!$, we have that $k=41760$ , so that $2k=83520$. So, if there is a prime number, $p_B~,$ such that $41760<p_B<83520$ , then what can be stated about $2p_B$?

We technically have that $p_B\ge41761$ , so that $2p_B\ge83522>83521=n$.

Doesn't that mean $2p_B\geq n$?

 

[fresh_42]

Doesn't that mean $2p_B\geq n$?

$p_B$ certainly divides $n!$

Consider the following list:
$$
1\quad 2 \quad 3\quad \ldots\quad n/2\quad \ldots \quad p_B\quad \ldots \quad n
$$
Now, every prime divisor of $n!$ must divide one of these numbers. Hence particularly $p_B$ has to divide one of these numbers one more time, if $p_B^2\,|\,n!$

Can this happen? If yes, why? If not, why?

 

[Math100]

$p_B$ certainly divides $n!$

Consider the following list:
$$
1\quad 2 \quad 3\quad \ldots\quad n/2\quad \ldots \quad p_B\quad \ldots \quad n
$$
Now, every prime divisor of $n!$ must divide one of these numbers. Hence particularly $p_B$ has to divide one of these numbers one more time, if $p_B^2\,|\,n!$

Can this happen? If yes, why? If not, why?

No.

 

[Math100]

Suppose for the sake of contradiction that $n!$ is a perfect square.
Let $p$ denote the largest prime such that $p<n$.
Then $p\mid n!$.
Since $n!$ is a perfect square,
it follows that $p^2\mid n!\implies p\mid (\frac{n!}{p})$.
Note that $\frac{n!}{p}=1\cdot 2\cdot 3\dotsb (p-1)(p+1)\dotsb n$
where $\frac{n!}{p}$ must have $2p$ as its factor.
Thus $p<2p<n$, which is a contradiction because the Bertrand's conjecture
states that there exists at least one prime $p$ satisfying $n<p<2n$.
Therefore, if $n>1$, then $n!$ is never a perfect square.

 

[SammyS]

Suppose for the sake of contradiction that $n!$ is a perfect square.
Let $p$ denote the largest prime such that $p<n$.
Then $p\mid n!$.
Since $n!$ is a perfect square,
it follows that $p^2\mid n!\implies p\mid (\frac{n!}{p})$.
Note that $\frac{n!}{p}=1\cdot 2\cdot 3\dotsb (p-1)(p+1)\dotsb n$
where $\frac{n!}{p}$ must have $2p$ as its factor.

The Prime, $p$, guaranteed by Bertrand (below) has nothing to do with the choice of $p$ above.

Thus $p<2p<n$, which is a contradiction because the Bertrand's conjecture
states that there exists at least one prime $p$ satisfying $n<p<2n$.
Therefore, if $n>1$, then $n!$ is never a perfect square.

For prime, $p$, what is the smallest composite number divisible by $p~?$