Sachverhalt: Sachverhalt: A. W._ war seit Gründung bis zum 11. Januar 1999 Vize-, danach Verwaltungsratspräsident der Firma A._ AG; Z._ amtete zuerst als Präsident, ab 11. Januar 1999 bis zu seinem Ausscheiden am 16. März 2000 als Vizepräsident des Verwaltungsrates. Die A._ AG war seit ihrer Gründung im Dezember 1998 der Ausgleichskasse Zug als Arbeitgeberin angeschlossen. Gemäss dem Abklärungsbogen der Ausgleichskasse waren Rechnungen und Korrespondenz an die Filiale in L._ zu schicken. 2000 wurde über die Firma der Konkurs eröffnet. Der Kollokationsplan wurde am ...... aufgelegt. Mit Verfügung vom 11. November 2002 verpflichtete die Ausgleichskasse Z._ zur Bezahlung von Schadenersatz für entgangene Beiträge in der Höhe von Fr. 36'304.40. A. W._ war seit Gründung bis zum 11. Januar 1999 Vize-, danach Verwaltungsratspräsident der Firma A._ AG; Z._ amtete zuerst als Präsident, ab 11. Januar 1999 bis zu seinem Ausscheiden am 16. März 2000 als Vizepräsident des Verwaltungsrates. Die A._ AG war seit ihrer Gründung im Dezember 1998 der Ausgleichskasse Zug als Arbeitgeberin angeschlossen. Gemäss dem Abklärungsbogen der Ausgleichskasse waren Rechnungen und Korrespondenz an die Filiale in L._ zu schicken. 2000 wurde über die Firma der Konkurs eröffnet. Der Kollokationsplan wurde am ...... aufgelegt. Mit Verfügung vom 11. November 2002 verpflichtete die Ausgleichskasse Z._ zur Bezahlung von Schadenersatz für entgangene Beiträge in der Höhe von Fr. 36'304.40. B. Nachdem Z._ Einspruch erhoben hatte, reichte die Ausgleichskasse am 5. Dezember 2002 Klage ein, mit welcher sie beantragte, Z._ sei zu verpflichten, ihr Schadenersatz in der Höhe von Fr. 36'304.40 zu bezahlen. Das Verwaltungsgericht des Kantons Zug hiess mit Entscheid vom 21. August 2003 die Klage im Betrag von Fr. 35'311.50 gut. B. Nachdem Z._ Einspruch erhoben hatte, reichte die Ausgleichskasse am 5. Dezember 2002 Klage ein, mit welcher sie beantragte, Z._ sei zu verpflichten, ihr Schadenersatz in der Höhe von Fr. 36'304.40 zu bezahlen. Das Verwaltungsgericht des Kantons Zug hiess mit Entscheid vom 21. August 2003 die Klage im Betrag von Fr. 35'311.50 gut. C. Z._ lässt Verwaltungsgerichtsbeschwerde führen mit dem Antrag, es seien der vorinstanzliche Entscheid aufzuheben und die Klage der Ausgleichskasse abzuweisen; eventualiter sei die Sache an das kantonale Gericht zurückzuweisen. Das Verwaltungsgericht des Kantons Zug und die Ausgleichskasse schliessen auf Abweisung der Verwaltungsgerichtsbeschwerde. Das Bundesamt für Sozialversicherung verzichtet auf eine Vernehmlassung. 