szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 19 mar 2008, o 15:02 
Użytkownik
Avatar użytkownika

Posty: 666
Lokalizacja: Ustroń
Wyznaczyc wszystkie pary (n, p) liczb całkowitych dodatnich takie, ze
p jest liczba pierwsza,
n \leq 2p,
(p-1)^n + 1 dzieli sie przez n^{p-1}.
Góra
Mężczyzna Offline
PostNapisane: 22 mar 2008, o 13:51 
Użytkownik
Avatar użytkownika

Posty: 15
Lokalizacja: Kraków
Jesli masz tylko napisac ile takich par jest to raczej 'widac', ze bedzie ich nieskonczenie wiele, po prostu ciagle dawaj n=1

i wtedy:

\frac{p}{1} ...

edit: tak da sie rade wyznaczyc 'ambitniejsze' pary, moze byc tez (2,2) (3,3).. (korzystalem z przeksztalconego wzoru: n^(1 - p)�((p - 1)^n + 1))

nie wiele to pomoga, jak wpadne na cos bardziej ambitnego to dam znac
Góra
Mężczyzna Offline
PostNapisane: 22 mar 2008, o 15:44 
Użytkownik
Avatar użytkownika

Posty: 666
Lokalizacja: Ustroń
Hmmm... No w sumie racja, ale zadanie pochodzi z MOM więc wydaje mi się, że jakieś ambitniejsze pary też powinno się wyznaczyć. Ma ktoś pomysł jak to zrobić?
Góra
Mężczyzna Offline
PostNapisane: 2 mar 2009, o 20:22 
Gość Specjalny
Avatar użytkownika

Posty: 2643
Lokalizacja: Warszawa
Nie wiem, czy rozwiązałeś, czy nie, więc napiszę co mi się udało w szkole uzyskać.

Gdy p=2, to n \in \{1,2 \}, gdy n=1, to p jest dowolną liczbą pierwszą.

Niech zatem p \ge 3 \wedge n \ge 2, stąd: (p-1)^n+1 jest liczbą nieparzystą, czyli n^{p-1} też jest nieparzysta, więc: n=2a+1.

Rozpatrzmy najmniejszą liczbę pierwszą q dzielącą n (co za tym idzie najmniejszym dzielnikiem właściwym liczby n), czyli q też jest nieparzysta. Niech a będzie najmniejszą liczbą całkowitą dodatnią taką, że: (p-1)^a \equiv -1 \ (mod \ q), z tego wynika, że b=2a jest najmniejszą liczbą całkowitą dodatnią taką, że: (p-1)^{b} \equiv 1 \ (mod \ q) (czyli 2a jest rzędem p-1 modulo q). Ponieważ z Małego Twierdzenia Fermata zachodzi też: (p-1)^{q-1} \equiv 1 \ (mod \ q), to: q-1 \ge 2a \ \Rightarrow q>a.

Z drugiej strony: (p-1)^n \equiv - 1 \ (mod \ q), z tego łatwo wywnioskować, że: n=(2c+1)a, ale ponieważ a jest dzielnikiem n i jest mniejsze od najmniejszego dzielnika właściwego liczby n, to: a=1.

Stąd: (p-1)^a \equiv -1 \ (mod \ q) \ \Rightarrow q|p, a ponieważ obie te liczby są pierwsze, to: p=q.

Zostało nam znaleźć takie liczby pierwsze p \ge 3, że:
p^{p-1}|(p-1)^p+1. Dla p=3 jest OK, pokażemy, że dla wyższych liczb pierwszych już nie jest OK. Rozwijając lewą stronę ze wzoru dwumianowego Newtona: L=\alpha \cdot p^3 - \binom{p}{2}p^2+\binom{p}{1}p- \binom{p}{0}+1= \beta \cdot p^3+p^2, gdzie \alpha,\beta są całkowite.

Zatem mamy: p^{p-1}|(p-1)^p+1 \ \Rightarrow \ p^3 | \beta \cdot p^3+p^2 \ \Rightarrow \ p|1 - sprzeczność.

Odpowiedź: (p,n) \in \{ (p,1), \ (2,2), \ (3,3) \}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 (4 zadania) Sprawdz podzielność liczb przez 10  Anonymous  4
 Czy podana liczba jest różnicą kwadratów 2 liczb calko  pennywise  1
 Różnica cyfr pewnej liczby wynosi 5 ... Znajdź tę liczb  Tomasz B  4
 Zadanie z dowodem na sumę liczb naturalnych  scn  5
 podzielnosc liczb?  Anonymous  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl