Faits : A. X._, ressortissant algérien né en 1972, est entré en Suisse le 2 mai 2003 en vue d'y déposer une demande d'asile. Celle-ci a été rejetée par l'ancien Office fédéral des réfugiés (actuellement le Secrétariat d'Etat aux migrations; ci-après: le Secrétariat d'Etat) le 21 juillet 2003. Le recours interjeté contre cette décision a été déclaré irrecevable par l'ancienne Commission suisse de recours en matière d'asile (actuellement le Tribunal administratif fédéral) le 21 juillet 2003. Malgré le délai au 25 novembre 2003 imparti à l'intéressé pour quitter la Suisse, celui-ci a poursuivi son séjour. Le 29 novembre 2008, X._ a épousé une ressortissante française née en 1973 et au bénéfice d'une autorisation d'établissement. L'intéressé a obtenu une autorisation de séjour au titre du regroupement familial. Suite à plusieurs interruptions de la vie commune, les époux ont définitivement cessé de faire ménage commun en février 2011 au plus tard. Ils ont tous deux allégué avoir subi des violences conjugales. Leur divorce a été prononcé le 6 janvier 2015. Par courrier du 20 mars 2014, l'Office cantonal de la population et des migrations de la République et canton de Genève (ci-après: l'Office cantonal) a expliqué à l'intéressé qu'il était disposé à soumettre à l'Office fédéral des migrations (actuellement le Secrétariat d'Etat) le renouvellement de son autorisation de séjour pour approbation. B. Par décision du 19 mars 2015, le Secrétariat d'Etat a refusé de donner son approbation au renouvellement de l'autorisation de séjour de l'intéressé. Celui-ci, par acte du 24 avril 2015, a contesté cette décision auprès du Tribunal administratif fédéral. Par arrêt du 24 septembre 2015, le Tribunal administratif fédéral a rejeté le recours de X._, considérant que ce dernier ne pouvait se prévaloir d'une union conjugale suffisamment longue et que la poursuite du séjour ne s'imposait pas pour des raisons personnelles majeures. C. Agissant par la voie du recours en matière de droit public, X._ demande en substance au Tribunal fédéral, sous suite de dépens, outre l'effet suspensif et l'assistance judiciaire, d'annuler l'arrêt du Tribunal administratif fédéral du 24 septembre 2015 et d'enjoindre au Secrétariat d'Etat d'approuver la décision de l'Office cantonal; subsidiairement de renvoyer la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il se plaint de violation du droit fédéral. Par ordonnance du 29 octobre 2015, le Juge présidant de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif. Le Tribunal administratif fédéral renonce à prendre position. Le Secrétariat d'Etat conclut au rejet du recours.