Reszty z dzielenia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Reszty z dzielenia

Post autor: Kanodelo »

Wyznacz reszty z dzielenia
\(\displaystyle{ 15^{231}}\) przez 14
\(\displaystyle{ 3^{80}+2^{80}}\) przez 11
\(\displaystyle{ 208^{208}}\) przez 23

Nawet nie wiem jak zacząć... Jakby ktoś pokazał na jednym przykładzie jak to robić byłoby fajnie, i jaki jest wogóle na to sposób, bo w drugim jest suma i nie wiem za bardzo co z nią zrobic.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Reszty z dzielenia

Post autor: norwimaj »

\(\displaystyle{ 15\equiv1\pmod{14}}\)

Zatem
\(\displaystyle{ 15^{231}\equiv1^{231}\pmod{14}}\).

Następne już wiesz jak?
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Reszty z dzielenia

Post autor: Kanodelo »

Ostatnie
\(\displaystyle{ 208 \equiv 1 (mod 23)}\)
Tak powinno byc? Jak tak to chyba dam rade z algorytmu euklidesa

A w drugim nie wiem jak się zabrać niestety
Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 612 razy

Reszty z dzielenia

Post autor: Vax »

2) Z twierdzenia Eulera:

\(\displaystyle{ \begin{cases} 3^{\varphi(11)} \equiv 1 (mod 11) \\ 2^{\varphi(11)} \equiv 1 (mod \ 11)\end{cases} \Leftrightarrow \begin{cases} 3^{10} \equiv 1 (mod \ 11)\\ 2^{10} \equiv 1 (mod \ 11) \end{cases} \Leftrightarrow \begin{cases} 3^{80} \equiv 1 (mod 11)\\ 2^{80} \equiv 1 (mod \ 11) \end{cases} \Rightarrow 3^{80}+2^{80} \equiv 2 (mod \ 11)}\)

3 podobnie.

Pozdrawiam.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Reszty z dzielenia

Post autor: Kanodelo »

A da się to zrobić bez tego twierdzenia, bo zanim ja to ogarne to całe święta chyba zlecą....
Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 612 razy

Reszty z dzielenia

Post autor: Vax »

Tak, można bez żadnego twierdzenia zauważyć:

\(\displaystyle{ 3^{2} \equiv (-2) (mod \ 11) \Rightarrow 3^{80} \equiv 2^{40} (mod \ 11) \Leftrightarrow 3^{80} +2^{80} \equiv 2^{40}+2^{80} (mod \ 11)}\)

Teraz zauważ, że \(\displaystyle{ 2^5 \equiv (-1) (mod \ 11) \Rightarrow 2^{40} \equiv 1 (mod \ 11) \wedge 2^{80} \equiv 1 (mod \ 11) \Rightarrow 2^{40}+2^{80} \equiv 2 (mod \ 11)}\)

Pozdrawiam.
Kanodelo
Użytkownik
Użytkownik
Posty: 1267
Rejestracja: 1 kwie 2011, o 11:37
Płeć: Mężczyzna
Lokalizacja: Malbork
Podziękował: 419 razy
Pomógł: 114 razy

Reszty z dzielenia

Post autor: Kanodelo »

No już coś mi sie rozjaśniło. Przez swięta nad tym porządnie usiąðę i postaram się zrozumieć, ale dzięki za pomoc, bo coś zaczynam ogarniać.
ODPOWIEDZ