1. Pokazać, że \(\displaystyle{ 61! \equiv 63!(mod 71)}\).
2. Pokazać, że \(\displaystyle{ 2^{11*31}\equiv 2(mod 11*31)}\)
3. Rozwiązać:
\(\displaystyle{ x^{100}\equiv 1(mod 7)}\)
4.Wykaż, że:
\(\displaystyle{ 3^{80}+7^{80}\equiv2(mod5)}\).
Kongruencje - kilka zadań
-
- Użytkownik
- Posty: 2826
- Rejestracja: 30 gru 2006, o 20:38
- Płeć: Kobieta
- Lokalizacja: Lublin/warszawa
- Podziękował: 62 razy
- Pomógł: 482 razy
Kongruencje - kilka zadań
Ad 1
Wystarczy skorzystać z tego, że:
\(\displaystyle{ 62\cdot 63\equiv 1\ (mod\ 71)}\).
Ad 4
\(\displaystyle{ (3^2)^{40}\equiv (-1)^{40}\equiv 1\ (mod\ 5)\\
(7^2)^{40}\equiv (-1)^{40}\equiv 1\ (mod\ 5)}\)
Wystarczy skorzystać z tego, że:
\(\displaystyle{ 62\cdot 63\equiv 1\ (mod\ 71)}\).
Ad 4
\(\displaystyle{ (3^2)^{40}\equiv (-1)^{40}\equiv 1\ (mod\ 5)\\
(7^2)^{40}\equiv (-1)^{40}\equiv 1\ (mod\ 5)}\)
- przemk20
- Użytkownik
- Posty: 1094
- Rejestracja: 6 gru 2006, o 22:47
- Płeć: Mężczyzna
- Lokalizacja: Olesno
- Podziękował: 45 razy
- Pomógł: 236 razy
Kongruencje - kilka zadań
3 zauwaz ze musi zachodzic NWD(x,7)=1
\(\displaystyle{ \phi(7)=6}\) (funkcja eulera)
a ze zchodzi
\(\displaystyle{ a^{\phi(n)} \equiv 1 \mod n, \ dla \ NWD(a,n)=1 \\
ale \ dla \ x=a, \ n=7 \\
x^{6} \equiv 1 \mod 7 \iff x^{96} \equiv 1 \mod 7 x^4 \equiv 1 \mod 7 \\}\)
teraz wystarczy sprawdzic wszystkie mozliwe reszty modulo 7
\(\displaystyle{ \phi(7)=6}\) (funkcja eulera)
a ze zchodzi
\(\displaystyle{ a^{\phi(n)} \equiv 1 \mod n, \ dla \ NWD(a,n)=1 \\
ale \ dla \ x=a, \ n=7 \\
x^{6} \equiv 1 \mod 7 \iff x^{96} \equiv 1 \mod 7 x^4 \equiv 1 \mod 7 \\}\)
teraz wystarczy sprawdzic wszystkie mozliwe reszty modulo 7
-
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
Kongruencje - kilka zadań
2)
Skoro 11 i 31 to liczby pierwsze, to ten zapis jest równoważny zapisowi:
\(\displaystyle{ (11|(2^{341}-2)) (31|(2^{341}-2))}\), co można łatwo udowodnić korzystając z tego, że:
\(\displaystyle{ 2^{5}\equiv 1 \ (mod31) 2^{5}\equiv (-1) \ (mod11)}\)
Skoro 11 i 31 to liczby pierwsze, to ten zapis jest równoważny zapisowi:
\(\displaystyle{ (11|(2^{341}-2)) (31|(2^{341}-2))}\), co można łatwo udowodnić korzystając z tego, że:
\(\displaystyle{ 2^{5}\equiv 1 \ (mod31) 2^{5}\equiv (-1) \ (mod11)}\)