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~?$

 

[Orodruin]

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.

17 is the largest prime factor in $17^4$, not in $(17^4)!$.

 

[fresh_42]

17 is the largest prime factor in $17^4$, not in $(17^4)!$.

So what?

My reply was to

Let $p$ denote the largest prime such that $p\leq n$.
...
Thus $n<2p$, so $p\mid n!$ but $p^2\nmid n!$, which is a contradiction.
...

 

[Orodruin]

So what?

My reply was to

So what? Having $n = q^4$ where $q$ is a prime smaller than $p$ affects nothing. $n$ is $17^4$, not 17.

 

[fresh_42]

So what? Having $n = q^4$ where $q$ is a prime smaller than $p$ affects nothing. $n$ is $17^4$, not 17.

Yes. But that wasn't my message. I responded to: why the OP's proof doesn't work.

I have nowhere claimed that $17$ is the largest prime divisor of $17^4!$ However, it is the largest prime divisor of $17^4=17 \cdot 17 \cdot 17\cdot 17.$

I only explained why the proof does not work. So, please either quote the complete quotation or read the thread.

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.

 

[Orodruin]

I only explained why the proof does not work. So, please either quote the complete quotation or read the thread.

This is your quote:

Why? What if n=p4 for example?

This never happens because $p$ was assumed to be the largest prime smaller than $n$. If $n = p^4$ for some prime $p$, then $p$ is not the largest prime factor in $n!$, which was the assumption:

Let p denote the largest prime such that p≤n.

If $n = q^4$ for some prime $q$, then there exists a prime $p$ which is larger than $q$ but smaller than $n$ by Bertrand'd conjecture because $n \geq 8 q > 2q$. Therefore, $n$ cannot be equal to $p^4$ where $p$ is the largest prime less than or equal to $n$. Talking about $n = p^4$ is therefore going to be quite confusing to OP.

The real issue in the proof of the OP is this:

Thus n<2p,

This should be something akin to "Since $p$ is the largest prime smaller than $n$, $n < 2p$ by Bertrand's postulate." Later, this is also an issue:

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

I don't know if this is just sloppiness from the OP or not. It should read "because there exists a prime p in the prime factorization of the integer 83521! only once".

A more compact version of the proof being attempted would read:

Let $p$ be the largest prime such that $p \leq n$.
$p$ exists in the prime factorization of $n!$ exactly once unless $n \geq 2p$.
If $n \geq 2p$, then by Bertrand's postulate there exists a prime $q$ such that $p < q < 2p \leq n$, which contradicts $p$ being the largest prime $p \leq n$.
Thus, $n < 2p$ and $p$ occurs only once in the prime factorization of $n!$.

I only explained why the proof does not work. So, please either quote the complete quotation or read the thread.

As explained above, your example of $n = 17^4$ with $p = 17$ is not applicable because 17 is not the largest prime $p$ such that $p \leq 17^4$.

 

[fresh_42]

I do not see why we should debate this nonsense. Read the posts.

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.

 

[Orodruin]

I do not see why we should debate this nonsense. Read the posts.

It is quite clear that you yourself has not read my post considering your post is submitted 6 minutes after mine, which is rather lengthy. At most you have glanced over it.

To summarize:
Your example of $n = p^4$ is not applicable and will just confuse the OP because $p$ was assumed to be the largest prime such that $p \leq n$.

So unless you want to argue that you can find an $n = p^4$ for which $p$ is the largest prime such that $p \leq n$, it is highly relevant.

 

[fresh_42]

I see that you deliberately a) ignore what I said, b) ignore why I said it (not to you btw), c) did not read the thread, and d) willingly misunderstand my example which was only meant as an answer to post #13.

Nowhere did I say that $17$ is the largest prime in $17^4!$
The opposite is true, I said it is $83497.$
I (still) claim that $17$ is the largest prime in $17^4.$
My example explains why a certain argument by the OP does not work.

Of course, it is up to you to go on misunderstanding me and arguing about it. You wouldn't be my first encounter with a professor who was wrong but insisted to be right qua office. Congratulations.

 

[Orodruin]

Nowhere did I say that 17 is the largest prime in 17^4!

But implicitly, you did say that. This is the message you quoted:

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.

It clearly states "Let $p$ denote the largest prime such that $p \leq n$", so this is the assumption. You go on to say:

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

We are still working under the assumption that $p$ is the largest prime such that $p \leq n$ so I cannot read this in any other way than implying that $n = p^4$ where $p$ is the largest prime such that $p \leq n$.

Context is important.

I (still) claim that 17 is the largest prime in 17^4.

Nobody has disputed this.

My example explains why a certain argument by the OP does not work.

It does not, because it does not apply to the OP's context of $p$ being the largest prime such that $p \leq n$.

 

[anuttarasammyak]

I observe if n!=M^2 where M is an integer,
n!=\Pi_p p^{2n_p}
where p is all the prime numbers p<n. It means n! consists of all the prime numbers in pairs.
It is obviously impossible if there exists n/2 < p < n at least.

 

[epenguin]

It happens that In the (London) Times leaders today

https://www.thetimes.co.uk/article/the-times-view-on-mathematics-living-by-numbers-m2hskf7p0 it is proclaimed:

"The Times view on mathematics: Living by Numbers

Maths is not only useful but elegant and beautiful"

"The Hungarian theorist Paul Erdos proved, at the age of 17, that between any two whole numbers n and 2n there must lie at least one prime." is their example!

So far as I could work out in a quick (Wikipedia) check, Chebyschev had proved the theorem in the 19th century, but Eordos' proof 1932 proof has an elementary character that previous ones didn't - so maybe useful here?

 

[Prof B]

Because there exists a prime p in the prime factorization of the integer 83521 only once, thus p2∤83521!.

p is the largest prime <= 83521, not the largest prime factor if 83521. You had it right the first time.

 

[fresh_42]

p is the largest prime <= 83521, not the largest prime factor if 83521. You had it right the first time.

Wrong. $p=17$ is the largest prime factor of $83521 = 17^4.$

 

[Orodruin]

Wrong. $p=17$ is the largest prime factor of $83521 = 17^4.$

Again, this is not what was assumed when the OP introduced $p$. It is also not what @Prof B said, he was clearly referring to the OP’s assumption. It was introduced as the largest prime $p\leq n$. Please read this by the OP again:

Let p denote the largest prime such that p≤n.

There is no number on the form $q^4$, where $q$ is prime, such that $p = q$.

This is also your post which shows that you do understand the proof - you are just introducing new meanings for p that do not correspond to what the OP introduced:

In my example, we have p=83497 which divides n!=83521!

This is the correct p for n = 83521. p is not 17 because 17 is the largest prime factor in 83521, which is not the same as the largest prime smaller than 83521.

I suggest you take the time to reread the entire thread with this in mind. What @Prof B said was perfectly appropriate with the OP’s assumption.

Again, to recap. OP says:

Let p denote the largest prime such that p≤n.

You say in response:

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

This statement is incompatible with the OP’s assumption of $p$ being the largest prime smaller than n because $n = p^4 \geq 8p > 2p$ means that there is at least one prime larger than $p$ but less than $p^4$, violating the OP’s assumption of $p$ being the largest prime sich that $p\leq n$.

The big problem here is that you are alternatingly using p to denote a prime such that n = p^4 and using it to denote the largest prime factor in n.

p=83497 is is the largest prime <= 83521, not the largest prime factor if 83521. You had it right the first time.

(Boldface my addition)

Wrong. $p=17$ is the largest prime factor of $83521 = 17^4.$

In my example, we have p=83497

I’d say there is no wonder that OP is getting confused by this.

 

[fresh_42]

Again, this is not what was assumed when the OP introduced ...

Guess I made the mistake to confuse prime with prime factor at the wrong places.