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$.

[lfe]

Svaret er 0, 1, 3, 5 og 11.
Trekker vi 2 fra begge sidene av likheten, får vi
\[
\frac{q-p+1}{(p+1)q} = \frac{4}{n+2}
\]
Dette gir oss at $2\mid q-p+1$ som betyr at en av av $p$ eller $q$ er lik 2.
Først anta at $q=2$. Vi har da
\[
\frac{3-p}{2(p+1)}=\frac{4}{n+2}
\]
Siden høyresiden er større enn 0, må $p=2$.
Anta nå at $p=2$. Det gir oss
\[
\frac{q-1}{3q} =\frac{4}{n+2}
\]
Av at $\gcd (q-1, q) = 1$, følger det at $q-1\mid 4$ eller $\frac{q-1}{3} \mid 4$, der $3\mid q-1$ i det siste tilfellet.
Dette gir oss at de mulige verdiene for $q$ er $(2, 3, 5, 7, 13)$. Disse verdiene for $q$ gir hhv løsningene $(22, 16, 13, 12, 11)$ for $n$.
Dermed er de mulige verdiene for $q-p$ kun de som tidliger ble nevnt.

[lfe]

Vi definerer følgen $\{ a_n\}_{n=1}^\infty$ rekursivt. La $a_1 = a_2 = 1$ og $a_{n+2} +a_n= 14a_{n+1}$ for $n\geq 1$. Vis at alle primtall $p$ som deler en av tallene i følgen er kongruent med $1$ modulo $12$,

[Lil_Flip39]

Ved hjelp av karakteristisk likning og litt algebraisk manupilasjon får vi
\[
a_n = \frac{(2+\sqrt{3})^{\,2n-3} + (2-\sqrt{3})^{\,2n-3}}{4}
\]Videre er det velkjent at Pell's likningen \(x^2-3y^2=1\) har generell løsning for \[x= \frac{(2+\sqrt{3})^n + (2-\sqrt{3})^n}{2}\]Dermed ser vi at \(2a_n\) former en delmengde av den generelle løsningen til \(x^2-3y^2=1\). Da får vi \[4a_n^2-3y^2=1\]Hvis nå \(p\mid a_n\), så har vi \(-3\) er en kvadratisk rest modulo \(p\). Dermed vet vi gjennom kvadratisk reprossoisjjoejajisojt at \[\left (\frac{p}{3}\right )= (-1)^{\frac{p-1}{2}} \left (\frac{3}{p}\right ) \]Hvis nå \(p\equiv 1 \pmod 4\), får vi at \( (-1)^{\frac{p-1}{2}} \left (\frac{3}{p}\right) = 1\times 1\), og hvis \(p\equiv 3\pmod 4\) får vi at \( (-1)^{\frac{p-1}{2}} \left (\frac{3}{p}\right )= -1\times -1\)så i begge tilfeller er \(p\) en kvadratisk rest mod \(3\). Det er lett å se at \(3\neq p\), så \(p\equiv 1\pmod 3\). Legg merke til at dette også viser at \(a_n\equiv 1\pmod 3\).

Påstand: \(2a_n-1\) er et kvadratall for alle \(n\).
Bevis: Vi har at \((2a_n-1)(2a_n+1)=3y^2\). Siden \(a_n\equiv 1\pmod 3\), så har vi \(2a_n+1=3k\). Legg merke til at \(\gcd(2a_n-1,k)=1\), kombinert \((2a_n-1)k\) er et kvadrat er påstanden vist.

Nå trenger vi bare å vise at hvis \(p\mid a_n\) så er \(p\equiv 1\pmod 4\). Dette følger av at \(2a_n=m^2+1\), så av fermat's juleteorem må alle primtall som deler \(a_n\) være \(1\pmod 4\), men vi har også \(p\equiv 1\pmod 3\), så \(p\equiv 1\pmod {12}\).

[Lil_Flip39]

Finn alle positive heltall \(n\), slik at hvis \(d\) er en positiv divisor av \(n\), så har vi \[d^2+d+1\mid n^2+n+1\]

[nilpotent1]

Solution: Let $n = xy$, then,
\[
x^2 + x + 1 \mid (xy)^2 + xy + 1
\]
notice that $x^2 + x + 1 \mid x^4 + x^2 + 1$, then we obtain,
\[
x^2 + x + 1 \mid x^2 (x^2 - y^2) + x^2 - xy
\]
next we obtain,
\[
x^2 + x + 1 \mid x(x^2 - y^2) + x - y = (x - y)(x(x + y) + 1)
\\ = (x - y)(x^2 + xy + 1)
\]
however,
\[
(x^2 + x + 1, x^2 + xy + 1) = (x^2 + x + 1, xy - x) = (x^2 + x + 1, y - 1)
\]
thus we obtain,
\[
x^2 + x + 1 \mid (x - y)(y - 1)
\]
thus if $x > y$ we obtain a contradiction, unless $y = 1$. Thus, it must be that $n \mid p^{2}$, trivially all primes $p \equiv 1 \pmod{3}$ work and all squares except for $9$. $\blacksquare$

[nilpotent1]

Problem: Find all triples of positive integers $(a,b,n)$ where $n\ge 2$, and both $a^n+b$ and $b^n+a$ are powers of $2$.

[Lil_Flip39]

\((a,b,n)=(3,5,3),(5,3,3),(1,1,n)\) hvor \(n\geq 2\) er de eneste løsningene. Først ser vi at hvis \(2\mid a\) eller \(2\mid b\) får vi motstigelse umiddelbart, siden hvis \(v_2(a)\le v_2(b)\) vil \(v_2(a^n+b)=v_2(b)\) som er en motstigelse. Dermed får vi \(\gcd(a,b)=1\). Hvis \(a\) eller \(b\) er \(1\), får vi at den andre også må være \(1\) av catalan og litt casework at \(a=b=1\). Da kan vi også anta \(a>b>1\), \(a,b\) odde. Nå ser vi at \[2^k=b^n+a\mid a^n+b\]men vi har \[a\equiv -b^n\pmod 2^k\implies 2^k\mid (-b^n)^n+b\]Nå deler vi inn i tilfeller.
Først hvis \(n\) er partall, så har vi \[2^k\mid b^{n^2-1}+1\]Av LTE har vi da \[\log_2(b^n+a)\leq v_2(b+1)\implies b^n+a\leq b+1\]som åpenbart ikke stemmer.

Hvis nå \(n\) er oddetall, får vi\[2^k\mid b^{n^2-1}-1\]så igjen av LTE har vi \[\log_2(b^n+a)\leq v_2(b^2-1)+v_2(n^2-1)-1\implies 2(b^n+a)\leq (b^2-1)(n^2-1)\]men legg merke til at dette impliserer \(2(b^{n-2})\le n^2\), kombinert med \(b\geq 3\) får vi at \(n\leq 3\implies n=3\). Da reduseres ulikheten til \(b\leq 4\), så \(b=3\). Da må \(27+a\) og \(a^3+3\) være \(2\)-er potenser, og \(a\geq 5\). Hvis \(a>5\), så motstiger dette \(54+2a\leq 64\), og det er lett å skjekke at \(a=5\) funker. Da er vi ferdige.

[Lil_Flip39]

La \(a_0,a_1,a_2\dots \) være definert rekursivt slik at \(a_0\) er ikke en \(2\)-er potens, og for alle ikkenegative heltall \(n\) har vi hvis \(a_n\) er partall, så er \(a_{n+1}\) den største odde faktoren til \(a_n\). Hvis \(a_n\) er odde, så er \(a_{n+1}=a_n+p^2\) hvor \(p\) er minste primfaktor i \(a_n\). Vis at det finnes et positivt heltall \(M\) slik at \(a_{n+2}=a_n\) for alle \(n>M\)