Более того, если чуть-чуть расширить класс многочленов до экспоненциальных многочленов, разрешив ещё возводить одну переменную в степень другой, то такой многочлен строится совсем "вручную".

Для начала вообще представим себе, что мы имеем право использовать ещё операцию "факториал". Как тогда можно задать простоту числа p?
Во-первых, нужно попросить, чтобы p было не меньше 2. Ну, тут мы уже видели, как это сделать: одно из уравнений системы будет
p=k+2.
А как проверить, что p не делится ни на что, кроме 1 и себя? Цикл использовать нельзя — но можно вместо него воспользоваться факториалом. А именно — давайте посмотрим на (p-1)! ; число p простое тогда и только тогда, когда оно взаимно просто с (p-1)!, а это проверяется алгоритмом Евклида:
a*(p-1)!-b*p=1.
На самом деле, теорема Валлиса утверждает, что простота p равносильна сравнимости (p-1)! с (-1) по модулю p, так что одну переменную можно сэкономить, и написать просто
(p-1)!+1-b*p=0.