Итак, один преподаватель дал мне "тривиальную" (на его взгляд) задачу: доказать, что в группе перестановок Sn найдётся элемент g, порядок которого больше или равен n^k (n в степени k), где k = 4, хотя может равняться 5, 6...и т.д. (как он сказал).

Каким образом этот "зверь" решается?
Я, конечно, прекрасно понимаю, что перестановку длины n надо разложить на циклы длины x1, ..., xk так, чтобы x1+...+xk = n, а далее надо указать такой набор x1, ..., xk, что НОК(x1, ..., xk) >= n^4.
Но как это сделать, это - большой вопрос...

По-моему, достаточно в качестве длин произвольных 8 циклов взять различные простые числа, превосходящие sqrt(n). Уже для n=1000 так точно можно сделать.