I have a^2, find b, and c.

[Graphmastur]

Given a², and the formula A²+B²=c², is it possible to find b and c, such that they are integers.

I know one B value is 2b+1=a², and the corresponding c value is b+1, but there is another solution, with both b and c being less then this easy to find one.

Take 221 for example. There is the solution b=110 and c=111, but there is also b=2 and c=15.
Take 27 for example. There is the solution b=13 and c=14, but there is also b=3 and c=6.

The number of solutions does not matter. With a semiprime, like 221, there are always two. A prime only leaves one solution. Is there a way to find these values?

[Weregoose]

You're saying that [font=times new roman][size="3"]a[/size]

[Graphmastur]

Ok, that works, but it's slow for big numbers. Is there any other way?

[Weregoose]

Not if you want the smallest solution; I think the primality of integers has some involvement here.

Obeying (A139544), this version will detect ahead of time whether an answer can be found:

If not(fPart(Ans/4-.5
Stop
For(B,0,Ans
If fPart(√(Ans+B[font=verdana]²
End
{B,√(Ans+B[font=verdana]²

[Graphmastur]

How would the extended Euclidean algorithm work here? That's just ax+by=gcd(a,B) right?

[Weregoose]

Without the smiley, yes. It's good for finding a number such that [font=times new roman][size="3"]a+b×n[/size]

[Graphmastur]

Can you give an example of the (m+n)² thing? It sounds very interesting and possibly worth studying further.

[Weregoose]

If you're given just the fractional part of the square root of an integer, there's no immediate way of telling what the integer part was. One could add the fraction to each of the natural numbers and then square it to see which one removes the fractional part altogether. But, my goal was to do better than that.

After invoking a little algebra to simplify the problem—which I should've done beforehand—[font=times new roman][size="3"](m+n)²[/size]

[Graphmastur]

Interesting. what about the problem that I showed? Any ideas for that?

[Weregoose]

Show me something that you have tried, first of all.

[bwang]

It is a well-known fact that all Pythagorean triples are of the form (m²-n², 2mn, m²-n²).

Case 1: a is of the form 2mn. Let a = 2 a₁. Then we see that m divides a₁. Hence, in this case, all solutions are given by b = m² - (a / 2m)², c = m² + (a / 2m)², with m a factor of a / 2. Note in this case, a must be even.

Case 2: a is of the form m² - n². Then we see that (m-n)(m+n) = a. Note that m-n and m+n are of the same parity, so if a is even but not divisible by 4 there are no solutions. Otherwise, Let p>q be two divisors of a with the same parity (i.e. if 4|a they are both even, else they are both odd). Then m+n = p and m-n = q, so m = (p+q)/2 and n = (p-q)/2. This lets us compute the values of b and c.

[Graphmastur]

[bwang]

Wait, that post of mine was overly complicated. Since b² - c² = a², then we see (b - c)(b + c) = a². We may then use the same techniques as in case 2 of my previous post to solve the problem.
Sadly, this problem is equivalent to factoring a², which is hard.

[Graphmastur]

Oh. Great. It seems that problem blocks a lot of math. I wish factoring was easier. Oh well. Thanks anyway.

[Xeda112358]

I know how to find pythagorean triples... does that help?
If you have a, then:
8b=(3a²-6)-(-1)^a(a²+2)
8c=(3a²+6)-(-1)^a(a²-2)

I was bored and I couldn't answer any more questions on the Putnam, so I did that I had to prove first that all integers above 2 were part of a Pythagorean Triple and I did that the same way I came up with the equation :P

I don't think it helps much if you want non integer inputs, though.

EDIT:I noticed that I put (-1)² instead of (-1)^a