Consecutive Products And Modulos!

You can rewrite the modular equation in a factored form.

$k(k+1)-60-72\equiv 0 \pmod{72}$

$k^2+k-132\equiv 0 \pmod{72}$

$(k+12)(k-11)\equiv 0 \pmod{72}$

$k+12$ and $k-11$ differ by 25, which isn't divisible by 2 nor 3 (the only prime factors of 72), so at most one of the factors could be divisible by 8, and this applies to 9 as well. Therefore, there are $2\cdot 2 = 4$ cases to consider.

Case 1: $k+12\equiv 0\pmod{8}$ and $k+12\equiv 0\pmod{9}$

$k+12\equiv 0\pmod{72}$

$k\equiv 60 \pmod{72}$

Case 2: $k-11\equiv 0\pmod{8}$ and $k-11\equiv 0\pmod{9}$

$k-11\equiv 0\pmod{72}$

$k\equiv 11\pmod{72}$

Case 3: $k+12\equiv 0 \pmod{8}$ and $k-11 \equiv 0 \pmod{9}$

You can write them as:

$k\equiv 4 \pmod{8}$ and $k\equiv 2 \pmod{9}$

By CRT, there is only one value of $k \pmod{72}$ that satisfies this congruence, which is $20$ . (This can be shown with simple algebra.)

Case 4: $k-11 \equiv 0 \pmod{8}$ and $k+12\equiv 0 \pmod{9}$

You can write them as:

$k\equiv 3 \pmod{8}$ and $k\equiv 6 \pmod{9}$

Following the same reasoning as the previous case, the only value of $k \pmod{72}$ is $51$ .

All 4 cases have different values $\pmod{72}$ so the answer is $60+11+20+51=\boxed{142}$ .

The first step is to solve the modular equation $k(k+1)\equiv60\pmod{72}$ . We can restate this equation as $k(k+1)=72n+60$ . It's clear that $12 \mid k(k+1)$ , because the RHS is divisible by 12. So, we can use a brute force approach to find all "valid" values of $k$ : $\begin{matrix}\bf k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline \bf k(k+1) \textrm{ mod 12} & 0 & 2 & 6 & 0 & 8 & 6 & 6 & 8 & 0 & 6 & 2 & 0\end{matrix}$

So, we have four cases: $k = 12a, k = 12a+3, k = 12a+8, k = 12a+11$

• For the first case, we have $12a(12a+1) = 72n+60$ . Simplifying it, we have $12a^2 + a = 6n+5$ $\Rightarrow 12a^2 - 6n = 5 - a$ . Since the LHS is divisible by 6, we have $6 \mid 5 - a$ , from which we deduce that $a = 6x+5$ . To prove that all $a$ is a solution, we can substitute it on the first equation: $432x^2 + 720x + 300 - 6n = -6x$ $\Rightarrow 6n = 432x^2 + 726x + 300$ $\Rightarrow n = 72x^2 + 121x + 50$ . So, as $a = 6x+5$ , we have $k = 72x+60$

• For the second case, we have $(12a+3)(12a+4) = 72n+60$ $\Rightarrow 144a^2 + 84a + 12 = 72n+60$ $\Rightarrow 12a^2 + 7a + 1 = 6n+5$ $\Rightarrow 12a^2 - 6n = 4-7a$ . As for the first case, $6 \mid 4-7a$ , from which $a = 6x+4$ . Substituting, we have $432x^2 + 576x + 192 - 6n = -42x-24$ $\Rightarrow 6n = 432x^2 + 618x + 216$ $\Rightarrow n = 72x^2 + 103x + 36$ . As $a = 6x+4$ , we have $k = 12(6x+4) + 3 = 72x+51$ .

