Następny dzielnik

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Następny dzielnik

Post autor: mol_ksiazkowy »

:arrow: Liczba \(\displaystyle{ n}\) ma tę własność, że jeśli jest podzielna przez \(\displaystyle{ d}\), to \(\displaystyle{ n+1}\) jest podzielna przez \(\displaystyle{ d+1}\). Udowodnić, że \(\displaystyle{ n}\) jest liczbą pierwszą.

Ukryta treść:    
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Następny dzielnik

Post autor: a4karo »

Przypuśćmy, że `n=pq`, gdzie `p,q\ne 1`.

Jeżeli `p=q`, to `p+1|n+1=p^2+1`, a to jest niemożliwe, bo \(\displaystyle{ \frac{p^2+1}{p+1}=\frac{p^2+2p+1-2p-2+2}{p+1}=p-1+\frac{2}{p+1}}\)
Możemy przyjąć zatem, że `p<q`. Wtedy dla pewnego naturalnego `k` zachodzi `n+1=(q+1)k`.
Jeżeli `k\le p-1`, to `n+1=(q+1)k\le (q+1)(p-1)=pq+p-q+1<pq+1=n+1`
Jeżeli zaś `k\ge p`, to `n+1=(q+1)k\ge (q+1)p=qp+p>qp+1>n+1`
Zatem żaden z tych warunków nie może zachodzić. CBDO
ODPOWIEDZ