# How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?

How would I prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?

-
I think you're asking two questions that are irrelevant to each other. –  some1.new4u Dec 3 '13 at 1:59
What do you mean? –  Antonio Montana Dec 3 '13 at 2:02
I mean that it is not clear to me what you're asking. Are you asking us to help you solve why either $2^{1000}+15$ or $2^{1000}+16$ isn't a perfect square or you're looking for some advices to help you with your problem solving skills? If it's the former, then I don't see how that is related to the title you've chosen, if it's the later one, I don't see how that particular elementary number theory question is relevant to proof-strategies, because one simply can't learn problem solving by only one problem of a particular kind. –  some1.new4u Dec 3 '13 at 2:07
Sorry, but yes, help with proving it. Sorry for title. –  Antonio Montana Dec 3 '13 at 2:09
it appears someone edited the question changing the 1000s to 500s.. –  Akshaj Kadaveru Dec 3 '13 at 22:07

Hint: hink about the distance between consecutive squares.

-
I have no experience writing proofs, so where do I begin? This here is practice work to improve my skills, just in case it is on the exam. Professor gave us a lot of practice problems to work on for ourselves without solutions, so thats the difficult part. –  Antonio Montana Dec 3 '13 at 2:07
What a proof is depends on what your prof considers "a proof". In this case, you could argue that the differences between consecutive squares are given by the odd numbers (as John shows) and so the only consecutive perfect squares are $0$ and $1$. –  Martin Argerami Dec 3 '13 at 2:24

Short solutions: $2^{1000} + 15 \equiv 3 \pmod{4}$, $2^{1000} + 16 \equiv 2 \pmod{3}$, neither of which are quadratic residues.

More elementary solution: $2^{1000} = (2^{500})^2$. The next perfect square is $$(2^{500} + 1)^2 = 2^{1000} + 2(2^{500}) + 1$$ which is clearly more than both $2^{1000} + 15$ and $2^{1000} + 16$. Therefore, these two can't possibly be perfect squares.

-
Sorry, but what does (mod 4) mean? Sorry for my ignorance. I'm a math novice trying to get better –  Antonio Montana Dec 3 '13 at 2:14
Maybe read up on my article here: artofproblemsolving.com/Forum/viewtopic.php?f=721&t=514795 For now, ignore the first solution if you don't understand it. It basically shows that $2^{1000} + 15$ leaves a remainder of $3$ when divided by $4$. However, no perfect squares can possibly leave a remainder of $3$ when divided by $4$, meaning that $2^{1000} + 15$ isn't a perfect square. –  Akshaj Kadaveru Dec 3 '13 at 2:28
Thanks for link and all your help! Will try and read up on it and see if I can prove it. –  Antonio Montana Dec 3 '13 at 2:34
@AkshajKadaveru can you explain why in quadratic residues you chose $\pmod{3}$ and $\pmod{4}$? –  0x90 Dec 3 '13 at 10:16
@0x90, because $(2n+1)^2=4 (n^2+n)+1$, so no square is of the form $4k+3$. Similarly, $(3n+2)^2=3 (3n^2+4n+1)+1$, so no square is of the form $3k+2$. –  Martin Argerami Dec 3 '13 at 11:04

To expand on Martin's hint a bit:

The difference between two perfect squares $n^2$ and $(n+1)^2$ is

$$(n+1)^2 - n^2 = 2n + 1.$$

You have two numbers that are expressed as the sum of a perfect square and another number.

What would be the smallest value that the other number would have to be in order for the sum to be a perfect square also?

-
Fancy seeing you here, John. I was about to respond, but you wrote exactly what I was thinking. –  JoeTaxpayer Dec 3 '13 at 14:50
Hey @JoeTaxpayer! I linked to your great lottery ticket answer on my blog. (This one.) –  John Dec 4 '13 at 0:34

Oh well, $2^{500}$ is a perfect square, namely it is $(2^{250})^2$. Any perfect square bigger than $2^{500}$ is at least $(2^{250}+1)^2$, that is $2^{500} + 2\cdot2^{250}+1$, which is of course much bigger than $2^{500}+16$.

-
I like this one –  Cruncher Dec 3 '13 at 14:48
Dude, you just gave him a fish. He'll die of starvation tomorrow. –  Mitch Dec 3 '13 at 19:05
Either the problem involved the actual number $2^{500}$, in which case it was obvious to use this fact (you should not ignore facts that are given as data in your problem), or the OP just gave a guess for a number and the problem was about an "arbitrarily large" or "large enough" number, in which case this solution serves at least to show the OP how NOT to choose example data. Or why one doesn't have to choos example data. –  rewritten Dec 3 '13 at 23:11

The question is not about that big numbers...

Question is about a result that two consecutive numbers can not be squares simultaneously..

Suppose $a=b^2\text { and }a+1=c^2\Rightarrow b^2+1=c^2\Rightarrow c^2-b^2=1\Rightarrow (c+b)(c-b)=1$

w.l.o.g. assume $c+b=1$ which implies

$a+1=c^2=(1-b)^2=1+b^2-2b\Rightarrow a=b^2-2b$ but then we have $a=b^2$

you should now be able to see some contradiction...

So...

-
(drunk) spinning! –  KMX Dec 3 '13 at 7:47
@KMX what do you mean? –  Praphulla Koushik Dec 3 '13 at 7:56
oh... well i mean i was lost when i went from left to right reading your equation.... that comment was for me! –  KMX Dec 3 '13 at 9:34

Well, it's obvious isn't it?

How could two consecutive numbers of that size be squares? Write $a = 2^{500}+15$ and $2^{500}+16=a+1$. Imagine $a$ were a square. Then its square root would be a pretty huge number. If you so much as add $1$ to that number, the square of the result will be massively larger than $a$, there'll be no way to get something that squares to $a+1$.

That's the gist of the other answers. The first step in many proofs is to think about why the answer is obvious.

-
I was once in a lecture where the professor said in the middle of a long derivation "and it obviously follows that..." when a student -- not me -- asked the professor "is it really obvious?" The professor stopped, stared silently at the board for a solid minute, announced "yes, it is obvious", and continued. The moral of the story is: your definition of "obvious" might be different from the original poster's definition. –  Eric Lippert Dec 3 '13 at 21:26
@EricLippert In this case, it's much more likely that the OP simply hadn't stopped to think about the problem in that way. –  Jack M Dec 3 '13 at 21:55

Alternative method (for fun):

Observe $2^4 = 16 \equiv 1$ mod $5$.

Then $2^{500} = (2^4)^{125} \equiv 1^{125} = 1$ mod $5$.

Thus, $2^{500} + 16 \equiv 1 + 1 = 2$ mod $5$.

But every square is either $0, 1$ or $4$ mod $5$.

Therefore, $2^{500} + 16$ cannot be a square. QED

-
+1 for constructive –  Guido Dec 3 '13 at 12:20

First write down exactly what it is that you're trying to prove is impossible. In this case, that means writing down these two equations: $$2^{500}+15=n^2$$ $$2^{500}+16=m^2$$

Next, play with the equations and see where they lead you. If you subtract the first from the second, you get $$1=m^2-n^2$$ or $$1=(m+n)(m-n)$$

Now think about what this tells you about $m$ and $n$. Hint: What are all the factors of $1$?

-
The question is unclear whether OP wants to prove that at least one of the numbers is not a perfect square, or that neither one is a perfect square? The way it is written, OP is only asking for one of them. This is a good answer for that version. –  Ross Millikan Dec 3 '13 at 20:15

All square numbers, modulo 16, are in $\{0, 1, 4, 9\}$. But $2^{500} + 15 = 16^{125} + 15 \equiv 15$ (mod 16), so it can't be a square number.

-

$2^{500} + 15$ is not a perfect square:

• $2^{500} \equiv 0 \pmod 4$
• $15 \equiv 3 \pmod 4$
• $2^{500} + 15 \equiv 3 \pmod 4$

A perfect square is congruent to 0 or 1 modulo 4, so $2^{500} + 15$ is not a perfect square.

-