0

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?

Gabe Kurtis
  • 13
  • 1
    Yes, there's plenty known about it. Google "Pythagorean triples" to start. – saulspatz Feb 16 '18 at 21:58
  • Maybe Euclid's formula can be used somehow https://en.m.wikipedia.org/wiki/Pythagorean_triple – Yuriy S Feb 16 '18 at 21:58
  • @saulspatz, please be more specific because i’ve googled “Pythagorean triples.” – Gabe Kurtis Feb 16 '18 at 22:02
  • 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. – Mark Bennet Feb 16 '18 at 22:10
  • @MarkBennet, your comment is confusing, the first sentence rephrased the fact that c is a Pythagorean triple, and your last sentence is my question but I defined specific as integer a,b. – Gabe Kurtis Feb 16 '18 at 22:17
  • 1
    @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. – Mark Bennet Feb 16 '18 at 22:25
  • @MarkBennet sorry, I just thought the information was a given based on the knowledge of Pythagorean triples – Gabe Kurtis Feb 16 '18 at 22:35
  • I believe the answer to my question is that it depends on the size of c or if you know the factors of c, based on current answers and comments, however does someone need one factor of c or all factors – Gabe Kurtis Feb 16 '18 at 22:41
  • It seems I was more pessimistic about the computations than necessary, nonetheless there are two steps including finding the prime factorisation and then representing the relevant primes. Once this is done, rebuilding the solutions is more straightforward. (See the link in saulspatz's answer) – Mark Bennet Feb 16 '18 at 22:59
  • @Gabe Kurtis The problem is easy using the formulas in another post about matching sides of Pythagorean triples. I hope you like what you find. – poetasis May 27 '19 at 15:27

3 Answers3

3

hint

Observe that

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

hamam_Abdallah
  • 62,951
2

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}$$

saulspatz
  • 53,131
  • 1
    FYI, $1,309,313 = 167^2 + 1132^2$. – Hw Chu Feb 16 '18 at 22:48
  • 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. – Gabe Kurtis Feb 16 '18 at 22:52
  • Gabe, I don't think there's any hope of that. – saulspatz Feb 16 '18 at 23:01
  • 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. – Hw Chu Feb 16 '18 at 23:03
  • @HwChu I will count this as an answer, but could you clarify why it wouldn’t be probabilistic polynomial time to solve my question? – Gabe Kurtis Feb 16 '18 at 23:11
  • Hw Chu is saying that it may be probabilistic polynomial time to decompose $p$ into the sum of two squares, once you have found p. Finding $p$ requires factorization, which so far as anyone knows is not probabilistic polynomial. – saulspatz Feb 16 '18 at 23:19
  • As saulspatz said. After looking for references it seemed that finding solution of $a^2 + b^2 = p$ is actually probabilistic polynomial time (deterministic if assuming GRH). – Hw Chu Feb 17 '18 at 00:20
0

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$.

poetasis
  • 6,338