I think that I have flawed,can someone please check? There are 21 pairs.Modulo $4$ yields that all elements of $S$ are $\equiv 0,1,2$.So there are $7$ pairs congruent to $0$ mod $4$.Now modulo $9$ gives they are $\equiv 1,4,7,5,2,8$.So there exist 2 pairs which are each $0$ mod $4$ and congruent modulo $9$

Assume the contrary.If any two $a_i^2$ and $a_j^2$ are same then we are done.Then $a_i^2\equiv 0,1,4,9,13,16,25,28$ so $a_i^2+a_j^2\equiv 1,4,9,13,16,25,28,5,10,14,17,26,29,20,32,22,34,2,8 $ so $19$ pairs.Since we are given such pairs so PHP finishes this now.

mmathss wrote: I think that I have flawed,can someone please check? There are 21 pairs.Modulo $4$ yields that all elements of $S$ are $\equiv 0,1,2$.So there are $7$ pairs congruent to $0$ mod $4$.Now modulo $9$ gives they are $\equiv 1,4,7,5,2,8$.So there exist 2 pairs which are each $0$ mod $4$ and congruent modulo $9$ Modulo 9, 0 is possible

Yeah forgot that! Here is how it can be modified.If atleast 8 terms of the set S are corresponding to the same residue modulo $4$ then we are done.So exactly 7 terms of S correspond to each residue.Now let $x$ be the number of even numbers in the given 7 numbers.So we get $x^2=(7-x)^2=x(7-x)=7$ which is absurd

mmathss wrote: Yeah forgot that! Here is how it can be modified.If atleast 8 terms of the set S are corresponding to the same residue modulo $4$ then we are done.So exactly 7 terms of S correspond to each residue.Now let $x$ be the number of even numbers in the given 7 numbers.So we get $x^2=(7-x)^2=x(7-x)=7$ which is absurd There's a typo. I think you meant $x^2+(7-x)^2=x(7-x)=7$

Proof: The possible values of $a^2+b^2$ mod $36$ (which we get from checking mod $4$ and mod $9$) are: $0,1,2,4,5,8,9,10,13,14,16,17,18,20,22,25,26,28,29,32,34$. There are exactly $21$ possible remainders as well as $21$ sums of the form $a_i^2+a_j^2$ so if no two sums are congruent mod $36$ then each possible remainder is achieved exactly once. Thus there are exactly $7$ multiples of $4$ among the sums. $4|a_i^2+a_j^2$ iff $a_i, a_j$ are even, so if $k$ even numbers are there we get the equation $\binom{k}{2}=7$ which has no integer solutions. Contradiction, so two of the sums are congruent mod $36$. Proved.

BOBTHEGR8 wrote: mmathss wrote: Yeah forgot that! Here is how it can be modified.If atleast 8 terms of the set S are corresponding to the same residue modulo $4$ then we are done.So exactly 7 terms of S correspond to each residue.Now let $x$ be the number of even numbers in the given 7 numbers.So we get $x^2=(7-x)^2=x(7-x)=7$ which is absurd There's a typo. I think you meant $x^2+(7-x)^2=x(7-x)=7$ No what I have written is right.$x^2$ denotes elements in S that will give $0 mod4$.Similarly $(7-x)^2$ gives number of elements in S giving $2 mod4$ and $x(7-x):1 mod4$

Hey, did you all assume $S$ is a multiset? Technically, the problem asks to show the existence of two elements in $S$ that are congruent modulo $36$. That is the same as finding indices $i,j,k,l$ such that $$a_i^2+a_j^2 \equiv a_k^2+a_l^2 \pmod {36}$$and $$a_i^2+a_j^2 \neq a_k^2+a_l^2 $$

By php there are at least 4 numbers among the 7 numbers of same parity(even or odd). If there are exactly 4 numbers of the same parity say $a_1<a_2<a_3<a_4$ and then $b_1<b_2<b_3$ of different parity then all the numbers $(b_1)^2+(a_1)^2,(b_1)^2+(a_2)^2,(b_1)^2+(a_3)^2,(b_1)^2+(a_4)^2,(b_2)^2+(a_3)^2,(b_2)^2+(a_4)^2,(b_3)^2+(a_4)^2,(b_3)^2+(a_3)^2$ are congruent to 1 $mod 4$ and are different. If 5 are same parity say$a_1<a_2<a_3<a_4<a_5$ and other 2 are of different parity say $b_1 <b_2$ then all the numbers $(b_2)^2+(a_5)^2,(b_2)^2+(a_4)^2,(b_2)^2+(a_3)^2,(b_2)^2+(a_2)^2,(b_2)^2+(a_1)^2,(b_1)^2+(a_1)^2,(b_1)^2+(a_2)^2,(b_1)^2+(a_3)^2$ are different and congruent to 1 $mod 4$. If at least 6 numbers are of same parity say $a_1<a_2<a_3<a_4<a_5<a_6$ then $(a_1)^2+(a_2)^2,(a_1)^2+(a_3)^2,(a_1)^2+(a_4)^2,(a_1)^2+(a_5)^2,(a_1)^2+(a_6)^2,(a_6)^2+(a_5)^2,(a_6)^2+(a_4)^2,(a_6)^2+(a_3)^2$ are all different and same in $mod 4$. In all cases at least 8 numbers of the form $x^2+y^2$ are same $mod 4$ but any number of the form $x^2+y^2$ can be equal to 0,1,2,4,5,6,8 $mod 9$ total 7 residues mod 9.So at least 2 of the numbers say $m^2+n^2$ and $a^2+b^2$are same $mod 9$ and also $mod 4$.So also same in $mod 36$.

biomathematics wrote: Hey, did you all assume $S$ is a multiset? Technically, the problem asks to show the existence of two elements in $S$ that are congruent modulo $36$. That is the same as finding indices $i,j,k,l$ such that $$a_i^2+a_j^2 \equiv a_k^2+a_l^2 \pmod {36}$$and $$a_i^2+a_j^2 \neq a_k^2+a_l^2 $$ Exactly so....

For storage - Also note that it is not necessary to find the remainders $\pmod{36}$ $$x \in \mathbb{N} \equiv 0,1,2,3 \pmod{4} \implies x^2 \equiv 0,1 \pmod{4}$$$$\implies a_i^2 \equiv 0,1 \pmod{4}$$$$\implies a_i^2 + a_j^2 = \{0,1,2\} \pmod{4} \quad \text{(3 Possible Remainders)}$$Similarly $$a_i^2 \equiv 0,1,4,7 \pmod{9}$$$$\implies a_i^2 + a_j^2 = \{0,1,2, 4,5,7,8\} \quad \text{(7 Possible Remainders)}$$Clearly $\mathcal{S}$ has $21$ elements. Consider the remainders $\pmod{4}$, there are $3$ possible remainders and there are $21$ terms in $\mathcal{S}$, so by PHP there exists atleast $7$ elements in $\mathcal{S}$ which have the same remainder $\pmod{4}$ But notice that there are exactly $7$ possible remainders $\pmod{9}$, so we can't conclude the problem directly using PHP here. Let's make $2$ cases, one when there is atleast a group of elements which have more than $7$ elements that give same remainder $\pmod{4}$ and another case when there are equal number of elements having same remainder $\pmod{4}$ i.e $7$ elements with remainder $0,1,2 \pmod{4}$ each. $\boxed{Case \ 1}$ There are $>7 \implies \geq 8$ elements that have same remainder $\pmod{4}$ (we don't have to think of what remainder it is i.e whether it be $0$ or $1$ or $2$, it doesn't matter) And there are exactly $7$ possible remainders $\pmod{9}$, so by PHP there exist atleast $\lceil{\frac{8}{7} \rceil} = 2$ elements in $\mathcal{S}$ which have the same remainder $\pmod{4}$ and $\pmod{9}$, hence they have the same remainder $\pmod{36}$. $\boxed{Case \ 2}$ There are $21$ total elements out of which $7$ are $\equiv 0 \pmod{4}$, other $7$ elements $\equiv 1 \pmod{4}$ and remaining $7$ elements $\equiv 2 \pmod{4}$ and there are $7$ possible remainders $\pmod{9}$ So every possible remainder is obtained exactly once $\pmod{36}$ From here proceed like #7 post by Mathotsav

My solution: $a^2\equiv 0,1,4,9,13,16,25,28 \pmod{36}$ So there are 7 +ve integers $a_i$ given but any $a_i^2$ has exactly 8 distinct remainders on dividing it by 36...Hence this is the most ideal situation to apply $BOX$ $PRINCIPLE$.So 2 $a_i^2$ s.t. $a_i^2\equiv a_j^2 \pmod{36}$ Adding $a_k^2$ to the above equation, we get $a_i^2$+$a_k^2$=$a_j^2$+$a_k^2$(mod 36) This is our desired result. @below yes I was too nub those days

@above the way you applied PHP seems wrong.