Niepodzielność różnicy

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

Niepodzielność różnicy

Post autor: mol_ksiazkowy »

Udowodnić, że dla dowolnej liczby pierwszej \(\displaystyle{ p}\) istnieje liczba pierwsza \(\displaystyle{ q}\) taka, że \(\displaystyle{ n^p - p}\) nie dzieli się przez \(\displaystyle{ q}\) dla \(\displaystyle{ n=1, 2, 3,...}\)
Ukryta treść:    
Awatar użytkownika
Richard del Ferro
Użytkownik
Użytkownik
Posty: 190
Rejestracja: 13 mar 2016, o 22:48
Płeć: Mężczyzna
Podziękował: 9 razy
Pomógł: 16 razy

Niepodzielność różnicy

Post autor: Richard del Ferro »

Mamy
\(\displaystyle{ n ^{p} - p}\)
oraz
\(\displaystyle{ q}\)
Gdzie \(\displaystyle{ p,q}\) należą do do zbioru liczb pierwszych.

Zauważmy, że
Reszta z dzielenia
\(\displaystyle{ n^{p} -p}\)
Jest równa reszcie z dzielenia
\(\displaystyle{ n^{p}}\)
przez \(\displaystyle{ p}\)
A stąd już widać z MTF
\(\displaystyle{ n^{p}=n}\) mod \(\displaystyle{ p}\)
no więc ostatecznie
\(\displaystyle{ n^{p}-p=n}\) mod \(\displaystyle{ p}\)
Wiec reszta dzielenia naszej liczby przez \(\displaystyle{ p}\) to \(\displaystyle{ n}\)
Przykład?
\(\displaystyle{ 3^{7} - 7 = 2180}\)

\(\displaystyle{ 2180=2177+3=311 \cdot 7+3}\)

Mamy więc,
\(\displaystyle{ n^{p}-p=p \cdot k + n}\) dla ustalonego \(\displaystyle{ k}\) całkowitego.

Chcemy, aby \(\displaystyle{ q}\) nie dzieliło \(\displaystyle{ p \cdot k + n}\)

Reszty jeszcze nie wymyśliłem


ps :
zakładam, że \(\displaystyle{ p \neq q}\) w koncu to dwie różne literki, co za tym idzie są względnie pierwsze
Ostatnio zmieniony 5 sty 2018, o 22:35 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Niepodzielność różnicy

Post autor: arek1357 »

Oczywiście:

\(\displaystyle{ p}\) nie dzieli \(\displaystyle{ n^p-p}\) - a kto powiedział, że muszą być różne, a nawet można poszukać masę innych \(\displaystyle{ q}\) co tego nie dzielą zadanie głupie...
relic
Użytkownik
Użytkownik
Posty: 88
Rejestracja: 17 sty 2017, o 05:51
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 19 razy
Pomógł: 2 razy

Re: Niepodzielność różnicy

Post autor: relic »

\(\displaystyle{ n=1, 2, 3,...p,...}\)
DamianTancerz
Użytkownik
Użytkownik
Posty: 71
Rejestracja: 2 sty 2018, o 20:23
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 12 razy
Pomógł: 11 razy

Re: Niepodzielność różnicy

Post autor: DamianTancerz »

Co myślicie o tym:
Niech \(\displaystyle{ \frac{n^p - p}{q} = n}\)
\(\displaystyle{ n^p - p = nq}\)
\(\displaystyle{ n^{p-1} - \frac{p}{n} = q}\)

skoro \(\displaystyle{ p}\) jest liczbą pierwszą, to \(\displaystyle{ n^{p-1}}\) jest liczbą naturalną, a \(\displaystyle{ \frac{p}{n}}\) nie jest liczbą naturalną (dla \(\displaystyle{ n \neq 1}\) i \(\displaystyle{ n \neq p}\)) zatem ich różnica nie jest naturalna, a więc \(\displaystyle{ q}\) nie jest liczbą pierwszą.


