[Teoria liczb] Kongruencja

[Sylwek]

Znajdź takie liczby pierwsze \(\displaystyle{ p,q}\), że dla każdej naturalnej wartości \(\displaystyle{ x}\) zachodzi:

\(\displaystyle{ x^{3pq} \ \equiv \ x \ (mod \ 3pq)}\)

Zapraszam do zmierzenia się z tym trudnym problemem

[TomciO]

Jesli sie wie co to jest generator (pierwiastek pierwotny) to jest to proste cwiczenie. Uzywajac jego istnienia latwo dowodzimy, ze musi byc \(\displaystyle{ p-1 | 3q-1}\) oraz \(\displaystyle{ q-1 | 3p-1}\). No, a teraz to juz jest latwe: zakladamy, ze \(\displaystyle{ p q q}\) i dochodzimy do tego, ze \(\displaystyle{ p=17, q=11}\).

[Piotr Rutkowski]

hehe, TomciO jak zwykle niezawodny Takie małe pytanko, skąd wiadomo, że 3pq posiada pierwiastek pierwotny? I pytanie do Sylwka, jak wygląda elementarna wzorcówka?

[TomciO]

\(\displaystyle{ 3pq}\) na pewno go nie posiada (chyba, ze \(\displaystyle{ p=q=3}\)). Ale przeciez ta kongruencje mozna rozpatrywac osobno mod \(\displaystyle{ p}\) i osobno mod \(\displaystyle{ q}\). I nie sadze, zeby to sie dalo zrobic w istotnie inny sposob...

[Sylwek]

Próbowałem to z funkcji Eulera, ale nie wychodziło, tzn. wychodził brak rozwiązań. Z drugiej strony jak zna się pewne właściwości liczb Carmichaela, to można od razu podać odpowiedź, że \(\displaystyle{ (p,q):(11,17)}\), stąd poznałem, że coś robię źle. No ale nie znam dowodu, że jedyną trójką liczb Carmichaela zawierającą w rozkładzie na czynniki pierwsze jest trójka \(\displaystyle{ (3,11,17)}\). Dzięki TomciO, poczytam sobie o pierwiastku pierwotnym

Btw. wzorcówki nie mam, to zadanie z kółka LO XIV w Warszawie dla klas starszych, a tam nie ma rozwiązań

[Mbach]

Tutaj nie potrzeba takiego już niełatwgo pojęcia pierwiastka pierwotnego. Wystarczy mały fermat.

Mamy \(\displaystyle{ x^{3pq} = x (mod 3pq)}\)
to znaczy że musi być: \(\displaystyle{ (x^{q})^{3p} = (x^{q-1} x)^{3p} = x^{3p} = x (mod q)}\)

bo z małego fermata \(\displaystyle{ x^{q-1} = 1 (mod q)}\)

czyli wracając\(\displaystyle{ x^{3p} = x (mod q)}\)
\(\displaystyle{ x(x^{3p-1} - 1) = 0 (mod q)}\)
ale q jest pierwsze a kongruencja ma byc spełniona dla każego x więc musi być:
\(\displaystyle{ x^{3p-1} = 1 (mod q)}\)
no i teraz wracając do grupy G(q) (lub \(\displaystyle{ Z_q}\) co na jedno wyjdzie) - jest cykliczna bo q jest pierwsze.
jako że kongruecja jest dla każdego x to znaczy że w wykładniku jest wielokrotność rzędu grupy, już. Analigocznie gdy rozpatrujemy modulo p

[MarcinT]

Uważam że korzystanie z cykliczności grupy i rzędu grupy jest na tym samym poziomie co pierwiastek pierwotny.

[Piotr Rutkowski]

Hmm, nie chcę tu wyjść na idiotę, ale czy ktoś mógłby mi przystępnie wytłumaczyć ostatnie 4 linijki?

[TomciO]

Przeciez to nie jest "na tym samym poziomie" tylko to jest dokladnie _to_samo_. To, ze grupa jest cykliczna znaczy dokladnie tyle, ze posiada generator czyli pierwiastek pierwotny...

[Mbach]

Wydaje mi się że, uwaga że Z_q jest cykliczna jest tutaj w ogóle niepotrzeba - i nie ponwinienem był tego napisać bo z tego nie korzystam. Korzystam jedynie z faktu że rząd tej grupy to q-1 i z twierdzenia Lagrange`a.

[TomciO]

Tzn. z tego, ze rzad elementu dzieli rzad grupy? Wg mnie to samo w sobie nic nie daje dopoki niewiadomo, ze istnieje element rzedu \(\displaystyle{ q-1}\). Ale jesli sie nie myle to latwo sie daje pokazac, ze w \(\displaystyle{ \mathbb{Z}_p}\) wielomian \(\displaystyle{ x^m - 1}\) dzieli wielomian \(\displaystyle{ x^n - 1}\) wtedy i tylko wtedy, gdy \(\displaystyle{ m|n}\) i to by zalatwilo sprawe.

[Sylwek]

Zrozumiałem raczej wszystko, tylko czemu

rząd tej grupy to q-1

[ Dodano: 25 Stycznia 2008, 12:47 ]

\(\displaystyle{ p-1 | 3q-1}\) oraz \(\displaystyle{ q-1 | 3p-1}\)

Wyszło mi, że rozwiązaniami są pary (\(\displaystyle{ p \geq q}\): \(\displaystyle{ (p,q): (2,2), \ (3,3), \ (5,3), \ (17,11)}\). Mógłbym prosić o kilka słów wyjaśnienia, czemu trzy pierwsze pary nie są rozwiązaniami tego zadania?


[EDIT po bardzo długim czasie]
Znalazłem przypadkowo ten post, więc dopiszę nieco. To, czego nie rozumiałem przed rokiem, zawiera się w tym temacie: https://matematyka.pl/95638.htm#352125 . Czyli dla pewnego x ze zbioru {1,2,...,p}, gdzie p jest pierwsze, najmniejszą naturalną potęgą t taką, że \(\displaystyle{ x^t \equiv 1 \ (mod \ p)}\), jest p-1. Patrząc na rozumowanie MBach-a mamy, że:
\(\displaystyle{ x^{3p-1} \equiv 1 \ (mod \ q)}\).

Prosto pokazać, że to 3p-1 musi być wielokrotnością rzędu liczby x, co za tym idzie, skoro dla pewnego x tym rzędem jest q-1, to mamy: \(\displaystyle{ (q-1)|(3p-1)}\), analogicznie: \(\displaystyle{ (p-1)|(3q-1)}\) - no i teraz już łatwo uzyskać powyższe rozwiązania.

Pierwsze trzy pary nie pasują - łatwo znaleźć dla nich kontrprzykłady (zapytacie - dlaczego nie pasują? przecież je wyliczyliśmy? no właśnie - ale co wyliczyliśmy? wyliczyliśmy takie p,q, że: \(\displaystyle{ x^{3pq} \equiv x \ (mod \ pq)}\), a nie \(\displaystyle{ mod \ 3pq}\) - dlatego trzeba sprawdzić).

Pasuje tylko ostatnia para - można to zrobić potwierdzając prawdziwość kongruencji: \(\displaystyle{ x^{3 \cdot 11 \cdot 17} \equiv x \ (mod \ 3 \cdot 11 \cdot 17)}\) oddzielnie modulo 3, modulo 11 i modulo 17 - a ponieważ te liczby są względnie pierwsze, to wyjściowa kongruencja też jest prawdziwa. I po zadaniu

[TomciO]

Od razu widac, ze zeby modulo \(\displaystyle{ 3}\) sie nie psulo to \(\displaystyle{ p, q}\) musza byc nieparzyste, a jesli ktoras jest trojka to psuje sie mod \(\displaystyle{ 9}\). Dlatego najlepiej na poczatku wykluczyc te przypadki i potem przyjac juz, ze \(\displaystyle{ p, q > 3}\). A to, ze rzad tej grupy to \(\displaystyle{ q-1}\) to przeciez wiadomo bo rzad grupy skonczonej to ilosc jej elementow...