III MEMO - Zadanie 4

Zawody matematyczne:

III MEMO, 2009

Wyznaczyć wszystkie liczby całkowite $k\geq2$ o następującej własności: liczba $n^{n-1}-m^{m-1}$ nie jest podzielna przez $k$ dla żadnej pary $(m,n)$ różnych liczb całkowitych dodatnich, mniejszych lub równych $k$ .

Rozwiązanie

Jeżeli $k\geq4$ i $k$ jest liczbą parzystą, to $(k-1)^{k-2}\equiv1^0\pmod2$ , więc nie znajdziemy rozwiązań wśród liczb parzystych większych niż 2.

Załóżmy, że $k$ jest liczbą nieparzystą. Dla $k\geq5$ przynajmniej $\frac{k+1}2+1$ liczb spośród $1^0,2^1,\dots,k^{k-1}$ jest kwadratami, ponieważ kwadratami są $1^0, 3^2, 5^4, \dots, k^{k-1}$ oraz $4^3$ . Jeśli zatem $k\geq5$ spełnia warunki zadania, to liczba reszt kwadratowych modulo $k$ musi być większa niż $\frac{k+1}2$ . (Resztą kwadratową modulo $k$ nazywamy resztę z dzielenia przez $k$ liczby będącej kwadratem liczby całkowitej.)

Z drugiej strony, $x^2\equiv(k-x)^2\pmod k$ dla $x=1,2,\dots,\frac{k-1}2$ , więc istnieje nie więcej niż $\frac{k-1}2+1=\frac{k+1}2$ różnych reszt kwadratowych modulo $k$ . Zatem żadna liczba nieparzysta większa niż 3 nie spełnia warunków zadania.

Na koniec sprawdzamy, że 1, 2 i 3 są rozwiązaniami zadania.

Odpowiedź: Jedynymi rozwiązaniami są liczby 1, 2 i 3.