Podzielność liczb o 1 mniejszych od potęgi 2
-
- 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
Znajdź wszystkie \(\displaystyle{ a}\) całkowite dodatnie, dla których zachodzi: \(\displaystyle{ a | 2^{a}-1}\).
-
- 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
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}\).
\(\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}\).
-
- 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
k ani a nie mogą być potęgami dwójki, skoro ich iloczyn daje liczbę nieparzystą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:
- arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzielność liczb o 1 mniejszych od potęgi 2
\(\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ą...
\(\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ą...
Pewnego rodzaju herezje...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.
-
- 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
no chyba nie do końca: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ą...
\(\displaystyle{ 2^{21}-1= 8^7-1=2097151}\)
co wygląda na podzielne przez 7 ...
- arek1357
- Użytkownik
- Posty: 5750
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podzielność liczb o 1 mniejszych od potęgi 2
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...
\(\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...