Kongruencja Patryk: 1. Wykaż, że reszta z dzielenia liczby np. trzycyfrowej przez 3, a także przez 9 jest taka sama jak reszta z dzielenia przez 3 (9) sumy jej cyfr. 2.Udowodnij cechę podzielności przez 11. 3. Wyznacz pary liczb m i n dla których zachodzi równość: 1!+2!+3!+4!+5!+...+n!=m² 4.Dla jakich n liczba (5ⁿ−2ⁿ) jest podzielna przez 9. 5.Uzasadnij, że dla każdej liczby naturalnej n, liczba 2ⁿ+1 nie jest podzielna przez 7. Uprzedzam że wszystkie te zadania trzeba zrobić kongruencją(modulo) inne sposoby nie są mi potrzebne. Z góry dzięki za pomoc.

Vax: 1) Każdą liczbę naturalną można zapisać jako n = ∑_i=0^k 10ⁱa_i, wystarczy zauważyć, że: n = ∑_i=0^k 10ⁱa_i = ∑_i=0^k a_i (mod 3) tak samo mod 9. 2) Jak wyżej, niech n = ∑_i=0^k 10ⁱa_i = ∑_i=0^k(−1)ⁱa_i (mod 11) Więc liczba dzieli się przez 11, jeżeli naprzemiennie dodając i odejmując cyfry tej liczby (zaczynając od ostatniej) dostaniemy liczbę podzielną przez 11, np 433026 dzieli się przez 11, bo 6−2+0−3+3−4 = 0 co się dzieli przez 11. 3) Jeżeli n ≥ 6 to 1!+2!+3!+..+n! = m² ⇔ 1!+2!+3!+4!+5!+5(...) = m² ⇔ 153+5(...) = m², skąd dostajemy sprzeczność, bo 3 jest nieresztą kwadratową mod 5, więc n ≤ 5, bezpośrednio sprawdzając widzimy, że tezę spełniają pary (n,m) = (1,0) v (1,1) v (3,3) 4) 5ⁿ = 2ⁿ (mod 9), rozpatrzmy 3 przypadki: 1*) n=3k, wtedy 5^3k = 2^3k (mod 9) ⇔ 125^k = 8^k ⇔(−1)^k = (−1)^k (mod 9) czyli n=3k gdzie k jest dowolną liczbą naturalną działa. 2*) n=3k+1 wtedy 5^3k+1 = 2^3k+1 (mod 9) ⇔ 5*125^k = 2*8^k (mod 9) ⇔ 5(−1)^k = 2(−1)^k (mod 9) ⇔ 3(−1)^k = 0 (mod 9)/:3 ⇔ (−1)^k = 0 (mod 3) skąd sprzeczność. 3*) n=3k+2 wtedy 5^3k+2 = 2^3k+2 (mod 9) ⇔ 25*125^k = 4*8^k (mod 9) ⇔ 7(−1)^k = 4(−1)^k (mod 9) ⇔ 3(−1)^k = 0 (mod 9)/:3 ⇔ (−1)^k = 0 (mod 3) Więc teza zachodzi dla wszystkich n=3k, gdzie k jest dowolną liczbą naturalną. 5) Nie wprost, niech 2ⁿ = −1 (mod 7)/² ⇒ 2²ⁿ = 1 (mod 7), oraz z twierdzenia Eulera 2⁶ = 1 (mod 7). Niech teraz t = ord₇ 2, mamy więc: t nie dzieli n, t dzieli 2n, więc t = 2n, zachodzi więc: 2n | 6 ⇔ n | 3 czyli n=1 v n=3, w obu przypadkach teza nie zachodzi więc nie istnieją takie naturalne n, cnd.

Patryk: Byłbym wdzięczny jakbyś mógł zapisać 1) i 2) bez tego dziwnego znaczku. I wyjaśnić dokładnie 3) Ale i tak wielkie dzięki

Vax: ∑_i=0^k10ⁱa_i = a₀ + 10a₁ + 100a₂ + ... + 10^ka_k W 3 mamy m² = 153 + 5k, gdzie k jest pewną liczbą naturalną (bo 6!,7! itd..) dzielą się przez 5, więc badając dane równanie modulo 5 widzimy, że musi być m² = 153 = 3 (mod 5), ale 3 jest nieresztą kwadratową modulo 5, czyli nie istnieje takie x, że x² = 3 (mod 5).

