Rainbow decompositions

A rainbow coloring of a graph is a coloring of the edges with distinct colors. We prove the following extension of Wilson's Theorem. For every integer $k$ there exists an $n_0=n_0(k)$ so that for all $n > n_0$, if

$$n \bmod k(k-1) \in \{1,k\},$$

then every properly edge-colored $K_n$ contains $\binom{n}{2}/\binom{k}{2}$ pairwise edge-disjoint rainbow copies of $K_k$.

Our proof uses, as a main ingredient, a double application of the probabilistic method.