0
$\begingroup$

Pretty self explanatory, but I haven’t seen any papers on whether someone can find a and b, given c, such that $a^2 + b^2 = c^2$ and a,b, and c are integers. If there isn’t a way is their an approximation formula?

Clarity: I am looking for method to calculate a and b given c such that a,b,c are a Pythagorean triple.

Example: Find the a,b given c is a large number asy 2048 bits where factoring isn’t an option, without brute forcing. My question is how do you find a,b?

$\endgroup$
10
  • 1
    $\begingroup$ Yes, there's plenty known about it. Google "Pythagorean triples" to start. $\endgroup$
    – saulspatz
    Commented Feb 16, 2018 at 21:58
  • $\begingroup$ Maybe Euclid's formula can be used somehow en.m.wikipedia.org/wiki/Pythagorean_triple $\endgroup$
    – Yuriy S
    Commented Feb 16, 2018 at 21:58
  • $\begingroup$ @saulspatz, please be more specific because i’ve googled “Pythagorean triples.” $\endgroup$ Commented Feb 16, 2018 at 22:02
  • $\begingroup$ You could start by checking out the numbers which can be expressed as the sum of two squares. In a Pythagorean Triple $c^2$ is a square number which can be expressed in such a way. The prime factorisation of $c$ is relevant here, both to the possibility of such an expression and the number of ways of doing it. Once it is known there is a solution, the search for specific $a,b$ is a different matter. $\endgroup$ Commented Feb 16, 2018 at 22:10
  • 1
    $\begingroup$ @GabeKurtis There are criteria for identifying when an integer can be expressed as the sum of two squares in terms of the prime factorisation (the existence problem) and also for the number of solutions. However, for example, every prime $p$ of the form $p=4n+1$ can be expressed as the sum of two squares $5=4+1, 13=9+4, 17=16+1, 29=25+4, 37=36+1, 41=25+16, 53=49+4\dots$ as can the prime $2=1+1$ - but there is no pattern - given $p$, say $p=89$, it is trial and error, so far as I know, to find $89=64+25$. And the solutions for composite numbers are built from the solutions for primes. $\endgroup$ Commented Feb 16, 2018 at 22:25

3 Answers 3

3
$\begingroup$

hint

Observe that

$$(x^2+y^2)^2=(x^2-y^2)^2+(2xy)^2$$

$\endgroup$
4
  • $\begingroup$ That’s as helpful as Wikipedia $\endgroup$ Commented Feb 16, 2018 at 22:06
  • 1
    $\begingroup$ @GabeKurtis ....which is a lot in this case. $\endgroup$
    – DonAntonio
    Commented Feb 16, 2018 at 22:23
  • $\begingroup$ @DonAntonio unless you can explain how I can use Euler’s formula to generate triples to find a,b this isn’t helpful. $\endgroup$ Commented Feb 16, 2018 at 22:27
  • 1
    $\begingroup$ @GabeKurtis "Without brute force", as you write in your question, given that horrendous number? No, I don't know...and that's not the meaning I give to "helpful". $\endgroup$
    – DonAntonio
    Commented Feb 16, 2018 at 22:31
2
$\begingroup$

Let's talk about the case where $a,b,c$ are co-prime first. Then we know that $\exists u,v (c=u^2+v^2).$ Also, once we can find $u,v$ we can find $a,b$. Furthermore, the sum of two squares theoremtells exactlt which integers can be expressed as the sum of two squares, so the problem is solved, provided $c$ is small enough to factor.

Then, of course, there's the question of finding all the different possibilities for $a$ and $b$, which comes down to counting the number of ways to express $c$ as the sum of two squares. You can find a discussion of that here .

Wolfram Alpha factors 158077286429 into three distinct primes, each of which is $\equiv 1 \pmod{4},$ so there is a solution. The first two primes in the factorization are $157$ and $769,$ so finding the representation as a sum of two squares can be done with a pencil. The third prime is $1,309,313$ and I imagine you'll need a computer; I know I would.

By the way, there's a theorem that the sum of two squares times the sum of two squares is again the sum of two squares, and there's a formula (or rather two) to get the representations.

