Tallteorimaraton

[Lil_Flip39]

ny oppgave:
for hvilke positive heltall $m$ finnes det en uendenlig aretmetisk rekke av heltall $a_1,a_2,....$ og en uendelig geometrisk rekke av heltall $g_1,g_2....$ som oppfyller følgene ting:

• $a_n-g_n$ er delelig på $m$ for alle heltall $n\ge 1$;
• $a_2-a_1$ er ikke delelig på $m$.

[lfe]

Ingen slik $m$ eksisterer.
Åpenbart kan ikke $m=1$. AFMS at det eksisterer en $m$ som tilfredsstiller oppgaven. Det må dermed eksistere et primtall $p$ slik at $p\mid m$ og $p\nmid a_2-a_1$. Vi kan skrive om følgene til $a_n=a_1+(n-1)d$ og $g_n=g_1{r}^{n-1}$, der $d,r\in \mathbb{Z}.Siden\text{(}p\nmid d$, må det eksistere en $n$ slik at $p\mid a_n$. Det betyr at $a_n\equiv g_n=0(\mathrm{mod}p)$. Det impliserer at $p\mid g_1$ eller $p\mid r$. Uansett har vi $p\mid g_i$ for $i\ge 2$, en motssigelse siden $p\nmid a_{n+1}$.

[lfe]

Ny oppgave:
Vis at for alle primtall $p$ eksisterer det et heltall $n$ slik at
$$\sum _{k=1}^n{k}^{n+1-k}\equiv 2020(\mathrm{mod}p)$$

[Lil_Flip39]

Jeg er lat, så jeg dropper å skrive detaljene så nøye.
La $f(n$ betegne den greia i oppgaven.
Vi viser mer generelt at $f(n)$ er surjektiv mod p og da er vi åpenbart ferdige.
Påstand: $f(n+p(p-1))\equiv f(n)-1(\mathrm{mod}p)$
Vi utvider $f(n+p(p-1))$. Observer at vi kan redusere grunntallet med $p$, og av FLT; kan vi redusere potensen med $p-1$
Vi starter med de første $n$ leddene. Etter redusering, finner vi at det er ekvalent med $f(n)$. Etter redusering, grupperer vi sammen alle tall som har lik potens, og da får vi dobbelsummen:
$\sum _{i=1}^{p-1}\sum _{i=1}^{p-1}{j}^i$
Men, denne summen er bare masse av den velkjente summen
$\sum _{i=1}^{p-1}{j}^x$, og da blir hele greia:
$f(n+p(p-1))\equiv f(n)+\sum _{i=1}^{p-1}\sum _{i=1}^{p-1}{j}^i\equiv f(n)-1(\mathrm{mod}p)$
Så Påstanden er bevist.
Da er vi ferdige siden dette viser surjektivitet.

[Lil_Flip39]

Ny oppgave:
Given a natural integer $l$, find all sequences $\{a_i{\}}_{i\ge 1}$ of positive integers such that for any natural numbers $n_1,n_2,\dots ,n_l$
$$n_1!+\cdots +n_l!\mid a_{n_1}!+\cdots +a_{n_l}!.$$

[lfe]

Svar: For $l=1$ har vi alle følger der $a_i\ge i$. Dersom $l\ge 2$ er den eneste løsningen $a_i=i$.
Åpenbart stemmer dette for $l=1$. Vi antar derfor $l\ge 2$.
$\mathbf{\text{Påstand 1:}}$ $a_i\ge i$
$\mathbf{\text{Bevis:}}$ La $n_k=m$ for alle $k$. Da har vi $l\cdot m!\mid l\cdot a_m!$. Dermed er $a_m\ge m$.

Videre i beviset ser vi bare på $n_1$ og $n_2$. Vi velger $n_3\dots n_l$ til å være så store at det ikke påvirker det vi gjør.
$\mathbf{\text{Påstand 2:}}$ $a_1=1$
$\mathbf{\text{Bevis:}}$ Anta for motsigelsens skyld at $a_1=b\ne 1$. La $n_1=1$ og $n_2=p-1$ der $p>b!$ er et primtall.
Vi har dermed at $p\mid \sum n_j$ og dermed $p\mid \sum a_{n_j}$. Det følger at $p\mid b!+a_{n_2}!$. Siden $p\nmid b!$, må $a_{n_2}=p-1$ og $b=1$ fordi $b\equiv -(p-1)!\equiv 1(\mathrm{mod}p)$.

Vi viser til slutt med induksjon at $a_i=i$. Av påstand 2 vet vi at $a_1=1$. Anta at $a_k=k$. La $n_1=k$ og $n_2=k+1$.
Vi har dermed at $k!+(k+1)!\mid k!+a_{k+1}!$. Det betyr at $k+2\mid 1+\frac{a_{k+1}!}{k!}$.
Dersom $a_{k+1}>k+1$, har vi $k+2\mid \frac{a_{k+1}!}{k!}$, en motsigelse. Dermed har vi $a_{k+1}=k+1$.

[lfe]

Ny oppgave:
Finn alle $(n,k)\in {\mathbb{N}}^2$ som tilfredsstiller likningen
$$n!+n=n^k$$

[Lil_Flip39]

$(n,k)=(2,2),(3,2),(5,3)$
Først prøver vi $n=2$, da har vi $(2,2)$ funker.
Vi deler på $n$, da har vi $(n-1)!+1=n^{k-1}$
Da har vi :
$(n-1)!=n^{k-1}-1$
Observer at siden $n>2$ har vi $n-1$ er partall, så $n$ må være oddetall. (faktisk må $n$ være et primtall)
Nå, ser vi på $v_2$ av begge sider.
$v_2(LHS)>\frac{n-1}{2}$ og av LTE:
$v_2(RHS)=v_2(n-1)+v_2(n+1)+v_2(k-1)-1$
så vi har $\frac{n-1}{2}<v_2(n-1)+v_2(n+1)+v_2(k-1)-1$, og hvis vi opphøyer i $2$ får vi:
$2^{\frac{n+1}{2}}<(n-1)(n+1)(k-1)$
så $\frac{2^{\frac{n+1}{2}}}{n^2-1}<k-1$, og for $n>17$ har vi at $k>n$, som er en motstigelse av størrelse i den orginale likningen. En rask sjekk gir at de eneste løsningene er:
$(n,k)=(2,2),(3,2),(5,3)$

[Lil_Flip39]

finn alle ikke negative heltall $n$ slik at $n^2+n+1$ er kvadrattall

[lfe]

$n^2+n+1$ ligger mellom to påfølgende kvadrattall: $n^2$ og $(n+1{)}^2$. Med mindre $n=0$. Dermed er det eneste svaret $n=0$.

[lfe]

Gitt $a\in \mathbb{N}$. Er $\frac{p-1}{or{d}_p(a)}$ bundet over primtall $p$?

[Lil_Flip39]

Svaret er nei.
Vi ser på største primfaktor av /(a^n-1/) for en /(n/). Av zsigmondy har vi at vi har en ny primfaktor når /(n/) øker med 1, som betyr at største primfaktor til /(a^n-1/) vokser minst like raskt som primtallene. Av prime numbers theorem, har vi at primtallene vokser raskere enn lineært. Dette vil impliserer at hvis vi ser på ordenen til /(a/) mod et stort primtall som deler /(a^n-1/) har vi at den ordenen er mindre enn n, men siden primtallet delt på /(n/) kan bli så stort som man vil, så følger oppgaven siden ordenen er mindre enn n

[Lil_Flip39]

Kall et tall vakkert hvis det har mindre lik $9$ unike primfaktorer. A, B spiller et spill hvor de starter med $100!$ og trekker fra tall en etter en. A starter. Eneste er at tallene som blir trukket fra må være vakre. Den som tar det siste tallet vinner. Hvem har vinnerne strategi

[Karl_Erik]

Kall et tall vakkert hvis det har mindre lik $9$ unike primfaktorer. A, B spiller et spill hvor de starter med $100!$ og trekker fra tall en etter en. A starter. Eneste er at tallene som blir trukket fra må være vakre. Den som tar det siste tallet vinner. Hvem har vinnerne strategi

(Antar at hensikten er å etterlate 0 etter sitt trekk.) Den andre spilleren vinner. La $P=2\cdot 3\cdot 5\cdot \dots \cdot 29$ være produktet av de første 10 primtallene. $P$ er da det minste ikke-vakre tallet. Den vinnende strategien er å holde på invarianten at tallet B får i starten av sin tur ikke er delelig med $P$, og at tallet B gir fra seg i slutten av sin tur er delelig med $P$. Siden tallet hele tiden blir mindre må det bety at B er den som først lager 0 og vinner.

Merk først at A hele tiden må gi fra seg et tall som ikke er delelig på $P$ så lenge B gir fra seg et tall som er delelig på $P$, siden alle tall som er delelige på $P$ har minst 10 primfaktorer og derfor ikke er vakre. Samtidig ser vi at dersom B får et tall som ikke er delelig på P har det en rest $Q<P(\mathrm{mod}P)$. B kan derfor holde på invarianten sin ved bare å trekker fra $Q$, som er lov siden $Q<P$ er vakkert.

Forskutterer litt og lanserer en ny oppgave: For et positivt heltall $N$ , la $c_1<c_2<\dots <c_m$ være alle positive heltall mindre enn $N$ som er relativt primiske med $N$. Finn alle $N>2$ slik at $gcd(N,c_i+c_{i+1})>1$ for alle $0<i<m$.

[lfe]

Dette er forgårs EGMO 2025 P1.
$\mathbf{\text{Påstand:}}$ Tallene som tilfredsstiller oppgaven er alle partall og potenser av 3.
$\mathit{\text{Bevis:}}$
Først viser vi at disse tallen tilfredsstiller oppgaven. For partall $N$ vil $c_i$ være et oddetall for alle $i$. Dermed er $gcd(N,c_i+c_{i+1})\ge 2$ siden $c_i+c_{i+1}$ er et partall. Hvis $N$ er en potens av 3, så har vi at $c_i\equiv -c_{i+1}(\mathrm{mod}3)$ fordi annenhver av tallene $c_i$ er kongruente med 1 eller 2 modulo 3. Det gir oss at $gcd(N,c_i+c_{i+1})\ge 3$.

Nå skal vi vise at ingen andre tall tilfredsstiller oppgaven. Anta at $N$ hverken er et partall eller en potens av 3. Hvis $3\nmid N$, så er $gcd(N,1+2)=1$. Vi har dermed at $N=3^{k}a$, der $3\nmid a>1$. $a$ er kongruent med 1 eller 2 modulo 3. Disse to tilfellene gir hhv. at $a-2$ og $a+1$, eller $a-1$ og $a+2$ er et par med påfølgende tall som er ip med $N$. Dette gir enten $gcd(N,2a-1)=1$ eller $gcd(N,2a+1)=1$ fordi vi hhv. har $2a-1\equiv 1(\mathrm{mod}3)$ og $2a+1\equiv 2(\mathrm{mod}3)$.