[Teoria liczb] gruba teoria liczb

[maXX]

Swistak podesłał mi zadanie, którego sam nie umie zrobić, a zrobił je kaszubek.

Niech \(\displaystyle{ a,b,c>1}\) będą liczbami parami względnie pierwszymi. Ponadto \(\displaystyle{ a|2^b+1, b|2^c+1, c|2^a+1}\). Wykaż, że taka trójka nie istnieje.

kaszubek przed chwilą mi powiedział, że prawdziwe jest uogólnienie:
Niech \(\displaystyle{ n>1}\) oraz \(\displaystyle{ a_1, a_2,...,a_n > 1}\) będą liczbami parami względnie pierwszymi. Ponadto dla każdego \(\displaystyle{ i}\) zachodzi \(\displaystyle{ a_i|2^{a_{i+1}}+1}\) \(\displaystyle{ (a_{n+1}=a_1}\)). Wykaż, że takie liczby \(\displaystyle{ a_1, a_2,...,a_n}\) nie istnieją.

[Sylwek]

Podpowiedź dla Świstaka: prosto idzie z rachunku na rzędach.

[maXX]

Mógłbyś napisać to rozwiązanie?

[binaj]

najpierw lemat \(\displaystyle{ x|2^x+1 \Rightarrow x=1}\)

jeśli \(\displaystyle{ a_i|2^{a_{i+1}}+1}\)
to wtedy \(\displaystyle{ lcm(a_1,...a_n)|2^{lcm(a_1,...a_n)}+1}\) sprzeczność

[limes123]

To dziala dla minusow a nie plusow.
3|8+1

[binaj]

racja, pisałem na pamięć

[Swistak]

Dla plusów sprawa jest bardzo ciekawa. Nietrudno zauważyć, że wszystkie potęgi trójki pasują. Ręczne sprawdzanie do pewnego momentu to potwierdza. Ale okazuje się, że to nieprawda, bo \(\displaystyle{ 171|2^{171}+1}\) :p.
Mógłby ktoś napisać jakiegoś większego hinta? Bo to zadanie prześladuje mnie od dawna, nawalałem rzędami z każdej możliwej strony i nie pykło : /.

[kaszubki]

rozwiązanie:    

Niech \(\displaystyle{ a_i = p_{1i}^{\alpha_{1i}} p_{2i}^{\alpha_{2i}} ... p_{k_i i}^{\alpha_{k_i i}}}\), gdzie \(\displaystyle{ p_{1i} < p_{2i} <...<p_{ni}}\). Załóżmy bez straty ogólności, że \(\displaystyle{ p_{11}<p_{12}}\). Wówczas \(\displaystyle{ p_{11}|2^{a_2} + 1 \Rightarrow ord_{p_{11}}(4) | a_2}\). Ale \(\displaystyle{ ord_{p_{11}}(4) < p_{11} < p_{12}}\), więc aby dzielił \(\displaystyle{ a_2}\), to musi być jedynką. Zatem \(\displaystyle{ ord_{p_{11}}(4) = 1}\), czyli \(\displaystyle{ p_{11}=3}\).
Założyliśmy, że \(\displaystyle{ p_{11} < p_{12}}\) i z tego od razu wynikło, że \(\displaystyle{ p_{11}=3}\). Zatem gdyby raz jeszcze zdarzyła się sytuacja, że \(\displaystyle{ p_{1k}<p_{1,k+1}}\), to byśmy dostali \(\displaystyle{ p_{1k}=3}\) i liczby \(\displaystyle{ a_1, a_k}\) nie byłyby względnie pierwsze. Zatem \(\displaystyle{ p_{12}>p_{13}>...>p_{1n}}\).
Gdyby było \(\displaystyle{ p_{21}<p_{12}}\), to tą samą drogą otrzymalibyśmy \(\displaystyle{ p_{21}=3}\). Zatem musi zachodzić \(\displaystyle{ p_{12}<p_{21}}\). Zatem \(\displaystyle{ p_{21} > p_{12}>p_{13}>...>p_{1n}}\), czyli \(\displaystyle{ p_{21}>p_{1n}>p_{12}}\). Czyli \(\displaystyle{ p_{1n}|2^{a_1} + 1}\), zatem \(\displaystyle{ ord_{p_{1n}}(4) | a_1}\), więc \(\displaystyle{ ord_{p_{1n}}(4) | p_{11}^{\alpha_{11}} \cdot x}\), gdzie każdy czynnik pierwszy \(\displaystyle{ x}\) jest większy od \(\displaystyle{ ord_{p_{1n}}(4)}\), czyli \(\displaystyle{ ord_{p_{1n}}(4) | p_{11}^{\alpha_{11}}}\).
Zastanówmy się teraz nad \(\displaystyle{ \alpha_{11}}\). Popatrzmy na kongruencję \(\displaystyle{ 2^m \equiv -1 (mod \ 9)}\). Kolejne reszty z dzielenia potęg dwójki przez 9 to 1,2,4,-1,-2,-4. Czyli jeśli \(\displaystyle{ 2^m \equiv 0 (mod \ 9)}\), to \(\displaystyle{ m \equiv 3 (mod \ 6)}\), czyli w szczególności \(\displaystyle{ 3|m}\). Zatem gdyby było \(\displaystyle{ \alpha_{11}\geq 2}\), to zachodziłoby \(\displaystyle{ 9|2^{a_2}+1}\), czyli jak już pokazałem musiałoby zachodzić \(\displaystyle{ 3|a_2}\), a tak być nie bydzie.
Zatem \(\displaystyle{ \alpha_{11}=1}\), czyli \(\displaystyle{ ord_{p_{1n}}(4) | p_{11}^{\alpha_{11}} \Rightarrow ord_{p_{1n}}(4) | 3 \Rightarrow p_{1n}|63}\). A skoro \(\displaystyle{ p_{1n} \neq 3}\), to \(\displaystyle{ p_{1n}=7}\). No więc \(\displaystyle{ 2^{a_1} \equiv 6 (mop \ 7)}\), a to jest już ostateczna sprzeczność, bo potęgi dwójki dają reszty 1,2,4 z dzielenia przez 7.

[KPR]

Ale blef, skąd wziąłeś \(\displaystyle{ p_{11}<p_{12}}\)? W ogóle weź przeczytaj swoje rozwiązanie i napraw indeksy

[kaszubki]

Założyłem \(\displaystyle{ p_{11}<p_{12}}\), bo nie może być \(\displaystyle{ p_{11}>p_{12}>p_{13}>...>p_{1n}>p_{11}}\). Albo mi się tylko wydaje.