Sprawdźmy jeszcze dla \(\displaystyle{ n = 1}\) - wtedy \(\displaystyle{ q < 1}\), nie jest liczbą pierwszą. Gdy \(\displaystyle{ n = p}\)
\(\displaystyle{ q = p^{p-1} - 1}\)
\(\displaystyle{ 1 = \frac{p^{p-1}}{q} - \frac{1}{q}}\)
Sprzeczność.
PoweredDragon
Użytkownik
Użytkownik
Posty: 817
Rejestracja: 19 lis 2016, o 23:48
Płeć: Mężczyzna
wiek: 21
Lokalizacja: Polska
Podziękował: 3 razy
Pomógł: 115 razy

Re: Niepodzielność różnicy

Post autor: PoweredDragon »

Pokazałeś, że \(\displaystyle{ n^p-p = nq}\) nie może zachodzić, ale może zachodzi \(\displaystyle{ n^p-p = (n+1)q}\)?
DamianTancerz
Użytkownik
Użytkownik
Posty: 71
Rejestracja: 2 sty 2018, o 20:23
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 12 razy
Pomógł: 11 razy

Re: Niepodzielność różnicy

Post autor: DamianTancerz »

PoweredDragon, Słuszna uwaga!

ale uzasadnienie jest analogiczne i na mocy indukcji matematycznej wszystko jest spoko.
Awatar użytkownika
Richard del Ferro
Użytkownik
Użytkownik
Posty: 190
Rejestracja: 13 mar 2016, o 22:48
Płeć: Mężczyzna
Podziękował: 9 razy
Pomógł: 16 razy

Re: Niepodzielność różnicy

Post autor: Richard del Ferro »

Panie Arkadiuszu co innego udowodnić, że sie nie dzieli a co innego wyznaczyć dokładną resztę z takiego dzielenia .

Damian Tancerz nie wiem skąd to wziąłeś, ponieważ ja dzieliłem przez \(\displaystyle{ p}\) a nie przez \(\displaystyle{ q}\).

Poza tym polecam rozważyć to zadanie najpierw zrozumieć o co chodzi.
Jeżeli wychodzi wam takie coś to juz coś nie gra, bo trzeba dowiesc, ze zawsze istnieje co najmniej jedna taka liczba PIERWSZA, czyli np. liczby \(\displaystyle{ 3,5,7}\) są mniejsze od \(\displaystyle{ n^{p}-p}\) ale tylko liczba \(\displaystyle{ 5}\) nie podzieli bez reszty.

Dodatkowo kto w ogole powiedzial, gdy\(\displaystyle{ p=n}\) to ta różnica jest naturalna.
PoweredDragon
Użytkownik
Użytkownik
Posty: 817
Rejestracja: 19 lis 2016, o 23:48
Płeć: Mężczyzna
wiek: 21
Lokalizacja: Polska
Podziękował: 3 razy
Pomógł: 115 razy

Re: Niepodzielność różnicy

Post autor: PoweredDragon »

Richard del Ferro pisze:...
1. DamianTancerz próbował uzasadnić, że \(\displaystyle{ n^{p} - p \neq nq}\) (czyli wykazał twoją tezę dla jednej z nieskończoności liczb)
2. Rozważył przypadek \(\displaystyle{ p=n}\) osobno. Faktycznie zrobił to jednak źle (nie wykazał sprzeczności, tylko stwierdził, że występuje)

Mamy pokazać, że
\(\displaystyle{ \forall_{n \in \mathbb N} \forall_{p \in \mathbb P} \exists_{q \in \mathbb P} q \nmid n^p-p}\)


Mam takie pytanko do bardziej ogarniających. Mamy prawo wzajemności reszt rzędów \(\displaystyle{ 2, 3, 4}\), mamy analogiczne prawa dla wyższych rzędów?
ODPOWIEDZ