Patryk: A skąd wiesz że 3 jest nieresztą kwadratową dla mod 5? i skąd 153 i czy k=6!+7!+8+...+n!?

Vax: Można sprawdzać po prostu wszystkie przypadki: 0² = 0 (mod 5) 1² = 1 (mod 5) 2² = 4 (mod 5) 3² = 9 = 4 (mod 5) 4² = 16 = 1 (mod 5) Więc resztami kwadratowymi mod 5 są jedynie 0 v 1 v 4, a na większych liczbach najczęściej korzysta się z symbolu Legendrea:

3 5		5 3		2 3
	=		=		= (−1)32−18 = −1 czyli 3 jest nieresztą kwadratową mod 5.

153 = 1!+2!+3!+4!+5! Tak, k = 6!+7!+..

Patryk: A możesz wyjaśnić twierdzenie Eulera i czy jest ono konieczne w rozwiązaniu zadania 5).?

Vax: Możesz bez tego twierdzenia zauważyć, że 2⁶ = 1 mod 7

Patryk: A czy możesz przetłumaczyć taki napis: t = ord7 2,

Patryk: kolejne pytania możesz objaśnij ten napis ∑i=0k 10ia c to jest a,i itd

Vax: t = ord₇ 2 czyli t jest najmniejszą liczbą naturalną taką, że 2^t = 1 (mod 7) No to napisałem wyżej, a_i to pewne liczby naturalne, każdą liczbę da się w ten sposób zapisać, np: 456 = 100*4 + 10*5 + 6 itd..

Patryk: A co znaczy ∑i=0^k w indeksie dolnym w zad 1) i 2)

Vax: Że sumujemy od i=0 do i=k

Patryk: A umiesz rozwiązać coś takiego?:Wyznacz dwie ostatnie cyfry liczby 2⁽999) z modulo oczywiście

Patryk: A umiesz rozwiązać coś takiego?:Wyznacz dwie ostatnie cyfry liczby 2⁹⁹⁹ z modulo oczywiście

Vax: Mamy wyznaczyć x = 2⁹⁹⁹ (mod 100) No tutaj już lepiej skorzystać z twierdzenia Eulera. Mówi ono nam o tym, że jak mamy dwie liczby a,n takie, że nwd(a,n) = 1, to a^phi(n) = 1 (mod n), gdzie phi(n) to funkcja Eulera: http://pl.wikipedia.org/wiki/Funkcja_%CF%86 Mamy wyznaczyć x = 2⁹⁹⁹ (mod 100), z Chińskiego Twierdzenia o Resztach wynika, że jest ona równoważna: {x = 2⁹⁹⁹ = 0 (mod 4) {x = 2⁹⁹⁹ (mod 25) Zauważ, że phi(25) = phi(5²) = 5²−5 = 20, więc: 2²⁰ = 1 (mod 25)/⁵⁰ ⇒ 2¹⁰⁰⁰ = 1 (mod 25) 2⁹⁹⁹ = x (mod 25) /*2 ⇔ 2¹⁰⁰⁰ = 2x (mod 25) czyli: 2x = 1 (mod 25)/*13 x = 13 (mod 25) mamy więc: {x = 0 (mod 4) {x = 13 (mod 25) z 1 kongruencji x = 4k, wstawiamy do 2: 4k = 13 (mod 25) /*19 k = 22 (mod 25) k = 25n+22 Więc x = 4k = 4(25n+22) = 100n+88, czyli 2 ostatnie cyfry danej liczby to 88

Patryk: Ok wielkie dzięki

Vax: Spoko, jakbyś miał jeszcze jakieś zadania pisz

pawelasz: Uzasadnij że przy dzieleniu przez 4 liczba utworzona z dwóch ostatnich cyfr dają taką samą resztę. (metoda modulo)

Vax: Dla k ≥ 2 mamy 10^k = 0 mod 4, więc ∑_i=0^k 10ⁱa_i = 10a₁+a₀ (mod 4) skąd teza.

pawelasz: Mógłbyś to opisać szczegółowo ?