matematikk.net

Først viser vi konstruksjon for uendelig mange gode tall.
$\textbf{Påstand:}$ Alle primtall $p\equiv 3\pmod 4$ er gode.
$\textit{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 \pmod 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\geq 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.
$\textbf{Påstand:}$ Ingen tall på formen $2^m$ er gode for $m\geq 2$.
$\textit{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.
$\square$

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$

\((a,b)=(1,1), (1,2),(2,1)\) er det eneste som funker.
Observer at det tredje punktet impliserer at \(k^2\leqslant b<a<(k+1)^2\) og \(a\neq 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\pmod p\implies (x-y)^8\equiv 1 \pmod p\) so \(ord_p(x-y)=8\implies p\equiv 1\pmod 8\)
Dermed har vi at alle odde primdivisorer av LHS må være \(1\pmod 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\pmod 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.

Ny oppgave
LIl_flip har en funksjon $f : \mathbb N \rightarrow \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.

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

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

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

Claim 3:
[tex]f(2^k-2^c) = f(2^c)[/tex] for [tex]c \in [1,k-1][/tex]
Bevis:
La [tex]a = 2^k -2^c, b = 2^c, x_1 = f(a), x_2 = f(b)[/tex].
Da følger det at
[tex]2^k | (2^c (2^{k-c}-1)^{x_1} + (2^c)^{x_2}[/tex]
Som er lik
[tex]2^{c x_1} *o - 2^{c x_2}[/tex]
Der oddetallet o er gitt ved [tex]o = (2^{k-c}-1)^{x_1}[/tex]
Dette er videre lik
[tex]2 ^ {cmin( x_1, x_2)}(2^{cx_1-cmin( x_1, x_2)} o - 2^{c x_2 -cmin(x_1, x_2)})[/tex]
Hvis [tex]x_1 \neq x_2[/tex], blir utrykket til høyre et oddetall.
Ved å la [tex]k \rightarrow \infty[/tex], 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
[tex]2^k-2^c+b | b^{f(b)} - b^{f(2^c)}[/tex]
av claim 3 og 2.
Lar vi k gå mot uendelig, følger det at [tex]f(b) = f(2^c)[/tex] 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

La [tex]P(x) = \prod_1^9 (x+d_j)[/tex], der [tex]d_j[/tex] er 9 parvis distinkte heltall.
Vis at det finnes et heltall N slik at for alle [tex]x \geq N[/tex] er P(x) delbart på et primtall større en 20

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}\neq 0
\]
for $1\leq i<j\leq 9$. Vi vet at $a_{ij}\in \mathbb{Z}$. La $S'$ 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. $\square$

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(\phi^m(n), \lfloor \sqrt[k]{an+b} \rfloor)=1$.

Vi claimer at vi kan velge uendelig \(n\) slik at \(p^k\leqslant an+b<(p+1)^k\) og \(n=px\) hvor \(x\) har bare primfaktorer mindre enn \(n\), og \(p\) er et primtall.
Hvis vi klarer dette, er vi ferdige siden \(\varphi\) kan ikke skape primfaktorer som er større. La \(x=\frac{(p+1)^{k-1}}{a}\). Merk at dette er et heltall for uendelig mange primtall av dirichlet. Åpenbart har vi \( p^k\leqslant an+b\). Nå må vi vise
\[p(p+1)^{k-1}+b<(p+1)^k\]
som er ekvalent med
\[b<(p+1)^{k-1}\] som åpenbart holder for stor nok \(p\). dermed er vi ferdige.

Finn alle positive heltall \(n\) slik at
\[v_2(3^k-n)\] er ubegrenset (Altså kan bli større en alle tall). Her er \(k\) er et positivt heltall.

Svaret er alle $n$ som er kongruent med 1 eller 3 modulo 8.

Først ser vi at $3^k$ er kongruent med 1 eller 3 modulo 8. Dermed er det nødvendig at $n\equiv1,3 \pmod 8$.
Videre har vi av LTE at $\nu_2 (3^k-1) = \nu_2 (2) + \nu_2 (4) + \nu_2 (k) - 1$. Det følger at ordenen til $3$ modulo $2^m$ er $2^{m-2}$. Det følger at de $2^{m-2}$ restklassene modulo $2^m$ som er kongruente med 1 eller 3 modulo 8 alle dekkes av en potens av 3.

La $P$ være et $n$-graders monisk polynom med koeffisienter i $\{0,1\}$. Den mørke og mysteriøse Nils vet hva $P$ er. Tristan Amadeus kan stille Nils spørsmål om $k$ er i mengden $\{P(m)| m\in \mathbb{Z}_+\}$. Ærlige Nils svarer så ja eller nei. Hva er det minste antallet spørsmål Tristan Amadeus må stille for å kunne være sikker på hva $P$ er?