[Teoria liczb] Równanie z liczbami pierwszymi

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: Sylwek » 25 lip 2008, o 16:01

polskimisiek pisze:Można w taki sposób, że jeśli a jest nieparzyste to prawa strona dzieli się przez cztery
No właśnie nie bardzo, gdy l jest nieparzyste, nie możemy sobie tak tego rozłożyć (tzn. możemy, ale mamy iloczyn dwóch liczb niewymiernych)...

Prosto dojść, że jeśli równość jest spełniona, to \(\displaystyle{ a \equiv 7 \ (mod 12)}\) i \(\displaystyle{ l \equiv 1 \ (mod 2)}\). Pytanie - jak tu dojść do sprzeczności? Znasz polskimiśku solucję?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

dr_grucha
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 27 maja 2005, o 20:16
Płeć: Mężczyzna
Lokalizacja: Frysztak
Pomógł: 28 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: dr_grucha » 25 lip 2008, o 20:52

Zauważmy, że skoro \(\displaystyle{ l>1}\) to \(\displaystyle{ a }\) i tym rozwiązaniem jest \(\displaystyle{ a=1}\), więc równość nie zachodzi.

Awatar użytkownika
max
Gość Specjalny
Gość Specjalny
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: max » 26 lip 2008, o 00:50

Tylko dlaczego
\(\displaystyle{ a\equiv 1 od{p_{i}}}\) ?

dr_grucha
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 27 maja 2005, o 20:16
Płeć: Mężczyzna
Lokalizacja: Frysztak
Pomógł: 28 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: dr_grucha » 26 lip 2008, o 17:11

No tak, mój błąd tutaj. Ale znalazłem inne mam nadzieje poprawne rozwiązanie. Załóżmy, że równość podana w zadaniu zachodzi. Skoro \(\displaystyle{ p _{1},p _{2},\ldots,p _{n}}\) są kolejnymi liczbami pierwszymi to \(\displaystyle{ p _{1} =2}\) więc:
\(\displaystyle{ 2\nmid p _{1}p _{2}\ldots p _{n}+1 \Longrightarrow 2\nmid a ^{l} \Longrightarrow 2\nmid a}\)
więc:
\(\displaystyle{ 4|(a-1)(a ^{l-1} + a ^{l-2}+\ldots +1) \Longrightarrow 4|p _{1}p _{2}\ldots p _{n}}\)
Sprzeczność.

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: Sylwek » 26 lip 2008, o 17:15

\(\displaystyle{ a \equiv 3 \ (mod 4) \ \ l \equiv 1 \ (mod 2)}\) ?

dr_grucha
Użytkownik
Użytkownik
Posty: 83
Rejestracja: 27 maja 2005, o 20:16
Płeć: Mężczyzna
Lokalizacja: Frysztak
Pomógł: 28 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: dr_grucha » 26 lip 2008, o 17:22

Chodzi o to, że jeżeli \(\displaystyle{ 2 \nmid a 2|a-1 2|a ^{l-1} + a ^{l-2} + \ldots + 1 4|(a-1)(a ^{l-1} + a ^{l-2} + \ldots + 1)}\)

Wasilewski
Użytkownik
Użytkownik
Posty: 3921
Rejestracja: 10 gru 2007, o 20:10
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 36 razy
Pomógł: 1194 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: Wasilewski » 26 lip 2008, o 17:26

Masz sumę l liczb nieparzystych, czyli chyba zależy od l, czy jest ona parzysta. A co do tego chińskiego twierdzenia o resztach, to nie można po prostu rozpatrywać:
\(\displaystyle{ a^{l} \equiv 1 (mod \ p_i)}\)
I skoro rozwiązaniem jest:
\(\displaystyle{ a^{l} = 1}\)
to otrzymujemy sprzeczność. Nie znam się na tym, zatem pytam, czy tak będzie poprawnie?
Sam sobie odpowiem; nie będzie, bo to tylko rozwiązanie z przedziału \(\displaystyle{ }\), czyli nie wyklucza rozwiązania: \(\displaystyle{ a^{l} = p_1p_2\ldots p_n +1}\)

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2711
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 155 razy
Pomógł: 654 razy

[Teoria liczb] Równanie z liczbami pierwszymi

Post autor: Sylwek » 27 lip 2008, o 16:55

OK, przedstawię ciekawe rozwiązanie - pokażemy, że równość nie może zachodzić. Pokażemy, że L nie może być wielokrotnością żadnej z \(\displaystyle{ p_1,...,p_n}\), nie wprost: \(\displaystyle{ L=kp_i}\), wówczas niech \(\displaystyle{ a^k=m}\), co za tym idzie mamy równość:
\(\displaystyle{ L=m^{p_i}=p_1...p_n+1=P}\), zapiszmy: \(\displaystyle{ m=qp_i+r}\), gdzie oczywiście: \(\displaystyle{ q qslant 1}\) i \(\displaystyle{ 1 qslant r qslant p_i-1}\).

Zatem: \(\displaystyle{ 1 \equiv P=L=m^{p_i} \equiv r^{p_i} \ (mod \ p_i)}\), z drugiej strony z MTF: \(\displaystyle{ r^{p_i} \equiv r \ (mod \ p_i)}\), zatem r=1 (ponieważ jest mniejsze od \(\displaystyle{ p_i}\)). Z drugiej strony:

\(\displaystyle{ m^{p_i}=(qp_i+1)^{p_{i}}=(qp_i)^{p_i}+{p_i \choose 1}(qp_i)^{p_i-1}+\ldots+{p_i \choose p_i-1}(qp_i)+1 \equiv 1 \ (mod \ p_i^2)}\), gdyż \(\displaystyle{ {p_i \choose t} \equiv 0 \ (mod p_i)}\) dla \(\displaystyle{ 0p_1...p_n+1=a^L}\) - sprzeczność

Zatem dla L>1 brak rozwiązań.

ODPOWIEDZ