Podzielność liczb o 1 mniejszych od potęgi 2

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
kacper01
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 23 maja 2018, o 18:06
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy

Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: kacper01 »

Znajdź wszystkie \(\displaystyle{ a}\) całkowite dodatnie, dla których zachodzi: \(\displaystyle{ a | 2^{a}-1}\).
PieknoMatematyki
Użytkownik
Użytkownik
Posty: 61
Rejestracja: 6 sty 2019, o 05:46
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 13 razy

Re: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: PieknoMatematyki »

Domyślam się, ze chodziło o:
\(\displaystyle{ a | \left( 2^{a}-1\right)}\)

Dla jedynki działa, teraz sprawdźmy większe liczby:

\(\displaystyle{ 2^a - 1 = k \cdot a}\)
Pokażemy, że nie istnieje takie naturalne\(\displaystyle{ k}\), które spełnia to równanie:


zatem \(\displaystyle{ k}\) i \(\displaystyle{ a+1}\) muszą być jednocześnie potęgami dwójki, takimi że:
\(\displaystyle{ a = 2^p - 1}\) i \(\displaystyle{ k = 2^q}\), gdzie \(\displaystyle{ q+p = a}\)
( \(\displaystyle{ p}\) dodatnie z założenia \(\displaystyle{ a > 0}\), \(\displaystyle{ q}\) dodatnie, bo \(\displaystyle{ 2^a > a+1}\))

\(\displaystyle{ 2^a - 1 = 2^q \cdot 2^p - 2^q \\ 2^a = 2^q \cdot 2^p - 2^q + 1 \\ 2^a = 2^a \left( 2^{-p} 2^{-q} - 2^{-p} + \frac{1}{2^a}\right)}\)

\(\displaystyle{ \left( 2^{-p} 2^{-q} - 2^{-p} + \frac{1}{2^a}\right) = 1}\) co jest nieprawdą. Zatem nie istnieje takie \(\displaystyle{ k}\).

Czyli jest tylko jedno takie \(\displaystyle{ a}\) i jest równe \(\displaystyle{ 1}\).
pasman
Użytkownik
Użytkownik
Posty: 171
Rejestracja: 26 lut 2016, o 17:32
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 14 razy

Re: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: pasman »

PieknoMatematyki pisze:Domyślam się, ze chodziło o:
\(\displaystyle{ a | \left( 2^{a}-1\right)}\)

Dla jedynki działa, teraz sprawdźmy większe liczby:

\(\displaystyle{ 2^a - 1 = k \cdot a}\)
Pokażemy, że nie istnieje takie naturalne\(\displaystyle{ k}\), które spełnia to równanie:


zatem \(\displaystyle{ k}\) i \(\displaystyle{ a+1}\) muszą być jednocześnie potęgami dwójki, takimi że:
k ani a nie mogą być potęgami dwójki, skoro ich iloczyn daje liczbę nieparzystą
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: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: arek1357 »

\(\displaystyle{ n>2}\)

\(\displaystyle{ n}\)- nieparzyste musi być,

\(\displaystyle{ p>2 , p|n}\)

\(\displaystyle{ p}\) - liczba pierwsza

niech:

\(\displaystyle{ n=pk}\)

\(\displaystyle{ 2^n-1=2^{pk}-1=\left( 2^k\right)^p-1}\)

niech.: \(\displaystyle{ a=2^k}\)

musiałoby być:

\(\displaystyle{ p|a^p-1}\)

co jest nieprawdą...

zatem \(\displaystyle{ k i a+1}\) muszą być jednocześnie potęgami dwójki, takimi że:
\(\displaystyle{ a = 2^p - 1 i k = 2^q,}\) gdzie \(\displaystyle{ q+p = a}\)
( \(\displaystyle{ p}\) dodatnie z założenia \(\displaystyle{ a > 0, q}\) dodatnie, \(\displaystyle{ bo 2^a > a+1}\))

\(\displaystyle{ 2^a - 1 = 2^q \cdot 2^p - 2^q \\ 2^a = 2^q \cdot 2^p - 2^q + 1 \\ 2^a = 2^a \left( 2^{-p} 2^{-q} - 2^{-p} + \frac{1}{2^a}\right)

\left( 2^{-p} 2^{-q} - 2^{-p} + \frac{1}{2^a}\right) = 1}\)


co jest nieprawdą. Zatem nie istnieje takie k.
Pewnego rodzaju herezje...
pasman
Użytkownik
Użytkownik
Posty: 171
Rejestracja: 26 lut 2016, o 17:32
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 14 razy

Re: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: pasman »

arek1357 pisze:\(\displaystyle{ n>2}\)

\(\displaystyle{ n}\)- nieparzyste musi być,

\(\displaystyle{ p>2 , p|n}\)

\(\displaystyle{ p}\) - liczba pierwsza

niech:

\(\displaystyle{ n=pk}\)

\(\displaystyle{ 2^n-1=2^{pk}-1=\left( 2^k\right)^p-1}\)

niech.: \(\displaystyle{ a=2^k}\)

musiałoby być:

\(\displaystyle{ p|a^p-1}\)

co jest nieprawdą...
no chyba nie do końca:

\(\displaystyle{ 2^{21}-1= 8^7-1=2097151}\)

co wygląda na podzielne przez 7 ...
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: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: arek1357 »

Masz rację zasugerowałem się małym tw. Fermata i za szybko wyciągnąłem wnioski
pasman
Użytkownik
Użytkownik
Posty: 171
Rejestracja: 26 lut 2016, o 17:32
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 14 razy

Re: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: pasman »

małe twierdzenie Fermata wygląda na dobry trop.
może autor zadania coś podpowie?
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: Podzielność liczb o 1 mniejszych od potęgi 2

Post autor: arek1357 »

Ale to jest do uratowania , trzeba wziąć p jako najmniejszy pierwszy dzielnik liczby n...

\(\displaystyle{ p>2}\)

niech też:

\(\displaystyle{ d=NWD(n,p-1)}\)

I teraz:

niech:

\(\displaystyle{ p|2^n-1}\)

Musi być jak wiadomo z m.t.F.

\(\displaystyle{ p|2^{p-1}-1}\)

stąd mamy:

\(\displaystyle{ p|2^d-1}\)

ale z warunków wyjdzie, że \(\displaystyle{ d=1}\)

czyli: \(\displaystyle{ p|1}\)

Sprzeczność...

No właśnie nie dopatrzyłem, że branie dowolnego \(\displaystyle{ p}\) nie musi doprowadzić do sprzeczności...
ODPOWIEDZ