276062003

12 Podstawy teorii liczb

Przykład zastosowania TCR: Rozwiązać układ kongruencji:

{x = 2 (mod 3) x = 3 (mod 5) x = 1 (mod 7)

Podać rozwiązanie ogólne oraz znaleźć najmniejszą liczbę naturalną będącą rozwiązaniem szczególnym.

Co zrobić, gdy moduły kongruencji nie są parami względnie pierwsze ? Oczywiście zawsze można sprowadzić układ do sytuacji, gdy moduły kongruencji są potęgami liczb pierwszych, a następnie "pozbyć” się zbędnych potęg, (o ile oczywiście układ otrzymany nie okazuje się sprzeczny). Można też stosować metody, które pozwalają na rozwiązywanie takich układów bez ich wcześniejszego sprowadzania do sytuacji parami względnie pierwszych modułów kongruencji.

Przykład 1.5.7.

{x = 7 (mod 8) x = 9 (mod 10)

X = 14 (mod 15)

Układ ten jest równoważny układowi

{x = 7 (mod 8) x = 4 (mod 5) x = 2 (mod 3)

Możemy też startowy układ, (bez jego równoważnego przekształcania) rozwiązać następująco: x = 7+8k, czyli 7+8k = 9 (mod 10) skąd 8k = 2 (mod 10) co daje 4A; = 1 (mod 5). Mnożymy obie strony kongruencji przez 4 i mamy k = 4 (mod 5), skąd k = 4 + 5/ i x = 39 + 40/. Podstawiamy do ostatniego równania i dostajemy 39 + 40/ = 14 (mod 15), skąd 10/ = 5 (mod 5) co jest równoważne 2/ = 1 (mod 3). Mnożąc przez 2 mamy wreszcie / = 2 + 3s i ostatecznie x = 119 + 120s, s 6 Z.

Oczywiście w przypadku tego akurat układu łatwo zgadnąć jedno z rozwiązań, ale nie zawsze jest to od razu możliwe:)

1.6 Funkcja Eulera, jej własności i zastosowania

Zaczniemy od zapoznania się z najważniejszą dla naszych dalszych zastosowań, (w szczególności w teorii grup oraz w wykorzystaniu dalej m.in. w teorii ciał, teorii Galois) funkcją arytmetyczną ⁹. Funkcję tę można definiować na różne sposoby, ale postawimy tu standardową definicję teorioliczbową.

Definicja 1.6.1 (funkcja Eulera). Niech ip : N —>N będzie funkcją przypisującą liczbie n liczbę względnie pierwszych z nią liczb całkowitych k G [0, n). Funkcję ip nazywamy funkcją Eulera.

(⁹)funkcja o dziedzinie N i wartościach zespolonych