• For the third case, $(12a+8)(12a+9) = 72n+60$ $\Rightarrow 144a^2 + 204a + 72 = 72n+60$ $\Rightarrow 12a^2 + 17a + 6 = 6n+5$ $\Rightarrow 12a^2 - 6n = -17a-1$ . We have $6 \mid 17a+1$ , from which $a = 6x+1$ . Substituting, $432x^2 + 144x + 12 - 6n = -102x-18$ $\Rightarrow 6n = 432x^2 + 246x + 30$ $\Rightarrow n = 72x^2 + 41x + 5$ . As $a = 6x+1$ , we have $k = 12(6x+1) + 3 = 72x+20$ .

• Finally, for the fourth case, we have $(12a+11)(12a+12) = 72n+60$ . As for the first case, we can simplify this to $(12a+11)(a+1) = 6n+5 \Rightarrow 12a^2 + 23a + 11= 6n + 5$ $\Rightarrow 12a^2-6n = -23a-6$ . So, $6 \mid 23a+6$ , from which $a = 6x$ . Substituting, $432x^2 - 6n = -138x-6$ $\Rightarrow 6n = 432x^2+138x+6$ $\Rightarrow n = 72x^2 + 23x + 1$ . As $a = 6x$ , we have $k = 72x+11$ .

So, we find that all $k$ that satisfy the modular equation $k(k+1)\equiv60\pmod{72}$ belongs to one of the families $72x+11, 72x+20, 72x+51, 72x+60$ for all $x \in \mathbb{Z}$ . Since $S_{72}$ has these numbers modulo 72, we state that $S_{72} = \{11, 20, 51, 60\}$ . So, the sum of the elements is $11 + 20 + 51 + 60 = \boxed{142}$ .

$k(k+1) \equiv 60 \mod72$ so $k(k+1) \equiv 60 \mod8$ and $k(k+1) \equiv 60 \mod9$ . Now for solve $k(k+1) \equiv 4 \mod8$ we use that $k \equiv 0 \mod8, k+1 \equiv 1 \mod8,$ so $k(k+1) \equiv 0 \mod8$ $k \equiv 1 \mod8, k+1 \equiv 2 \mod8,$ so $k(k+1) \equiv 2 \mod8$ $k \equiv 2 \mod8, k+1 \equiv 3 \mod8,$ so $k(k+1) \equiv 6 \mod8$ $k \equiv 3 \mod8, k+1 \equiv 4 \mod8,$ so $k(k+1) \equiv 4 \mod8$ $k \equiv 4 \mod8, k+1 \equiv 5 \mod8,$ so $k(k+1) \equiv 4 \mod8$ $k \equiv 5 \mod8, k+1 \equiv 6 \mod8,$ so $k(k+1) \equiv 6 \mod8$ $k \equiv 6 \mod8, k+1 \equiv 7 \mod8,$ so $k(k+1) \equiv 2 \mod8$ $k \equiv 7 \mod8, k+1 \equiv 0 \mod8,$ so $k(k+1) \equiv 0 \mod8$

Conclude that $k \equiv 3 \mod8$ or $k \equiv 4 \mod8$ . By other hand $k^2+k\equiv 6 \mod 9$ $4k^2+4k\equiv 24 \mod 9$ $(2k+1)^2=4k^2+4k+1\equiv 24+1\equiv 7 \mod 9$ But the residues of 9 that have cuadratic residues equal to 7 are 4 and 5. Now $2k+1\equiv 4 \mod 9$ so $k\equiv 6 \mod 9$ or $2k+1\equiv 5 \mod 9$ so $k\equiv 2 \mod 9$ .

By the Chinesse Residue Teorem we have that $k \equiv 3 \mod 8$ and $k\equiv 2 \mod9$ implies $k \equiv 11 \mod 72$ $k \equiv 3 \mod 8$ and $k\equiv 6 \mod9$ implies $k \equiv 51 \mod 72$ $k \equiv 4 \mod 8$ and $k\equiv 2 \mod9$ implies $k \equiv 20 \mod 72$ $k \equiv 4 \mod 8$ and $k\equiv 6 \mod9$ implies $k \equiv 60 \mod 72$

Finally the anwer is $11+20+51+60=142$ .