# Probability that $x^2+y^2$ is a perfect square

If two numbers $x$ and $y$ are chosen at random without any replacement(s) from $S=\{{0,1,2,3.....,189}\}$, then what is the probability that $x^2+ y^2$ is a perfect square?

I noticed that if $x=0$,then the number is a perfect square for all $y$. Hence 189 perfect squares are there. By trial and error, I could also figure out that $(4,5)$,$(6,8)$ are some other perfect squares. But I could not find out all of them.

• Perhaps you should tag "Combinatorics" as well. – JKEG Oct 11 '16 at 1:52
• The chance that neither number is $0$ is $(189/190)^2$ so out of $190^2$ equally likely outcomes, the number of outcomes in which at least one number is $0,$ is $190^2(1-(189/190)^2)=379.$ – DanielWainfleet Oct 16 '16 at 7:18

## 4 Answers

A possible way to solve this problem is to use the classical Diophantus formulas for the generation of triples of the form $x^2+y^2=z^2$. As shown below, this method leads to a final probability of $\frac {662}{35910} \approx 1.8 \%$. I checked this result by a direct counting algorithm and got the same value.

According to Diophantus parametrization, triples of the form $x^2+y^2=z^2$ with $x,y,z$ integers can be generated by choosing a pair of integers  $(a,b)$ (with $a>b$) and setting $x=a^2-b^2$, $y=2ab$, so that  $z=a^2+b^2$. In particular, if $a$ and $b$ are coprime and of opposte parity, we get a "primitive" triple (i.e. a triple where $gcd (x,y,z)=1$). Interestingly, all primitive triples can be generated in this way. For example, the pair $(2,1)$ generates $(3,4,5)$, the pair $(3,2)$ generates $(5,12,13)$, and so on. Also, when a primitive triple $(x,y,z)$ is identified, we  can generate infinite other triples by simply multiplying it to an integer $n$, that is to say writing $(nx,ny,nz)$. All  triples where a sum of two squared integers is a perfect square can be generated in this way.

Coming back to our random choice of two integers $x$ and $y$ in the range between $0$ and $189$, we can firstly note that there are $189+189=378$ trivial cases of the form $(0,y)$ or $(x,0)$ - i.e. cases where we pick $0$ in one of the two trials - that satisfy the condition that $x^2+y^2$ is a perfect square.

Focusing on the cases where  $x$ and $y$ are both different from zero, we can count the number of cases where $x^2+y^2$ is a perfect square by identifying the Diophantus pairs $(a,b)$ (with $a >b$) that generate primitive triples (i.e. with  $a$ and $b$ coprime and of opposte parity) and that satisfy the inequalities $x=a^2-b^2 \leq 189$ and $y=2ab \leq 189$. Then, we have to count - for each of these primitive triples - how many triples of the form $(nx,ny,nz)$ satisfy the same inequalities. Noting that the curves $a^2-b^2 = 189$ and $2ab =189$ cross at $a=\sqrt{189 (1+\sqrt{2})/2} \approx 15.1$, we get that the maximal theoretical value of $a$ is $15$ (for higher integer values, at least one inequality is not satisfied). We can also observe that, for $a=15$, the only value of $b$ that satisfies the inequalities is $b=6$, but since the pair $(15,6)$ violates the assumption that  $a$ and $b$ must be coprime, we can restrict our analysis to the values of $a \leq 14$. In other words, we have to calculate

$$\sum_{a,b} \left \lfloor \frac {189}{max (2ab,a^2-b^2)} \right \rfloor$$

where $max$ indicates the higher between the two quantities representing  $x$ and $y$, and the summation extends over all pairs $(a,b)$ that satisfy the conditions described above, in the range $1 \leq a \leq 14$.

We can now identify these pairs of integers $(a,b)$, and count how many triples are generated from each pair. It is not difficult to show that, for $a \leq 10$,  the two inequalities are satisfied for all values of $b < a$.  So we can include all $b <a$ where the two integers are coprime and of opposite parity. Thus our counting procedure begins as follows:

