Tallteorimaraton

[lfe]

Først viser vi konstruksjon for uendelig mange gode tall.
$\mathbf{\text{Påstand:}}$ Alle primtall $p\equiv 3(\mathrm{mod}4)$ er gode.
$\mathit{\text{Bevis:}}$ $-1$ er ikke en kvadratisk rest. Det følger at nøyaktig én av $a$ og $p-a$ er en kvadratisk rest og at de har ulik paritet. La $b_i\equiv -a_i(\mathrm{mod}p)$ Vi kan dermed ordne summen slik: $a_1+b_1+a_2+b_2\dots a_{k-1}+b_{k-1}+p+a_k+b_k+\dots$, der $a_i$ er odde for $i<k$ og partall $i\ge k$. Dette tilfredsstiller kravene i oppgaven fordi summen veksler mellom $0$ og en kvadratisk rest samtidig som pariteten skifter.


Videre viser vi at det eksisterer en uendelig familie med tall som ikke er gode.
$\mathbf{\text{Påstand:}}$ Ingen tall på formen $2^m$ er gode for $m\ge 2$.
$\mathit{\text{Bevis:}}$ Legg merke til at kvadratiske rester modulo 4 er 0 og 1. På et tidspunkt i summen, så må det legges til et tall kongruent med 2 modulo 4. Summen er da kongruent med 2 eller 3 modulo 4. Ingen av disse kan være kvadratiske rester. Dermed er ikke $2^m$ et godt tall.
$◻$

[lfe]

Ny oppgave:
Finn alle positive heltall $m,n$ som tilfredsstiller følgende:

• $a\mid b^4+1$
• $b\mid a^4+1$
• $\lfloor \sqrt{a}\rfloor =\lfloor \sqrt{b}\rfloor$

[Lil_Flip39]

$(a,b)=(1,1),(1,2),(2,1)$ er det eneste som funker.
Observer at det tredje punktet impliserer at $k^2⩽b<a<(k+1{)}^2$ og $a\ne b$ siden åpenbart $gcd(a,b)=1$. I tillegg har vi at
$$ab\mid (a-b{)}^4+1$$
som følger av å observere at alle deler i utvidelsen enten er deilig på $ab$ direkte, eller ender man opp med $a^4+1$ eller $b^4+1$.
Hvis vi skriver $a=k^2+x,b=k^2+y$ har vi at
$$(k^2+x)(k^2+y)\mid (x-y{)}^4+1$$
La $(x-y{)}^4+1=c(k^2+x)(k^2+y)$. Da ser vi at LHS tar maks på $(2k{)}^4+1$ som impliserer at $c<16$. Dermed resterer bare å skjekke noen tillfeller.
Først, anta at $p\mid (x-y{)}^4+1$ og $p$ odde. Da har vi at $(x-y{)}^4\equiv -1(\mathrm{mod}p)⟹(x-y{)}^8\equiv 1(\mathrm{mod}p)$ so $or{d}_p(x-y)=8⟹p\equiv 1(\mathrm{mod}8)$
Dermed har vi at alle odde primdivisorer av LHS må være $1(\mathrm{mod}8)$, og siden den minste slike primtallet er $17$, Gjenstår vi bare med $c=2^{ø}$
Dersom $c$ er partall, får vi at LHS$\equiv 2(\mathrm{mod}4)$, men $4\mid c(k^2+x)(k^2+y)$ siden $c$ er partall og $x,y$ har motsatt paritet.
Dermed gjenstår vi bare $c=1$. Da må vi løse $(x-y{)}^4+1=(k^2+x)(k^2+y)$. Hvis $k=1$, ender vi opp med løsningene vi allerede har.
Hvis $k>1$ derimot, har vi at $(k^2+1{)}^4>(2k{)}^4+1$ som betyr at $(k^2+1{)}^4>(x-y{)}^4+1=(k^2+x)(k^2+y)>k^4$, som impliserer $(k^2+x)(k^2+y)=k^4+1$ som åpenbart ikke holder.
Yippie.

[Lil_Flip39]

Ny oppgave
LIl_flip har en funksjon $f:\mathbb{N}\to \mathbb{N}$ slik at for alle heltall tall $a,b>0$ så holder følgene:
$$a+b\mid a^{f(a)}+b^{f(b)}$$
lfe har lyst til å finne ut av hvilke slike funksjoner Lil_flip kan ha. Problemet er at lfe er dårlig i tallteori, så hjelp lfe med å finne alle slike funksjoner.

