Tallteoretiske funksjoner

[Markus]

La $n\in \mathbb{N}$. Finn alle $n$ som er slik at $$n+\phi (n)=2\tau (n)$$ der $\phi (n)$ er antallet tall som er relativt primiske til $n$, og $\tau (n)$ er antall divisorer til $n$, inklusivt $n$ selv.

[stensrud]

Tillater meg å legge til en lignende oppgave! La $\sigma (n)$ være summen av alle de positive divisorene til $n$. Finn alle $n\in \mathbb{N}$ slik at
$$\sigma (n^2)-\sigma (n)=2016.$$

[Solar Plexsus]

De eneste løsningene av den diofantiske likningen

$(1)n+\phi (n)=2\tau (n)$

er $n=1$, $n=4$ og $n=6$.

Bevis: Vi ser at $n=1$ er en triviell løsning av likning (1). Anta at $n>1$ og at primtallsfaktoriseringen av $n$ er $\prod _{i=1}^k{p}_i^{r_i}$, der $\{p_i{\}}_{i=1}^k$ er en tiltagende sekvens.
Av likning (1) følger at $n<2\tau (n)$, i.e.

$(2)\prod _{i=1}^k\frac{p^{r_i}-1}{r_i+1}<2$.

Det faktum at $\frac{p^{r-1}}{r}\le \frac{p^r}{r+1}$ når $r\ge 2$ kombinert med ulikhet (2) impliserer

$(3)\prod _{i=1}^k\frac{p_i}{2}<2$.

Ulikheten (3) gir $p_k<4<5\le p_3$, som betyr at $k\le 2$ og at $n$ kun kan ha 2 og 3 som primfaktorer. Dermed har vi følgende muligheter:

$\bullet k=1$. Innsatt i likning (1) blir resultatet

$p_1^{r_1}+p_1^{r_1-1}(p_1-1)=2(r_1+1)$,

i.e.

$(4)p_1^{r_1-1}(2p_1-1)=2(r_1+1)$,

der $p_1\in \{2,3\}$. Ifølge likning (4) kan ikke $p_1$ være odde, hvilket betyr at $p_1=2$, som innsatt i likning (4) resulterer i

$(5)3\cdot 2^{r_1-2}=r_1+1$.

Det faktum at $VS>HS$ i likning (5) når $r_1\ge 3$ betyr at $0\le r_1-2\le 2-2=0$, i.e. $r_1=2$. Vi ser at $r_1=2$ faktisk tilfredsstiller likning (5). Altså har likning (1) en løsning, nemlig $n=p_1^{r_1}=2^2=4$.

$\bullet k=2$. Da vet vi at $p_1=2$ og $p_2=3$, som innsatt i likning (1) gir

$2^{r_1}\cdot 3^{r_2}+2^{r_1}\cdot 3^{r_2-1}=2(r_1+1)(r_2+1)$,

i.e.

$(6)\frac{2^{r_1+1}}{r_1+1}\cdot \frac{3^{r_2-1}}{r_2+1}=1$.

Funksjonene $f(r_1)=\frac{2^{r_1+1}}{r_1+1}$ og $g(r_2)=\frac{3^{r_2-1}}{r_2+1}$ er begge voksende når $r_1,r_2\in [1,\mathrm{\infty })$. Dette innebærer at hvis $r_1+r_2\ge 3$, så er

$f(r_1)\cdot g(r_2)\ge min\{f(1)\cdot g(2),f(2)\cdot g(1)\}=min\{2\cdot 1,\frac{8}{3}\cdot \frac{1}{2}\}=min\{2,\frac{4}{3}\}=\frac{4}{3}$.

Herav følger at $r_1+r_2<3$ (ettersom likning (1) er ekvivalent med $f(r_1)\cdot g(r_2)=1$), som medfører at $r_1=r_2=1$. Vi ser at disse to verdiene faktisk tilfredsstiller likning (6). Følgelig har likning (1) kun løsningen $n=2^{r_1}\cdot 3^{r_2}=2^1\cdot 3^1=6$.

Konklusjon: Likning (1) er tilfredsstilt hvis og bare hvis $n\in \{1,4,6\}$. q.e.d.

[stensrud]

