Faits : A. A.a. Selon contrat de travail du 20 juillet 2009, X._ (l'employé) a été engagé en qualité d'auxiliaire par le Royaume de Z._ (l'employeur), pour le Consulat général de Z._ à Genève. L'employé a fait l'objet d'une première décision disciplinaire le 15 novembre 2010 par laquelle il a été suspendu de ses fonctions du 1er janvier au 31 mars 2011 pour faute très grave: il avait soustrait le nouveau passeport d'une ressortissante de l'Etat Z._ afin de le lui remettre personnellement et en mains propres en dehors du Consulat, après avoir pris contact à plusieurs reprises avec elle à son numéro de téléphone privé et lui avoir proposé de déjeuner ensemble; il avait également pris des vacances non autorisées. A.b. Le 2 octobre 2012, des faits similaires sont survenus: l'employé a utilisé des données personnelles d'une ressortissante de l'Etat Z._ pour lui envoyer un SMS et lui téléphoner, présentant ses excuses à propos d'une erreur (la perforation du passeport de sa fille mineure) dont il avait déjà demandé pardon dans les locaux du Consulat, au point que l'intéressée s'est plainte de son insistance déplacée. X._ a été convoqué dans le bureau du Consul le même jour et a eu un autre entretien avec celui-ci le 15 octobre 2012. A.c. Par décision du 30 janvier 2013, qui lui a été notifiée le 31 janvier 2013, l'employé a été informé de l'ouverture d'une enquête disciplinaire à son encontre à raison des faits du 2 octobre 2012 et suspendu provisoirement de ses fonctions et de tout droit à son salaire durant toute la période de l'enquête disciplinaire. L'employé a été déclaré incapable de travailler dès le lendemain de sa suspension provisoire, soit le 1er février 2013, et ce jusqu'au 31 décembre 2013. Il n'a reçu aucune indemnité de la sécurité sociale de l'Etat Z._ pendant sa suspension provisoire. Au terme de l'enquête disciplinaire, l'employé a été licencié avec effet immédiat par son employeur selon résolution du 12 septembre 2013, qui lui a été notifiée le 17 septembre 2013. Alors que l'enquêteur avait proposé le transfert forcé de l'employé, avec ou sans changement de lieu de résidence, le Consulat général de Z._ a considéré, au vu des résultats de l'enquête, que le travailleur s'était rendu coupable d'une faute grave consistant dans l'utilisation indue de la documentation ou information à laquelle il avait eu accès dans l'exercice de ses fonctions, rendant impossible la poursuite des rapports de travail. L'employé n'a pas non plus perçu d'indemnité de la sécurité sociale de l'Etat Z._ après son licenciement. Par courrier du 22 octobre 2013 adressé à son employeur, l'employé a invoqué le caractère abusif du congé et a réclamé le paiement d'une somme de 63'673 fr.25, dont 21'065 fr.40 à titre d'indemnité pour licenciement abusif et 29'257 fr.15 à titre de salaire du 1er février au 17 septembre 2013. B. Par requête de conciliation du 16 décembre 2013, l'employé a ouvert action contre son employeur devant le Tribunal des prud'hommes de Genève. Par demande du 6 juin 2014, modifiée sur requête du Tribunal le 25 juin 2014, il a conclu à la délivrance d'un certificat de travail et au paiement de 37'029,60 euros bruts à titre de salaire du 1er février au 30 novembre 2013, de 20'440,80 euros bruts à titre d'indemnité pour licenciement abusif, de 2'858,60 euros bruts à titre d'indemnité pour jours de vacances non pris en nature et de 16'000 euros nets à titre d'indemnité pour tort moral. Par jugement du 7 août 2015 rendu en procédure simplifiée, le Tribunal des prud'hommes a notamment condamné le défendeur à verser à l'employé demandeur le montant de 9'671,55 euros (ch. 2), le paiement des charges sociales et légales usuelles étant à la charge de l'employeur (ch. 3). Statuant sur l'appel de l'employé par arrêt du 3 mai 2016, la Chambre des prud'hommes de la Cour de justice du canton de Genève a confirmé le jugement attaqué sur ce point. Examinant la chronologie des événements, la cour cantonale a considéré que les faits reprochés au travailleur à l'appui de son licenciement sont ceux qui se sont passés le 2 octobre 2012. Or, malgré un entretien avec le Consul le même jour et un autre quelques jours après, ce n'est que trois mois plus tard, le 31 janvier 2013, qu'une procédure disciplinaire a été engagée contre lui, avec suspension provisoire de ses fonctions et de son droit au salaire dès cette date, qui a conduit à une décision de licenciement lui ayant été notifiée le 17 septembre 2013. La cour cantonale en a déduit que l'on ne saurait ainsi parler de congé immédiat au sens du droit suisse, à savoir de l'art. 337 CO. La cour cantonale a ensuite examiné si le congé devait être qualifié d'abusif au sens de l'art. 336 CO, ce qu'elle a nié au motif que l'employé avait commis une faute professionnelle d'une gravité qui ne saurait être minimisée, ayant déjà été sanctionné pour des faits comparables. Elle a estimé que le harcèlement psychologique dont se plaignait l'employé n'était pas suffisamment établi. Retenant ensuite le comportement déplacé de l'employé le 2 octobre 2012, elle a jugé le congé non abusif et, considérant qu'il s'agissait d'un congé ordinaire, a estimé qu'il devait prendre effet au 30 novembre 2013. Considérant encore que l'employé avait été incapable de travailler du 1er février au 31 décembre 2013, elle a estimé qu'il n'aurait pas pu travailler, même s'il n'en avait pas été dispensé, et a réduit ses prétentions à deux mois de salaire en application de l'art. 324a al. 1 CO. Enfin, elle a rejeté les prétentions de l'employé en réparation du tort moral allégué. C. Contre cet arrêt, l'employé exerce un recours en matière civile au Tribunal fédéral, concluant à la condamnation de l'employeur à lui payer les montants bruts de 30'216 euros à titre de salaire et de 20'440,80 euros à titre d'indemnité pour résiliation immédiate injustifiée ou licenciement abusif, ainsi que de 16'000 euros pour tort moral, soit au total 66'656,80 euros. Subsidiairement, il conclut au renvoi de la cause à la cour cantonale pour nouvelle décision dans le sens des considérants. Le recourant invoque la violation des art. 335c, 337, 324a CO et 9 Cst. en tant que la cour cantonale a qualifié le congé d'ordinaire, de l'art. 337c al. 1 CO et de l'art. 324a CO en relation avec la prétendue influence de son incapacité de travail sur son droit à des dommages-intérêts, des art. 336 al. 1 let. d CO et 9 Cst. en tant qu'il s'est plaint de mobbing et des art. 328 et 49 CO en relation avec sa prétention pour tort moral. L'employeur intimé propose le rejet du recours en tant qu'il est recevable et la confirmation de l'arrêt attaqué. Il soulève la question du droit applicable.