zadania z l.pierszych

[vinci]

pisze ten topic jeszcze raz ostatnim razem gdzies go wyrombalo...

1. Pokazac ze dla kazdego naturalnego \(\displaystyle{ 561|a^{561}-a}\).

2. Znalezc wszystkie takie liczby pierwsze p, ze \(\displaystyle{ 4p^2+1}\) i \(\displaystyle{ 6p^2+1}\) sa rowniez liczbami pierwszymi.

3. Niech p, q,r beda liczbami pierwszymi, wiemy, ze \(\displaystyle{ p|qr-1}\), \(\displaystyle{ q|pr-1}\) i \(\displaystyle{ r|pq-1}\). Wyznaczyc wszystkie mozliwe wartosci \(\displaystyle{ pqr}\).

i jeszcze znalazlem takie:

4. p jest nieparzysta liczba pierwsza. Niech a, b, c, d beda liczbami calkowitymi niepodzielnymi przez p, takimi, ze {na/p}+{nb/p}+{nc/p}+{nd/p}=2 dla dowolnego n niepodzielnego przez p. udowdnic, ze istnieja przynajmniej dwie pary sposrod a, b, c, d takie ze ich suma jest podzielna przez p.

rozstrzal trudnosci tych zadan jest dosc duzy (szczegolnie miedzy pierwszymi trzema i czwartym)

[TomciO]

1.Poniewaz \(\displaystyle{ 561=3*11*17}\) wystarczy pokazac, ze \(\displaystyle{ a^561-a}\) dzieli sie przez \(\displaystyle{ 3, 11, 17}\). Mozemy tez zalozyc, ze \(\displaystyle{ a}\) nie dzieli sie przez zadna z tych liczb, poniewaz te liczby sa pierwsze musimy wtedy dowiesc, ze \(\displaystyle{ a^560-1}\) dzieli sie przez \(\displaystyle{ 3, 11, 17}\). Podzielnosc przez 3 jest prosta, kwadrat liczby naturalnej w dzieleniu przez 3 daje reszte 1. Do podzielnosci przez 11 uzyjemy Malego Twierdzenia Fermata. Wiadomo, ze:
\(\displaystyle{ 11|a^{10}-1}\)
czyli inaczej
\(\displaystyle{ a^{10} \equiv 1 mod 11}\)
a wiec rowniez
\(\displaystyle{ a^{560} \equiv 1 mod 11}\)
Dla 17 sprawa ma sie identycznie bo 17|560.

2. Modulo 5, nie chce mi sie pisac : P.

3. To jest najciekawsze z tych trzech zdecydowanie, ale moje rozwiazanie jest brzydkie (o ile sie nigdzie nie pomylilem i jest w ogole poprawne).

Niech \(\displaystyle{ qr-1=pa, pq-1=rb, pr-1=qc}\). Zauwazmy po pierwsze, ze \(\displaystyle{ p, q, r}\) sa rozne. Teraz, niech bez straty ogolnosci \(\displaystyle{ p}\) bedzie najmniejsza z nich. Po odrobinie prostej algebry latwo otrzymujemy rownosci:
\(\displaystyle{ r(p^2-bc)=p+c}\) *
\(\displaystyle{ q(p^2-bc)=p+b}\)
Z ktorejkolwiek z tych rownosci widzimy, ze musi byc \(\displaystyle{ p^2-bc > 0}\), gdyz prawa strona w tych rownosciach jest dodatnia. Oznacza to, ze zachodzi przynajmniej jedna z nierownosci: \(\displaystyle{ p q b}\) lub \(\displaystyle{ p q c}\). Niech wiec, np. \(\displaystyle{ p q c}\). Zalozmy tez na razie, ze \(\displaystyle{ p^2-bc q 2}\). Mamy wtedy (ze wzgledu na minimalnosc p):
\(\displaystyle{ p+c q 2p < 2r q (p^2-bc)r}\)
czyli sprzecznosc. Stad \(\displaystyle{ p^2-bc=1}\), czyli tez (z rownosci *):
\(\displaystyle{ r = p+c}\)
\(\displaystyle{ q = p+b}\)
Wstawiajac to wszystko do rownania \(\displaystyle{ qr-1 = pa}\) oraz pamietajac o tym, ze \(\displaystyle{ p^2 = bc + 1}\) dostajemy:
\(\displaystyle{ p(2p+b+c-a)=2}\)
Czyli \(\displaystyle{ p|2}\) a poniewaz p jest pierwsze to \(\displaystyle{ p=2}\). Dalej juz bardzo latwo otrzymac, ze pozostale 2 liczby to 3 i 5. Uwalniajac sie od zalozenia co do minimalnosci \(\displaystyle{ p}\) otrzymujemy, ze odpowiedz to \(\displaystyle{ (p, q, r) = (2, 3, 5)}\) i permutacje.

[półpasiec]

popraw tresc czwartego, bo teraz w ogole nie wiadomo o co chodzi

[_el_doopa]

3) troche inaczej prosciej:
bez straty ogolnosci: \(\displaystyle{ p>q>r}\)
\(\displaystyle{ pqr|(pq-1)(qr-1)(rp-1)}\)
zatem
\(\displaystyle{ pqr|pq+qr+rp-1}\)
musi byc
\(\displaystyle{ pqr\le pq+qr+rp-1}\)

[vinci]

teraz dobrze? {x} - czesc ulamkowa

[ Dodano: Sob Gru 24, 2005 11:47 pm ]
zeby bylo ze tez cos zrobilem...

2. zapiszmy p w postaci: \(\displaystyle{ p=5k+r}\), gdzie \(\displaystyle{ r\in{{0,1,2,3,4}}}\)
\(\displaystyle{ a=4p^2+1}\)
\(\displaystyle{ b=6p^2+1}\)

\(\displaystyle{ a=100k^2+40kr+4r^2+1}\)
\(\displaystyle{ b=150k^2+60kr+6r^2+1}\)
rozwazamy \(\displaystyle{ p\equiv r(mod5)}\)
patrzymy jakie wartoscie modulo 5 przyjmuje a, b dla roznych r
wychodzi, ze tylko jedna liczba sposrod a, b, p jest podzielna przez 5.
p jest liczba pierwsza:
p>=2
a>5
b>5
zatem p=5
wtedy a=101 i b=151

[Gobol]

Co do pierwszego to z tego co pamiętam to można indukcyjnie udowodnić że
\(\displaystyle{ p|n^{p}-n}\) dla dowolnej liczby pierwszej.

[TomciO]

A 561 to jest pierwsza? Bo chyba niebardzo... ale oczywiscie to twierdzenie wystarczy do zrobienia tego zadania (a udowadniac go wcale nie trzeba bo je zna kazdy).

[juzef]

można znaleźć ciekawostkę mającą związek z pierwszym zadaniem.