Michał Miśkiewicz XI Warsztaty Matematyczne

Teoria liczb I

1 Teoria

1. Definicja. Jeśli n|a − b, to mówimy, że a przystaje do b modulo n (według modułu n) lub piszemy a ≡ b (mod n).

2. Relacja kongruencji jest relacj _{}a równoważności, tj. dla dowolnych a, b, c, n zachodzi:

• a ≡ a (mod n)

• Jeśli a ≡ b (mod n), to b ≡ a (mod n)

• Jeśli a ≡ b (mod n) i b ≡ c (mod n), to a ≡ c (mod n)

3. Kongruencje można dodawać, mnożyć, a czasami nawet dzielić jak normalne równania:

• Jeśli a ≡ c (mod n) i b ≡ d (mod n), to a + b ≡ c + d (mod n)

• Jeśli a ≡ c (mod n) i b ≡ d (mod n), to ab ≡ cd (mod n)

• Jeśli a ⊥ n, to z dokładności _{}a do przystawania istnieje dokładnie jedna liczba b taka, że ab ≡ 1 (mod n).

4. Lemat Euklidesa. Jeśli p jest liczb _{}a pierwsz _{}a i p|ab, to p|a lub p|b. Ogólnie: jeśli a ⊥ n i n|ab, to n|b.

5. Algorytm Euklidesa. Aby obliczyć najwi_{}ekszy wspólny dzielnik dwóch liczb, korzystamy z faktu (a, b) = (b, a − kb) aż do skutku.

6. Twierdzenie Wilsona. Liczba p > 1 jest liczb _{}a pierwsz _{}a wtedy i tylko wtedy gdy (p − 1)! ≡ −1 (mod p).

7. Małe Twierdzenie Fermata. Jeśli p jest liczb _{}a pierwsz _{}a i p ∤ a, to a^{p−1} ≡ 1 (mod p).

2 Zadania

1. Liczby całkowite a, b, c spełniaj _{}a warunek 7|a^{3} + b^{3} + c^{3}. Wykaż, że 7|abc.

2. Wykaż, że dla a ∈ ℤ ułamek \frac{a^{3}+2a}{a^{4}+3a^{2}+1} jest nieskracalny.

3. Wykaż, że dla dowolnej liczby pierwszej p istnieje nieskończenie wiele liczb naturalnych n takich, że p|2^{n} − n.

4. Udowodnij, że istnieje nieskończony zbiór parami wzgl_{}ednie pierwszych liczb postaci 2^{n} − 3, gdzie n > 1.

5. Znajdź wszystkie nieujemne liczby całkowite k i n spełniaj _{}ace równanie k! + 48 = 48(k + 1)^{n}