Kongruencje - kilka zadań

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
19Radek88
Użytkownik
Użytkownik
Posty: 105
Rejestracja: 2 lis 2007, o 21:01
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 14 razy
Pomógł: 4 razy

Kongruencje - kilka zadań

Post autor: 19Radek88 »

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)}\).
*Kasia
Użytkownik
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ń

Post autor: *Kasia »

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)}\)
19Radek88
Użytkownik
Użytkownik
Posty: 105
Rejestracja: 2 lis 2007, o 21:01
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 14 razy
Pomógł: 4 razy

Kongruencje - kilka zadań

Post autor: 19Radek88 »

No faktycznie, dzięki.
Awatar użytkownika
przemk20
Użytkownik
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ń

Post autor: przemk20 »

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
Piotr Rutkowski
Użytkownik
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ń

Post autor: Piotr Rutkowski »

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