1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving something cant be written as a square

  1. Jun 10, 2012 #1
    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 )
    Last edited: Jun 10, 2012
  2. jcsd
  3. Jun 10, 2012 #2
    this is disproved if you take a=0 since 4 is a square
  4. Jun 10, 2012 #3
    You go like this.

    First, expand out as follows: [itex]p^{m+a}-p^m+3p^a-3+4=p^{m+a}-p^m+3p^a+1[/itex]

    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 [itex](n+2)^2=n^2+4n+4[/itex]. We will derive a contradiction from this. Since two sides must be equal, we get [itex]n^2+4n=p^{m+a}-p^m+3p^a-3[/itex]. Now, define the right hand side to be A and solve the second-degree equation to get [itex]n=-2\pm\sqrt{4-A}=-2\pm\sqrt{7-p^{m+a}+p^m-3p^a}[/itex] so we get [itex]-(n+2)^2=p^{m+a}-p^m+3p^a-7[/itex]. From here, we see that [itex]-(n+2)^2=(n+2)^2-4[/itex], so it easily follows that [itex](n+2)^2=4[/itex] 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.
    Last edited: Jun 10, 2012
  5. Jun 10, 2012 #4
    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 [itex]n+2[/itex]?
    3) " [itex]n=-2\pm\sqrt{4-A}[/itex] " . Solving that equation will yield you something different. [itex] n^2+4n-A=0. [/itex]. Will be the equation. Applying quadratic formula we get [itex]\frac{-4\pm \sqrt{16+4A}}{2}[/itex]. So we would end up with this. [itex]-2\pm \sqrt{4+A}[/itex]. So you cant end up getting [itex]-(n+2)^2=p^{m+a}-p^m+3p^a-7[/itex].

    Thanks a lot sir, for patiently answering my questions.
    Last edited: Jun 10, 2012
  6. Jun 10, 2012 #5


    User Avatar
    Homework Helper

    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 noone else can learn from the exchange.
  7. Jun 10, 2012 #6
    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
  8. Jun 10, 2012 #7
    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.
  9. Jun 10, 2012 #8
    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 [itex](n+2)^4=(n-2)^4[/itex]. Thank you sir.
    Last edited: Jun 10, 2012
  10. Jun 10, 2012 #9
    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 ?.
  11. Jun 10, 2012 #10
    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.
  12. Jun 10, 2012 #11
    Thanks a lot for your reply. I am in debt with your interaction sir.
  13. Jun 11, 2012 #12


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
  14. Jun 11, 2012 #13
    Yes sir, you are right. I ended up with a blunder at-last. I didn't look at the equation sign. Ashhhhhh
    Last edited: Jun 11, 2012
  15. Jun 11, 2012 #14
    Sir, I am sure that we dont 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.
  16. Jun 11, 2012 #15
    Sir, my proof has turned to be not correct. Can you give some hints in proving that ?
    There "a" is non-zero sir
    Last edited: Jun 11, 2012
  17. Jun 11, 2012 #16
    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.
    Last edited: Jun 11, 2012
  18. Jun 11, 2012 #17
    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 ?.
  19. Jun 11, 2012 #18
    Sir I tried it day and night sir. I would be extremely happy if you can post it here.
  20. Jun 11, 2012 #19
    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:


    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.
  21. Jun 11, 2012 #20
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook