What I think is that Gauss's law is an independent law of nature which shouldn't change on modifying Coulomb's law.Am I correct?
Well the relation between Gauss's law and Coulomb's law is very strong but I can't strictly say that they can be derived from each other just like I can't say that law of conservation of linear momentum can be derived from Newton's 3rd law.
Edit
It's my gentle request that if one of them is a theorem then please name one of them as a theorem as it makes them quite complicated.