Proving something cant be written as a square

[S.Iyengar]

Prove that (p^m+3)(p^a-1)+4 is not a perfect square. Here the p is an odd prime and all exponents are non-negative. Given m=2n+a, for some n>0 and for some a ( where a is an integer )

 

[oli4]

Hi,
this is disproved if you take a=0 since 4 is a square

 

[Millennial]

You go like this.

First, expand out as follows: $p^{m+a}-p^m+3p^a-3+4=p^{m+a}-p^m+3p^a+1$

Note that since p is an odd prime, this is an even number, so the only way it can be a square is that it is the square of an even number. By induction, we will show this can't hold.

First step is to disprove that this is not the square of zero, but since p is positive and we have a plus one sign, this expression is not zero. So the first step of induction is complete.

Second step is to prove that if it fails for n, it also fails for n+2. To achieve this, we acknowledge that $(n+2)^2=n^2+4n+4$. We will derive a contradiction from this. Since two sides must be equal, we get $n^2+4n=p^{m+a}-p^m+3p^a-3$. Now, define the right hand side to be A and solve the second-degree equation to get $n=-2\pm\sqrt{4-A}=-2\pm\sqrt{7-p^{m+a}+p^m-3p^a}$ so we get $-(n+2)^2=p^{m+a}-p^m+3p^a-7$. From here, we see that $-(n+2)^2=(n+2)^2-4$, so it easily follows that $(n+2)^2=4$ and n=0. But we assumed that the expression could not hold for n=0 in the first place! Contradiction. Hence it is impossible to express this as a perfect square.

In general, what you do is to use reductio ad absurdum in such questions. Just play with the expression for a while (like I did), and you will eventually hit a contradiction.

 

[S.Iyengar]

You go like this.

First, expand out as follows: $p^{m+a}-p^m+3p^a-3+4=p^{m+a}-p^m+3p^a+1$

Note that since p is an odd prime, this is an even number, so the only way it can be a square is that it is the square of an even number. By induction, we will show this can't hold.

First step is to disprove that this is not the square of zero, but since p is positive and we have a plus one sign, this expression is not zero. So the first step of induction is complete.

Second step is to prove that if it fails for n, it also fails for n+2. To achieve this, we acknowledge that $(n+2)^2=n^2+4n+4$. We will derive a contradiction from this. Since two sides must be equal, we get $n^2+4n=p^{m+a}-p^m+3p^a-3$. Now, define the right hand side to be A and solve the second-degree equation to get $n=-2\pm\sqrt{4-A}=-2\pm\sqrt{7-p^{m+a}+p^m-3p^a}$ so we get $-(n+2)^2=p^{m+a}-p^m+3p^a-7$. From here, we see that $-(n+2)^2=(n+2)^2-4$, so it easily follows that $(n+2)^2=4$ and n=0. But we assumed that the expression could not hold for n=0 in the first place! Contradiction. Hence it is impossible to express this as a perfect square.

Simply awesome proof!, I enjoyed it. I thank you whole-heartedly for your help.. thank you very much.
But I didnt understand the answer clearly. I didn't understand the following things sir.

1) " Note that since p is an odd prime, this is an even number ". Is that already known sir? . How can one prove that statement ?
2) "Second step is to prove that if it fails for n, it also fails for n+2." why is that so sir?. Why we need to prove for $n+2$?
3) " $n=-2\pm\sqrt{4-A}$ " . Solving that equation will yield you something different. $n^2+4n-A=0.$. Will be the equation. Applying quadratic formula we get $\frac{-4\pm \sqrt{16+4A}}{2}$. So we would end up with this. $-2\pm \sqrt{4+A}$. So you can't end up getting $-(n+2)^2=p^{m+a}-p^m+3p^a-7$. Thanks a lot sir, for patiently answering my questions.

 

[Curious3141]

Never mind

Please note that it's not good form to delete your original post. Deleting it after it's been replied to means that others don't know what you asked in the first place, and no one else can learn from the exchange.

 

[S.Iyengar]

Please note that it's not good form to delete your original post. Deleting it after it's been replied to means that others don't know what you asked in the first place, and no one else can learn from the exchange.