Alternativt: Det er klart at $n$ ikke har noen divisorer blant $\lceil \frac{n}{2}\rceil +1,\lceil \frac{n}{2}\rceil +2,\dots ,n-1$, så $\tau (n)\le \lceil \frac{n}{2}\rceil +1<\frac{n}{2}+2$. Med den opprinnelige ligningen betyr dette at
$$n+\phi (n)<n+4⟹\phi (n)<4,$$
så det er bare en håndfull tilfeller vi trenger å sjekke.

[Solar Plexsus]

Den diofantiske likningen

$(1)\sigma (n^2)-\sigma (n)=2016$

har ingen løsning i naturlige tall.

Bevis Det er åpenbart at $n>1$. La $\prod _{i=1}^k{p}_i^{r_i}$ være primtallsfaktoriseringen av $n$. Likning (1) kan nå uttrykkes på formen

$(2)\prod _{i=1}^k\frac{p_i^{2_i+1}-1}{p_i-1}-\prod _{i=1}^k\frac{p_i^{r_i}-1}{p_i-1}=2016$.

I fortsettelsen er $p$ et primtall og $r$ et naturlig tall. I så fall er

$\frac{p^{2r+1}-1}{p-1}=\sum _{i=0}^{2r}{p}^i\equiv 1(\mathrm{mod}2)$,

hvilket betyr at $\sigma (n^2)$ er odde. Ergo må $\sigma (n)$ være odde ifølge likning (1), som impliserer at $r_i$ er like når $p_i$ er odde. Så hvis $n$ er en løsning av likning (1), er $n=2^u\cdot (2v+1{)}^2$, der $u$ og $v$ er to ikke-negative heltall.

Videre har vi at

$\frac{p^{2r+1}-1}{p^r(p^{r+1}-1)}>1$,

og

$\frac{p^{2r+1}-1}{p^r(p-1)}<2$,

hvilket gir oss

$(3)\frac{\sigma (n^2)}{n\cdot \sigma (n)}=\prod _{i=1}^k\frac{p^{2r_i+1}-1}{p_i^{r_i}(p_i^{r_i+1}-1)}>\prod _{i=1}^{k}1=1^k=1$

og

$(4)\frac{\sigma (n^2)}{n^2}=\prod _{i=1}^k\frac{p^{2r_i+1}-1}{p_i^{2r_i}(p_i-1)}>\prod _{i=1}^{k}2=2^k$.

Med andre ord er

$(5)\sigma (n^2)>n\cdot \sigma (n)$

og

$(6)\sigma (n^2)<2^k\cdot n^2$.


Ulikhet (5) kombinert med likning (1) medfører at

$2016>(n-1)\sigma (n)\ge (n-1)(n+1)=n^2-1$,

i.e. $n^2<2017$. Herav følger at $n\le 44$. Dette kombinert med at $n=2^u(2v-1{)}^2$ gir oss at $n$ har høyst to primfaktorer, som betyr at $k\le 2$. Dette faktum kombinert med ulikhet (6) gir oss

$\frac{\sigma (n^2)}{n^2}<2^k\le 2^2=4$,

i.e.

$(7)\sigma (n)<4n^2$.

Nå er $\sigma (n)>2016$ ifølge likning (1), som kombinert med ulikhet (7) gir $4n^2>2016$. Med andre ord er $n^2>504$, i.e. $n\ge 23$. Summa summarum har at $23\le n=2^u\cdot (2v+1{)}^2$, hvilket betyr at $n\in \{25,32,36\}$. Nå er $\sigma (p^k)<2p^k$ ifølge ulikhet (6), som gir

$\sigma ({25}^2)<2\cdot {25}^2=2\cdot 625=1250<2016$

og

$\sigma ({32}^2)-\sigma (32)<2\cdot {32}^2-\sigma (32)<2\cdot 1024-32=2048-32=2016$.

Dermed er $n=36$ eneste mulige løsning av likning (1). Ved regning får vi at

$\sigma ({36}^2)-\sigma (36)=\sigma (2^4\cdot 3^4)-\sigma (2^2\cdot 3^2)=\frac{2^5-1}{2-1}\cdot \frac{3^5-1}{3-1}-\frac{2^3-1}{2-1}\cdot \frac{3^3-1}{3-1}=31\cdot 121-7\cdot 13=3751-91=3660$.

Konklusjon: Likning (1) har ingen løsninger i naturlige tall. q.e.d.

[Markus]

Flotte løsninger! Elegant med en så kort løsning, stensrud!