Re: n*2^k+17

On Jun 15, 10:11 pm, no comment <adler.m...@xxxxxxxxx> wrote:
On Jun 15, 11:55 am, Saysero <says...@xxxxxxxxx> wrote:



On Jun 15, 6:19 pm, no comment <adler.m...@xxxxxxxxx> wrote:

On Jun 15, 6:05 am, Saysero <says...@xxxxxxxxx> wrote:

Prove that for every natural number k there exists natural number n
such that n*2^k+17 is a square of some natural number.
Thanks in advance.

P.S.
I tried using induction however it did not work for me.

Hello,

Induction will work. Suppose that the result holds at k. We need to
show that the result holds at k + 1. Note that we can assume that k
is greater than or equal to 3.

Because the result holds at k, there is an integer x (greater than 4)
such that x^2 - 17 is divisible by 2^k. Note that x is odd.

If x^2 - 17 is divisible by 2^{k+1}, then we are finished.

If x^2 - 17 is not divisible by 2^{k+1}, let y = x + 2^{k-1}.

Then y^2 = x^2 + (x)(2^k) + 2^{2k-2}. Because k is greater than or
equal to 3, the term 2^{2k-2} is divisible by 2^{k+1}.

As to the rest, the remainder when x^2 is divided by 2^{k+1} is 2^k.

2^5 | 9^2 - 17
9^2 = 1*2^6 + 17
17 != 32
It is not true that the remainder when x^2 is divided by 2^{k+1} is
2^k.

The remainder when (x)(2^k) is divided by 2^{k+1} is also 2^k. It
follows that the remainder when y^2 is divided by 2^{k+1} is 0.

I also do not fallow this. If n*2^k=(x^2)-17 and y=x+2^k then
y^2=(x^2)+x2^{k+1}+2^{2k} then (y^2)-17=(2^k)(n+2x+2^k) so (y^2)-17 is
divisible by 2^{k+1} only if n is even and n does not have to be even.

Hello,

You are very right not to follow it. There are two "misprints" in
what I wrote earlier. It should say, "As to the rest, the remainder
when x^2 -17 is ....." and then a little later
"the remainder when y^2 - 17 ....."

The whole thing would look better in the language of congruences, but
I avoided that in case that was less familiar. The general argument
is a special case of "lifting", or "Hensel's Lemma." These nanmes
will I hope make it easy to search for information.

So what you wanted to say is:
y=x+2^{k-1}
y^2=x^2+2^k+2^{2k-2}
y^2-17=x^2-17+2^k+2^{2k-2}
Since x is odd x^2-17 is congruent to 2^k modulo 2^{k+1} so y^2-17 is
divisible bu 2^{k+1}.
This seems correct.

Also your proof is very nice.

Since the proof does not use the properties of 17 (except maybe that
it is odd) it can be replaced with 9,33,... That is also nice result.
.

Relevant Pages

  • Re: querry
    ... but cumbersome way is an exhaustion process that much resembles long division. ... This is best illustrated by preparing a square piece of paper and cutting out a smaller square at a corner, so that the remainder looks like a carpenter's square. ... Now you see that taking square roots is essentially different from power ...
    (sci.math)
  • Re: Binary sqrt
    ... square root in square brackets ... ... Subtract value in 4 squared from active-value ... Append numbers of next block to remainder ...
    (comp.lang.pascal.delphi.misc)
  • Re: n*2^k+17
    ... such that n*2^k+17 is a square of some natural number. ... I tried using induction however it did not work for me. ... It is not true that the remainder when x^2 is divided by 2^is ... The whole thing would look better in the language of congruences, ...
    (sci.math)
  • Re: Non-linear curve fitting: y = Ae^(-t/tau) + C
    ... ya know, Markus, i spelled out a closed form expression for a least square ... with that C subtracted out from y, the remainder, Ae^, can be ...
    (comp.dsp)