Честно говоря, не особенно понятно, от чего можно отталкиваться; для этой задачи найдены решения компьютерным перебором для довольно больших n. если у кого-нибудь есть идеи, с чего можно разбирать эту задачу, просьба отписаться. задача взята с листа В.В. Трушкова "Задачи на 12 баллов".
ссылка на источник материалов по перебору:
http://www.immortaltheory.com/NumberTheory/2nmodn.htm