Désolé des écarts de réponse, beaucoup de boulot en ce moment.
La revue RMS n'a jamais réellement été de niveau prépa, elle cible les taupins certes mais plus dans un intérêt culturel que scolaire, même si sa lecture prépare bien aux concours type X/ENS (l'exercice de ce topic pouvant typiquement être donné à un oral d'ENS)
Je pense avoir fini par trouver une solution au problème:
Si -23 est un carré X²+23 a une racine et c'est réglé.
Si -23 n'est pas un carré et -3 non plus alors 23/27 = (-23)*(-3)/9² est un carré donc X^3-X-1=0 a une racine.
Si -23 n'est pas un carré mais que -3 en est un, c'est le cas difficile que je n'ai pas su résoudre sans passer par Galois. On raisonnement pour p premier (puis on étend à p^n et à n entier quelconque). On note S le produit des racines de X^3-X-1 dans un corps de décomposition k de ce polynôme. Alors S²=-23 (discriminant de X^3-X-1). S est de degré 2 sur k. Or k est de degré 3 sur Z/pZ (car il est de degré 3 ou 6 mais ne peut pas être de degré 6 sinon le groupe de Galois de X^3-X-1 ne serait pas cyclique ce qui n'est pas possible dans un corps fini). Il s'ensuit que S est en fait dans Z/pZ, si bien que X²+23 a bien une solution dans ce corps.