Sorry sir, actually I didn't know how to edit. I suddenly edited the whole question and it lead to such situation. Please don't mind

 

[Millennial]

I will be glad to answer your questions, though I strongly advise you work the proof out yourself.

1) Actually, it is sufficient that p is odd, being prime is not necessary. Just prove that the powers of an odd number are always odd, and then it will be straightforward to show.

2) You are right, I did make a mistake there, but it really does not change the course of the proof. I was testing if you would actually see my mistake. In the correct case you posted, you get an even graver contradiction. I won't post it here, you should be able to derive it from there.

 

[S.Iyengar]

I will be glad to answer your questions, though I strongly advise you work the proof out yourself.

1) Actually, it is sufficient that p is odd, being prime is not necessary. Just prove that the powers of an odd number are always odd, and then it will be straightforward to show.

2) You are right, I did make a mistake there, but it really does not change the course of the proof. I was testing if you would actually see my mistake. In the correct case you posted, you get an even graver contradiction. I won't post it here, you should be able to derive it from there.

Sir thanks a lot for your reply. [STRIKE]But I didn't get any contradiction now sir [/STRIKE]. I have worked out the entire proof.. I did get a contradiction which is $(n+2)^4=(n-2)^4$. Thank you sir.

 

[S.Iyengar]

I will be glad to answer your questions, though I strongly advise you work the proof out yourself.

1) Actually, it is sufficient that p is odd, being prime is not necessary. Just prove that the powers of an odd number are always odd, and then it will be straightforward to show.

2) You are right, I did make a mistake there, but it really does not change the course of the proof. I was testing if you would actually see my mistake. In the correct case you posted, you get an even graver contradiction. I won't post it here, you should be able to derive it from there.

Sir I wanted to hear something more about this sir . "Second step is to prove that if it fails for n, it also fails for n+2." Why should we take such construct there ?.

 

[Millennial]

Because we only need to prove it fails for even n, since it already fails for odd (your first question.) To do that, you start with n=0 and then use induction that covers only even numbers rather than all.

 

[S.Iyengar]

Because we only need to prove it fails for even n, since it already fails for odd (your first question.) To do that, you start with n=0 and then use induction that covers only even numbers rather than all.

Thanks a lot for your reply. I am in debt with your interaction sir.

 

[haruspex]

This is the strangest thread.
Millennial, did it not strike you as odd that you have not used any of the features of the expression A? You could substitute all sorts of expressions for A and apparently deduce the same contradiction. Clearly there was an error, which you found. But I harbour very strong doubts that you could have repaired it so easily.
S.Iyengar, I am concerned that you may have fallen into a similar error. Would you mind posting your solution?

 

[S.Iyengar]

This is the strangest thread.
Millennial, did it not strike you as odd that you have not used any of the features of the expression A? You could substitute all sorts of expressions for A and apparently deduce the same contradiction. Clearly there was an error, which you found. But I harbour very strong doubts that you could have repaired it so easily.
S.Iyengar, I am concerned that you may have fallen into a similar error. Would you mind posting your solution?

Yes sir, you are right. I ended up with a blunder at-last. I didn't look at the equation sign. Ashhhhhh

 

[S.Iyengar]

I will be glad to answer your questions, though I strongly advise you work the proof out yourself.

1) Actually, it is sufficient that p is odd, being prime is not necessary. Just prove that the powers of an odd number are always odd, and then it will be straightforward to show.

2) You are right, I did make a mistake there, but it really does not change the course of the proof. I was testing if you would actually see my mistake. In the correct case you posted, you get an even graver contradiction. I won't post it here, you should be able to derive it from there.

Sir, I am sure that we don't get any contradiction if we go through the same course of proof. Yesterday I thought that I got a contradiction. But I too really made a mistake in the case of sign.

 

[S.Iyengar]

Hi,
this is disproved if you take a=0 since 4 is a square

Sir, my proof has turned to be not correct. Can you give some hints in proving that ?
There "a" is non-zero sir

 

[Millennial]

Yes, I think I made a mistake there. I used another logic this time and came up with a contradiction. I won't post it here, I will tell you what kind of a contradiction it is. Try to obtain it yourself.

