Tallteoretiske funksjoner

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

La $n \in \mathbb{N}$. Finn alle $n$ som er slik at $$n+ \varphi(n) = 2\tau(n)$$ der $\varphi(n)$ er antallet tall som er relativt primiske til $n$, og $\tau(n)$ er antall divisorer til $n$, inklusivt $n$ selv.
stensrud
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Sted: Cambridge

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
Over-Guru
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.
stensrud
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Sted: Cambridge

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.
Solar Plexsus
Over-Guru
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.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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