Funkcja Eulera

Tym razem o kilku ciekawych własnościach funkcji Eulera.

Niech $φ (n)$ (gdzie $n$ jest dodatnią liczbą naturalną) oznacza funkcję Eulera, czyli liczbę liczb naturalnych nie większych od $n$ i względnie pierwszych z $|n.$ Na przykład

φ(1) = 1,φ(2) = 1,φ (3) = 2,φ(4) = 2,φ (5) = 4,φ (6) = 2.

Przypomnijmy dwie powszechnie znane własności funkcji Eulera:

Twierdzenie 1. Jeśli $p ,p ,...,p 1 2 k$ są różnymi liczbami pierwszymi i $m1,m2,...,mk > 0$ są liczbami naturalnymi, to

m1 m2 mk m1 m2 mk -1 -1- -1- φ(p1 ⋅p2 ⋅...⋅p k ) = p1 ⋅p2 ⋅...⋅pk ⋅(1− p1)⋅(1− p2 )⋅...⋅(1 − pk) ⋅

Twierdzenie (Eulera). Jeśli $a,n > 0$ są liczbami naturalnymi oraz $|nwd(a, n) = 1,$ to $|n aφ n −1.$

Zauważmy, że jeśli $|n = p$ jest liczbą pierwszą i $|nwd(a, p) = 1$ (czyli $|p a$ ), to wobec $φ (p) = p − 1$ mamy podzielność $p−1 p a − 1,$ czyli tezę w małym twierdzeniu Fermata.

Nietrudno jest udowodnić, że dla $n ⩾ 3$ liczba $φ(n)$ jest parzysta (Czytelniku, spróbuj sam!). Okazuje się, że nie każda liczba naturalna parzysta jest wartością funkcji Eulera $φ .$ Andrzej Schinzel udowodnił, że dla żadnego naturalnego $k ⩾ 1$ liczba $2 ⋅7k$ nie jest wartością funkcji $|φ.$

Jeśli $p$ jest liczbą pierwszą, to $|φ(p) p −1$ (bo $|φ(p) = p− 1$ ). W 1932 roku Derrick Henry Lehmer spytał, czy istnieje taka liczba złożona $n,$ że $|φ(n) n −1.$ Pytanie to do dzisiaj pozostaje bez odpowiedzi. Można łatwo uzasadnić, że jeśli $|n = pm11 ⋅pm22 ⋅...⋅pmk , k$ to podzielność $|φ(n) n −1$ jest równoważna podzielności

(p − 1)⋅(p − 1) ⋅...⋅(p − 1) p p ...p − 1. 1 2 k 1 2 k

(1)

Oczywiście, gdy $k = 1,$ to powyższa podzielność zachodzi (wtedy $|n = p1$ jest liczbą pierwszą). Dla $|k⩾ 2$ nie znaleziono liczb pierwszych $|p,p ,...,p 1 2 k$ spełniających podzielność (1) i jest wątpliwe, czy takie liczby istnieją. W 1980 roku Geoffrey L. Cohen i Peter Hagis dowiedli, że jeśli $|n$ jest liczbą złożoną i zachodzi podzielność (1), to $|k⩾ 14$ i $n > 1020.$

Zajmijmy się teraz równaniem

φ (x) = m,

(2)

gdzie $m > 0$ jest daną liczbą naturalną. Można udowodnić, że powyższe równanie

(a): dla $|m = 2 ⋅7k$ ma 0 rozwiązań,
(b): dla $|m = 2 ⋅36k+1$ ma 2 rozwiązania,
(c): dla $|m = 12⋅72k+1$ ma 3 rozwiązania.

Zachodzi twierdzenie ogólne (Paul Erdős, Kevin Ford): dla każdej liczby naturalnej $s ⩾ 2$ istnieje taka liczba naturalna $|m,$ że równanie (2) ma dokładnie $s$ rozwiązań, co więcej, dla danego $s⩾ 2$ takich liczb jest nieskończenie wiele.

W 1922 roku Robert Daniel Carmichael sformułował hipotezę: nie istnieje takie $|m,$ że równanie (2) ma dokładnie jedno rozwiązanie. Hipotezę można również wyrazić następująco: dla każdej liczby naturalnej $n ⩾1$ istnieje taka liczba naturalna $x ≠ n,$ że $|φ(x) = φ(n).$

W 1994 roku Aaron Schlafly i Stan Wagon, przeprowadzając obszerne obliczenia numeryczne, wykazali, że jeśli równanie $φ(x) = φ(n)$ ma dokładnie jedno rozwiązanie (tj. $|x = n$ ), to $7 n > 1010 ,$ tzn. najmniejszy kontrprzykład (jeśli istnieje) dla hipotezy Carmichaela ma ponad 10 milionów cyfr.

Przejdźmy do równania

x −φ (x) = k,

(3)

gdzie $k ⩾1$ jest daną liczbą naturalną. Dla $|k = 1$ mamy nieskończenie wiele rozwiązań i są nimi wszystkie liczby pierwsze (dlaczego?). Dla $|k = 3$ i $k = 5$ mamy rozwiązania odpowiednio $|x = 9$ i $|x = 25,$ co Czytelnik zechce sprawdzić. Niech teraz $|k⩾ 7$ będzie dowolnie ustaloną liczbą nieparzystą. Na mocy wzmocnionej hipotezy Goldbacha (każda liczba większa od 6 jest sumą dwóch różnych liczb pierwszych) istnieją takie różne liczby pierwsze $p$ i $q,$ że $k + 1 = p +q.$ Przyjmijmy $|x = pq.$ Wtedy $x$ spełnia równanie (3), gdyż

x− φ(x) = pq − φ(pq) = pq − (p− 1)(q −1) = p + q −1 = k.

To pokazuje hipotetyczną rozwiązalność równania (3) dla każdego nieparzystego $|k⩾ 1.$

Okazuje się, że równanie (3) może nie mieć rozwiązania dla $|k > 0$ parzystych. Najmniejszymi takimi $k$ są: 10, 26, 34, 50, 52, 58, 86, 100. W 1995 roku Jerzy Browkin i Andrzej Schinzel udowodnili następujący

Fakt. Równanie

x− φ(x) = 2n ⋅509203

nie ma rozwiązań dla każdego naturalnego $| n⩾ 1.$

Na koniec kilka zadań dla Czytelnika.