Structural models for the Ga (or Al)-rich GaAs(100)-(2×1) surface and for the As-rich (2×4) surface are examined by tight-binding based total-energy calculations. The most stable (2×1) surface contains 1/2 monolayer of Ga vacancies which make the surface nonmetallic and nonpolar. For the (2×4) surface, unit cells containing various combinations of As2 dimers, missing dimers, and Ga vacancies were considered. The most likely surface structure contains three As2 dimers per unit cell. Two such structures, nearly degenerate in energy, are possible. The calculated surface electronic structures agree with photoemission data to within ±0.3 eV. The c(2×8) and (2×4) structures are closely related and both are expected to occur at the surface.