Contradiction: Let n be the number which gives the expression you gave when squared. Then, n can't be divided by p. However, either n-4 and n+1, or n-2 and n-1 are divisable by p. From here, it is easy to see that only the first case can be valid where p is 5. However, with some effort you can show that a perfect square can be written as 5x+1 if and only if the number to be squared is in the form 5y+1. Since this can't hold with your expression (because if it did, n+1 would not be divisable by 5), we achieve a contradiction.

 

[S.Iyengar]

Yes, I think I made a mistake there. I used another logic this time and came up with a contradiction. I won't post it here, I will tell you what kind of a contradiction it is. Try to obtain it yourself.

Contradiction: Let n be the number which gives the expression you gave when squared. Then, n can't be divided by p. However, either n-4 and n+1, or n-2 and n-1 are divisable by p. From here, with some calculations, it follows that p is either 2 or irrational.

Sir very nice answer, But my brain is small sir. I am not as intelligent as you. So can you elaborate that a bit.

I mean did you use the induction still ?.

 

[S.Iyengar]

Yes, I think I made a mistake there. I used another logic this time and came up with a contradiction. I won't post it here, I will tell you what kind of a contradiction it is. Try to obtain it yourself.

Contradiction: Let n be the number which gives the expression you gave when squared. Then, n can't be divided by p. However, either n-4 and n+1, or n-2 and n-1 are divisable by p. From here, it is easy to see that only the first case can be valid where p is 5. However, with some effort you can show that a perfect square can be written as 5x+1 if and only if the number to be squared is in the form 5y+1. Since this can't hold with your expression (because if it did, n+1 would not be divisable by 5), we achieve a contradiction.

Sir I tried it day and night sir. I would be extremely happy if you can post it here.

 

[Millennial]

I used modular arithmetic this time, along with reductio ad absurdum.

Here is the first thing I did. I used the properties of the expression you gave as follows:

$$n^2=p^{m+a}-p^m+3p^a+1$$
$$n^2-1=(n-1)(n+1)=p^{m+a}-p^m+3p^a=p^a(p^m-p^{m-a}+3)$$

From here, you see either n-1, n+1, or both are divisable by p (since a is nonzero.) If both were divisable, it would imply p=2, which you stated can't be true; since p is an odd prime. I hope you can carry the proof on.

 

[S.Iyengar]

I used modular arithmetic this time, along with reductio ad absurdum.

Yes sir, I do know that you might have used modular arithmetic when you deal with divisibility. I too tried a lot reducing it. But I found out that if n mod 4 = 2 or 3 then n is not a perfect square. But I am unable to prove further.

I would be happy if you can elaborate and send me the proof.

 

[S.Iyengar]

I used modular arithmetic this time, along with reductio ad absurdum.

Here is the first thing I did. I used the properties of the expression you gave as follows:

$$n^2=p^{m+a}-p^m+3p^a+1$$
$$n^2-1=(n-1)(n+1)=p^{m+a}-p^m+3p^a=p^a(p^m-p^{m-a}+3)$$

From here, you see either n-1, n+1, or both are divisable by p (since a is nonzero.) If both were divisable, it would imply p=2, which you stated can't be true; since p is an odd prime. I hope you can carry the proof on.

Yes sir, indeed a nice argument and nice proof this time. But how about proving for (n+2)^2 ? . Shall I need to use the same logic master ?

 

[Millennial]

You don't need to prove it for n+2.

 

[S.Iyengar]

I used modular arithmetic this time, along with reductio ad absurdum.

Here is the first thing I did. I used the properties of the expression you gave as follows:

$$n^2=p^{m+a}-p^m+3p^a+1$$
$$n^2-1=(n-1)(n+1)=p^{m+a}-p^m+3p^a=p^a(p^m-p^{m-a}+3)$$

From here, you see either n-1, n+1, or both are divisable by p (since a is nonzero.) If both were divisable, it would imply p=2, which you stated can't be true; since p is an odd prime. I hope you can carry the proof on.

Sorry sir, a small doubt again. you said "you see either n-1, n+1, or both are divisable by p, If both were divisable, it would imply p=2". But if both are not-divisible at the same time , I mean if either n-1 or n+1 is divisible then what is the case?

 

[Millennial]

That is the part which you should answer.

 

[S.Iyengar]

That is the part which you should answer.

Sir, I would be really happy if you can give some clue. I am not trained in modular arithmetic. I am not asking for complete proof . But only hints in that direction.

 

[oli4]

Sir, my proof has turned to be not correct. Can you give some hints in proving that ?
There "a" is non-zero sir

Hi, is it me or the original statement has changed ?
I remember a and m to be non negative, and I don't remember this m=2n+a for some integer n
So anyway, when I said a=0 disproves it, I was not talking about the proof given later, it wasn't yet here anyway, I was just pointing at the fact that you were trying to prove something which is not true as stated
Do you have any context for this question ? are you being stuck in the middle of a 'bigger' proof that would rely on this to be validated ? or is this the real exercise ? can you state it exactly as it comes ?
If it is an exercise, in which context does it come ? you are often asked to apply some recently learned theorem or rule or lemma.. that would help everyone I think.
Meanwhile, I didn't look closely at the other proof you say turned out to be wrong or incomplete, but I saw among comments that there was something about odd/even numbers, so one thing is certain, for this expression to be a square of some integer, this integer has to be even.

Cheers...

 

[S.Iyengar]

I used modular arithmetic this time, along with reductio ad absurdum.

Here is the first thing I did. I used the properties of the expression you gave as follows:

$$n^2=p^{m+a}-p^m+3p^a+1$$
$$n^2-1=(n-1)(n+1)=p^{m+a}-p^m+3p^a=p^a(p^m-p^{m-a}+3)$$

From here, you see either n-1, n+1, or both are divisable by p (since a is nonzero.) If both were divisable, it would imply p=2, which you stated can't be true; since p is an odd prime. I hope you can carry the proof on.

There is another potential error here sir. p doesn't divide both the things simultaneously. It must divide the product. So assumed that n is even, as per your previous arguments ( even square would give rise to even square ) so n+1 and n-1 would be odd then. So p will be never 2 here .

 

[S.Iyengar]

Hurray , I got it sir. Perfectly this time I have got it.. I know the complete proof for all the things now. I completed the whole proof. It does involves the even and odd manipulations. But its very easy and not complex.

I just used to show that $P^a$ doesn't divide an even number in both (n+1) and (n-1) case. It turned out to be right perfectly from some series of arguments.

 

[S.Iyengar]

That is the part which you should answer.

Sir, I have tried the following proof. Please verify whether it is right or wrong. I used t for m and $\phi$ for a for the sake of brevity. So let us show that this fails in the case of $n^2$. Let us start with the equation $p^{t+\phi}-p^{t}+3p^{\phi}+1$. If that is a square it would be equal to some n^2 for some even $n$. $p^{t+\phi}-p^{t}+3p^{\phi}+1=n^2$. We prove that it will not happen based upon two cases. Let us simplify it further. $p^{\phi}(p^t-p^{t-\phi}+3)= n^2-1$
\begin{equation}
p^{\phi}(p^t-p^{t-\phi}+3) = (n+1)(n-1).
\end{equation}

From the above equation its evident that $p^{\phi}$ may divide either $(n+1)$ or $(n-1)$. So there are two cases possible.
\subsubsection{ Dividing n-1 }

As we said that $p^{\phi}|(n-1)$ . From here the proof turns out to be interesting. We know that $n$ is even, hence $n-1$ would be odd. So if $p^{\phi}$ divides $(n-1)$ in $(n-1)(n+1)$ it must give rise to some new term of the form $d.(n+1)$ where $d$ is odd ( Since, odd number divided by odd number would give rise to odd number ). So that $d.(n+1) = (p^t-p^{t-\phi}+3)$ (since from (2)). So let us prove that its a contradiction.
$d.(n+1) = (p^t-p^{t-\phi}+3)$
$d.(n+1) = p^t(1-p^{-\phi})+3$
$d.(n+1)-3= p^t(1-p^{-\phi})$---(3)

So here its evident that $p^t | d.(n+1)-3$ . So the equation (3) can be written as
$M.(d.(n+1)-3)=(1-p^{-\phi})$. Where it divides $M$ times ( $M$ can be even $1$ in which the same equation is obtained ).
So its clearly evident that L.H.S is an integer. So the R.H.S is

