Пусть k— натуральное число, а m— нечетное число. Докажите, что существует натуральное число n такое, что n^n - m делится на 2^k

Случай тривиален, возьмем . Предположим, что существует натуральное число такое, что , скажем, или имеем и, очевидно, нечетно

Рассмотрим два случая

1. Если делит

утверждение ясно, потому что нам нужно только взять .

2. Если не делит .

Мы можем положить с нечетным числом и по теореме Эйлера, для каждого нечетного числа мы имеем , следовательно, мы имеем

потому что и , и нечетны.

Следовательно, удовлетворяет утверждению