но особо легче как-то не становится
Продолжайте идти дальше. Лучше ввести обозначения:

,

. Основная идея: левая часть делится на

, значит,

делится на

, а значит, получаем некоторые ограничения на

(какие?). Учитывая их, можно получить некоторую информацию о

. После этого снова уточняется информация о

. И так далее до тех пор, пока не будет получено противоречие.
На форуме подобных задач разбиралось довольно много, можно попробовать поискать.
Например:
topic44444.html