$\frac{p^{\phi}-1}{p^{\phi}}$---(4)

So its evident that a prime number minus one is an even number. Prime numbers are nothing but in some sense odd numbers. So odd number minus one would be an even number. So the numerator in the (4) is a even number and denominator is the odd number. So it would never turn to an integer. Which is a contradiction.

 

[S.Iyengar]

Sir, I have tried the following proof. Please verify whether it is right or wrong. I used t for m and $\phi$ for a for the sake of brevity.


So let us show that this fails in the case of $n^2$. Let us start with the equation $p^{t+\phi}-p^{t}+3p^{\phi}+1$. If that is a square it would be equal to some n^2 for some even $n$. $p^{t+\phi}-p^{t}+3p^{\phi}+1=n^2$. We prove that it will not happen based upon two cases. Let us simplify it further. $p^{\phi}(p^t-p^{t-\phi}+3)= n^2-1$
\begin{equation}
p^{\phi}(p^t-p^{t-\phi}+3) = (n+1)(n-1).
\end{equation}

From the above equation its evident that $p^{\phi}$ may divide either $(n+1)$ or $(n-1)$. So there are two cases possible.
\subsubsection{ Dividing n-1 }

As we said that $p^{\phi}|(n-1)$ . From here the proof turns out to be interesting. We know that $n$ is even, hence $n-1$ would be odd. So if $p^{\phi}$ divides $(n-1)$ in $(n-1)(n+1)$ it must give rise to some new term of the form $d.(n+1)$ where $d$ is odd ( Since, odd number divided by odd number would give rise to odd number ). So that $d.(n+1) = (p^t-p^{t-\phi}+3)$ (since from (2)). So let us prove that its a contradiction.
$d.(n+1) = (p^t-p^{t-\phi}+3)$
$d.(n+1) = p^t(1-p^{-\phi})+3$
$d.(n+1)-3= p^t(1-p^{-\phi})$---(3)

So here its evident that $p^t | d.(n+1)-3$ . So the equation (3) can be written as
$M.(d.(n+1)-3)=(1-p^{-\phi})$. Where it divides $M$ times ( $M$ can be even $1$ in which the same equation is obtained ).
So its clearly evident that L.H.S is an integer. So the R.H.S is

$\frac{p^{\phi}-1}{p^{\phi}}$---(4)

So its evident that a prime number minus one is an even number. Prime numbers are nothing but in some sense odd numbers. So odd number minus one would be an even number. So the numerator in the (4) is a even number and denominator is the odd number. So it would never turn to an integer. Which is a contradiction.

I have still proved many things, but I didn't end up with any contradiction sir.

 

[haruspex]

$d.(n+1)-3= p^t(1-p^{-\phi})$---(3)

So here it's evident that $p^t | d.(n+1)-3$ .

No, you can't do that. $1-p^{-\phi}$ is not an integer.
E.g. 18 = 3³-3² = 3³(1-3^-1), but 3³ does not divide 18.

 

[Norwegian]

Strange thread indeed. Have you agreed on what statement you are looking to prove? For example, when p=3, m=a+2 then (p^m+3)(p^a-1)+4 is a square, so you may want p>3 in your original statement.

 

[S.Iyengar]

Strange thread indeed. Have you agreed on what statement you are looking to prove? For example, when p=3, m=a+2 then (p^m+3)(p^a-1)+4 is a square, so you may want p>3 in your original statement.

Yes sir, I am sorry. There p>3 actually. But later I came to know that exception

 

[S.Iyengar]

No, you can't do that. $1-p^{-\phi}$ is not an integer.
E.g. 18 = 3³-3² = 3³(1-3^-1), but 3³ does not divide 18.

So is there any alternate way of fixing it sir ?. I do know , but I thought that the equation would imply that.

 

[S.Iyengar]

Strange thread indeed. Have you agreed on what statement you are looking to prove? For example, when p=3, m=a+2 then (p^m+3)(p^a-1)+4 is a square, so you may want p>3 in your original statement.

Sir, I am sorry, can you suggest me some hints to prove that statement sir. I do apologize for not mentioning that special exception which you pointed out cleverly.