I tried this:
PythagoreanTrip[p_] /; z>0 := With[
{result = Reduce[((Mod[x^2,p]+Mod[y^2,p]==Mod[z^2,p] && x>y) || Mod[x^2,p]+Mod[z^2,p]==Mod[y^2,p]) &&
Element[{x,y},Integers] && x>0 && y>0]},
If [result===False, {},
Sort[Map[Sort, {x,y,z} /. {ToRules[result]}]]]]
This does not work...