Neocijenjeno
16. ožujka 2018. 08:22 (6 godine, 4 mjeseci)
Determine all integers
![n > 1](/media/m/c/8/9/c8999d29e042cf52e485c7a7b7301b0a.png)
such that
is an integer.
%V0
Determine all integers $n > 1$ such that
$$\frac {2^n + 1}{n^2}$$
is an integer.
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Uvjet zadatka je ekvivalentan sa
![2^n \equiv -1 \enspace (mod\enspace n^2)](/media/m/b/2/5/b255ce1eb865ab30ce245386536d098b.png)
Neka je
![p>2](/media/m/7/4/c/74cac2be359b29114e872b34bebfb11b.png)
najmanji prosti djelitelj broja
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
. Broj
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
nije
![2](/media/m/e/e/e/eeef773d19a3b3f7bdf4c64f501e0291.png)
jer tada ne dijeli
![2^n+1](/media/m/d/c/6/dc6604b76ccd8037db5e25d3d709e1d5.png)
Vrijedi
![2^{2n} \equiv 1 \enspace (mod\enspace p)](/media/m/8/9/2/892b74b0eaa3578ff7a5464b83ba31b4.png)
Odnosno kako vrijedi
![2^{p-1} \equiv 1 \enspace (mod\enspace p)](/media/m/8/e/c/8ecd46bcffefb5a50ded6f606436244a.png)
imamo i
![2^{gcd(p-1,2n)} \equiv 1 \enspace (mod\enspace p)](/media/m/6/7/5/67592cd28a23cdbb1c5fddce80a0e371.png)
. Kako
![p|n](/media/m/4/e/7/4e7dd12833ce64240e39b8ddd1317a26.png)
i
![p](/media/m/1/c/8/1c85c88d10b11745150467bf9935f7de.png)
je najmanji takav slijedi da
![gcd(p-1,n)=1](/media/m/3/9/6/396d99694e9082a31a61905de20862eb.png)
pa zatim
![2^2 \equiv 4 \equiv 1 \enspace (mod \enspace p) \Rightarrow p=3](/media/m/5/a/3/5a3e320536b18410514472d0b3720012.png)
Odnosno
![n=3^kl](/media/m/6/0/8/608312483b3990d18b95cc09c239b034.png)
za neki
![k\in \mathbb{N}](/media/m/3/4/a/34ab69e5b15d1d2848a2375453133270.png)
tj. sada vrijedi
![3^{2k} | 2^{3^k}+1 \iff 9^k | 2^{3^k}+1](/media/m/a/9/8/a9895bce570207a7e124366ce31364ee.png)
Posmatrajmo
![v_3(2^n+1)=v_3(2+1)+v_3(n)=k+1](/media/m/5/d/2/5d2f241cdbe1635ecec71ee9c0d1a22a.png)
ali s druge strane je
![v_3(n^2)=2k](/media/m/3/e/9/3e93d558b9246dbec71786db0d83589c.png)
dakle
![k=1](/media/m/f/7/1/f71077af98878d94ee3faacc57dd14b5.png)
odnosno
![n=3l](/media/m/3/7/0/370651fef47e329e9242a4f2a62a3d18.png)
![l=1](/media/m/7/1/a/71a9c1f0e7cbb73f77760471cd139a81.png)
nas dovodi do rijesenja
![n=3](/media/m/6/e/8/6e8cc663572ec564892ed13a28debcb1.png)
Pretpostavimo tada da
![l>1](/media/m/8/7/0/870c6f68fc877eebbf74714debebf5e9.png)
i neka je
![q>3](/media/m/2/5/0/250e0d0123965f11756563c8530d2b85.png)
najmanji prosti djelitelj od
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
.
Tada imamo
![2^n \equiv 8^l \equiv -1 \pmod{q}](/media/m/3/2/1/321c2301ca7294cd8d1a4a8139d220ff.png)
odnosno
![8^{2l}\equiv 1 \pmod{q}](/media/m/a/e/e/aeef4261a9b250d974fdb931ab99e7a4.png)
što uz
![8^{p-1}\equiv 1 \pmod{q}](/media/m/8/2/5/825f688c4b9394a8e650d62e244dbffd.png)
daje
![8^{gcd(q-1,2l)}\equiv 64 \equiv 1 \pmod{q}](/media/m/d/b/7/db7f3a1a955975373fab48773d6a6c0b.png)
dakle
![q|63 \Rightarrow q=7](/media/m/7/d/2/7d2f657fabe450ff55a0d3e993b74047.png)
Ali
![2^{3l}+1 \equiv 8^l+1 \equiv 2 \pmod{7}](/media/m/e/0/2/e02a9769574b8f6ac22215bcaddd0946.png)
što vodi u kontradikciju jer s druge strane
![q|2^{3l}+1](/media/m/e/6/6/e66eb06f48abbf48d6631f761eb32f8d.png)
Dakle takav
![l>1](/media/m/8/7/0/870c6f68fc877eebbf74714debebf5e9.png)
ne postoji i jedino rijesenje je
%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$$