Wyznacz reszty z dzielenia - sprawdzenie.

tometomek91 · Post autor: **tometomek91** » 24 cze 2010, o 21:37

a) \(\displaystyle{ 15^{231}}\) przez 14
b) \(\displaystyle{ 3^{80}+7^{80}}\) przez 11
c) \(\displaystyle{ 208^{208}}\) przez 23
d) \(\displaystyle{ 18^{2815}}\) przez 14

czy te odpowiedzi są dobre?
a)1 b)3 c)1 d)1

BettyBoo · Post autor: **BettyBoo** » 24 cze 2010, o 21:57

Tylko a) i c) są dobrze. Podaj obliczenia, to Ci powiem co jest nie tak z b i d.

Pozdrawiam.

tometomek91 · Post autor: **tometomek91** » 24 cze 2010, o 22:09

W d) zauważyłem błąd - w trzeciej linijce miałem że 1024=1, teraz dochodzę do pewnego momentu:
\(\displaystyle{ 18 \equiv 4\ (mod\ 14)\\
18^{2815} \equiv 4^{2815}\ (mod\ 14)\\
1024 \equiv 2\ (mod\ 14)\\
4^{5} \equiv 2\ (mod\ 14)\\
4^{2815} \equiv 2^{563}\ (mod\ 14)}\)

a w b) wychodzi jednak 2, tak?

BettyBoo · Post autor: **BettyBoo** » 24 cze 2010, o 22:15

Tak, w b) będzie 2.

Natomiast w d) kluczowa jest druga linijka w tym, co napisałeś. Ponieważ ponadto masz

\(\displaystyle{ 4^2=2 \mod14, \ 4^4=2^2=4\mod14}\)

więc..... ?

Pozdrawiam.

tometomek91 · Post autor: **tometomek91** » 24 cze 2010, o 22:52

nie wiem, co dalej. mogłabyś rozwiązać?

BettyBoo · Post autor: **BettyBoo** » 24 cze 2010, o 23:51

Metoda w miarę standardowa - wystarczy wykładnik przedstawić w postaci sumy potęg dwójki i skorzystać z tego, co wyżej.

Pozdrawiam.

tometomek91 · Post autor: **tometomek91** » 25 cze 2010, o 09:00

Wyszła mi reszta 8. dobrze?

BettyBoo · Post autor: **BettyBoo** » 25 cze 2010, o 16:08

U mnie wyszło 4.

Możesz to też zrobić tak: po przeliczeniu kilku początkowych potęg widać, że

\(\displaystyle{ 4^{3k+1}=4,\ 4^{3k+2}=2,\ 4^{3k}=8}\)

wobec tego

\(\displaystyle{ 4^{2815}=4^{3\cdot 938+1}=4}\)

Pozdrawiam.

Mariusz M · Post autor: **Mariusz M** » 19 lip 2010, o 01:17

Można też użyć twierdzenia Eulera

Do a) b) c) można użyć tw Eulera (w b) i c) i d) pokrywa się ono z tw Fermata)

W d) trzeba skorzystać z

\(\displaystyle{ 14=2 \cdot 7}\)

Następnie obliczyć potęgi modulo 2 i modulo 7 (korzystając np z twierdzenia Eulera)
Na koniec trzeba skorzystać z chińskiego tw o resztach

W d) po zastosowaniu twierdzenia Eulera otrzymujesz układ kongruencji

\(\displaystyle{ \begin{cases} x\equiv 0 \left(\mod 2 \right) \\ x \equiv 4 \left(\mod 7 \right) \end{cases}}\)

Z tego wynika że Betty obliczyła dobrze

W a) i c) nie potrzeba korzystać z twierdzenia Eulera ale jak ktoś się uprze to można

W b) stosując twierdzenie Eulera które w tym przypadku pokrywa z twierdzeniem Fermata
otrzymujesz

\(\displaystyle{ 3^{8 \cdot 10}+7^{8 \cdot 10} \equiv 1+1 \left(\mod 11 \right)}\)

\(\displaystyle{ x \equiv 2 \left(\mod 11 \right)}\)

i znowu Betty obliczyła dobrze

BettyBoo, zamiast przeliczać początkowe potęgi można skorzystać z twierdzenia Eulera
które w tym wypadku pokrywa się z twierdzeniem Fermata

BettyBoo · Post autor: **BettyBoo** » 6 wrz 2010, o 23:07

mariuszm, można zrobić różne rzeczy. W tym zadaniu d) rzeczywiście chińskie twierdzenie o resztach daje szybkie rezultaty, ze względu na specyficzna postać równań, które się otrzymuje. Ogólnie to jest jak zwykle - czyli można podać przykłady, w których jedna bądź druga metoda działają lepiej.

Pozdrawiam.