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$
Tallteorimaraton
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Lil_Flip39
- Cantor
- Posts: 102
- Joined: 25/04-2024 12:57
- Location: Oslo
\((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.
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.
-
Lil_Flip39
- Cantor
- Posts: 102
- Joined: 25/04-2024 12:57
- Location: Oslo
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.
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
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
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$
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$
Last edited by lfe on 11/06-2025 02:09, edited 1 time in total.
-
Lil_Flip39
- Cantor
- Posts: 102
- Joined: 25/04-2024 12:57
- Location: Oslo
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.
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.
-
Lil_Flip39
- Cantor
- Posts: 102
- Joined: 25/04-2024 12:57
- Location: Oslo
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.
\[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.
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?