We study 1 or 2 neighboring Mn impurities, as well as complexes of 1 Mn and 1 or 2 Mg ions in a 64 atoms supercell of GaN by means of density functional calculations. Taking into account the electron correlation in the local spin density approximation with explicit correction of the Hubbard term (the LSDA+U method) and full lattice relaxation we determine the nearest neighbor exchange J for a pair of Mn impurities. We find J to be ferromagnetic and of the order of about 18 meV in the Hamiltonian H=-2*J1*J2. That J is only weakly influenced by the U parameter (varying between 2 and 8 eV) and by the lattice relaxation. From a detailed analysis of the magnetization density distribution we get hints for a ferromagnetic super-exchange mechanism. Also the Mn valence was found to be 3+ without any doubt in the absence of co-doping with Mg. Co-doping with Mg leads to a valence change to 4+ for 1 Mg and to 5+ for 2 Mg. We show that the valence change can already be concluded from a careful analysis of the density of states of GaN doped with Mn without any Mg.