Wykładniki dwójki
- mol_ksiazkowy
- Użytkownik
- Posty: 11509
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3163 razy
- Pomógł: 749 razy
Wykładniki dwójki
Niech a będzie największą liczbą naturalną taką, że \(\displaystyle{ 5^n -3^n}\) dzieli się przez \(\displaystyle{ 2^a}\). I niech \(\displaystyle{ b}\) będzie największą liczbą naturalną taką, że \(\displaystyle{ 2^b \leq n}\). Udowodnić, że \(\displaystyle{ a \leq b+3}\).
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Wykładniki dwójki
To jest kolejne zadanko na Lifting the Exponent Lemma.
Jeśli \(\displaystyle{ n}\) jest nieparzyste, to \(\displaystyle{ v_2\left(5^n-3^n\right)=v_2(5-3)=1}\) i oczywiście wówczas postulowana nierówność zachodzi.
Jeśli \(\displaystyle{ n}\) jest parzyste, to \(\displaystyle{ v_2\left(5^n-3^n\right)=v_2(5-3)=v_2(5+3)+v_2(n)-1=v_2(n)+3}\). Pozostaje łatwa obserwacja, że
jeśli \(\displaystyle{ b}\) jest największą liczbą naturalną, dla której \(\displaystyle{ 2^b\le n}\), to \(\displaystyle{ v_2(n)\le b}\). Gdyby było inaczej, to \(\displaystyle{ v_2(n)>b}\), tj. \(\displaystyle{ v_2(n)\ge b+1}\), czyli \(\displaystyle{ 2^{b+1}>n\ge 2^{v_2(n)}\ge 2^{b+1}}\), a to jest sprzeczność.
Jeśli \(\displaystyle{ n}\) jest nieparzyste, to \(\displaystyle{ v_2\left(5^n-3^n\right)=v_2(5-3)=1}\) i oczywiście wówczas postulowana nierówność zachodzi.
Jeśli \(\displaystyle{ n}\) jest parzyste, to \(\displaystyle{ v_2\left(5^n-3^n\right)=v_2(5-3)=v_2(5+3)+v_2(n)-1=v_2(n)+3}\). Pozostaje łatwa obserwacja, że
jeśli \(\displaystyle{ b}\) jest największą liczbą naturalną, dla której \(\displaystyle{ 2^b\le n}\), to \(\displaystyle{ v_2(n)\le b}\). Gdyby było inaczej, to \(\displaystyle{ v_2(n)>b}\), tj. \(\displaystyle{ v_2(n)\ge b+1}\), czyli \(\displaystyle{ 2^{b+1}>n\ge 2^{v_2(n)}\ge 2^{b+1}}\), a to jest sprzeczność.