Funkcje arytmetyczne w teorii liczb

Program

Warsztaty mają na celu zaprezentowanie pewnych metod teorii liczb. Przedmiotem badań będą głównie funkcje arytmetyczne (duży nacisk położymy na funkcje multiplikatywne), asymptotyki, metody sitowe oraz związki pomiędzy tymi pojęciami.

Wymagania

Zadania kwalifikacyjne

1.

Proszę zapoznać z definicją funkcji μ Möbiusa. Wykazać, że dla naturalnych \(n \geq 2\) zachodzi
\(\sum_{d|n} \mu(d) = 0\). (3 pkt.)

Uwaga odnośnie notacji: suma powyżej przebiega wszystkie dzielniki liczby \(n\). Mamy więc np. dla \(n=12\):
\(\sum_{d|12} \mu(d) = \mu(1) + \mu(2) + \mu(3) + \mu(4) + \mu(6) + \mu(12) = 1-1-1+0+1+0=0\).

2.

Powiemy, że ciągi \(f,g:\mathbb{N}\rightarrow \mathbb{R}\) spełniają zależność \(f(n) = O(g(n))\), jeżeli
istnieją stałe \(n_0, C\) takie, że dla wszystkich \(n > n_0\) zachodzi \(|f(n)| \leq C|g(n)|\)
(jest to pewna szczególna wersja notacji "duże O").

Wykaż, że:
a) \(4n^2 + 5n -12 = O(n^2)\) (1 pkt.)


b) \(\log n =O(n)\) (1 pkt.)


c) \(\log n! = O(n \log n)\) (2 pkt.)

 

3.*

Uzasadnij, że dla każdego naturalnego \(n\) wartość sumy \(\sum^{n}_{k=1} \frac {1}{k}\) różni się od \(\log n\) o co najwyżej 1. (6 pkt.)


Prohint: Warto skorzystać z geometrycznej interpretacji całki oznaczonej.

 

Uwaga: Nie trzeba (oczywiście jeżeli ktoś się tego podejmie, to świetnie) w ramach rozwiązania proponować
formalnego dowodu; wystarczy graficzna interpretacja zjawiska, ewentualnie inne "heurystyczne, acz
dostatecznie przekonujące" wyjaśnienie.

4.

Udowodnij, że układ równań: \(x^2 + y = z^2, y^2 + x = t^2\) nie ma rozwiązań w liczbach naturalnych. (4 pkt.)

5.

Zbadaj zbieżność szeregów:
a) \(\sum^{\infty}_{n=1} \frac{1}{n}\) (1 pkt.)


b) \(\sum^{\infty}_{n=1} \frac{1}{n^{\alpha}}\) dla każdego \(\alpha > 1\) (*) (3 pkt.)


c) \(\sum^{\infty}_{n=1} \frac{ (-1)^{ [n \sqrt2]} }{n} \), gdzie \([n \sqrt2 ]\) oznacza zaokrąglenie w dół danej liczby rzeczywistej do części całkowitej. (***)

 

6.

Wykaż, że funkcje \(\phi\) Eulera oraz \(\mu\) Möbiusa są multiplikatywne (odpowiednie definicje wymieniłem
w opisie warsztatów). (3 pkt.)

7.

Uzasadnij, że odległość (moduł różnicy) między dwiema kolejnymi liczbami pierwszymi może być dowolnie duża. (3 pkt.)

8.*

Znajdź liczbę rozwiązań kongruencji \(x^2 \equiv 1 \mod 20!\) w zbiorze \(\{1,2,...,20!-1\}\). (6 pkt.)

9.

Dla "dużego O" zdefiniowanego w zadaniu 2. oraz ciągów \(f,g,h : \mathbb{N} \rightarrow \mathbb{R}\)
wyprowadź zależności:
a) Jeżeli\(f = O(g)\) i \(g = O(h)\), to\(f = O(h)\). (1 pkt.)


b) Jeżeli \(f,g = O(h)\), to \(f+g, f-g = O(h)\). (1 pkt.)


c) Jeżeli \(f = O(g)\), to \(fh = O(g|h|)\). (1 pkt.)

 

Miłej zabawy.

Wyniki

Przepraszam za duże opóźnienie; wszystkie wyniki zostały już wpisane. Jeżeli ktoś uważa, że został źle oceniony (np. jeżeli ktoś dostał 0 punktów na 6, ponieważ odpowiednie rozwiązania nie pojawiły się w mojej skrzynce mailowej), to proszę o pilny kontakt.