Prosta podzielność

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: 11265
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Prosta podzielność

Post autor: mol_ksiazkowy »

Udowodnić, że gdy \(\displaystyle{ n>1}\) to \(\displaystyle{ 3^n-1}\) nie dzieli się przez \(\displaystyle{ 2^n-1}\)
Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 166 razy

Re: Prosta podzielność

Post autor: Poszukujaca »

Nie wiem, czy to co napiszę się do czegoś przyda, ale kto wie.

\(\displaystyle{ 3^{n}-1= (3-1)(3^{n-1}+3^{n-2}+3^{n-3}+...+3+1)= 2 \cdot \sum_{i=1}^{n-1}3^{i}}\)

\(\displaystyle{ 2^{n}-1=(2-1)(2^{n-1}+2^{n-2}+2^{n-3}+...+2+1)= \sum_{i=1}^{n-1} 2^{i}}\)
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: Prosta podzielność

Post autor: PoweredDragon »

@UP
W jaki sposób suma liczb parzystych i nieparzystej stała się parzysta, a liczba niepodzielna przez 3 jest podzielna przez 3? Sumowanie powinno się rozpocząć od \(\displaystyle{ i = 0}\).

Załóżmy, że podzielność zachodzi:
\(\displaystyle{ n}\) nie może być postaci \(\displaystyle{ 2k}\), bo wtedy podzielność nie mogłaby zachodzić (\(\displaystyle{ 2^n-1}\) byłoby podzielne przez \(\displaystyle{ 3}\), a \(\displaystyle{ 3^n-1}\) już nie)
Z postu wyżej wynika, że \(\displaystyle{ \frac{3^{2k}+3^{2k-1}+...+3^1 + 3^0}{2^{2k}+2^{2k-1}+...+2^1+2^0} \in\mathbb Z}\) (w świetle założeń)

Trzebaby przeanalizować wyrażenie wyżej modularnie i rozpatrzeć takie moduły, żeby mianownik był równy zero, a licznik niezerowy...
Ostatnio zmieniony 28 sie 2017, o 16:00 przez PoweredDragon, łącznie zmieniany 2 razy.
Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 166 razy

Re: Prosta podzielność

Post autor: Poszukujaca »

PoweredDragon pisze:@UP
W jaki sposób suma liczb parzystych i nieparzystej stała się parzysta, a liczba niepodzielna przez 3 jest podzielna przez 3? Sumowanie powinno się rozpocząć od \(\displaystyle{ i = 0}\).
Tak, oczywiście. Z rozmachu napisałam. Dzięki!
Hydra147
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 31 mar 2013, o 20:23
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz
Pomógł: 82 razy

Prosta podzielność

Post autor: Hydra147 »

Jeśli \(\displaystyle{ n}\) jest parzyste, to \(\displaystyle{ 2^n-1}\) dzieli się przez trzy, a \(\displaystyle{ 3^n-1}\) nie. Jeśli jest nieparzyste, to \(\displaystyle{ 2^n-1}\) daje resztę minus pięć z dzielenia przez dwanaście. Jednak wszystkie liczby pierwsze poza dwójką i trójką (a one wspomnianej wyżej liczby nie dzielą) dają reszty plus minus jeden i plus minus pięć z dzielenia przez dwanaście. Zatem istnieje jakaś liczba pierwsza \(\displaystyle{ p|2^n-1}\) i dająca resztę pięć lub minus pięć z dzielenia przez dwanaście. Ale wówczas trzy nie jest resztą kwadratową modulo \(\displaystyle{ p}\). Gdyby jednak owa podzielność zachodziła, to \(\displaystyle{ p|3^n-1}\), czyli \(\displaystyle{ (3^{ \frac{n+1}{2} })^2=3(mod p)}\), czyli trzy jednak jest resztą i sprzeczność.
ODPOWIEDZ