Dowód lematu

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
alchem
Użytkownik
Użytkownik
Posty: 251
Rejestracja: 10 cze 2014, o 19:10
Płeć: Mężczyzna
Lokalizacja: Wrocław

Dowód lematu

Post autor: alchem » 9 wrz 2019, o 22:08

Weźmy \(A= \{a_1,a_2,...,\}\) jako zbiór dodatnich liczb całkowitych.
Zbiór ten posiada określone własności:
a: \(nwd\{a_1,a_2,...\}=1 \)
b: jest zamknięty na dodawanie

Wtedy istnieje \(N < \infty\), takie, że \(n \in A \) dla każdego \(n \geq N\).
Potrzebuję tego dowodu aby móc udowodnić fakt z łańcuchów Markowa, jednak nie wiem jak się za to za bardzo zabrać, trochę nie moja bajka.

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 76
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu

Re: Dowód lematu

Post autor: Gosda » 10 wrz 2019, o 06:16

To się nazywa problem monet Frobeniusa: mając nominały ze zbioru \(A\), jaka jest największa kwota, której nie da się wypłacić? Na przykład dla \(A = \{3, 4, 3+3. 3+4, 4+4, 3+3+3, \ldots\}\) odpowiedź brzmi \(5\). Twoje założenie, że zbiór jest zamknięty na dodawanie oznacza po prostu, że każdego nominału można brać dowolną ilość.

Natomiast fakt, który próbujesz udowodnić, to wg wiki kombinatoryczne twierdzenie Schura... (gdybyś chciał podrążyć temat). Explicite rozwiązanie znalazłem w https://pdfs.semanticscholar.org/9ea2/8 ... fc4ec6.pdf: \(N = (a_1 - 1)(a_k - 1)\), jeśli ciąg \((a_n)\) jest rosnący i \(\operatorname{NWD} (a_1, \ldots, a_k) = 1\).

Awatar użytkownika
alchem
Użytkownik
Użytkownik
Posty: 251
Rejestracja: 10 cze 2014, o 19:10
Płeć: Mężczyzna
Lokalizacja: Wrocław

Re: Dowód lematu

Post autor: alchem » 10 wrz 2019, o 19:02

Wielkie dzięki za naprowadzenie na temat.

ODPOWIEDZ