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.
\(\displaystyle{ x= \frac{p}{q}}\) dla pewnych calkowitych dodatnich wzglednie pierwszych \(\displaystyle{ p,q}\). wobec tego istnieje taka funkcja \(\displaystyle{ h}\), że \(\displaystyle{ f(x)=h(p,q)}\). wstawiamy to drugiej rownosci, mnozymy stronami przez \(\displaystyle{ q}\) i dostajemy \(\displaystyle{ (p+q)h(p-q,q)=ph(p,q)}\). \(\displaystyle{ 1=(p,q)=(p+q,p)}\) więc \(\displaystyle{ p|h(p-q,q)}\). wstawiamy \(\displaystyle{ p:=p+q}\) i mamy \(\displaystyle{ p+q|h(p,q)}\) więc dla pewnej funkcji \(\displaystyle{ g}\) przyjmujacej wartosci w zbiorze liczb calkowitych zachodzi \(\displaystyle{ h(p,q)=(p+q)g(p,q)}\). wstawiamy to do obu rownosci z tresci zadania, skracamy co sie da i dostajemy \(\displaystyle{ g(p,q)=g(p-q,q)}\) (\(\displaystyle{ p>q}\))
oraz \(\displaystyle{ g(p,q)=g(q,p)}\)
dla pewnych calkowitych \(\displaystyle{ k,r}\) mamy \(\displaystyle{ p=kq+r}\) (\(\displaystyle{ 0 \le r<q)}\)) wiec \(\displaystyle{ g(p,q)=g(r,q)}\) powtarzamy te czynnosc tyle razy ile trzeba. to postepowanie jest analogiczne do tego w algorytmie Euklidesa, wiec wobec \(\displaystyle{ (p,q)=1}\) dostaniemy \(\displaystyle{ g(p,q)=g(X,1)=g(X-1,1)=...=g(1,1)=a \in Z}\)
wobec tego \(\displaystyle{ f( \frac{p}{q})=a(p+q)}\) dla calkowitego \(\displaystyle{ a}\)
XMaS11 pisze:No to 7.
Odpowiedź : \(\displaystyle{ n= \frac{p-1}{2}}\) .
Niech \(\displaystyle{ g}\) będzie generatorem mod p. Weźmy zbiór składający się z \(\displaystyle{ \frac{p-3}{2}}\) elementów : \(\displaystyle{ \lbrace g^2,g^2 \ldots , g^2 \rbrace}\) Oczywiście iloczyn elementów jakiegokolwiek jego podzbioru nie przystaje do 1 mod p, zatem \(\displaystyle{ n> \frac{p-3}{2}}\), czyli \(\displaystyle{ n \ge \frac{p-1}{2}}\) .
Z drugiej strony weźmy dowolny zbiór \(\displaystyle{ n= \frac{p-1}{2}}\) kwadratów: \(\displaystyle{ \lbrace a_1^2,a_2^2...a_n^2 \rbrace}\)
Rozważmy \(\displaystyle{ n}\) reszt mod p: \(\displaystyle{ a_1^2}\) \(\displaystyle{ a_1^2a_2^2}\) \(\displaystyle{ \cdots}\) \(\displaystyle{ a_1^2a_2^2\ldots a_n^2}\).
Jeśli któraś z nich jest jedynką mod p to jest ok, jeśli nie to pewne dwie przystają do siebie mod p, powiedzmy, ze są to reszty : \(\displaystyle{ (a_1a_2...a_k)^2}\) i \(\displaystyle{ (a_1a_2...a_m)^2}\) (\(\displaystyle{ m>k}\)).
Czyli: \(\displaystyle{ (a_1a_2...a_k)^2 \equiv (a_1a_2...a_m)^2 (p)}\) \(\displaystyle{ (a_1a_2...a_k)^2(a_{k+1}a_{k+2}...a_m-1) \equiv 0 (p)}\).
Skąd \(\displaystyle{ a_{k+1}a_{k+2}...a_m \equiv 1 (p)}\) czyli też jest ok.
Pod pojęciem generatora mam rozumieć resztę, której rząd mod p wynosi p-1?? Warto jednak udowodnić, że dla każdej liczby pierwszej taka reszta istnieje. Wynika to między innymi z tego że dowolna unormowana konguerencja wielomianowa mod p (p-liczba pierwsza) stopnia k ma co najwyżej k rozwiązań. Rozważamy wówczas konguerencje \(\displaystyle{ a^x - 1}\) przystaje do 0 mod p gdzie x jest dzielnikiem p-1 i wykorzystując wzór włączeń i wyłączeń udowadniamy że liczba ich rozwiązań (w Zp) jest mniejsza od p-1.
