Podzielność i niepodzielność

[mol_ksiazkowy]

Udowodnić, że istnieje nieskończenie wiele \(\displaystyle{ n}\) takich, że \(\displaystyle{ n }\) dzieli \(\displaystyle{ 2^{2^n+1}+ 1}\), ale nie dzieli \(\displaystyle{ 2^n+1}\).

[arek1357]

my , że \(\displaystyle{ (2,n)=1}\)

z prostych przyczyn


załóżmy, że n nie dzieli \(\displaystyle{ 2^n+1}\)

ze wzoru teraz:

(*)\(\displaystyle{ 2^{2^n+1}+1=(2+1)(2^{2^n}-2^{2^n-1}+2^{2^n-2}-...+1)=3(2^{2^n}-2^{2^n-1}+2^{2^n-2}-...+1)}\)

załóżmy , że:

\(\displaystyle{ 2^n+1=k\varphi(n)+s , s< \varphi(n) , r=\varphi(n)}\)

\(\displaystyle{ \varphi(n)}\) - to ilość liczb względnie pierwszych z n...

rozpiszmy nawias duży w (*):

\(\displaystyle{ (1-2+2^2-...+2^{r-1})+2^r(1-2+2^2-...+2^{r-1})+2^{2r}(1-2+2^2-...+2^{r-1})+...+2^{k-1}(1-2+2^2-...+2^{r-1})+2^{2^n}-2^{2^n-1}+2^{2^n-2}-...+2^{2^n-(s-1)}= \sum_{i=0}^{k-1}2^{i-1} \frac{1-2^r}{3} +2^{2^n}\left[ 1-2^{-1}+2^{-2}-... \pm 2^{-(s-1)}\right] }\)

W pierwszej sumie\(\displaystyle{ 2^r=2^{\varphi(n)}=1 \mod n}\)

drugi nawias:

\(\displaystyle{ \left[ 1-2^{-1}+2^{-2}-... \pm 2^{-(s-1)}\right] = \frac{1-(-2^{-1})^s}{3} }\)

jeżeli teraz przyjmiemy dla pewnych n takich, że:

\(\displaystyle{ s=ord_{n}(-2^{-1})}\)

czyli będziemy wybierać właśnie takie n...

to wtedy:

\(\displaystyle{ (-2^{-1})^s=1 , s<\varphi(n)}\)


Więc prawa suma właśnie dla takich n może być równa zero modulo n...