zasada bartek: Vax mógłbyć mi pomóc, jeżeli miałbyś czas? Mając podany zbiór liczb {1,2,...,k} wybieramy (k + 1) liczb, wykaż, że jest taka para liczb, która będzie różniła się o wielokrotność k. (zastosuj metodę szufladkową)

Vax: Ten zbiór nie powinien przypadkiem wyglądać tak: {1,2,3,...,2k} ?

bartek: nie, ale początek powinien wyglądać tak: "Mamy dowolne (k + 1) liczb, wykaż, że jest taka para liczb, która będzie różniła się o wielokrotność k. (zastosuj metodę szufladkową)" przepraszam za błąd

Vax: No to popatrzmy na te liczby modulo k, wszystkich możliwych wartości reszt jest k (są to 0,1,2,...,k−1)) a danych liczb mamy k+1, skąd na mocy zasady szufladkowej Dirichleta pewne dwie reszty się powtórzą ⇔ różnica tych liczb będzie podzielna przez k ⇔ różnią się o wielokrotność k

bartek: rzeczywiście, kluczowe było rozpatrzenie modulo a to zadanie, które pomyliło mi się początkiem treści: "Mając podany zbiór liczb {1,2, ..., 2k} wybieramy (k + 1) różnych liczb, uzasadnij, że są takie 2 liczby, gdzie jedna jest wielokrotnością drugiej."

Vax: To jest szczególny przypadek tego zadania co przed chwilą wykazałem

bartek: Myślałem, aby utworzyć k − szufladek i coś na podstawie tego zrobić, czy tutaj trzeba też arytmetykę modularną ?

Vax: No można z samej ZSD, popatrzmy na takie szufladki: {1,k+1} {2,k+2} .. {k,2k} mamy k szufladek i k+1 liczb, więc w pewnej szufladce są 2 liczby − one różnią się o k, cnd.

bartek: a jakbym chciał tak jak ty, modulo − też się da ? dziękuję bardzo za pomoc

bartek: mógłbyś mi jeszcze pomóc przy takim zadaniu? "Odszukaj (wypisz) wszystkie m, gdzie φ(m) = 160"

Panko: Jeżeli φ(n) to funkcja Eulera to φ(160)= φ(2⁵*5)=φ(2⁵)*φ(5)= ( 2⁵−2⁴) * (5−1)= 16*4=64 uwagi: jeżeli (m,n)=1 ⇒φ(m*n)=φ(m)*φ(n) jeżeli p −−pierwsza to φ(p^α)=p^α−p^α−1 w szczególności φ(p)=p−1

Panko: No tak pomyliłem wartość z argumentem !

bartek: chyba nie o to chodziło w zadaniu

Vax: Na początku zanotujmy, że 160 = 2⁵ * 5 i zauważmy parę faktów: 1) m nie może się dzielić przez kwadrat żadnej liczby pierwszej różnej od 2 i 5 Dowód: Z multiplikatywności funkcji φ oraz wzoru φ(p^k) = p^k−1(p−1) wynikałoby, że φ(m) dzieliłoby się przez liczbę pierwszą różną od 2,5 sprzeczność. 2) Wystarczy sprawdzać m nieparzyste, albo podzielne przez 4. Dowód: Wynika to bezpośrednio z tego, że wartość funkcji φ dla nieparzystego argumentu k wynosi tyle samo co dla argumentu 2k, gdyż φ(2k) = φ(2)φ(k) = φ(k). 3) Wszystkie liczby pierwsze różne od 2 i 5, postaci 2^α*5^β+1 gdzie α,β ≥ 0, α ≤ 5 oraz β ≤ 1 to 3,11,17,41 Przejdźmy do zadania. Załóżmy na początku, że m dzieli się przez 2 i 5, tj m = 2^x*5^y * p₁*p₂*..*p_k. (y ≥ 1 oraz x ≥ 2 (z 2 faktu), oraz każda z p_i jest jedną z wypisanych w 3 fakcie). Czyli φ(m) = 2^x+15^y−1(p₁−1)(p₂−1)...(p_k−1) φ(m) = 2⁵*5, więc ma zachodzić 2^x−2*5^y−1(p₁−1)(p₂−1)..*(p_k−1) = 2²*5 Rozpatrzmy przypadek, gdy y ≥ 2, wtedy musi być y=2, czyli 2^x−2(p₁−1)..(p_k−1) = 2², jeżeli x=4 to (p₁−1)..(p_k−1) = 1, tj k=0 czyli m = 2⁴ * 5². Jeżeli x=3 to (p₁−1)..(p_k−1) = 2, skąd może być jedynie p₁=3, skąd m = 2³*3*5² Rozpatrzmy teraz przypadek gdy y=1, czyli 2^x−1(p₁−1)..(p_k−1) = 2³*5 Lecimy po kolei, jeżeli x=4 to (p₁−1)..(p_k−1) = 5, skąd z faktu 3 łatwo dostajemy, że nie ma takich p_i. Jeżeli x=3 to otrzymujemy (p₁−1)..(p_k−1) = 2*5, skąd może być jedynie p₁=11, co nam daje m = 2³*5*11. Jeżeli x=2 to dostajemy (p₁−1)..(p_k−1) = 2²*5, skąd dostajemy p₁=3 , p₂ = 11 czyli m = 2²*3*5*11 Załóżmy teraz, że m dzieli się przez 2 (czyli z faktu 2 też przez 4) i nie dzieli przez 5, tj: m = 2^xp₁p₂...p_k, więc 2⁵*5 = 2^x−1(p₁−1)..(p_k−1)/:2 ⇔ 2^x−2(p₁−1)...(p_k−1) = 2⁴*5 Jeżeli x=2 to (p₁−1)...(p_k−1) = 2⁴*5 skąd p₁=3 , p₂=41, czyli m = 2²*3*41. Jeżeli x=3 to (p₁−1)..(p_k−1) = 2³*5, skąd p₁ = 41 więc m = 2³*41. Jeżeli x=4 to (p₁−1)..(p_k−1) = 2²*5, czyli p₁=3 , p₂ = 11 stąd m = 2⁴*3*11. Jeżeli x=5 to (p₁−1)...(p_k−1) = 2*5 skąd p₁=11 co nam daje m = 2⁵*11. Dla x=6 nie dostajemy rozwiązań. Załóżmy, że m dzieli się przez 5 i nie dzieli przez 2, tj m = 5^xp₁p₂...p_k, więc: 4*5^x−1(p₁−1)..(p_k−1) = 2⁵*5 ⇔ 5^x−1(p₁−1)..(p_k−1) = 2³*5 Jeżeli x=2 to (p₁−1)..(p_k−1) = 2³, skąd brak rozwiązań Jeżeli x=1 to (p₁−1)..(p_k−1) = 2³*5, skąd p₁=41 i m = 5*41 Rozważmy przypadek, gdy m nie dzieli się ani przez 2 ani przez 5, tj m = p₁p₂...p_k, czyli (p₁−1)(p₂−1)..(p_k−1) = 2⁵*5, skąd znowu z faktu 3 dostajemy, że może być jedynie p₁=11 , p₂=17, czyli m = 11*17 Więc ostatecznie wszystkie m spełniające tezę (pamiętając o tym, że dla m nieparzystego 2m też działa) to: {187,205,328,352,374,400,410,440,492,528,600,660}