Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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 \%$.
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.$)
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.
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.
