"And they believed in God and in Moses his servant,"
But why not just say,
The answer is a simple axiom of Chassidus: Because there can be no connection directly to God without the mediation of the "Moses of the generation"! As sure as every body needs a head to function, God casts a Moses for every generation to be its leader (Tikunei Zohar 469). No generation can exist without its "Moses" (Beraishit Rabba 56:7).
Failure to believe in this Tzaddik, the leader of the generation, causes forfeiture of the belief in God - because the Moses of the generation is the perfect conduit through whom belief in God can be actualized.
One might ask, "Who needs Moses (or the present leader of the generation)? I can believe or connect to God directly - without need of a "conduit" (ממוצא המחבר)!
That's like saying, "I'll pray to Abraham, Isaac and Jacob to help me out"; But who says they will accept you? But, if your request is carried to them by the "Prince of the Generation" (נשיא הדור), now suddenly your request is deemed worthy for acceptance.
That's just what Torah insinuates. There is a formal channel of communication to God. You might have the right "number" to dial, but without the right "area code", you cannot get through.
(How failure of faith in God manifests is a different story.)
So it is not for nothing "ובמשה עבדו" follows "ויאמינו בד'"! One requires the other!
This truth might hurt those who do not practice "ויאמינו במשה עבדו", in which case "ויאמינו בד'" therefore fails, but this is Torah truth, and nothing but Torah truth!
As R' Yossi taught, "Woe to those who see, but know not what they see, who stand, but know not upon what they stand; Upon what does the earth stand? ... 'And the righteous one is the foundation of the whole world' (Proverbs 10)." (Chagigah 12b)
Here's an indication of the same concept. It says "And when you wish to raise the heads of the Jewish people ..." (Ex.30:12), you do it by counting them, because counting attributes equal importance to every Jew. You count them by counting the coins they each provide, the Half-Shekel (מחצית השקל) coins. The word מחצית, says the Tzemach-Tzedek, shows that those who connect to the Tzaddik, represented by the middle letter of this word - are "alive", as suggested by this letter's two adjoining letters, חי; Whereas those remote from the Tzaddik, as suggested by the two letters furthest from the Tzaddik, מת, suffer a metaphoric death. To be uplifted, then, a connection to the Tzaddik of the generation is warranted.