Sachverhalt: Sachverhalt: A. Der aus der Türkei stammende, *** 1972 geborene AX._ reiste am 18. September 2000 illegal in die Schweiz ein und stellte ein Asylgesuch. Das Bundesamt für Flüchtlinge wies das Gesuch am 15. Januar 2001 ab. Die dagegen erhobene Beschwerde wies die Schweizerische Asylrekurskommission mit Urteil vom 29. Mai 2001 ab. AX._ tauchte in der Folge unter. Am 20. Juni 2002 reiste er wieder in die Schweiz ein, und *** August 2002 heiratete er in C._ die 1956 geborene Schweizerin B._. Am 17. September 2002 stellte BX._ ein Gesuch um Nachzug ihres Ehemannes; gleichentags ersuchte AX._ um Erteilung einer Aufenthaltsbewilligung. Mit Schreiben vom 15. Januar 2003 teilte das Ausländeramt des Kantons Thurgau BX._ mit, es gehe davon aus, dass es sich bei ihrer Ehe mit AX._ um eine Gefälligkeitsehe handle, und machte sie auf die Möglichkeit aufmerksam, eine rekursfähige Verfügung zu verlangen. Hierauf ersuchte das Ehepaar X._, nunmehr durch einen Anwalt vertreten, am 31. Januar 2003 erneut um eine Aufenthaltsbewilligung für AX._. Mit Verfügung vom 17. Februar 2003 wies das Ausländeramt des Kantons Thurgau das Gesuch ab mit der Begründung, es handle sich um eine Gefälligkeitsehe. Dagegen erhob AX._ am 10. März 2003 Rekurs beim Departement für Justiz und Sicherheit des Kantons Thurgau. Dieses entscheid mit Zwischenverfügung vom 13. März 2003, dass sich AX._ bis zu einem anders lautenden Entscheid des Departements im Kanton Thurgau aufhalten dürfe; mit Entscheid vom 16. September 2003 wies es den Rekurs ab. Gegen diesen Entscheid erhoben AX._ und BX._ am 15. Oktober 2003 Beschwerde beim Verwaltungsgericht des Kantons Thurgau. Dieses wies die Beschwerde mit Entscheid vom 21. Januar 2004 ab. A. Der aus der Türkei stammende, *** 1972 geborene AX._ reiste am 18. September 2000 illegal in die Schweiz ein und stellte ein Asylgesuch. Das Bundesamt für Flüchtlinge wies das Gesuch am 15. Januar 2001 ab. Die dagegen erhobene Beschwerde wies die Schweizerische Asylrekurskommission mit Urteil vom 29. Mai 2001 ab. AX._ tauchte in der Folge unter. Am 20. Juni 2002 reiste er wieder in die Schweiz ein, und *** August 2002 heiratete er in C._ die 1956 geborene Schweizerin B._. Am 17. September 2002 stellte BX._ ein Gesuch um Nachzug ihres Ehemannes; gleichentags ersuchte AX._ um Erteilung einer Aufenthaltsbewilligung. Mit Schreiben vom 15. Januar 2003 teilte das Ausländeramt des Kantons Thurgau BX._ mit, es gehe davon aus, dass es sich bei ihrer Ehe mit AX._ um eine Gefälligkeitsehe handle, und machte sie auf die Möglichkeit aufmerksam, eine rekursfähige Verfügung zu verlangen. Hierauf ersuchte das Ehepaar X._, nunmehr durch einen Anwalt vertreten, am 31. Januar 2003 erneut um eine Aufenthaltsbewilligung für AX._. Mit Verfügung vom 17. Februar 2003 wies das Ausländeramt des Kantons Thurgau das Gesuch ab mit der Begründung, es handle sich um eine Gefälligkeitsehe. Dagegen erhob AX._ am 10. März 2003 Rekurs beim Departement für Justiz und Sicherheit des Kantons Thurgau. Dieses entscheid mit Zwischenverfügung vom 13. März 2003, dass sich AX._ bis zu einem anders lautenden Entscheid des Departements im Kanton Thurgau aufhalten dürfe; mit Entscheid vom 16. September 2003 wies es den Rekurs ab. Gegen diesen Entscheid erhoben AX._ und BX._ am 15. Oktober 2003 Beschwerde beim Verwaltungsgericht des Kantons Thurgau. Dieses wies die Beschwerde mit Entscheid vom 21. Januar 2004 ab. B. Dagegen haben AX._ und BX._ beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben. Sie beantragen, den Entscheid des Verwaltungsgerichts aufzuheben und AX._ eine Aufenthaltsbewilligung zu erteilen; eventuell die Sache zu neuer Beurteilung an das Verwaltungsgericht oder an das Ausländeramt zurückzuweisen. Das Departement für Justiz und Sicherheit und das Verwaltungsgericht des Kantons Thurgau beantragen die Abweisung der Beschwerde. Denselben Antrag stellt das Bundesamt für Zuwanderung, Integration und Auswanderung.