Potęga trójki
- mol_ksiazkowy
- Użytkownik
- Posty: 11480
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3158 razy
- Pomógł: 749 razy
Potęga trójki
Udowodnić, że jeśli \(\displaystyle{ 1+2^n+4^n = p}\) jest liczbą pierwszą , to \(\displaystyle{ n}\) jest potęgą trójki (tj. \(\displaystyle{ n=3^k}\)), gdzie \(\displaystyle{ k}\) jest liczbą naturalną)
- 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: Potęga trójki
Niech:
(*) \(\displaystyle{ 1+2^n+4^{2n}=1+2^n+2^{2n}= \frac{2^{3n}-1}{2^n-1}=p }\)
dla:
\(\displaystyle{ n=1}\)
\(\displaystyle{ 1+2+2^2=7 }\) mamy: \(\displaystyle{ n=3^0=1}\)
dla:
\(\displaystyle{ n=3, k=1}\) mamy:
\(\displaystyle{ 1+2^3+2^6=73 }\) - liczba pierwsza
załóżmy, że:
\(\displaystyle{ k>1 }\) dla bezpieczeństwa
przejdźmy z powrotem do (*) i rozłóżmy go na czynniki:
\(\displaystyle{ \frac{2^{3n}-1}{2^n-1}=}\)
załóżmy, że:
\(\displaystyle{ n=s3^r }\)
\(\displaystyle{ \frac{2^{3n}-1}{2^n-1}= \frac{2^{3s3^r}-1}{2^{s3^r}-1}= \frac{\left( 2^{3 \cdot 3^r}-1\right)\left[\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1\right] }{\left( 2^{3^r}-1\right)\left[ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] }= \frac{\left[ \left( 2^{3^r}\right)^2+2^{3^r}+1 \right] \left( 2^{3^r}-1\right)\left[\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1\right] }{\left( 2^{3^r}-1\right)\left[ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] }= }\)
\(\displaystyle{ =\frac{\left[ \left( 2^{3^r}\right)^2+2^{3^r}+1 \right] \left[\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1\right] }{\left[ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] }}\)
łatwo też zauważyć, że:
\(\displaystyle{ NWD\left[ \left( 2^{3^r}\right)^2+2^{3^r}+1 , \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] =1 }\)
Stosując choćby algorytm Euklidesa...
musi więc:
\(\displaystyle{ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 | \left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1}\)
Widać, że w wyniku tego podziału, gdy: \(\displaystyle{ s>1}\) powstanie liczba większa od jeden, np: \(\displaystyle{ a>1}\)
czyli mamy:
\(\displaystyle{ 1<a= \frac{\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1}{ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1}}\)
otrzymamy:
\(\displaystyle{ p= \left[ \left( 2^{3^r}\right)^2+2^{3^r}+1\right] \cdot a, a>1}\)
a powinno być jeden
dzieli się to tylko wtedy gdy \(\displaystyle{ s=1 \Rightarrow a=1}\)
więc:
\(\displaystyle{ n=s \cdot 3^r=1 \cdot 3^r=3^r}\)
cnd...
(*) \(\displaystyle{ 1+2^n+4^{2n}=1+2^n+2^{2n}= \frac{2^{3n}-1}{2^n-1}=p }\)
dla:
\(\displaystyle{ n=1}\)
\(\displaystyle{ 1+2+2^2=7 }\) mamy: \(\displaystyle{ n=3^0=1}\)
dla:
\(\displaystyle{ n=3, k=1}\) mamy:
\(\displaystyle{ 1+2^3+2^6=73 }\) - liczba pierwsza
załóżmy, że:
\(\displaystyle{ k>1 }\) dla bezpieczeństwa
przejdźmy z powrotem do (*) i rozłóżmy go na czynniki:
\(\displaystyle{ \frac{2^{3n}-1}{2^n-1}=}\)
załóżmy, że:
\(\displaystyle{ n=s3^r }\)
\(\displaystyle{ \frac{2^{3n}-1}{2^n-1}= \frac{2^{3s3^r}-1}{2^{s3^r}-1}= \frac{\left( 2^{3 \cdot 3^r}-1\right)\left[\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1\right] }{\left( 2^{3^r}-1\right)\left[ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] }= \frac{\left[ \left( 2^{3^r}\right)^2+2^{3^r}+1 \right] \left( 2^{3^r}-1\right)\left[\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1\right] }{\left( 2^{3^r}-1\right)\left[ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] }= }\)
\(\displaystyle{ =\frac{\left[ \left( 2^{3^r}\right)^2+2^{3^r}+1 \right] \left[\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1\right] }{\left[ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] }}\)
łatwo też zauważyć, że:
\(\displaystyle{ NWD\left[ \left( 2^{3^r}\right)^2+2^{3^r}+1 , \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 \right] =1 }\)
Stosując choćby algorytm Euklidesa...
musi więc:
\(\displaystyle{ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1 | \left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1}\)
Widać, że w wyniku tego podziału, gdy: \(\displaystyle{ s>1}\) powstanie liczba większa od jeden, np: \(\displaystyle{ a>1}\)
czyli mamy:
\(\displaystyle{ 1<a= \frac{\left( 2^{3 \cdot 3^r}\right)^{s-1} +\left( 2^{3 \cdot 3^r}\right)^{s-2}+...+1}{ \left(2^{3^r} \right)^{s-1}+ \left(2^{3^r} \right)^{s-2}+...+1}}\)
otrzymamy:
\(\displaystyle{ p= \left[ \left( 2^{3^r}\right)^2+2^{3^r}+1\right] \cdot a, a>1}\)
a powinno być jeden
dzieli się to tylko wtedy gdy \(\displaystyle{ s=1 \Rightarrow a=1}\)
więc:
\(\displaystyle{ n=s \cdot 3^r=1 \cdot 3^r=3^r}\)
cnd...