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.

Das Eidg. Versicherungsgericht zieht in Erwägung:
Das Eidg. Versicherungsgericht zieht in Erwägung:
1. Nachdem die Ausgleichskasse lediglich Schadenersatz für entgangene Beiträge der AHV/IV/EO und der Arbeitslosenversicherung (zuzüglich Verzugszinsen) sowie Verwaltungs- und Betreibungskosten geltend macht, ist auf die Verwaltungsgerichtsbeschwerde vollumfänglich einzutreten (<ref-ruling> Erw. 1 mit Hinweis).
1. Nachdem die Ausgleichskasse lediglich Schadenersatz für entgangene Beiträge der AHV/IV/EO und der Arbeitslosenversicherung (zuzüglich Verzugszinsen) sowie Verwaltungs- und Betreibungskosten geltend macht, ist auf die Verwaltungsgerichtsbeschwerde vollumfänglich einzutreten (<ref-ruling> Erw. 1 mit Hinweis).
2. Da es sich bei der angefochtenen Verfügung nicht um die Bewilligung oder Verweigerung von Versicherungsleistungen handelt, hat das Eidgenössische Versicherungsgericht nur zu prüfen, ob das vorinstanzliche Gericht Bundesrecht verletzt hat, einschliesslich Überschreitung oder Missbrauch des Ermessens, oder ob der rechtserhebliche Sachverhalt offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt worden ist (Art. 132 in Verbindung mit Art. 104 lit. a und b sowie Art. 105 Abs. 2 OG).
2. Da es sich bei der angefochtenen Verfügung nicht um die Bewilligung oder Verweigerung von Versicherungsleistungen handelt, hat das Eidgenössische Versicherungsgericht nur zu prüfen, ob das vorinstanzliche Gericht Bundesrecht verletzt hat, einschliesslich Überschreitung oder Missbrauch des Ermessens, oder ob der rechtserhebliche Sachverhalt offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt worden ist (Art. 132 in Verbindung mit Art. 104 lit. a und b sowie Art. 105 Abs. 2 OG).
3. Am 1. Januar 2003 ist das Bundesgesetz über den Allgemeinen Teil des Sozialversicherungsrechts (ATSG) vom 6. Oktober 2000 in Kraft getreten. Mit ihm sind zahlreiche Bestimmungen im AHV-Bereich, insbesondere auch hinsichtlich der Arbeitgeberhaftung nach <ref-law>, geändert sowie Art. 81 und 82 AHVV aufgehoben worden. Weil in zeitlicher Hinsicht grundsätzlich diejenigen Rechtssätze massgebend sind, die bei der Erfüllung des zu Rechtsfolgen führenden Tatbestandes Geltung haben (<ref-ruling> Erw. 1, 126 V 166 Erw. 4b), kommen jedoch die bis 31. Dezember 2002 geltenden Bestimmungen zur Anwendung.
3. Am 1. Januar 2003 ist das Bundesgesetz über den Allgemeinen Teil des Sozialversicherungsrechts (ATSG) vom 6. Oktober 2000 in Kraft getreten. Mit ihm sind zahlreiche Bestimmungen im AHV-Bereich, insbesondere auch hinsichtlich der Arbeitgeberhaftung nach <ref-law>, geändert sowie Art. 81 und 82 AHVV aufgehoben worden. Weil in zeitlicher Hinsicht grundsätzlich diejenigen Rechtssätze massgebend sind, die bei der Erfüllung des zu Rechtsfolgen führenden Tatbestandes Geltung haben (<ref-ruling> Erw. 1, 126 V 166 Erw. 4b), kommen jedoch die bis 31. Dezember 2002 geltenden Bestimmungen zur Anwendung.
4. Die Vorinstanz hat die massgebenden Bestimmungen (<ref-law>; <ref-law> in Verbindung mit <ref-law>) sowie die dazu ergangene Rechtsprechung, insbesondere über die subsidiäre Haftung der Organe eines Arbeitgebers (<ref-ruling> Erw. 5b; SVR 2003 AHV Nr. 1 S. 2 Erw. 3, je mit Hinweisen), den zu ersetzenden Schaden (<ref-ruling> Erw. 3a, 123 V 15 Erw. 5b, 121 III 384 Erw. 3bb, je mit Hinweisen), die erforderliche Widerrechtlichkeit (<ref-ruling> Erw. 2a; SVR 2001 AHV Nr. 15 S. 52 Erw. 6, je mit Hinweisen), die Voraussetzung des Verschuldens (<ref-ruling> Erw. 1b, 202 Erw. 3a; ZAK 1992 S. 248 Erw. 4b, 1985 S. 620 Erw. 3b, je mit Hinweisen) sowie den verlangten adäquaten Kausalzusammenhang (<ref-ruling> Erw. 5a, 119 V 406 Erw. 4a; AHI 1996 S. 292 Erw. 4, je mit Hinweisen), zutreffend dargelegt. Darauf wird verwiesen.
4. Die Vorinstanz hat die massgebenden Bestimmungen (<ref-law>; <ref-law> in Verbindung mit <ref-law>) sowie die dazu ergangene Rechtsprechung, insbesondere über die subsidiäre Haftung der Organe eines Arbeitgebers (<ref-ruling> Erw. 5b; SVR 2003 AHV Nr. 1 S. 2 Erw. 3, je mit Hinweisen), den zu ersetzenden Schaden (<ref-ruling> Erw. 3a, 123 V 15 Erw. 5b, 121 III 384 Erw. 3bb, je mit Hinweisen), die erforderliche Widerrechtlichkeit (<ref-ruling> Erw. 2a; SVR 2001 AHV Nr. 15 S. 52 Erw. 6, je mit Hinweisen), die Voraussetzung des Verschuldens (<ref-ruling> Erw. 1b, 202 Erw. 3a; ZAK 1992 S. 248 Erw. 4b, 1985 S. 620 Erw. 3b, je mit Hinweisen) sowie den verlangten adäquaten Kausalzusammenhang (<ref-ruling> Erw. 5a, 119 V 406 Erw. 4a; AHI 1996 S. 292 Erw. 4, je mit Hinweisen), zutreffend dargelegt. Darauf wird verwiesen.
5. Die Beschwerdeführer bestreiten insbesondere den Schaden, ein massgebliches Verschulden sowie den erforderlichen Kausalzusammenhang.
5.1 Die Beschwerdeführer machen geltend, während ihres Mandats als Verantwortliche der konkursiten Firma seien die Ausstände gegenüber der Ausgleichskasse kleiner geworden; es könne somit nicht gesagt werden, sie hätten den Betrieb auf Kosten der Ausgleichskasse weitergeführt. Diesen Ausführungen ist entgegen zu halten, dass sämtliche geltend gemachten Zahlungen vor Erlass der Schadenersatzverfügung über das Betreibungsamt geleistet wurden, weil die Firma für die andauernden und grossen Ausstände betrieben werden musste. Zudem übersehen die Beschwerdeführer, dass sie mit Übernahme ihres Mandats als Organ der Firma auch die Verantwortung für die ausstehenden Beiträge übernommen hatten (<ref-ruling> Erw. 4c; ZAK 1992 S. 254 Erw. 7b, je mit Hinweisen). Dementsprechend sind sie nicht nur für die während ihrer Zeit als Organ der Firma fällig gewordenen Beiträge haftbar, sondern auch für alle früheren. Etwas anderes würde nur gelten, wenn die Firma bei Antritt des Mandats als Organ bereits zahlungsunfähig und der Schaden somit bereits eingetreten gewesen wäre (<ref-ruling> Erw. 4b und c). Dem ist entgegen der Ansicht der Beschwerdeführer nicht so: Die Vorinstanz hat zutreffend erkannt, dass sich die Firma im Zeitpunkt der Übernahme der Geschäftsführung durch die Beschwerdeführer wohl in einem Liquiditätsengpass befand, nicht aber zahlungsunfähig war. So waren die Beschwerdeführer in der Lage, sowohl die Löhne auszubezahlen als auch andere Gläubiger zu befriedigen. In dieser Situation wären die Beschwerdeführer gehalten gewesen, nur soviel Lohn auszubezahlen, als sie in der Lage waren, auch die darauf ex lege geschuldeten paritätischen Beiträge zu bezahlen (SVR 1995 AHV Nr. 70 S. 214 Erw. 5).
5.2 Die Belangten verweisen zudem auf das Darlehen der vom Beschwerdeführer beherrschten Firma C._ AG. Dies vermag sie jedoch nicht zu entlasten, da weder das Erleiden persönlicher Verluste noch das Einschiessen privater Mittel eine konkrete Bemühung um Bezahlung der ausstehenden Beiträge darstellt (vgl. Urteil D. vom 8. Oktober 2001, H 94/01, Urteil B. vom 26. September 2001, H 19/01, Urteil V. vom 15. September 2000, H 45/00, sowie Urteil W. und C. vom 13. Dezember 2000, H 124/00 und H 125/00). So ist denn auch weder ersichtlich noch wird geltend gemacht, dass die eingebrachten Fr. 60'000.- oder ein Teil davon zur Begleichung der aufgelaufenen Beitragsschulden verwendet wurde.
5.3 Die Beschwerdeführer erheben weiter den Einwand, die Ausgleichskasse habe es versäumt, auch andere ehemalige Verwaltungsräte und die Revisionsstelle zu belangen, und es unterlassen, eine Haftungsminderung auf Grund des Mitverschuldens dieser Mitbeteiligten vorzunehmen. Sie verkennen dabei, dass es sich bei der Haftung nach <ref-law> um eine solidarische Haftung handelt; mithin steht es der Ausgleichskasse frei, einen, mehrere oder alle möglichen Schadenersatzpflichtigen zu belangen (<ref-ruling> Erw. 5a; AHI 1996 S. 293 Erw. 6, je mit Hinweisen; vgl. auch Urteil B. vom 25. September 2002, H 92/01). Im Übrigen kennt das Verfahren nach <ref-law> eine Haftungsreduktion infolge Mitverschuldens anderer Personen, insbesondere gestützt auf <ref-law>, nicht (AHI 1996 S. 291 mit Hinweisen). Einzig ein Mitverschulden der Ausgleichskasse wäre ein Herabsetzungsgrund (<ref-ruling>); es liegen jedoch keine Anhaltspunkte vor, die ein Mitverschulden der Ausgleichskasse als wahrscheinlich erscheinen lassen würden.
5.3 Die Beschwerdeführer erheben weiter den Einwand, die Ausgleichskasse habe es versäumt, auch andere ehemalige Verwaltungsräte und die Revisionsstelle zu belangen, und es unterlassen, eine Haftungsminderung auf Grund des Mitverschuldens dieser Mitbeteiligten vorzunehmen. Sie verkennen dabei, dass es sich bei der Haftung nach <ref-law> um eine solidarische Haftung handelt; mithin steht es der Ausgleichskasse frei, einen, mehrere oder alle möglichen Schadenersatzpflichtigen zu belangen (<ref-ruling> Erw. 5a; AHI 1996 S. 293 Erw. 6, je mit Hinweisen; vgl. auch Urteil B. vom 25. September 2002, H 92/01). Im Übrigen kennt das Verfahren nach <ref-law> eine Haftungsreduktion infolge Mitverschuldens anderer Personen, insbesondere gestützt auf <ref-law>, nicht (AHI 1996 S. 291 mit Hinweisen). Einzig ein Mitverschulden der Ausgleichskasse wäre ein Herabsetzungsgrund (<ref-ruling>); es liegen jedoch keine Anhaltspunkte vor, die ein Mitverschulden der Ausgleichskasse als wahrscheinlich erscheinen lassen würden.
6. Da es nicht um die Bewilligung oder Verweigerung von Versicherungsleistungen geht, ist das Verfahren kostenpflichtig (Art. 134 OG e contrario). Die unterliegenden Beschwerdeführer haben demnach die Gerichtskosten zu tragen (Art. 156 Abs. 1 in Verbindung mit Art. 135 OG).

Demnach erkennt das Eidg. Versicherungsgericht:
Demnach erkennt das Eidg. Versicherungsgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 4000.- werden den Beschwerdeführern zu gleichen Teilen auferlegt. Sie sind durch den Kostenvorschuss von insgesamt Fr. 7000.- gedeckt; der Differenzbetrag von je Fr. 1500.- wird den Beschwerdeführern zurückerstattet.
2. Die Gerichtskosten von Fr. 4000.- werden den Beschwerdeführern zu gleichen Teilen auferlegt. Sie sind durch den Kostenvorschuss von insgesamt Fr. 7000.- gedeckt; der Differenzbetrag von je Fr. 1500.- wird den Beschwerdeführern zurückerstattet.
3. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht Basel-Stadt und dem Bundesamt für Sozialversicherung zugestellt.
Luzern, 9. Februar 2004
Im Namen des Eidgenössischen Versicherungsgerichts
Der Präsident der IV. Kammer: Die Gerichtsschreiberin: