teoria liczb damian: Vax miałbyś może dzisiaj czas na wytłumaczenie paru zadań z teorii liczb ? 1. Odszukaj x liczby 29, gdzie 29^x musi kończyć się "00001" 2. Wiedząc, że jest siedem liczb należących do zbioru liczb całkowitych, wybieramy z nich dwie i musimy udowodnić, że różnica kwadratów tych dwóch liczb jest podzielna przez dziesięć. 3. Mamy danych siedemnaście liczb z których musimy wybrać pięć liczb, uzasadnij, że zawsze z sumy tych pięciu liczb otrzymamy liczbę podzielną przez pięć. 4. Wyznacz liczbę którą otrzymamy przy działaniu 3⁴⁷ : 23. Dla zadania pierwszego zastanawiałem się nad twierdzeniem Eulera, lecz nie wiem jak to rozpisać, podobnie z zadaniem czwartym − tam będzie chyba MTF. Mógłbyś pomóc mi przy tych zadaniach ?

olo: Teza z zadania drugiego nie musi zachodzić

olo: w 4 wykonaj mamy resztę, zatem co oznacza polecenie "wyznacz liczbę?"

olo: Zadanie 3 2+3+4+5+7 − weźmy takie liczby Przecież ich suma nie dzieli się przez 5. Treści zadań są do bani

Panko: (a,p)=1, p−pierwsza ⇒ a^p−1≡ 1 (mod p) (3,23)=1 ,23 −−pierwsza ⇒3²²≡1 (mod 23) ( 3²²)²≡(1)² (mod 23) czyli 3⁴⁴≡1 (mod 23) 3⁴⁴*3³≡ 3³ ( mod 23) i 3³≡ 4 (mod 23) ⇒ 3⁴⁷≡ 4 (mod 23 ) czyli 3⁴⁷= ( 3⁴⁷−4)/23 +4

Panko: Szukasz takiego x : 29^x ≡ 1 ( mod 10⁵ )

Panko:

	347−4
Errata : powinno być : 347= 23 *		+4
	23

damian: Jak zrobić zadanie z Eulrem, bo nie wiem czy, to jest na pewno poprawne oraz co z zadaniami 2 i 3 ?

Panko: Zadanie 20 Reszt z dzielenia liczby całkowitej przez 10 jest r∊{ 0,1,2,...,9} czyli 10 Jeżeli dzielę kwadrat liczby całkowitej prze 10 to reszt jest Kwadrat reszty r²∊{0,1,4,5,6, 9} . Jest ich 6 Jeżeli wezmę dowolne siedem liczb całkowitych to co najmniej dwie w kwadracie dają tą samą resztę z dzielenia przez 10 ( bo reszt jest 6−ść) , stąd ich różnica dzieli sie przez 10

damian: dziękuję bardzo, teraz widzę, że było to proste zadanie, natomiast w zadaniu 3 jest błąd, powinno być, że możemy zawsze dobrać tak pięć tych liczb, aby suma była podzielna przez pięć

Vax: Zostało chyba tylko 1 i 3, więc: 1) Chcemy znaleźć takie x, że 29^x = 1 (mod 10⁵), a tu z tw Eulera wystarczy wziąć x = φ(10⁵) 3) Jeżeli istnieje 5 liczb dających tą samą resztę z dzielenia przez 5 to bierzemy je. Załóżmy, że takie nie istnieją i zauważmy, że wówczas musi istnieć piątka liczb, z których każda daje różną resztę z dzielenia przez 5, istotnie, jakby istniała pewna reszta, której nie dawałaby żadna liczba, to liczb mogłoby być maksymalnie 4*4 = 16 < 17 sprzeczność (bo wszystkich możliwych reszt jest 5, oraz liczb dających tę samą resztę jest maksymalnie 4), zadanie kończy trywialna obserwacja: 5 | 0+1+2+3+4.

damian: Dziękuję bardzo za pomoc Panko i Vaxowi, moglibyście mi jeszcze powiedzieć, czy dobrze to obliczyłem: Φ(10⁵) = Φ(2⁴)*Φ(5⁴) = 2³ * 1 * 5³ * 4 = 4000. I dlaczego mogliśmy obliczyć to tak z twierdzenie Eulera?

Vax: 10⁵ = 2⁵ * 5⁵, więc φ(10⁵) = φ(2⁵)φ(5⁵) = 2⁴ * 5⁴*4 = 40000 Liczymy to, gdyż z tw. Eulera wiemy, że dla dowolnych (a,n) = 1 zachodzi a^φ(n) = 1 (mod n), po prostu zauważamy, że to nam da tezę zadania

damian: Jeszcze odnośnie tego Eulera, 29^x ≡ 1 mod (10⁵) i musi (29, 10⁵) = 1 ? ale 10⁵ ma chyba inne dzielniki, więc jak to jest dokładnie? Mogłem coś pominąć Znalazłem jeszcze jedno zadanie z którym mam małą zagwostkę: Stosując http://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84 znajdź rozwiązanie x₁ + x₂ + x₃ = 16, gdzie (x₁, x₂, x₃) są liczbami całkowitymi nieujemnymi oraz każda z podanych liczb może być maksymalnie siódemką

damian:

zombi: Co do tego pytania odnośnie (29, 10⁵) = 1 oczywiście, że jest spełnione, bo 29 jest liczbą pierwszą a 10⁵ nie jest iloczynem 29, więc nasze NWD jest równe 1. Jeśli o to pytałeś. Jeśli (a,n) = 1, to a^φ(n) ≡ 1 (mod n) A tutaj rzeczywiście (29, 10⁵) = 1, zatem tw. Eulera pyka.

damian: a jak zrobić to zadanie, które napisałem o 12:01 ?

damian:

damian: pomożesz?