$$(2,1) \rightarrow \lfloor 189/4 \rfloor=47$$

$$(3,2) \rightarrow \lfloor 189/12 \rfloor=15$$

$$(4,1) \rightarrow \lfloor 189/15 \rfloor=12$$

$$(4,3) \rightarrow \lfloor 189/24 \rfloor=7$$

$$(5,2) \rightarrow \lfloor 189/21 \rfloor=9$$

$$(5,4) \rightarrow \lfloor 189/40 \rfloor=4$$

$$(6,1) \rightarrow \lfloor 189/35 \rfloor=5$$

$$(6,5) \rightarrow \lfloor 189/60 \rfloor=3$$

$$(7,2) \rightarrow \lfloor 189/45 \rfloor=4$$

$$(7,4) \rightarrow \lfloor 189/56 \rfloor=3$$

$$(7,6) \rightarrow \lfloor 189/84 \rfloor=2$$

$$(8,1) \rightarrow \lfloor 189/63 \rfloor=3$$

$$(8,3) \rightarrow \lfloor 189/55 \rfloor=3$$

$$(8,5) \rightarrow \lfloor 189/80 \rfloor=2$$

$$(8,7) \rightarrow \lfloor 189/112 \rfloor=1$$

$$(9,2) \rightarrow \lfloor 189/77 \rfloor=2$$

$$(9,4) \rightarrow \rfloor 189/72 \rfloor=2$$

$$(9,8) \rightarrow \lfloor 189/144 \rfloor=1$$

$$(10,1) \rightarrow \lfloor 189/99 \rfloor =1$$

$$(10,3) \rightarrow \lfloor 189/91 \rfloor=2$$

$$(10,7) \rightarrow \lfloor 189/140 \rfloor = 1$$

$$(10,9) \rightarrow \lfloor 189/180 \rfloor = 1$$

For $a=11$ to $15$ some pairs $(a,b)$ with $a$, $b$ coprime and of opposite parity must be rejected because do not satisfy the two inequalities (for example, $(11,10)$, which gives $2ab=220 >189$). Then, continuing our counting with the same procedure, we get:

$$(11,2) \rightarrow 1$$

$$(11,4) \rightarrow 1$$

$$(11,6) \rightarrow 1$$

$$(11,8) \rightarrow 1$$

$$(12,1) \rightarrow 1$$

$$(12,5) \rightarrow 1$$

$$(12,7) \rightarrow 1$$

$$(13,2) \rightarrow 1$$

$$(13,4) \rightarrow 1$$

$$(13,6) \rightarrow 1$$

$$(14,3) \rightarrow 1$$

$$(14,5) \rightarrow 1$$

The total count, summing the numbers above, is $142$. This expresses the number of valid triples $x^2+y^2=z^2$ where $x$ is odd and  $y$ is even and both are different from zero. Due to the symmetry of the problem, we have to count other $142$ triples where $x$ and $y$ are switched (e.g., $(3,4,5)$ and $(4,3,5)$). This gives a total of $284$ valid triples where $x$ and $y$ are different from zero.

Adding to these the $378$ triples where $x$ or $y$ is zero, we get a total number of $284+378=662$ valid triples that satisfy the conditions given by the OP. This corresponds to the number of choices of two random numbers $x$ and $y$ in the range from $0$ to $189$, so that $x^2+y^2$ is a perfect square.

Because the total possible choices of $x$ and $y$, if picked without replacement, are $190 \cdot 189=35910$, we conclude that the probability that $x^2+y^2$ is a perfect square is $662/35910 \approx 1.8 \%$.

• And that 1.8% is big enough to cause the answer to the Boolean Pythagorean triples problem to be NEGATIVE. – EulerSpoiler Jul 18 '20 at 20:46

