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

  • Thread starter Math100
  • Start date
  • Tags
    Square
In summary: Bertrand conjecture correctly.3. should use the fact that ##n>1##, so that you can show that every prime factor of ##n!## appears at most once.4. should use the fact that ##n>1##, so that you can show that at least one prime factor of ##n!## appears at least twice.5. should explain what you are doing, so that it will be clear why your approach works.6. should not write anything that is irrelevant.7.
  • #1
Math100
750
201
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.
 
Physics news on Phys.org
  • #2
Math100 said:
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?
 
  • Like
Likes Orodruin, Delta2 and valenumr
  • #3
  • Like
Likes SammyS
  • #4
Start from definitions. A number ##N## is a perfect square if and only if every prime factor of ##N## has even power.
Math100 said:
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.
 
  • Like
Likes Delta2
  • #5
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:
Math100 said:
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.
 
Last edited:
  • #6
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?
 
  • Like
Likes Delta2
  • #7
Math100 said:
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.
 
  • #8
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?
 
  • #9
Math100 said:
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.
 
  • Like
Likes Math100
  • #10
Orodruin said:
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 ##?
 
  • #11
Math100 said:
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?
 
  • Like
Likes SammyS
  • #12
Math100 said:
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## .
 
  • #13
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.
 
  • #14
Math100 said:
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)##

Math100 said:
Thus ## n<2p ##, ...
Why? What if ##n=p^4## for example?
Math100 said:
... 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.
 
  • #15
fresh_42 said:
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 ##.
 
  • #16
## n\neq p^4 ##
 
  • #17
Given the fact that ## p\leq n ##.
 
  • #18
Math100 said:
Given the fact that ## p\leq n ##.
Say ##n=83521.## Why is ##83521!## not a perfect square?
 
  • #19
Because there exists a prime ## p ## in the prime factorization of the integer 83521 only once, thus ## p^2\nmid 83521! ##.
 
  • #20
Math100 said:
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.
 
  • #21
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.
 
  • #22
Math100 said:
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.
 
  • #23
Because ## p^2\nmid 83521 ## when ## p=17 ##.
 
  • #24
But since ## n\nless 2p ##, how should I correct my proof, knowing that my proof doesn't work in this case.
 
  • #25
Math100 said:
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?
 
  • #26
## p\leq n ##
 
  • #27
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?
 
  • #28
fresh_42 said:
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##.
 
Last edited:
  • #29
SammyS said:
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}.##
 
  • #30
fresh_42 said:
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##.
 
  • #31
SammyS said:
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 ##?
 
  • #32
Math100 said:
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?
 
  • Like
Likes SammyS
  • #33
fresh_42 said:
##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.
 
  • #34
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.
 
  • #35
Math100 said:
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.

Math100 said:
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~?##
 
Last edited:
<h2>1. What does it mean for a number to be a perfect square?</h2><p>A perfect square is a number that can be expressed as the product of two equal integers. For example, 9 is a perfect square because it can be written as 3 x 3. In other words, a perfect square is the result of squaring a whole number.</p><h2>2. How do you show that a number is not a perfect square?</h2><p>To show that a number is not a perfect square, you can use the method of contradiction. This means assuming that the number is a perfect square and then showing that it leads to a contradiction or impossibility. This proves that the number cannot be a perfect square.</p><h2>3. What is the significance of n>1 in this statement?</h2><p>The statement "n>1" means that the number n is greater than 1. This is significant because perfect squares are always greater than or equal to 1. So, by showing that n is not a perfect square when it is greater than 1, we can prove that it is never a perfect square.</p><h2>4. Can you provide an example of a number that is not a perfect square when n>1?</h2><p>Yes, for example, let's take the number 6. If we assume that 6 is a perfect square, then it can be expressed as 6 = a x a, where a is a whole number. However, there is no whole number that can be multiplied by itself to give 6. This leads to a contradiction, and therefore, 6 is not a perfect square.</p><h2>5. Is there any other way to prove that n is never a perfect square when n>1?</h2><p>Yes, there are other methods to prove this statement, such as using the properties of perfect squares or using mathematical induction. However, the method of contradiction is the most straightforward and commonly used approach to prove this statement.</p>

1. What does it mean for a number to be a perfect square?

A perfect square is a number that can be expressed as the product of two equal integers. For example, 9 is a perfect square because it can be written as 3 x 3. In other words, a perfect square is the result of squaring a whole number.

2. How do you show that a number is not a perfect square?

To show that a number is not a perfect square, you can use the method of contradiction. This means assuming that the number is a perfect square and then showing that it leads to a contradiction or impossibility. This proves that the number cannot be a perfect square.

3. What is the significance of n>1 in this statement?

The statement "n>1" means that the number n is greater than 1. This is significant because perfect squares are always greater than or equal to 1. So, by showing that n is not a perfect square when it is greater than 1, we can prove that it is never a perfect square.

4. Can you provide an example of a number that is not a perfect square when n>1?

Yes, for example, let's take the number 6. If we assume that 6 is a perfect square, then it can be expressed as 6 = a x a, where a is a whole number. However, there is no whole number that can be multiplied by itself to give 6. This leads to a contradiction, and therefore, 6 is not a perfect square.

5. Is there any other way to prove that n is never a perfect square when n>1?

Yes, there are other methods to prove this statement, such as using the properties of perfect squares or using mathematical induction. However, the method of contradiction is the most straightforward and commonly used approach to prove this statement.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
7
Views
936
  • Precalculus Mathematics Homework Help
Replies
4
Views
763
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
750
  • Precalculus Mathematics Homework Help
Replies
3
Views
631
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
586
  • Precalculus Mathematics Homework Help
Replies
1
Views
730
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
Back
Top