Udowadnianie podzielności - matematyka dyskretna Intersleter: Witam. Mam problemy ze zrozumieniem pewnej rzeczy. 13 | 10⁶−1 korzystając z: a≡b (mod m) ⇔ m | (a−b) ∨ a mod m = b mod m 10⁶≡1 (mod 13) 10⁶ (mod 13) 10² (mod 13)= 100 (mod 13)= 9 10⁴ (mod 13)= 100*100 (mod 13)= 81 (mod 13)= 3 10⁶ (mod 13)= 10⁴*10² (mod 13) = 27 (mod 13) = 1 Przykład został tak wykonany na ćwiczeniach bez względnego wytłumaczenia. Byłbym wdzięczny za wyjaśnienie na jakiej zasadzie tutaj zostaje określona prawdziwość 10⁶≡1 (mod 13) lub nieprawdziwość (choć sprawdzałem tą liczbę i jest ona podzielna). Pozdrawiam i z góry dziękuję za pomoc.

Mila: 10²=100=7*13+9⇔ 10²=9(mod13) /² (ponieważ reszta z dzielenia liczby 100 przez 13 jest równa 9) 10⁴=81(mod13)=3(mod13) bo 81=6*13+3 czyli mamy : 10⁴=3(mod13) 10²=9(mod13) ======== mnożymy stronami 10⁶=27(mod13)=1(mod13) dlatego, że 27=2*13+1 Możesz sprawdzić ile wynosi reszta z dzielenia liczby 1000 000 przez 13. 1000 000=76923*13+1

Intersleter: Dziękuje Ci niezmiernie. Odrobinę się rozjaśniło. Teraz tylko mam pytanie. Jeśli 13 | 10⁶−1, to −1 ma tutaj znaczenie? Z tego co widzę z Twoich obliczeń jak i swoich notatek najpierw wyliczamy resztę dla 10⁶ | 13, ale −1 zostaje jakby pominięte. Nie jestem w pełni pewien jaką ta liczba spełnia rolę w udowadnianiu. Co gdyby było tam cokolwiek innego?

Mila: 10⁶=1(mod13) / −1 10⁶−1=0(mod13) a to oznacza, że 13 |(10⁶−1) bo reszta z dzielenia tej liczby przez 13 jest równa 0.

Intersleter: Teraz moja próba na innym przykładzie. 17 | 10⁸+1 10²=100 (mod 17)=5 (mod 17) 10⁴= 15 * 15 (mod 17)=4 (mod 17) 10⁸=16(mod 17) Postępowanie jest podobne jak we wcześniejszym przykładzie Sprawdzenie 100000000=5882352*17+16 Sensownie to wygląda?

Mila: Uważaj na zapisy: 10²≡15 (mod17) 10⁴≡225 (mod17)⇔ 10⁴≡4 (mod17) /² 10⁸≡16 (mod17) /+1 10⁸+1≡ 17(mod17)⇔ 10⁸+1≡0(mod17)⇔17|(10⁸+1)

Intersleter: Wydaje mi się, że już rozumiem. Ogromnie Ci dziękuję za naprowadzenie.

Mila: