Znaleźć liczby pierwsze p i q

[ruduq7]

To zadanie nurtuje mnie już od dłuższego czasu:
Wyznaczyć wszystkie takie pary liczb pierwszych \(\displaystyle{ p}\), \(\displaystyle{ q}\), ze liczba \(\displaystyle{ 5 ^{p}+ 5 ^{q}}\) jest podzielna przez \(\displaystyle{ pq}\).

[Zahion]

Oczywiście jedna z liczb musi wynosić pięć stąd niech \(\displaystyle{ p = 5}\) mamy wtedy, że
nasze wyrażenie wynosi \(\displaystyle{ 5 ^{5}(5 ^{q-5}+1)}\) stąd wnioskujemy, że \(\displaystyle{ q=2, q=5}\) co jest odpowiedzią.

[ruduq7]

Niekoniecznie \(\displaystyle{ p=5}\), bo na przykład dla \(\displaystyle{ p=3}\) i \(\displaystyle{ q=2}\) mamy \(\displaystyle{ pq=2 \cdot 3=6}\) i \(\displaystyle{ 5 ^{p}+5 ^{q}=25+125=150}\), a \(\displaystyle{ 6|150}\).

[Vax]

Załóżmy na początku, że \(\displaystyle{ p,q \neq 5 \wedge p,q \neq 2}\), czyli w szczególności \(\displaystyle{ 0 \equiv 5^p+5^q \equiv 5^p+5 \pmod{q} \iff 5^{p-1} \equiv -1\pmod{q} \Rightarrow 5^{2(p-1)} \equiv 1\pmod{q}}\)

Niech \(\displaystyle{ t = ord_q 5}\), czyli \(\displaystyle{ t \nmid p-1 \wedge t\mid 2(p-1)}\) oraz z małego twierdzenia Fermata \(\displaystyle{ t \mid q-1}\), ale to oznacza, że \(\displaystyle{ v_2(p-1) < v_2(q-1)}\), jednak analogicznie (patrząc na dane równanie \(\displaystyle{ \pmod{p}}\)) dochodzimy do wniosku, że \(\displaystyle{ v_2(q-1) < v_2(p-1)}\) sprzeczność.

Jeżeli któraś z \(\displaystyle{ p,q}\) jest równa \(\displaystyle{ 2}\), bso \(\displaystyle{ q=2}\) otrzymujemy:

\(\displaystyle{ 2p \mid 5^p+25}\), jeżeli \(\displaystyle{ p=5}\) to dana podzielność zachodzi, załóżmy, że \(\displaystyle{ p \neq 5}\), ale wtedy dostajemy: \(\displaystyle{ 0 \equiv 5^p+25 \equiv 5+25 \equiv 30\pmod{p}}\)

Skąd \(\displaystyle{ p \in \lbrace 2;3;5\rbrace}\), z czego \(\displaystyle{ p=3}\) działa, czyli \(\displaystyle{ (p,q) = (5,2) , (3,2)}\) i analogicznie gdy \(\displaystyle{ p=2}\) dostajemy \(\displaystyle{ (p,q) = (2,5) , (2,3)}\).

Jeżeli któraś z \(\displaystyle{ p,q}\) jest równa \(\displaystyle{ 5}\), bso \(\displaystyle{ q=5}\) otrzymujemy równoważnie (\(\displaystyle{ p=5}\) działa, więc zakładamy, że \(\displaystyle{ p \neq 5}\)):

\(\displaystyle{ 5p \mid 5^p+5^5 \iff p \mid 5^{p-1}+5^4}\), czyli \(\displaystyle{ 0 \equiv 5^{p-1}+5^4 \equiv 1+5^4 \equiv 626 \pmod {p}}\)

Skąd \(\displaystyle{ p \in \lbrace 2;313\rbrace}\), czyli ostatecznie dana podzielność zachodzi dla:

\(\displaystyle{ (p,q) = (2,3) , (3,2) , (2,5) , (5,2) , (5,5) , (5,313) , (313,5)}\)

[ruduq7]

Mógłby mi ktoś wyjaśnić, co to znaczy \(\displaystyle{ t = ord_q 5}\) i \(\displaystyle{ v_2}\)?

[AndrzejK]

\(\displaystyle{ ord_{p}(a)}\) jest rzędem liczby \(\displaystyle{ a}\) modulo \(\displaystyle{ p}\), czyli najmniejszą liczbą naturalną \(\displaystyle{ d}\) taką, że \(\displaystyle{ a^d \equiv 1\pmod{p}}\)