\(\displaystyle{ x^7\equiv x \pmod{42}}\)
Strzelam że trzeba to podejść Fermatem \(\displaystyle{ a^{p-1}\equiv 1 \pmod{7}}\)
\(\displaystyle{ 7}\) jest l.pierwsza wiec pasowałoby, ale nie znamy \(\displaystyle{ x}\) wiec nie możemy przyjąć ze jest jedynką...
Udowadnianie równania z modulo
-
freevolity
- Użytkownik
- Posty: 110
- Rejestracja: 8 paź 2011, o 11:24
- Płeć: Kobieta
- Lokalizacja: Czestochowa
- Podziękował: 12 razy
Udowadnianie równania z modulo
Ostatnio zmieniony 12 sty 2013, o 19:41 przez Ponewor, łącznie zmieniany 1 raz.
Powód: Stosuj \pmod{p}.
Powód: Stosuj \pmod{p}.
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Udowadnianie równania z modulo
rozwiązaniem tego są wszystkie liczby względnie pierwsze z \(\displaystyle{ 42}\), o rzędzie sześć:
\(\displaystyle{ 1,5,11,13,17,19,23,25,29,31,37,41}\)
jest takie coś:
\(\displaystyle{ a^{s} \equiv a^{t} \pmod n}\)
jeżeli:
\(\displaystyle{ s \equiv t \pmod r}\)
gdzie \(\displaystyle{ r \equiv ord_{n}a}\)
\(\displaystyle{ a^{r} \equiv 1 \pmod n}\)
\(\displaystyle{ 1,5,11,13,17,19,23,25,29,31,37,41}\)
jest takie coś:
\(\displaystyle{ a^{s} \equiv a^{t} \pmod n}\)
jeżeli:
\(\displaystyle{ s \equiv t \pmod r}\)
gdzie \(\displaystyle{ r \equiv ord_{n}a}\)
\(\displaystyle{ a^{r} \equiv 1 \pmod n}\)
-
Ponewor
- Moderator
- Posty: 2218
- Rejestracja: 30 sty 2012, o 21:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 70 razy
- Pomógł: 297 razy
Udowadnianie równania z modulo
arek1357 to nie było równanie, tylko twierdzenie.
freevolity chyba nie do końca rozumiesz Małe Twierdzenie Fermata. Zgodnie z nim: \(\displaystyle{ x^{7} \equiv x \pmod{42}}\). Ponieważ \(\displaystyle{ \mathbb{NWD}\left(6, \ 7 \right)=1}\) pozostaje jeszcze wykazać, że:
\(\displaystyle{ x^{7} \equiv x \pmod {6} \Leftrightarrow 6|x^{7}-x=x \left(x^{6}-1 \right)=x \left(x^{3}-1 \right) \left(x^{3}+1 \right) = x \left(x-1 \right) \left(x+1 \right) \left( x^{2} +x+1 \right)\left( x^{2} -x+1 \right)}\)
Wśród czynników mamy iloczyn trzech kolejnych liczb naturalnych, wśród nich jedna jest parzysta, i jedna podzielna przez \(\displaystyle{ 3}\), a ponieważ \(\displaystyle{ \mathbb{NWD} \left( 2, \ 3 \right)=1}\) to cały iloczyn jest podzielny przez \(\displaystyle{ 6}\).
Podzielność przez \(\displaystyle{ 7}\) można też wykazać inaczej bez strzelania z MTF:
\(\displaystyle{ x \left(x-1 \right) \left(x+1 \right) \left( x^{2} +x+1 \right)\left( x^{2} -x+1 \right)=x \left(x-1 \right) \left(x+1 \right) \left( \left(x-2 \right) \left(x+3 \right)+7 \right) \left( \left(x+2 \right) \left(x-3 \right) +7 \right) = \left(x-3 \right) \left(x-2 \right) \left( x-1 \right) x \left(x+1 \right) \left( x+2 \right) \left( x+3 \right) + \\ 7 \left( \left(x-2 \right) \left( x-1 \right)x \left(x+1 \right) \left(x+3 \right) + \left(x-3 \right) \left( x-1 \right)x \left(x+1 \right) \left(x+2 \right) + 7 \left(x-1 \right) x \left(x+1 \right) \right)}\)
Pierwszy składnik to iloczyn siedmiu kolejnych liczb naturalnych, z których jedna musi być podzielna przez \(\displaystyle{ 7}\), więc niewątpliwie ów składnik jest podzielny przez \(\displaystyle{ 7}\). Drugi składnik też jest podzielny przez \(\displaystyle{ 7}\), bo ma \(\displaystyle{ 7}\) przed nawiasem, a zatem cała suma jest podzielna.
freevolity chyba nie do końca rozumiesz Małe Twierdzenie Fermata. Zgodnie z nim: \(\displaystyle{ x^{7} \equiv x \pmod{42}}\). Ponieważ \(\displaystyle{ \mathbb{NWD}\left(6, \ 7 \right)=1}\) pozostaje jeszcze wykazać, że:
\(\displaystyle{ x^{7} \equiv x \pmod {6} \Leftrightarrow 6|x^{7}-x=x \left(x^{6}-1 \right)=x \left(x^{3}-1 \right) \left(x^{3}+1 \right) = x \left(x-1 \right) \left(x+1 \right) \left( x^{2} +x+1 \right)\left( x^{2} -x+1 \right)}\)
Wśród czynników mamy iloczyn trzech kolejnych liczb naturalnych, wśród nich jedna jest parzysta, i jedna podzielna przez \(\displaystyle{ 3}\), a ponieważ \(\displaystyle{ \mathbb{NWD} \left( 2, \ 3 \right)=1}\) to cały iloczyn jest podzielny przez \(\displaystyle{ 6}\).
Podzielność przez \(\displaystyle{ 7}\) można też wykazać inaczej bez strzelania z MTF:
\(\displaystyle{ x \left(x-1 \right) \left(x+1 \right) \left( x^{2} +x+1 \right)\left( x^{2} -x+1 \right)=x \left(x-1 \right) \left(x+1 \right) \left( \left(x-2 \right) \left(x+3 \right)+7 \right) \left( \left(x+2 \right) \left(x-3 \right) +7 \right) = \left(x-3 \right) \left(x-2 \right) \left( x-1 \right) x \left(x+1 \right) \left( x+2 \right) \left( x+3 \right) + \\ 7 \left( \left(x-2 \right) \left( x-1 \right)x \left(x+1 \right) \left(x+3 \right) + \left(x-3 \right) \left( x-1 \right)x \left(x+1 \right) \left(x+2 \right) + 7 \left(x-1 \right) x \left(x+1 \right) \right)}\)
Pierwszy składnik to iloczyn siedmiu kolejnych liczb naturalnych, z których jedna musi być podzielna przez \(\displaystyle{ 7}\), więc niewątpliwie ów składnik jest podzielny przez \(\displaystyle{ 7}\). Drugi składnik też jest podzielny przez \(\displaystyle{ 7}\), bo ma \(\displaystyle{ 7}\) przed nawiasem, a zatem cała suma jest podzielna.