Case specific perfect square test: $sqrtx^2 + 8a$

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

Let's say I have a function: $f(x) = sqrtx^2+8a$,

Constraints: $a,x in mathbbN$, $a$ mod 2 = 1.

What would be the most efficient algorithm to find every natural $x$, so that $f(x) in mathbbN$?

$a$ is arbitrarily large, thus evaluating $f(x)$ for all $x$ is too computationally expensive.
Is it possible to formulate a case specific test, to check that $x^2 + 8a$ is a perfect square?

roots square-numbers natural-numbers

share|cite|improve this question

edited Jul 18 at 20:43

RayDansh

882214

asked Jul 18 at 20:03

quaternion1337

111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How big $a$ for example?
  – Mostafa Ayaz
  Jul 23 at 9:33
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

Let's say I have a function: $f(x) = sqrtx^2+8a$,

Constraints: $a,x in mathbbN$, $a$ mod 2 = 1.

What would be the most efficient algorithm to find every natural $x$, so that $f(x) in mathbbN$?

$a$ is arbitrarily large, thus evaluating $f(x)$ for all $x$ is too computationally expensive.
Is it possible to formulate a case specific test, to check that $x^2 + 8a$ is a perfect square?

roots square-numbers natural-numbers

share|cite|improve this question

edited Jul 18 at 20:43

RayDansh

882214

asked Jul 18 at 20:03

quaternion1337

111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How big $a$ for example?
  – Mostafa Ayaz
  Jul 23 at 9:33
  

  
  
  
  

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

Let's say I have a function: $f(x) = sqrtx^2+8a$,

Constraints: $a,x in mathbbN$, $a$ mod 2 = 1.

What would be the most efficient algorithm to find every natural $x$, so that $f(x) in mathbbN$?

$a$ is arbitrarily large, thus evaluating $f(x)$ for all $x$ is too computationally expensive.
Is it possible to formulate a case specific test, to check that $x^2 + 8a$ is a perfect square?

roots square-numbers natural-numbers

share|cite|improve this question

edited Jul 18 at 20:43

RayDansh

882214

asked Jul 18 at 20:03

quaternion1337

111

Let's say I have a function: $f(x) = sqrtx^2+8a$,

Constraints: $a,x in mathbbN$, $a$ mod 2 = 1.

What would be the most efficient algorithm to find every natural $x$, so that $f(x) in mathbbN$?

$a$ is arbitrarily large, thus evaluating $f(x)$ for all $x$ is too computationally expensive.
Is it possible to formulate a case specific test, to check that $x^2 + 8a$ is a perfect square?

roots square-numbers natural-numbers

share|cite|improve this question

edited Jul 18 at 20:43

RayDansh

882214

asked Jul 18 at 20:03

quaternion1337

111

share|cite|improve this question

share|cite|improve this question

edited Jul 18 at 20:43

RayDansh

882214

edited Jul 18 at 20:43

RayDansh

882214

edited Jul 18 at 20:43

RayDansh

882214

882214

asked Jul 18 at 20:03

quaternion1337

111

asked Jul 18 at 20:03

quaternion1337

111

asked Jul 18 at 20:03

quaternion1337

111

111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How big $a$ for example?
  – Mostafa Ayaz
  Jul 23 at 9:33
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How big $a$ for example?
  – Mostafa Ayaz
  Jul 23 at 9:33
  

  
  
  
  

How big $a$ for example?
– Mostafa Ayaz
Jul 23 at 9:33

How big $a$ for example?
– Mostafa Ayaz
Jul 23 at 9:33

add a comment | 

2 Answers
2

active

oldest

votes

up vote
1
down vote

If $x^2+8a=y^2$, then $$8a=y^2-x^2=(y+x)(y-x), $$
so looking for the factorizations of $8a$ might help. In fact, as $8a$ is a multiple of $8$, at least one of $ypm x$ must be a multiple of $4$, but that means the other factor is also even. Thus find all positive factors $d$ of $2a$, and then $x=|d-frac2ad|$ is a non-negative integer solution; indeed $$beginalignleft|d-frac2adright|^2+8a&=d^2-2cdot dcdot frac2ad+left(frac2adright)^2+8a\&=d^2+2cdot dcdot frac2ad+left(frac2adright)^2\&=left(d+frac2adright)^2.endalign$$

share|cite|improve this answer

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
  – Mark Bennet
  Jul 19 at 6:19
  

  
  
  
  

add a comment | 

up vote
0
down vote

Set $y=f(x)$

You have $y^2=x^2+8a$ whence $y^2-x^2=(y+x)(y-x)=8a$

Now $y+x$ and $y-x$ differ by $2x$ hence have the same parity, and at least one of them is even ...

I will leave you to work out the consequences of this.

Suppose $a$ (given as odd) is factored as $pq$. Working through leads to the identities $(p+2q)^2=(p-2q)^2+8a$ and/or $(2p+q)^2=(2p-q)^2+8a$

share|cite|improve this answer

edited Jul 19 at 6:24

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855947%2fcase-specific-perfect-square-test-sqrtx2-8a%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

If $x^2+8a=y^2$, then $$8a=y^2-x^2=(y+x)(y-x), $$
so looking for the factorizations of $8a$ might help. In fact, as $8a$ is a multiple of $8$, at least one of $ypm x$ must be a multiple of $4$, but that means the other factor is also even. Thus find all positive factors $d$ of $2a$, and then $x=|d-frac2ad|$ is a non-negative integer solution; indeed $$beginalignleft|d-frac2adright|^2+8a&=d^2-2cdot dcdot frac2ad+left(frac2adright)^2+8a\&=d^2+2cdot dcdot frac2ad+left(frac2adright)^2\&=left(d+frac2adright)^2.endalign$$

share|cite|improve this answer

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
  – Mark Bennet
  Jul 19 at 6:19
  

  
  
  
  

add a comment | 

up vote
1
down vote

If $x^2+8a=y^2$, then $$8a=y^2-x^2=(y+x)(y-x), $$
so looking for the factorizations of $8a$ might help. In fact, as $8a$ is a multiple of $8$, at least one of $ypm x$ must be a multiple of $4$, but that means the other factor is also even. Thus find all positive factors $d$ of $2a$, and then $x=|d-frac2ad|$ is a non-negative integer solution; indeed $$beginalignleft|d-frac2adright|^2+8a&=d^2-2cdot dcdot frac2ad+left(frac2adright)^2+8a\&=d^2+2cdot dcdot frac2ad+left(frac2adright)^2\&=left(d+frac2adright)^2.endalign$$

share|cite|improve this answer

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
  – Mark Bennet
  Jul 19 at 6:19
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

If $x^2+8a=y^2$, then $$8a=y^2-x^2=(y+x)(y-x), $$
so looking for the factorizations of $8a$ might help. In fact, as $8a$ is a multiple of $8$, at least one of $ypm x$ must be a multiple of $4$, but that means the other factor is also even. Thus find all positive factors $d$ of $2a$, and then $x=|d-frac2ad|$ is a non-negative integer solution; indeed $$beginalignleft|d-frac2adright|^2+8a&=d^2-2cdot dcdot frac2ad+left(frac2adright)^2+8a\&=d^2+2cdot dcdot frac2ad+left(frac2adright)^2\&=left(d+frac2adright)^2.endalign$$

share|cite|improve this answer

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

If $x^2+8a=y^2$, then $$8a=y^2-x^2=(y+x)(y-x), $$
so looking for the factorizations of $8a$ might help. In fact, as $8a$ is a multiple of $8$, at least one of $ypm x$ must be a multiple of $4$, but that means the other factor is also even. Thus find all positive factors $d$ of $2a$, and then $x=|d-frac2ad|$ is a non-negative integer solution; indeed $$beginalignleft|d-frac2adright|^2+8a&=d^2-2cdot dcdot frac2ad+left(frac2adright)^2+8a\&=d^2+2cdot dcdot frac2ad+left(frac2adright)^2\&=left(d+frac2adright)^2.endalign$$

share|cite|improve this answer

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

share|cite|improve this answer

share|cite|improve this answer

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

answered Jul 18 at 20:22

Hagen von Eitzen

265k20258477

265k20258477

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
  – Mark Bennet
  Jul 19 at 6:19
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
  – Mark Bennet
  Jul 19 at 6:19
  

  
  
  
  

Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
– Mark Bennet
Jul 19 at 6:19

Previous comment was not helpful. $a$ is given as odd. Factor $a$ as $pq$ and you have the pair $(2p, 4q)$.
– Mark Bennet
Jul 19 at 6:19

add a comment | 

up vote
0
down vote

Set $y=f(x)$

You have $y^2=x^2+8a$ whence $y^2-x^2=(y+x)(y-x)=8a$

Now $y+x$ and $y-x$ differ by $2x$ hence have the same parity, and at least one of them is even ...

I will leave you to work out the consequences of this.

Suppose $a$ (given as odd) is factored as $pq$. Working through leads to the identities $(p+2q)^2=(p-2q)^2+8a$ and/or $(2p+q)^2=(2p-q)^2+8a$

share|cite|improve this answer

edited Jul 19 at 6:24

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

add a comment | 

up vote
0
down vote

Set $y=f(x)$

You have $y^2=x^2+8a$ whence $y^2-x^2=(y+x)(y-x)=8a$

Now $y+x$ and $y-x$ differ by $2x$ hence have the same parity, and at least one of them is even ...

I will leave you to work out the consequences of this.

Suppose $a$ (given as odd) is factored as $pq$. Working through leads to the identities $(p+2q)^2=(p-2q)^2+8a$ and/or $(2p+q)^2=(2p-q)^2+8a$

share|cite|improve this answer

edited Jul 19 at 6:24

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

add a comment | 

up vote
0
down vote

up vote
0
down vote

Set $y=f(x)$

You have $y^2=x^2+8a$ whence $y^2-x^2=(y+x)(y-x)=8a$

Now $y+x$ and $y-x$ differ by $2x$ hence have the same parity, and at least one of them is even ...

I will leave you to work out the consequences of this.

Suppose $a$ (given as odd) is factored as $pq$. Working through leads to the identities $(p+2q)^2=(p-2q)^2+8a$ and/or $(2p+q)^2=(2p-q)^2+8a$

share|cite|improve this answer

edited Jul 19 at 6:24

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

Set $y=f(x)$

You have $y^2=x^2+8a$ whence $y^2-x^2=(y+x)(y-x)=8a$

Now $y+x$ and $y-x$ differ by $2x$ hence have the same parity, and at least one of them is even ...

I will leave you to work out the consequences of this.

Suppose $a$ (given as odd) is factored as $pq$. Working through leads to the identities $(p+2q)^2=(p-2q)^2+8a$ and/or $(2p+q)^2=(2p-q)^2+8a$

share|cite|improve this answer

edited Jul 19 at 6:24

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

share|cite|improve this answer

share|cite|improve this answer

edited Jul 19 at 6:24

edited Jul 19 at 6:24

edited Jul 19 at 6:24

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

answered Jul 18 at 20:22

Mark Bennet

76.4k773170

76.4k773170

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855947%2fcase-specific-perfect-square-test-sqrtx2-8a%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email