Školjka

%V0 Uvjet zadatka je ekvivalentan sa $$ 2^n \equiv -1 \enspace (mod\enspace n^2)$$ Neka je $p>2$ najmanji prosti djelitelj broja $n$. Broj $p$ nije $2$ jer tada ne dijeli $2^n+1$ Vrijedi $$2^{2n} \equiv 1 \enspace (mod\enspace p)$$ Odnosno kako vrijedi $2^{p-1} \equiv 1 \enspace (mod\enspace p)$ imamo i $2^{gcd(p-1,2n)} \equiv 1 \enspace (mod\enspace p)$. Kako $p|n$ i $p$ je najmanji takav slijedi da $gcd(p-1,n)=1$ pa zatim $gcd(p-1,2n)=2 \Rightarrow$ $$2^2 \equiv 4 \equiv 1 \enspace (mod \enspace p) \Rightarrow p=3 $$ Odnosno $n=3^kl$ za neki $k\in \mathbb{N}$ tj. sada vrijedi $$3^{2k} | 2^{3^k}+1 \iff 9^k | 2^{3^k}+1 $$ Posmatrajmo $v_3(2^n+1)=v_3(2+1)+v_3(n)=k+1$ ali s druge strane je $v_3(n^2)=2k$ dakle $k=1$ odnosno $n=3l$ $l=1$ nas dovodi do rijesenja $n=3$ Pretpostavimo tada da $l>1$ i neka je $q>3$ najmanji prosti djelitelj od $l$. Tada imamo $2^n \equiv 8^l \equiv -1 \pmod{q}$ odnosno $8^{2l}\equiv 1 \pmod{q}$ što uz $8^{p-1}\equiv 1 \pmod{q}$ daje $$8^{gcd(q-1,2l)}\equiv 64 \equiv 1 \pmod{q}$$ dakle $q|63 \Rightarrow q=7$ Ali $2^{3l}+1 \equiv 8^l+1 \equiv 2 \pmod{7}$ što vodi u kontradikciju jer s druge strane $q|2^{3l}+1$ Dakle takav $l>1$ ne postoji i jedino rijesenje je $$n=3$$