Условия про НОД и НОК

Как вообще можно доказать, что число не является квадратом? Если число не квадрат, то в его разложении есть простое число в нечетной степени. Но мы поступим тут немного наглее, докажем, что существует , такое что оставшееся число делится на , но не делится на . Посмотрим на число .

1) Если , то НОД.

2) Если . Тогда дает остаток 1 при делении на ,
поэтому НОД.

3) Если , то НОД.

Мы нашли инвариант! Четность количества чисел, которые делятся на , не меняется. Изначально их было 33, значит, последнее число делится на 3. Покажем, что оно не делится на 9. То есть были в конце числа мы их заменили на НОД, при этом этом так как последнее число делится на 3, то это могло быть только во 2-ом случае (только в этом случае НОД делится на 3). Но давайте заметим, что точно не делится на 9 в этом случае, а значит, и НОД. Таким образом, последнее число не квадрат.