A fundamental Pythagorean triplet $(x,y,z)$ has $\gcd (x,y)=1.$ Every Pythagorean triplet is of the form $(kx,ky,kz)$ where $(x,y,z)$ is fundamental and $k \in \mathbb N.$ When $(x,y,z)$ is fundamental then $$\bullet \;\{x,y\}=\{2mn, m^2-n^2\}$$ where $m,n$ are co-prime members of $\mathbb N,$ with $m>n$ and with exactly one of $m,n$ odd and the other one even.

If we can find all fundamental triplets $(x,y,z)$ with $\max (x,y)\leq 189,$ then then for each one, the non-fundamental triplets in the required range are of the form $(kx,ky,kz)$ for $2\leq k$ and $189\geq k\cdot \max (x,y).$

To find fundamental triplets with $\max (x,y)\leq 189$ : Referring to $\bullet$, consider that $2mn\leq 189\implies mn\leq 94.$ Now $n^2+n=n(n+1)\leq nm\leq 94$ so $$n\leq 9.$$ But we also require $m^2-n^2\leq 189.$ So $m^2-9^2\leq m^2-n^2\leq 189,$ implying $m\leq 270.$ Hence $$m\leq 16.$$ Altogether we have now $n<m\leq 16$ with $n\leq 9,$ with $\gcd (m,n)=1,$ and with $m$ odd and $n$ even, OR $m$ even and $n$ odd. Thus the values of $m,n$ are among the following: $$m\in \{10,12,14,16\}, n\in \{1,3,5,7,9\}.$$ $$m=8,n\in \{1,3,5,7\}.$$ $$m=6, n\in \{1,5\}.$$ $$m=4, n\in \{1,3\}.$$ $$m=2,n=1.$$ $$m\in \{9,11,13,15\}, n\in \{2,4,6,8\}.$$ $$m=7, n\in \{2,4,6\}.$$ $$m=5, n\in \{2,4\}.$$ $$m=3,n=2.$$ Not all of the above pairs will give fundamental triplets in the required range. Some of them give $m^2-n^2>189$ or $2mn>189,$ and some of them are (e.g. $m=14,n=7$) are not co-prime pairs. So some of the above pairs must be removed. This is a matter of some elementary arithmetic. (In particular all the cases with $m=16$ are to be removed, for if $n\leq 7$ then $16^2-n^2>189,$ and if $n=9$ then $2mn=2\cdot 16\cdot 9>189.$)

• I considered that with a cap of 189, trial and error on paper would work, but I thought that if the cap was, say, 10 million, you'd want a better method. – DanielWainfleet Oct 18 '16 at 3:17

Hey I'm no number theorist, but I'm pretty sure you are looking for solutions to the equation

$x^2 + y^2 = z^2$. Look familiar? You need Pythagorean triplets such that $x,y \leq 189$.

Hope this can get you started.

• Absolutely true. And while you may not be a number theorist, this is precisely the answer simplest for the OP. Of course, studying the methods used to generate the triples is fascinating.... I believe you can do it with a generalization of the solution to Pells Equation? Correct me if I'm wrong here, I'm no number theorist myself, but I dabble ;) – Brevan Ellefsen Oct 11 '16 at 2:07
• You can generate all primitive Pythagorean triples with a very simple process. It's not just trial and error. – Trevor Squires Oct 11 '16 at 2:13
• @Deepak I get that. But typically, I try not to do too much for the questioner if he/she hasn't started the problem. – Trevor Squires Oct 11 '16 at 2:20
• The set S is quite small, so couldn't you code a simple algorithm to count the number of feasible pairs, or do you need a more general solution? – K. Miller Oct 11 '16 at 2:57

Hint: You can use this, Pythagorean triples are in the form of:

$$(m^2-n^2, 2mn, m^2+n^2)$$

Given $m>n$.

Hope you can take it form here. Its basic combinatorics with a little bit of logic.