Just for grins: $$\begin{align} 145807675179^2 + 61061856700^2 &= 158077286429^2 \\ 155253825771^2 + 29743538260^2 &= 158077286429^2 \\ 4741142229^2 + 158006170940^2 &= 158077286429^2 \\ 91317244821^2 + 129033287500^2 &= 158077286429^2 \end{align}$$

$\endgroup$
7
  • 1
    $\begingroup$ FYI, $1,309,313 = 167^2 + 1132^2$. $\endgroup$
    – Hw Chu
    Commented Feb 16, 2018 at 22:48
  • $\begingroup$ Thanks for the answer, however since factoring isn’t reliable with sufficiently large numbers and I would like the solution to work for any size number. $\endgroup$ Commented Feb 16, 2018 at 22:52
  • $\begingroup$ Gabe, I don't think there's any hope of that. $\endgroup$
    – saulspatz
    Commented Feb 16, 2018 at 23:01
  • $\begingroup$ State-of-the-art factorization algorithms (like GNFS) is subexponential. For a $4k+1$ prime $p$, finding $a$ and $b$ such that $a^2 + b^2 = p$ is probably as hard as finding a square root of $-1 \pmod p$, which is probabilistic polynomial. So I expect the algorithm provided by saulspatz to be subexponential on $\log c$. It would be interesting if there is a polynomial time algorithm, but I am skeptical. $\endgroup$
    – Hw Chu
    Commented Feb 16, 2018 at 23:03
  • $\begingroup$ @HwChu I will count this as an answer, but could you clarify why it wouldn’t be probabilistic polynomial time to solve my question? $\endgroup$ Commented Feb 16, 2018 at 23:11
0
$\begingroup$

We can find triples for any given $C$, if they exist, by solving Euclid's formula function $C=f(m,n)$ for $n$ and testing a defined range of $m$-values to see which, if any, yield integers for $n$.

$$C=m^2+n^2\Rightarrow n=\sqrt{C-m^2}\qquad\qquad \biggl\lceil\sqrt{\frac{C}{2}}\biggr\rceil \le m < \sqrt{C}$$

In the case of $158077286429$,

$n=\sqrt{158077286429-m^2}\quad $where$\quad\biggl\lceil\sqrt{\frac{158077286429}{2}}\biggr\rceil=281139 \le m < \sqrt{158077286429}=397589$

This is quite a range to search and this formula will only find primitives, doubles, and square multiples of primitives so a better approach is to try the factors of $158077286429$ $(157 * 769 * 1309313)$and then multiply any primitives found by the cofactors.

For $157\quad 9\le m\le12\qquad\sqrt{157-11^2}=6\qquad F(11,6)=(85,132,157)$

For $769\quad 20\le m\le 27\qquad\sqrt{769-25^2}=12\qquad F(25,12)=(481,600,769)$

For $1309313\quad 809\le m\le 1144\qquad\sqrt{1309313-1132^2}=167\qquad F(1132,167)=(1253535,378088,1309313)$

For $157*769=120733\quad 246\le m\le347\qquad\sqrt{120733-282^2}=203\qquad F(282,203)=(38315,114492,120733)$

For $1309313*157=205562141\qquad 10139\le m\le 14337\qquad \\ \sqrt{205562141-11450^2}=8629\qquad F(11450,8629)=(56642859,197604100,205562141) \\ \sqrt{205562141-13454^2}=4955\qquad F(13454,4955)=(156458091,133329140,205562141)$

For $1309313*769=1006861697\qquad 22438\le m\le 31731\qquad \\ \sqrt{1006861697-26296^2}=17759\qquad F(26296,17759)=(376097535,933981328,1006861697) \\ \sqrt{1006861697-30304^2}=9409\qquad F(30304,9409)=(829803135,570260672,1006861697)$

If you multiply each of these $8$ triples by their corresponding cofactors of $C$ you will find unique triples where $C=158077286429$. These were found in a spreadsheet. With $110000$ values of $m$ to test, I would recommend a computer program to find out if there are primitives where $C=158077286429$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .