5. Zadatak

Prvo rješenje.

Neka je $p=101$. Označimo s $\nu_p(k)$ najveći nenegativan cijeli broj $t$ takav da $p^t$ dijeli $k$. Tada vrijedi

$$\nu_p(n!)=\left\lfloor\frac np\right\rfloor +\left\lfloor\frac n{p^2}\right\rfloor +\left\lfloor\frac n{p^3}\right\rfloor +\ldots +\left\lfloor\frac n{p^s}\right\rfloor$$

gdje je $s$ najveći cijeli broj takav da je $p^s\le n$, jer za svaki $j=1,2,\ldots,s$ postoji točno $\left\lfloor\frac n{p^j}\right\rfloor$ brojeva manjih ili jednakih $n$ koji su djeljivi s $p^j$.

Uvjet da su brojevi $m$ i $n$ prijatelji je ekvivalentan s

$$m\cdot\left( \left\lfloor\frac np\right\rfloor +\left\lfloor\frac n{p^2}\right\rfloor +\left\lfloor\frac n{p^3}\right\rfloor+\ldots \right) =n\cdot\left( \left\lfloor\frac mp\right\rfloor +\left\lfloor\frac m{p^2}\right\rfloor +\left\lfloor\frac m{p^3}\right\rfloor+\ldots \right).$$

Primijetimo da vrijedi

$$\begin{aligned} \left\lfloor\frac np\right\rfloor +\left\lfloor\frac n{p^2}\right\rfloor +\left\lfloor\frac n{p^3}\right\rfloor +\ldots +\left\lfloor\frac n{p^s}\right\rfloor &\le \frac np+\frac n{p^2}+\frac n{p^3}+\ldots+\frac n{p^s}\\ &=\frac np\cdot\frac{1-\frac1{p^{s+1}}}{1-\frac1p} <\frac n{p-1}<n. \end{aligned}$$

Neka je sada $n$ prost broj s točno $12$ prijatelja. Ako je $n<101$, onda je svaki broj $m<101$ prijatelj od $n$, kontradikcija. Ako je $n\ge101$ i $m$ njegov prijatelj, onda slijedi da $n$ dijeli $m$, jer dijeli

$$m\cdot\left( \left\lfloor\frac np\right\rfloor +\left\lfloor\frac n{p^2}\right\rfloor +\left\lfloor\frac n{p^3}\right\rfloor+\ldots \right),$$

a drugi faktor je manji od $n$. Dakle, $m=kn$ za neki prirodan broj $k$, te vrijedi

$$k\cdot\left( \left\lfloor\frac np\right\rfloor +\left\lfloor\frac n{p^2}\right\rfloor +\left\lfloor\frac n{p^3}\right\rfloor+\ldots \right) =\left\lfloor\frac{kn}{p}\right\rfloor +\left\lfloor\frac{kn}{p^2}\right\rfloor +\left\lfloor\frac{kn}{p^3}\right\rfloor+\ldots.$$

Kako je $\lfloor a+b\rfloor\le\lfloor a\rfloor+\lfloor b\rfloor$ za sve pozitivne realne brojeve $a$ i $b$ uz jednakost ako i samo ako je , slijedi da za sve $j$ treba vrijediti

$$k\left\lfloor\frac n{p^j}\right\rfloor=\left\lfloor\frac{kn}{p^j}\right\rfloor.$$

Ta jednakost pak vrijedi ako i samo ako $n$ pri dijeljenju s $p^j$ daje ostatak manji od $\frac{p^j}{k}$.

Slijedi da, ako su $n$ i $(k+1)\cdot n$ prijatelji, onda su i $n$ i $kn$ prijatelji, odnosno skup prijatelja od $n$ sastoji se od prvih nekoliko višekratnika od $n$.

Dakle, prost broj $n$ ima $12$ prijatelja ako i samo ako mu je $13n$ prijatelj i $14n$ nije prijatelj.

Broj $13n$ mu je prijatelj ako i samo ako je ostatak koji $n$ daje pri dijeljenju s $p^j$ manji od $\frac{p^j}{13}$ za svaki $j$, a broj $14n$ mu nije prijatelj ako i samo ako postoji $j$ takav da je ostatak koji $n$ daje pri dijeljenju s $p^j$ veći ili jednak $\frac{p^j}{14}$.

Zapišimo $n=a_0+a_1p+a_2p^2+\ldots+a_tp^t$ za $a_1,a_2,\ldots,a_t\in\{0,1,\ldots,p-1\}$. Tada je ostatak pri dijeljenju $n$ sa $p^j$ jednak $a_0+a_1+\ldots+a_{j-1}p^{j-1}$. Ako je $a_{j-1}\ge8$ za neki $j$, onda je taj ostatak veći ili jednak $8\cdot p^{j-1}>\frac{p^j}{13}$, jer je $8\cdot13=104>101=p$. Dakle, $a_0,a_1,\ldots$ su svi manji od $8$. Međutim, onda je

$$a_0+a_1p+\ldots+a_{j-1}p^{j-1} \le7\cdot\frac{p^j-1}{p-1}<\frac{p^j}{14},$$

jer je $7\cdot14=98<100<\frac{(p-1)\cdot p^j}{p^j-1}$. Dakle, svaki prost broj s barem $12$ prijatelja nužno ima i $13$ prijatelja.

Primjer prostog broja s točno $13$ prijatelja je $7\cdot101+2=709$.

Drugo rješenje.

Neka je $p=101$ kao u prvom rješenju. Prema Legendreovoj formuli za $\nu_p(n!)$, slijedi

$$\nu_p(n!)=\frac{n-s_p(n)}{p-1},$$

gdje je $s_p(n)$ zbroj znamenaka broja $n$ zapisanog u bazi $p$. Tada su $m$ i $n$ prijatelji ako i samo ako je

$$n\cdot(m-s_p(m))=m\cdot(n-s_p(n)),$$

ili ekvivalentno

$$n\cdot s_p(m)=m\cdot s_p(n).$$

Ako je $n<101$ prost, onda je $n=s_p(n)$ i svaki $m<101$ mu je prijatelj. Ako je $n\ge101$ prost, onda je $n>s_p(n)$, pa $n$ dijeli sve svoje prijatelje. Tada je $m=kn$ prijatelj od $n$ ako i samo ako vrijedi

$$k\cdot s_p(n)=s_p(kn).$$

Općenito, vrijedi $s_p(a+b)\le s_p(a)+s_p(b)$ uz jednakost ako i samo ako u zbrajanju $a$ i $b$ u bazi $p$ ne dolazi do “jedan dalje”, odnosno ako su znamenke uz istu potenciju $p$ u zbroju manje od $p$. Dakle, $s_p(kn)=k\cdot s_p(n)$ ako i samo ako je svaka znamenka od $n$ u bazi $p$ manja od $\frac pk$. Dakle, da bi prost broj $n$ bio prijatelj s točno $12$ brojeva, to moraju biti $2n,3n,4n,\ldots,13n$ i svaka znamenka od $n$ u bazi $101$ je manja od $\frac{101}{13}<8$. Međutim, tada je svaka znamenka manja i od $\frac{101}{14}<8$, pa je i $14n$ prijatelj od $n$, kontradikcija.