Sachverhalt: Sachverhalt: A. Die Firma X._ war bei der Ausgleichskasse Gastrosuisse (nachfolgend: Ausgleichskasse) als Arbeitgeberin angeschlossen. Am 16. August 2001 wurde über die Firma der Konkurs eröffnet und am 11. September 2001 mangels Aktiven wieder eingestellt. B._ war ab 13. November 2000 bis zum 29. Juni 2001 Mitglied des Verwaltungsrates mit Einzelunterschrift. Ab demselben Datum verfügte A._ über die Einzelunterschriftsberechtigung. Mit Verfügungen vom 4. Januar 2002 verpflichtete die Ausgleichskasse die beiden unter solidarischer Haftung zur Zahlung von Fr. 47'555.- Schadenersatz für entgangene Beiträge. A. Die Firma X._ war bei der Ausgleichskasse Gastrosuisse (nachfolgend: Ausgleichskasse) als Arbeitgeberin angeschlossen. Am 16. August 2001 wurde über die Firma der Konkurs eröffnet und am 11. September 2001 mangels Aktiven wieder eingestellt. B._ war ab 13. November 2000 bis zum 29. Juni 2001 Mitglied des Verwaltungsrates mit Einzelunterschrift. Ab demselben Datum verfügte A._ über die Einzelunterschriftsberechtigung. Mit Verfügungen vom 4. Januar 2002 verpflichtete die Ausgleichskasse die beiden unter solidarischer Haftung zur Zahlung von Fr. 47'555.- Schadenersatz für entgangene Beiträge. B. Nachdem sowohl A._ als auch B._ Einspruch erhoben hatten, beantragte die Ausgleichskasse mit Klage vom 13. Februar 2002, A._ und B._ seien unter solidarischer Haftbarkeit je zur Zahlung von 47'555.- Schadenersatz für entgangene Beiträge zu verpflichten. Nachdem am 11. März 2002 eine Zahlung geleistet wurde, reduzierte die Ausgleichskasse ihr Begehren auf Fr. 40'106.35. Das Sozialversicherungsgericht Basel-Stadt hiess die Klage mit Entscheid vom 21. Mai 2003 im reduzierten Umfang gut. B. Nachdem sowohl A._ als auch B._ Einspruch erhoben hatten, beantragte die Ausgleichskasse mit Klage vom 13. Februar 2002, A._ und B._ seien unter solidarischer Haftbarkeit je zur Zahlung von 47'555.- Schadenersatz für entgangene Beiträge zu verpflichten. Nachdem am 11. März 2002 eine Zahlung geleistet wurde, reduzierte die Ausgleichskasse ihr Begehren auf Fr. 40'106.35. Das Sozialversicherungsgericht Basel-Stadt hiess die Klage mit Entscheid vom 21. Mai 2003 im reduzierten Umfang gut. C. A._ und B._ lassen Verwaltungsgerichtsbeschwerde führen und beantragen, es seien der vorinstanzliche Entscheid aufzuheben und die Klage vom 13. Februar 2002 abzuweisen. Die Ausgleichskasse schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde. Das Bundesamt für Sozialversicherung verzichtet auf eine Vernehmlassung.