układ kongruencji (chińskie twierdzenie o resztach)

ptj · Post autor: **ptj** » 3 lis 2013, o 12:15

Hey, mam do rozwiazania takie rownanie kongruencji:
\(\displaystyle{ 2^{n} \approx 1 \pmod{5 \cdot 7 \cdot 9 \cdot 11 \cdot 13}}\) dla \(\displaystyle{ n}\) należacych do naturalnych.
Od razu nasuwa się że jest to \(\displaystyle{ n=0}\) jednak jeśli założymy że nie jest to l. naturalna to zadanie staje się znacznie trudniejsze (rozwiązując układ kongruencji dostajemy właśnie \(\displaystyle{ 1}\)). Jakiś inny pomysł na rozwiązanie?

robertm19 · Post autor: **robertm19** » 3 lis 2013, o 12:25

Z twierdzenia Eulera wynika, że \(\displaystyle{ n=\phi(5\cdot 7\cdot 9 \cdot 11 \cdot 13)}\).

ptj · Post autor: **ptj** » 3 lis 2013, o 12:42

też tak rozwiązałem:
\(\displaystyle{ n= \phi (5\cdot7\cdot 9\cdot 11 \cdot 13 )= \phi(5)\cdot \phi(7)\cdot \phi(9)\cdot \phi(11)\cdot \phi(13)= 4 \cdot 6 \cdot 3 \cdot2 \cdot 10 \cdot 12 = 17280}\)
gdzie jest błąd?

wolfram mówi że 60n.

Zordon · Post autor: **Zordon** » 4 lis 2013, o 20:59

bo \(\displaystyle{ NWW(4,6,3,2,10,12)=60}\)

robertm19 · Post autor: **robertm19** » 4 lis 2013, o 22:21

Zordon, wyjaśnisz skąd taki wynik?

Zordon · Post autor: **Zordon** » 4 lis 2013, o 22:34

Z chińskiego twierdzenia o resztach:
\(\displaystyle{ 2^n=1 \pmod{5\cdot 7 \cdot 9 \cdot 11\cdot 13}}\)
wtedy i tylko wtedy gdy:
\(\displaystyle{ \begin{cases}
2^n=1 \pmod{5} \\
2^n=1 \pmod{7} \\
2^n=1 \pmod{9} \\
2^n=1 \pmod{11} \\
2^n=1 \pmod{13} \\
\end{cases}}\)
wtedy i tylko wtedy gdy:
\(\displaystyle{ \begin{cases}
4|n\\
3|n \\
6|n \\
10|n \\
12|n \\
\end{cases}}\)
wtedy i tylko wtedy gdy \(\displaystyle{ NWW(4,3,6,10,12)|n}\)