Reszta z dzielenia liczb / male tw Fermata i tw Eulera

[zxc18]

mam taki problem, nie wiem jak policzyc takie cos :

Oblicz reszte z dzielenia liczby a przez b:
a) a = \(\displaystyle{ 1946^{1972}}\) b = \(\displaystyle{ 26}\)

b) a = \(\displaystyle{ 1946^{1972} + 1972^{1946}}\), b = \(\displaystyle{ 26}\)

c) a = \(\displaystyle{ 5555^{190}}\) b =\(\displaystyle{ 191}\)

Bede bardzo wdzieczny za pomoc, dziekuje i pozdrawiam[/latex]

EDIT : jeszcze raz prosze o pomoc, to sa wazne zadania a nikt ze znajomych nie potrafi mi pomoc :/

[Majorkan]

Rozwiązanie punktu c) to bezpośredni wniosek z tw. Eulera.
Ponieważ 191 jest liczbą pierwszą i 191 nie dzieli 5555, to 191 i 5555 są względnie pierwsze.
Zatem \(\displaystyle{ 5555^{\varphi(191)} \equiv 1 (mod 191)}\)
gdzie \(\displaystyle{ \varphi}\) oznacza funkcję Eulera.
Ponieważ 191 jest pierwsza, to \(\displaystyle{ \varphi(191)=190}\)
Czyli szukana reszta to 1.

Niestety nie można powtórzyć tego rozumowania dla a) i b) gdyż 26 i 1946 nie są względnie pierwsze, tak więc nie wiem jak to zrobić.

[Undre]

male tw Formata ?

to moze jeszcze

Kod: Zaznacz cały

fermat c:

?

[zxc18]

Ty sie Undre nie śmiej , ale pomóż.... no po prostu mała literówka Ale nie zaprzeczysz, iż by się przydało twierdzenie Formata

[unikat900]

Dobra Maciek. Po kilku godzinach prób chyba doszedłem jak zrobić tego typu zadania. Bombnijmy podpunkt
a):
\(\displaystyle{ 1946^{1972} : 26}\)
Wiemy, że \(\displaystyle{ 26=2*13}\) oraz \(\displaystyle{ 1946 = 0mod2}\), więc niczego nie zmieni w naszym rozumowaniu.
Dalej przyjmujemy, że \(\displaystyle{ b=13}\)
Rozpisujemy sobie potęgę do obliczeń: \(\displaystyle{ 1972= 13*151+9}\)
Tutaj stosujemy małe twierdzenie Fermata:
\(\displaystyle{ 1946^{13}=1mod13}\)
\(\displaystyle{ 1946^{13^{151}}=1mod13}\)
\(\displaystyle{ 1946=9mod13}\)
\(\displaystyle{ 1946^2=3mod13}\)
\(\displaystyle{ 1946^4=9mod13}\)
\(\displaystyle{ 1946^8=3mod13}\)
\(\displaystyle{ 1946^9=1mod13}\)
Mnożąc obustronnie stronami:
\(\displaystyle{ 1946^{1972}=(1*1)mod13=1mod26}\)
Mam nadzieję, że reszta z dzielenia faktycznie wynosi 1...

[Wasilewski]

Niestety muszę Cię zmartwić; nie słyszałem jeszcze, żeby przy dzieleniu liczby parzystej przez liczbę parzystą można było dostać resztę nieparzystą.

[Szemek]

wyniki, jakie zwróciła Mathematica:
a) 22
b) 12
c) 1

[unikat900]

No to jeszcze inaczej:
\(\displaystyle{ 1946=22mod26}\)
\(\displaystyle{ 1946^2=16mod26}\)
\(\displaystyle{ 1946^3=14mod26}\)
\(\displaystyle{ 1946^4=22mod26}\)
\(\displaystyle{ 1946^5=16mod26}\)
\(\displaystyle{ 1946^6 = 14mod26}\)
.
.
.
itd.

Otrzymujemy funkcję okresową o T=3;
\(\displaystyle{ 1972 : 3 = 657\frac{1}{3}}\)
Ta 1 z \(\displaystyle{ \frac{1}{3}}\) to 22mod26, więc to 22 jest resztą. Zaraz sprawdzę dla drugiego przykładu...

[ Dodano: 20 Kwietnia 2008, 15:12 ]
Działa, więc teraz bombardujemy podpunkt b):
Pierwszą liczbę mamy juz obliczoną i wiemy, że \(\displaystyle{ 1946^{1972}=22mod26}\)
Teraz liczymy resztę dla drugiej cyfry z zadania:
\(\displaystyle{ 1972=22mod26}\)
\(\displaystyle{ 1972^2=16mod26}\)
\(\displaystyle{ 1972^3=14mod26}\)
\(\displaystyle{ 1972^4=22mod26}\)
\(\displaystyle{ 1972^5=16mod26}\)
.
.
.
itd.
\(\displaystyle{ 1946 : 3 =648 \frac{2}{3}}\)
Z tego faktu wnioskujemy, że \(\displaystyle{ 1972^{1946}=16mod26}\)
Na koniec dodajemy kongruencje stronami i:
\(\displaystyle{ 1972^{1946}+1946^{1972}=(22+16)mod26=12mod26}\)
Reszta z dzielenia wynosi 12 uff...

[sprzedamsanki]

No to jeszcze inaczej:

\(\displaystyle{ 1946=22mod26}\)

Sory za nekrofilię, ale co oznacza ten zapis (i kolejne)?

przecież

\(\displaystyle{ 22 mod 26 = 22 \neq 1946}\)

Może mi to ktoś wyjaśnić?

[Louner]

Tutaj chodzi o przystawanie, powinno być:

\(\displaystyle{ 1946 \equiv 22 \left( mod 26 \right)}\)

Czyli innymi słowy:

\(\displaystyle{ 26 | \left(1946-22\right)}\)

Przez znak równości wyszedł taki skrót myślowy.

[dziubo1]

A te poszczególne \(\displaystyle{ 1946^2, 1946^3}\)itd. to policzyłeś w pamięci rozumiem... Czyli żeby obliczyć "ręcznie" zadania a nie kalkulatorem i tak użyłeś kalkulatora... troszku się z celem mija

WIADOMOŚĆ DO STUDENTÓW PWR:
NIE SKUMACIE TEGO CO POWYŻEJ! ODSYŁAM WAS TAM:

Kod: Zaznacz cały

http://www.cauchy.pl/kolko/gimnazjum/34/ro/

SKORO JA TO ROZKMINIŁEM TO WY TEŻ MOŻECIE!!! POWODZENIA