We have investigated the lattice parameters, bond lengths, and band-gap energies of ordered and random alloys of wurtzite-phase AlN and GaN, using density-functional local-orbital theory based on the local-density approximation and the pseudopotential method. The lattice constants a and c are found to change nearly linearly with x for all structures. However, the Ga-N and Al-N bond lengths exhibit significantly smaller variations, which is in agreement with the data from recent x-ray absorption fine-structure measurements. The alloys are direct-gap semiconductors for all Al fractions x. The alloy structures investigated exhibit a small downward bowing of the band-gap energy. The bowing is substantially reduced by optimizing the lattice parameters. For ordered alloys, the band-gap energies are found to show a nearly linear variation with the Al fraction.