[CCPenguin]

Ganske vanskelig oppgave, trengte mange hint for å finne 2^ndelen.

Claim 1: $f(x)$ er odde for x >1
Bevis:
Observer at $1+a|1^{f(a)}+a^{f(a)}$
Hvis $p\ne 2$ deler venstresiden, ser vi at f(a) må være odde av LTE for alle a>1.

Claim 2:
$a+b|b^{f(b)}-b^{f(a)}$
Bevis:
Siden f(a) og f(b) er odde, følger det at
$a+b|a^{f(a)}+b^{f(a)}$
og lignende for f(b).
Ser vi på en differanse med det originale utrykket følger resultatet.

Claim 3:
$f(2^k-2^c)=f(2^c)$ for $c\in [1,k-1]$
Bevis:
La $a=2^k-2^c,b=2^c,x_1=f(a),x_2=f(b)$.
Da følger det at
$2^k|(2^c(2^{k-c}-1{)}^{x_1}+(2^c{)}^{x_2}$
Som er lik
$2^{c{x}_1}\ast o-2^{c{x}_2}$
Der oddetallet o er gitt ved $o=(2^{k-c}-1{)}^{x_1}$
Dette er videre lik
$2^{cmin(x_1,x_2)}(2^{c{x}_1-cmin(x_1,x_2)}o-2^{c{x}_2-cmin(x_1,x_2)})$
Hvis $x_1\ne x_2$, blir utrykket til høyre et oddetall.
Ved å la $k\to \mathrm{\infty }$, får vi at v2 på høyre siden er større, og en motsigelse. Dermed følger claim 3.

Vi fullfører oppgaven.
Observer at
$2^k-2^c+b|b^{f(b)}-b^{f(2^c)}$
av claim 3 og 2.
Lar vi k gå mot uendelig, følger det at $f(b)=f(2^c)$ for alle b.
Dermed må f(x) være konstant for alle x>1.
Observer at f(1) = n, f(x) = 2k+1 er en gyldig løsning.
Dette løser oppgaven

[CCPenguin]

La $P(x)=\prod _1^9(x+d_j)$, der $d_j$ er 9 parvis distinkte heltall.
Vis at det finnes et heltall N slik at for alle $x\ge N$ er P(x) delbart på et primtall større en 20

[lfe]

Algebraisk tallteori:
Over tallkroppen $\mathbb{Q}$ definerer vi S-enhet, der S er en mengde primtall, til å være mengden reduserte rasjonale tall der alle primtallsfaktorene til både nevener og teller er i S. Det er et velkjent, men ikke-trivielt, resultat at likningen $x+y=1$ har endelig mange løsninger for S-enhetene $x$ og $y$. Dette bruker vi videre i løsningen.
Først oversetter vi oppgaven til våre nye kule fagbegrep. Vi ønsker å vise at det kun er endelig mange $x\in \mathbb{N}$ slik at $P(x)$ er et produkt av S-enheter, der $S$ er mengden primtall mindre eller lik 20. Vi har et lineært likningssystem av S-enheter:
$$(x-d_i)-(x-d_j)=d_j-d_i=a_{ij}\ne 0$$
for $1\le i<j\le 9$. Vi vet at $a_{ij}\in \mathbb{Z}$. La $S^{\prime }$ være mengden av alle primtall som deler en av $a_{ij}$ eller er i $S$. det følger at vi har likningssystemet
$$\frac{x-d_i}{a_{ij}}+\frac{-x+d_j}{a_{ij}}=1$$
der hver av $\frac{x-d_i}{a_{ij}}$ er en S'-enhet. Vi vet dermed at alle likningene har endelig mange løsninger og at likningssystemet dermed også har endelig mange løsninger. Det betyr at oppgaven er vist. $◻$

[lfe]

Ny oppgave:
Gitt positive heltall $a$, $b$, $m$ og $k$, der $k>1$. Vis at det eksisterer uendelig mange positive heltall $n$ slik at $gcd({\varphi }^m(n),\lfloor \sqrt[k]{an+b}\rfloor )=1$.