Faits: Faits: A. X._, ressortissant turc né le 16 janvier 1960, est entré illégalement en Suisse le 2 janvier 1985. Il a déposé une demande d'asile qui a été définitivement rejetée le 30 avril 1987. Un délai, prolongé au 18 juillet 1987, lui a été imparti pour quitter le pays et une interdiction d'entrée, valable jusqu'au 30 août 1990, a été prononcée à son encontre pour des motifs préventifs d'assistance publique. A. X._, ressortissant turc né le 16 janvier 1960, est entré illégalement en Suisse le 2 janvier 1985. Il a déposé une demande d'asile qui a été définitivement rejetée le 30 avril 1987. Un délai, prolongé au 18 juillet 1987, lui a été imparti pour quitter le pays et une interdiction d'entrée, valable jusqu'au 30 août 1990, a été prononcée à son encontre pour des motifs préventifs d'assistance publique. B. L'intéressé est à nouveau entré en Suisse le 9 octobre 1992 et il a épousé Z._, ressortissante suisse née le 19 octobre 1946. Il a été mis au bénéfice d'une autorisation de séjour régulièrement renouvelée, puis il a obtenu une autorisation d'établissement le 30 janvier 1998. En mars 1998, il s'est rendu seul en Turquie où il a conçu un enfant avec une compatriote, Y._, née le 25 janvier 1971. Le 18 août 1998, il a acquis la nationalité suisse par naturalisation facilitée. Les époux X.Z._ ont signé une convention sur les effets accessoires du divorce le 4 novembre 1998; leur divorce a été prononcé le 9 mars 1999. Le 18 juin 1999, l'intéressé a épousé Y._, qui est venue le rejoindre en Suisse le 3 décembre 1999 avec leur fils A._ (né le 24 décembre 1998). Par courrier du 22 décembre 1999, le Service de l'état civil et des étrangers du canton du Valais (ci-après: le Service cantonal) a informé Y._, que son séjour ainsi que celui de son fils était toléré jusqu'à droit connu sur la procédure d'annulation de la naturalisation facilitée ouverte à l'endroit de son mari. X._ et Y._ ont encore eu deux enfants, B._, né le 12 mars 2000 et C._, né le 1er février 2003. L'Office fédéral de l'immigration, de l'intégration et de l'émigration, actuellement l'Office fédéral des migrations (ci-après: l'Office fédéral), a annulé la naturalisation facilitée de X._ le 5 juin 2003. Il a considéré que l'union conjugale entre les époux X.Z._ ne pouvait plus être qualifiée de stable au moment de la décision de naturalisation et que l'intéressé n'en avait pas informé les autorités compétentes pour ne pas compromettre la procédure. Aucun recours n'a été formé contre cette décision. L'Office fédéral a informé le Service cantonal que X._ retrouvait le statut qui était le sien précédemment, à savoir titulaire d'une autorisation d'établissement (cf. courrier du 1er décembre 2004), dont le délai de contrôle était échu le 31 octobre 2000. L'Office fédéral de l'immigration, de l'intégration et de l'émigration, actuellement l'Office fédéral des migrations (ci-après: l'Office fédéral), a annulé la naturalisation facilitée de X._ le 5 juin 2003. Il a considéré que l'union conjugale entre les époux X.Z._ ne pouvait plus être qualifiée de stable au moment de la décision de naturalisation et que l'intéressé n'en avait pas informé les autorités compétentes pour ne pas compromettre la procédure. Aucun recours n'a été formé contre cette décision. L'Office fédéral a informé le Service cantonal que X._ retrouvait le statut qui était le sien précédemment, à savoir titulaire d'une autorisation d'établissement (cf. courrier du 1er décembre 2004), dont le délai de contrôle était échu le 31 octobre 2000. C. Le 21 mars 2005, le Service cantonal a révoqué l'autorisation d'établissement de X._ et a refusé de délivrer une autorisation de séjour à son épouse Y._ et à leurs enfants A._, B._ et C._. Un délai fixé au 3 mai 2005 a été imparti à la famille X.Y._ pour quitter le territoire valaisan. Par décision du 14 décembre 2005, le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a rejeté le recours formé par l'intéressé et sa famille contre la décision du Service cantonal du 21 mars 2005. Par décision du 14 décembre 2005, le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a rejeté le recours formé par l'intéressé et sa famille contre la décision du Service cantonal du 21 mars 2005. D. Le 31 mars 2006, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours interjeté par X._, son épouse Y._ et leurs enfants A._, B._ et C._, contre la décision du Conseil d'Etat du 14 décembre 2005. Le Tribunal cantonal a en effet considéré que si X._ avait correctement renseigné l'autorité de police des étrangers sur le fait que la communauté conjugale avec Z._ n'était plus effective pendant les dernières années de mariage, l'autorisation d'établissement lui aurait été refusée. Enfin, la révocation de l'autorisation d'établissement de l'intéressé avait pour conséquence le refus d'une autorisation de séjour en faveur des autres membres de la famille. D. Le 31 mars 2006, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours interjeté par X._, son épouse Y._ et leurs enfants A._, B._ et C._, contre la décision du Conseil d'Etat du 14 décembre 2005. Le Tribunal cantonal a en effet considéré que si X._ avait correctement renseigné l'autorité de police des étrangers sur le fait que la communauté conjugale avec Z._ n'était plus effective pendant les dernières années de mariage, l'autorisation d'établissement lui aurait été refusée. Enfin, la révocation de l'autorisation d'établissement de l'intéressé avait pour conséquence le refus d'une autorisation de séjour en faveur des autres membres de la famille. E. Agissant par la voie du recours de droit administratif, la famille X.Y._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 31 mars 2006 ainsi que la décision du Service cantonal 21 mars 2005, de mettre X._ au bénéfice d'une autorisation d'établissement et les autres membres de la famille au bénéfice d'une autorisation de séjour. Les recourants se plaignent d'une violation de leur droit d'être entendus, d'une mauvaise constatation des faits et application du droit ainsi que d'une violation du principe de la proportionnalité. Ils invoquent, à l'appui de leurs griefs, l'art. 7 al. 1 2ème phrase de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142.20). Le Tribunal cantonal a renoncé à se déterminer sur le recours. Le Conseil d'Etat a conclu au rejet du recours avec suite de frais et sans allocation de dépens. L'Office fédéral propose le rejet du recours. L'Office fédéral propose le rejet du recours. F. Par ordonnance du 8 juin 2006, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif contenue dans le recours. Le 5 septembre 2006, le Tribunal de Sierre a produit le dossier du divorce des époux X.Z._, dont les recourants ont pris connaissance le 6 novembre 2006, par l'intermédiaire de leur représentant. 