Что-то ничего в голову не приходит. Более того, в самом равенстве

нет ничего криминального — вполне можно найти такую парочку и при простом

. Вот из первого равенства можно сделать вывод о непростоте (малая теорема Ферма), а поскольку, кажется навскидку, первый показатель степени делится на второй, можно привести эти равенства к одному показателю степени и стоит проверить на общие делители разности оснований и того страшного числа; впрочем, и это никаких гарантий обнаружения делителя не даёт.