Tallteorimaraton

[guessthefunction]

Vis at for alle heltall $n$ finnes det et multiplum av $n$ med distinkte divisorer

Legg først merke til at for $n=1$ er $1$ et slikt multiplum. Deretter antar vi at $n≥2$. La
$$n=p_1^{e_1} p_2^{e_2}\dots p_m^{e_m}$$
og
$$n'=p_1^{p_1^{e_1}-1}p_2^{p_2^{e_2}-1}\dots p_m^{p_m^{e_m}-1}$$.
hvor $p_1$, $p_2$,..., $p_m$ er primtall og $e_1$, $e_2$,..., $e_m$ er naturlige tall. Legg merke til at $e_i≥p_i^{e_i}-1$ for alle $1\le i\le m$. Derfor er $n'$ et multiplum av $n$. Nå har $n'$
\begin{align}
((p_1^{e_1}-1)+1)((p_2^{e_2}-1)+1)\dots ((p_m^{e_m}-1)+1)&=p_1^{e_1}p_2^{e_2}\dots p_m^{e_m}\\
&=n
\end{align}

delere. Derfor er $n'$ et multiplum av $n$ med $n$ delere. Siden $n'$ kan konstrueres for alle naturlige tall $n$, er denne delen av problemet løst.

Finn alle $n$ som dette multiplumet er unikt for.

Dette multiplumet er unikt for $1$ og alle naturlige tall på formen $p_1p_2\dots p_n$ hvor $p_1$, $p_2$,..., $p_n$ er primtall.

Vi viser først at det faktisk er unikt for $1$ og alle produkter av distinkte primtall. Det er tydelig at $1$ er det eneste naturlige tallet med én divisor. For et naturlig tall på formen $p_1p_2\dots p_n$, er det eneste slike multiplumet $p_1^{p_1-1}p_2^{p_2-1}\dots p_n^{p_n-1}$. Dette følger av båsprinsippet om potensene i primtallsfaktoriseringen.

Vi viser nå at for alle andre naturlige tall finnes det flere slike multipler. Legg merke til at for tall på formen $p^n$, hvor $p$ er primtall og $n\ge 2$, er både $p^{p^n-1}$ og $p^{p^{n-1}-1}q^{p-1}$, hvor $q$ er primtall, slike multipler. Vi har nå følgende påstand.

Påstand: Hvis $a$ og $b$ er koprime naturlige tall, og $a'$, $b'$ er slike multipler av $a$, $b$ som er koprime, er $a'b'$ et slikt multiplum for $ab$.

Bevis: Siden $a'$, $b'$ er koprime, er antallet divisorer av $a'b'$ $ab$. Siden $a\mid a'$ og $b\mid b'$, $ab\mid a'b'$, er slutten ...

Legg nå merke til at hvis vi har et tall som er delelig med et primtall i en potens større enn én, gjør denne påstanden det mulig å konstruere uendelige slike multipler, noe som løser problemet.

[guessthefunction]

Let $m$, $n$ be distinct positive integers. Prove that
$$\gcd(m,n)+\gcd(m+1,n+1)+\gcd(m+2,n+2)\le 2|m-n|+1.$$
Further, determine when equality holds.

[Lil_Flip39]

WLOG \(m>n\). La da \(d=m-n\). Først ser vi på tilfellene \(d=1,2\). Da er det lett å se at likhet holder når \(m-n=1\), og \(m-n=2\) og \(m,n\) er begge partall. Vi viser at ulikheten er streng for alle andre \(m,n\). Legg merke til at \(\gcd(m,n) = \gcd(m,d)\mid m\), og vi får også at \(\gcd(m+1,d)\mid m+1\) og \(\gcd(m+2,d)\mid m+2\). I tillegg er alle gcd'ene divisorer av \(d\). Legg merke til at maks en av \[\gcd(m,d),\gcd(m+1,d),\gcd(m+2,d)\]kan være lik \(d\), siden \(\gcd(m+i,m+j)\leq 2\) hvor \(0\leq i<j\leq 2\). Dermed får vi \[\gcd(m,d)+\gcd(m+1,d)+\gcd(m+2,d)\leq d+\frac{d}{2}+\frac{d}{2}=2d<2d+1\] som er det vi skulle vise, så vi er ferdige. (Legg merke til at \(a\mid b\), \(a\neq b\implies a\leq \frac{b}{2}\))

[Lil_Flip39]

The numbers $p$ and $q$ are prime and satisfy
\[\frac{p}{{p + 1}} + \frac{{q + 1}}{q} = \frac{{2n}}{{n + 2}}\]
for some positive integer $n$. Find all possible values of $q-p$.