Wyznacz reszte z dzielenia

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
justdzo
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 27 paź 2015, o 19:57
Płeć: Kobieta
Lokalizacja: Warszawa

Wyznacz reszte z dzielenia

Post autor: justdzo »

Hej, podpowie ktoś jak ugryźć to zadanie?

Wyznacz resztę z dzielenia \(\displaystyle{ 15^{231}}\) przez \(\displaystyle{ 14}\).
Ostatnio zmieniony 25 sty 2018, o 21:25 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
szw1710

Wyznacz reszte z dzielenia

Post autor: szw1710 »

To trywialne. Reszta wynosi \(\displaystyle{ 1}\), bo \(\displaystyle{ 15\mod 14=1.}\) A kongruencje można potęgować.
justdzo
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 27 paź 2015, o 19:57
Płeć: Kobieta
Lokalizacja: Warszawa

Wyznacz reszte z dzielenia

Post autor: justdzo »

szw1710 pisze:To trywialne. Reszta wynosi \(\displaystyle{ 1}\), bo \(\displaystyle{ 15\mod 14=1.}\) A kongruencje można potęgować.
Dzięki

Proszę jeszcze o sprawdzenie, korzystam z twierdzenia Eulera.

\(\displaystyle{ 18^{2815}}\) przez \(\displaystyle{ 14}\)

\(\displaystyle{ NWD(18,14)=1 \Rightarrow 18^{\varphi(14)} = 1\pmod{14} \Rightarrow 18^{6} = 1 \pmod{14} \Rightarrow (18^{6})^{469} \cdot 18 = 18 \pmod{14} = 4\pmod{14}}\)

Jest ok ?
Ostatnio zmieniony 25 sty 2018, o 21:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Wyznacz reszte z dzielenia

Post autor: Premislav »

Przecież \(\displaystyle{ \NWD(14,18)=2}\)

Tak nie da rady, zastanowiłbym się nad modulo \(\displaystyle{ 7}\). Już \(\displaystyle{ \NWD(18,7)=1}\), więc z tw. Eulera masz \(\displaystyle{ 18^{6}\equiv 1\pmod{7}}\) (właściwie to MTF w tym wypadku wystarcza).
Mamy \(\displaystyle{ 2815=2814+1\equiv 1\pmod{6}}\) i
\(\displaystyle{ 18^{2814}\equiv 1\pmod{7}\\18^{2815}\equiv 18\pmod{7}}\)
czyli \(\displaystyle{ 18^{2815}\equiv 18\pmod{7}\equiv 4\pmod{7}}\).
Ponadto jest to liczba parzysta, zatem musi być postaci \(\displaystyle{ 14k+4}\), tj. odpowiedź:
\(\displaystyle{ 18^{2815}\equiv 4\pmod{14}}\).
Ale u Ciebie wyszło poprawnie tylko przez przypadek.
justdzo
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 27 paź 2015, o 19:57
Płeć: Kobieta
Lokalizacja: Warszawa

Wyznacz reszte z dzielenia

Post autor: justdzo »

Premislav pisze:Przecież \(\displaystyle{ \NWD(14,18)=2}\)

Tak nie da rady, zastanowiłbym się nad modulo \(\displaystyle{ 7}\). Już \(\displaystyle{ \NWD(18,7)=1}\), więc z tw. Eulera masz \(\displaystyle{ 18^{6}\equiv 1\pmod{7}}\) (właściwie to MTF w tym wypadku wystarcza).
Mamy \(\displaystyle{ 2815=2814+1\equiv 1\pmod{6}}\) i
\(\displaystyle{ 18^{2814}\equiv 1\pmod{7}\\18^{2815}\equiv 18\pmod{7}}\)
czyli \(\displaystyle{ 18^{2815}\equiv 18\pmod{7}\equiv 4\pmod{7}}\).
Ponadto jest to liczba parzysta, zatem musi być postaci \(\displaystyle{ 14k+4}\), tj. odpowiedź:
\(\displaystyle{ 18^{2815}\equiv 4\pmod{14}}\).
Ale u Ciebie wyszło poprawnie tylko przez przypadek.
Dzięki! chyba bardzo chciałam zeby NWD wyszło 1
ODPOWIEDZ