Tallteoretiske funksjoner
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
La $\sigma(n) $ være summen av alle de positive divisorene til $n$. Finn alle $n\in \mathbb{N}$ slik at-
Solar Plexsus
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
De eneste løsningene av den diofantiske likningen
$(1) \;\; n + \varphi(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} \leq \frac{p^r}{r+1}$ når $r \geq 2$ kombinert med ulikhet (2) impliserer
$(3) \;\; \prod_{i=1}^k \frac{p_i}{2} < 2$.
Ulikheten (3) gir $p_k < 4 < 5 \leq p_3$, som betyr at $k \leq 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 \geq 3$ betyr at $0 \leq r_1 - 2 \leq 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,\infty)$. Dette innebærer at hvis $r_1 + r_2 \geq 3$, så er
${\textstyle f(r_1) \cdot g(r_2) \geq \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.
$(1) \;\; n + \varphi(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} \leq \frac{p^r}{r+1}$ når $r \geq 2$ kombinert med ulikhet (2) impliserer
$(3) \;\; \prod_{i=1}^k \frac{p_i}{2} < 2$.
Ulikheten (3) gir $p_k < 4 < 5 \leq p_3$, som betyr at $k \leq 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 \geq 3$ betyr at $0 \leq r_1 - 2 \leq 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,\infty)$. Dette innebærer at hvis $r_1 + r_2 \geq 3$, så er
${\textstyle f(r_1) \cdot g(r_2) \geq \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.
Alternativt: Det er klart at $n$ ikke har noen divisorer blant $\left\lceil\frac{n}{2}\right\rceil+1,\left\lceil\frac{n}{2}\right\rceil+2,\dotsc,n-1$, så $\tau(n)\leq \left\lceil \frac{n}{2}\right\rceil +1<\frac{n}{2}+2$. Med den opprinnelige ligningen betyr dette at
\[n+\varphi(n)<n+4\implies \varphi(n)<4,\]
så det er bare en håndfull tilfeller vi trenger å sjekke.
\[n+\varphi(n)<n+4\implies \varphi(n)<4,\]
så det er bare en håndfull tilfeller vi trenger å sjekke.
-
Solar Plexsus
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
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 \pmod{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) \geq (n - 1)(n + 1) = n^2 - 1$,
i.e. $n^2 < 2017$. Herav følger at $n \leq 44$. Dette kombinert med at $n = 2^u (2v - 1)^2$ gir oss at $n$ har høyst to primfaktorer, som betyr at $k \leq 2$. Dette faktum kombinert med ulikhet (6) gir oss
$\frac{\sigma(n^2)}{n^2} < 2^k \leq 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 \geq 23$. Summa summarum har at $23 \leq 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.
$(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 \pmod{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) \geq (n - 1)(n + 1) = n^2 - 1$,
i.e. $n^2 < 2017$. Herav følger at $n \leq 44$. Dette kombinert med at $n = 2^u (2v - 1)^2$ gir oss at $n$ har høyst to primfaktorer, som betyr at $k \leq 2$. Dette faktum kombinert med ulikhet (6) gir oss
$\frac{\sigma(n^2)}{n^2} < 2^k \leq 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 \geq 23$. Summa summarum har at $23 \leq 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.