Ny oppgave:
Vis at det eksisterer uendelig mange \(n \in \mathbb{N}\) slik at \(n^2+1\) har en divisor \(d\) slik at \(d+n\mid n^2+1\).
Tallteorimaraton
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Vi viser en sterkere påstand, nemlig at det er uendelig mange \(n\in\mathbb{N}\) slik at \(n^2+1\) har en divisor \(d\) slik at \(d(d+n)=n^2+1\). Hvis vi ser på dette som en andregrads likning med hensyn til \(d\), har vi at \(d^2+dn-n^2-1=0\). Vi vil finne uendelig mange \(n\) slik at dette har en positiv heltallsløsning. Av abc formelen, har vi \(d=\frac{-b\pm \sqrt{5n^2+4}}{2}\), så vi vil essensielt vise at
\[k^2-5n^2=4\]
har uendelig mange løsninger, men dette er et spesieltilfelle av den generaliserte pell's likningen, og det er trivielt å finne en løsning til denne, og man kan generere uendelig mange løsninger \((x,y)\) definert rekursivt med \((\frac{5y-x}{2},\frac{x-y}{2})\). Det er lett å verifisere at alle genererte tall er ikkenegative heltall, så vi vil naturligvis da ha uendelig mange \(n\) slik at \(\sqrt{5n^2+4}\in \mathbb{N}\). Da er det lett å se at \(\sqrt{5n^2+4}\) og \(n\) har lik paritet, og at \(\sqrt{5n^2+4}>n\) så \(d\in \mathbb{N}\), så vi er ferdige.
\[k^2-5n^2=4\]
har uendelig mange løsninger, men dette er et spesieltilfelle av den generaliserte pell's likningen, og det er trivielt å finne en løsning til denne, og man kan generere uendelig mange løsninger \((x,y)\) definert rekursivt med \((\frac{5y-x}{2},\frac{x-y}{2})\). Det er lett å verifisere at alle genererte tall er ikkenegative heltall, så vi vil naturligvis da ha uendelig mange \(n\) slik at \(\sqrt{5n^2+4}\in \mathbb{N}\). Da er det lett å se at \(\sqrt{5n^2+4}\) og \(n\) har lik paritet, og at \(\sqrt{5n^2+4}>n\) så \(d\in \mathbb{N}\), så vi er ferdige.
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
La \(x_1,x_2.....\) være en følge av positive heltall slik at for alle par av positive heltall \((m,n)\), \(x_{mn}\neq x_{m(n+1)}\). Vis at det eksisterer en \(i\) slik at \(x_i>2025\).
Det holder å vise at det eksisterer 2026 innbyrdes ulike tall. Vi viser med induksjon at det eksisterer \(n\) innbyrdes ulike tall for alle \(n\) i følgen. Åpenbart stemmer dette for \(n=2\). Anta at for alle indeksene \(i_1<i_2<\cdots i_{n-1}\) eksisterer \( (m,n) \) slik at \(i_a =mn\) og \(i_b = m(n+1)\). Da gjelder det samme for indeksene \(i_{n-1}!, i_{n-1}! +i_{1}, i_{n-1}!+i_2, \dots, i_{n-1}!+i_{n-1}\).
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Ny oppgave:
Let $S$ be a set of integers with the following properties:
Let $S$ be a set of integers with the following properties:
- $\{ 1, 2, \dots, 2025 \} \subseteq S$.
- If $a, b \in S$ and $\gcd(a, b) = 1$, then $ab \in S$.
- If for some $s \in S$, $s + 1$ is composite, then all positive divisors of $s + 1$ are in $S$.
$\textbf{Påstand:}$ La $p>2025$ være et primtall. Hvis $\{1,2,\dots,p-1\}\subseteq S$, så er $p\in S$.
$\textit{Bevis:}$
Anta at hverken $p-1$ eller $p+1$ er en potens av 2. AFMS at $p+1$ er en potens av et primtall. Da er $p$ delelig på 2, en motsigelse. $p+1$ har derfor minst to ulike primfaktorer. Vi kan skrive $p+1=q^km$, der $k$ er et positivt heltall og $q\not \mid m$. Da er $q^k, m\in S$ og $\gcd(q,m)=1$. Av punkt 2 er $p+1$ i $S$. Videre skriver vi $p-1=2^xa$ og $p+1=2^yb$, der $x$ og $y$ er positive heltall og $2\not \mid a,b>1$. Vi har at $2^{x+1}, 2^{y+1}\in S$ fordi de begge er mindre enn $p$. Dermed er også $2p-2=2^{x+1}a$ og $2p+2=2^{y+1}b$ i $S$. En av $\gcd(2p-2, \frac{p+1}{2})$ og $\gcd(\frac{p-1}{2},2p+2)$ er 1 siden $\gcd(p-1,p+1)=2$. Åpenbart er $\frac{p\pm 1}{2} \in S$. Dermed har vi at $(2p-2)\cdot \frac{p+1}{2}=\frac{p-1}{2} \cdot (2p+2)=p^2-1$ er i $S$. Siden $p^2$ er et sammensatt tall følger det av punkt 3 at $p^2$ og dens devisorer, blant annet $p$, er i $S$.
Anta nå at $p-1=2^k$. Av å se på modulo 3 får vi at $k$ er et partall. Det betyr at $2^{k+1}+1$ er delelig på 3. Av Mihailescus teorem er $2^{k+1}+1$ ikke en primtallspotens. Dermed kan vi skrive $2^{k+1}+1=3^{a}b$, der $a$ er et positivt heltall og $3\not \mid b$. Siden $3, b>2$, så er både $3^{a}$ og $b$ mindre enn $p-1$ og dermed i $S$. Av punkt 2 er $2^{k+1}+1$ i $S$. Av punkt 3 er $2^{k+1}+2=2p$ og dens divisorer, blant annet $p$, i $S$.
Anta til slutt at $p+1=2^k$, altså at $p$ er et Mersenne primtall. Det følger at $3p-1$ er delelig på 4. I tillegg kan ikke $3p-1$ være en potens av 2. Det betyr at $3p-1=2^{a}b$, der $a$ er et positivt heltall og $2\not \mid b$ slik at både $2^{a}$ og $b$ er mindre enn $p$ og dermed i $S$. Det følger av punkt 2 at $3p-1$ er i $S$. Til slutt har vi av punkt $3$ at $3p$, og dermed $p$, også er i $S$. $\square$
Oppgaven følger nå umiddelbart av induksjon. Anta at $\{1,2,\dots,n-1\} \subseteq S$, der $n> 2025$. Hvis $n$ er et sammensatt tall, følger det av punkt 3 at $n\in S$. Hvis $n$ er et primtall, følger det av påstanden ovenfor at $n\in S $. Dermed er alle positive heltall i $S$. $\blacksquare$
$\textit{Bevis:}$
Anta at hverken $p-1$ eller $p+1$ er en potens av 2. AFMS at $p+1$ er en potens av et primtall. Da er $p$ delelig på 2, en motsigelse. $p+1$ har derfor minst to ulike primfaktorer. Vi kan skrive $p+1=q^km$, der $k$ er et positivt heltall og $q\not \mid m$. Da er $q^k, m\in S$ og $\gcd(q,m)=1$. Av punkt 2 er $p+1$ i $S$. Videre skriver vi $p-1=2^xa$ og $p+1=2^yb$, der $x$ og $y$ er positive heltall og $2\not \mid a,b>1$. Vi har at $2^{x+1}, 2^{y+1}\in S$ fordi de begge er mindre enn $p$. Dermed er også $2p-2=2^{x+1}a$ og $2p+2=2^{y+1}b$ i $S$. En av $\gcd(2p-2, \frac{p+1}{2})$ og $\gcd(\frac{p-1}{2},2p+2)$ er 1 siden $\gcd(p-1,p+1)=2$. Åpenbart er $\frac{p\pm 1}{2} \in S$. Dermed har vi at $(2p-2)\cdot \frac{p+1}{2}=\frac{p-1}{2} \cdot (2p+2)=p^2-1$ er i $S$. Siden $p^2$ er et sammensatt tall følger det av punkt 3 at $p^2$ og dens devisorer, blant annet $p$, er i $S$.
Anta nå at $p-1=2^k$. Av å se på modulo 3 får vi at $k$ er et partall. Det betyr at $2^{k+1}+1$ er delelig på 3. Av Mihailescus teorem er $2^{k+1}+1$ ikke en primtallspotens. Dermed kan vi skrive $2^{k+1}+1=3^{a}b$, der $a$ er et positivt heltall og $3\not \mid b$. Siden $3, b>2$, så er både $3^{a}$ og $b$ mindre enn $p-1$ og dermed i $S$. Av punkt 2 er $2^{k+1}+1$ i $S$. Av punkt 3 er $2^{k+1}+2=2p$ og dens divisorer, blant annet $p$, i $S$.
Anta til slutt at $p+1=2^k$, altså at $p$ er et Mersenne primtall. Det følger at $3p-1$ er delelig på 4. I tillegg kan ikke $3p-1$ være en potens av 2. Det betyr at $3p-1=2^{a}b$, der $a$ er et positivt heltall og $2\not \mid b$ slik at både $2^{a}$ og $b$ er mindre enn $p$ og dermed i $S$. Det følger av punkt 2 at $3p-1$ er i $S$. Til slutt har vi av punkt $3$ at $3p$, og dermed $p$, også er i $S$. $\square$
Oppgaven følger nå umiddelbart av induksjon. Anta at $\{1,2,\dots,n-1\} \subseteq S$, der $n> 2025$. Hvis $n$ er et sammensatt tall, følger det av punkt 3 at $n\in S$. Hvis $n$ er et primtall, følger det av påstanden ovenfor at $n\in S $. Dermed er alle positive heltall i $S$. $\blacksquare$
Først observer at n/an går mot uendelig, og starter <1.
La c være et naturlig tall.
Siden følgen går mot uendelig vil det per definisjon finnes en index k slik at k/ak <c, (k+1)/a_(k+1) >=c.
Vi viser at vi må ha likhet, som fullfører oppgaven.
Førsr observer st siden følgen er >1, så kan ikke an øke, siden følgen vil da synke. I tilleg kan den heller ikke lande på 1 hvis an øker.
Av det fåe vi ak=a_(k+1)
Dermed har vi en k slik at:
k<ak*c
k+1>=ak*c
Som gir k+1=a_(k+1)c
Som løser oppgaven
La c være et naturlig tall.
Siden følgen går mot uendelig vil det per definisjon finnes en index k slik at k/ak <c, (k+1)/a_(k+1) >=c.
Vi viser at vi må ha likhet, som fullfører oppgaven.
Førsr observer st siden følgen er >1, så kan ikke an øke, siden følgen vil da synke. I tilleg kan den heller ikke lande på 1 hvis an øker.
Av det fåe vi ak=a_(k+1)
Dermed har vi en k slik at:
k<ak*c
k+1>=ak*c
Som gir k+1=a_(k+1)c
Som løser oppgaven
Antar det er ment at $d_1<d_2<\dots<d_k$.
Løsningene er $n=p^m$, der $p$ er et primtall og $m>3$. Åpenbart fungerer disse. Vi skal nå vise at dette er den eneste løsningen.
La $\{b_i\}_i=1^{k-1}$ være følgen gitt av $b_i=d_{i+1}-d_i$. Vi antar at $\{b_i\}$ er geometrisk med kvotient $r$. Siden alle $d_{i+1}-d{i}$ er positive, må $r$ også være positivt. Vi ser at $d_k-d_{k-1}=d_{k-1}(d_2-d_1)$. Dermed må det eksistere en $a\in \mathbb{N}$ slik at $r^{a}=d_{k-1}$. Det betyr at $r$ er et positivt heltall.
$\textbf{Påstand:}$ $\max \{b_i\}=d_k-d_{k-1}$ og $\min \{b_i\}=d_2-d_1$
$\textit{Bevis:}$
Vi har $d_k-d_{k-1}=d_{k-1}(d_2-d_1)\geq d_{k-1}\geq d_i > \geq d_{i}-d{i-1}$ for alle $i<k$. Dermed er $\max \{b_i\}=d_k-d_{k-1}$.
AFMS at det eksisterer $i>1$ slik at $d_{i+1}-d_i<d_2-d_1$. Det må da eksistere en $a\in \mathbb{N}$ slik at $r^{a}b_i=b_1$. Det impliserer at $r\mid d_2-d_1$, men det betyr at $r\mid \gcd(d_2-d_1,d_{k-1})=1$, en motsigelse. $\square$
La $\tau(n)$ være antall divisorer av $n$. Av påstanden ovenfor vet vi at $\tau (n)=\tau (d_2\cdot r^{k-2})=k$. AFMS at $r$ har to ulike primtallsfaktorer $q_1$ og $q_2$. Da er
\[
k =\tau ( d_2 \cdot r^{k-2}) \geq \tau(q_1^{k-2}q_2^{k-2}) =k^2-2k+1 > k
\]
for $k\geq 3$, en motsigelse. Dermed er $r$ et primtall.
$d_2$ er den minste primtallsfaktoren til $n$. Hvis $d_2\neq r$, så er $k = \tau(d_2\cdot r^{k-2})=2(k-1)>k$, en motsigelse. Det betyr at $d_2=r$ og $n=d_k=r^{k-1}$. $\blacksquare$
Løsningene er $n=p^m$, der $p$ er et primtall og $m>3$. Åpenbart fungerer disse. Vi skal nå vise at dette er den eneste løsningen.
La $\{b_i\}_i=1^{k-1}$ være følgen gitt av $b_i=d_{i+1}-d_i$. Vi antar at $\{b_i\}$ er geometrisk med kvotient $r$. Siden alle $d_{i+1}-d{i}$ er positive, må $r$ også være positivt. Vi ser at $d_k-d_{k-1}=d_{k-1}(d_2-d_1)$. Dermed må det eksistere en $a\in \mathbb{N}$ slik at $r^{a}=d_{k-1}$. Det betyr at $r$ er et positivt heltall.
$\textbf{Påstand:}$ $\max \{b_i\}=d_k-d_{k-1}$ og $\min \{b_i\}=d_2-d_1$
$\textit{Bevis:}$
Vi har $d_k-d_{k-1}=d_{k-1}(d_2-d_1)\geq d_{k-1}\geq d_i > \geq d_{i}-d{i-1}$ for alle $i<k$. Dermed er $\max \{b_i\}=d_k-d_{k-1}$.
AFMS at det eksisterer $i>1$ slik at $d_{i+1}-d_i<d_2-d_1$. Det må da eksistere en $a\in \mathbb{N}$ slik at $r^{a}b_i=b_1$. Det impliserer at $r\mid d_2-d_1$, men det betyr at $r\mid \gcd(d_2-d_1,d_{k-1})=1$, en motsigelse. $\square$
La $\tau(n)$ være antall divisorer av $n$. Av påstanden ovenfor vet vi at $\tau (n)=\tau (d_2\cdot r^{k-2})=k$. AFMS at $r$ har to ulike primtallsfaktorer $q_1$ og $q_2$. Da er
\[
k =\tau ( d_2 \cdot r^{k-2}) \geq \tau(q_1^{k-2}q_2^{k-2}) =k^2-2k+1 > k
\]
for $k\geq 3$, en motsigelse. Dermed er $r$ et primtall.
$d_2$ er den minste primtallsfaktoren til $n$. Hvis $d_2\neq r$, så er $k = \tau(d_2\cdot r^{k-2})=2(k-1)>k$, en motsigelse. Det betyr at $d_2=r$ og $n=d_k=r^{k-1}$. $\blacksquare$
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Svaret er $n=2^k$ og $n=p$ hvor $p$ er et primtall. Først ser vi at $a_i$ må enten være synkende eller økende, siden ellers vil den bytte tegn midt i, som er en motsigelse. Så vi antar at $a_1=1$
Anta nå $n$ er odde. Da har vi at alle differanser må være $1$, siden $2,1$ er begge med, som betyr at alle tall under $n$ må være med, eller at $n$ må være et primtall.
Anta nå $n$ er partall. Hvis nå $3$ ikke deler $n$, har vi at $a_1=1,a_2=3$ så alle oddetall dukker opp under $n$, som impliserer at $n$ ikke kan ha noe odde faktor annet enn $1$. Da kan vi anta $3\mid n$. Da er $a_2=p\neq 3$ og $p\equiv 1 \pmod 3$ siden $a_3=2p-1$ som er delig på \(3\) hvis $p\equiv 2 \pmod 3$. Vi har også av at differansen er konstant at $n=(k-1)(p-1)+1$, som betyr at $n\equiv -1\pmod 3$, en motsigelse, så vi er ferdige.
Anta nå $n$ er odde. Da har vi at alle differanser må være $1$, siden $2,1$ er begge med, som betyr at alle tall under $n$ må være med, eller at $n$ må være et primtall.
Anta nå $n$ er partall. Hvis nå $3$ ikke deler $n$, har vi at $a_1=1,a_2=3$ så alle oddetall dukker opp under $n$, som impliserer at $n$ ikke kan ha noe odde faktor annet enn $1$. Da kan vi anta $3\mid n$. Da er $a_2=p\neq 3$ og $p\equiv 1 \pmod 3$ siden $a_3=2p-1$ som er delig på \(3\) hvis $p\equiv 2 \pmod 3$. Vi har også av at differansen er konstant at $n=(k-1)(p-1)+1$, som betyr at $n\equiv -1\pmod 3$, en motsigelse, så vi er ferdige.
-
Lil_Flip39
- Cayley
- Posts: 83
- Joined: 25/04-2024 12:57
- Location: Oslo
Nytt problem for folket:
An integer $n > 1$ is called ${good}$ if there exists a permutation $a_1, a_2, a_3, \dots, a_n$ of the numbers $1, 2, 3, \dots, n$, such that:
$(i)$ $a_i$ and $a_{i+1}$ have different parities for every $1 \leq i \leq n-1$;
$(ii)$ the sum $a_1 + a_2 + \cdots + a_k$ is a quadratic residue modulo $n$ for every $1 \leq k \leq n$.
Prove that there exist infinitely many good numbers, as well as infinitely many positive integers which are not good.
An integer $n > 1$ is called ${good}$ if there exists a permutation $a_1, a_2, a_3, \dots, a_n$ of the numbers $1, 2, 3, \dots, n$, such that:
$(i)$ $a_i$ and $a_{i+1}$ have different parities for every $1 \leq i \leq n-1$;
$(ii)$ the sum $a_1 + a_2 + \cdots + a_k$ is a quadratic residue modulo $n$ for every $1 \leq k \leq n$.
Prove that there exist infinitely many good numbers, as well as infinitely many positive integers which are not good.