Matematyka.pl

\(\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ą...

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}\)

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.