Gauss' law and Coulomb's law are equivalent - meaning that they are one and the same thing. Either one of them can be derived from the other. The rigorous derivations can be found in any of the electrodynamics textbooks, for eg., Jackson. For eg., consider a point charge q. As per Coulomb's law, the electric field produced by it is given by $$\vec{E} = \frac{kq}{r^2}\hat{r}$$, where $k = \frac{1}{4 \pi \epsilon_0}$. Now, consider a sphere of radius $r$ centred on charge q. So, for the surface S$S$ of this sphere you have: $$ \int_{S}\vec{E}.\vec{ds} = \int_{S}\frac{kq}{r^2}ds = \frac{kq}{r^2}\int_{S}ds = \frac{kq}{r^2}(4\pi r^2) = 4\pi k q = \frac{q}{\epsilon_0}$$, which is Gauss' law. Note that if the $r^2$ in the expression for the surface area of the sphere in the numerator did not exactly cancel out the $r^2$ in the denominator of Coulomb's law, the surface intergral would actually depend on $r$. Hence you would not have the result that the surface integral is independent of the area of the surface, which is what is implied by Gauss' law. Though this result has been derived for a sphere, it can be derived for any arbitrary shape and size of the surface, you can refer to Jackson for eg., for the rigorous derivation. Note that by performing these steps in reverse, you can also derive Coulomb's law from Gauss' law, thus demonstrating that they are equivalent.