Tallteorimaraton

[popdit]

Siden ingen har lagt ut ny oppgave, har jeg en her:
Find all prime numbers $p$ and $q$ such that
$$1+\frac{p^q-q^p}{p+q}$$
is a prime number.

Alle primtall $p,q$ som oppfyller dette er $\boxed{(p,q)=(2,5)}$.

$\mathbf{\text{Claim}}$: $1+{\displaystyle \frac{p^q-q^p}{p+q}}=p$

$\mathbf{\text{Bevis}}$: Vi kan vite at $p\ne q$ ettersom det ville gjort at uttrykket er 1, som ikke er et primtall. Vi setter
$$\begin{array}{rl}1+\frac{p^q-q^p}{p+q}& =r\\ p^q-q^p& =(r-1)(p+q)\end{array}$$
som modulo $p$ gir
$$\begin{array}{rl}(r-1)q& =q\\ rq& =0\\ r& =0\end{array}$$
og siden $r$ er et primtall har vi $r=p$.

$\mathbf{\text{Claim}}$: Det finnes ikke løsninger for $p>2$

$\mathbf{\text{Bevis}}$: Vi antar $p>2$. Vi vet at
$$\begin{array}{r}{p}^q-q^p=(p-1)(p+q)\end{array}$$
Refererer videre til denne likningen som $(1)$. Ser vi modulo $q$ finner vi at
$$\begin{array}{rl}p& =(p-1)p\\ p^2& =2p\\ p& =2\end{array}$$
som vil si at $q|p-2$, og siden $p>2$ får vi at $q\le p-2$.

Betrakter vi $(1)$ modulo $p-1$ får vi at
$$\begin{array}{rl}{p}^q-q^p& =0\\ q^p& =1\end{array}$$
Vi skriver $v={\text{ord}}_{p-1}(q)$. Vi vet at $v|\varphi (p-1)$, og fra likningen over vet vi også at $v|p$. Siden $v\le \varphi (p-1)<p$, må vi ha at $v=1$, of vi får videre at
$$\begin{array}{r}q=1\end{array}$$
modulo $p-1$. Men dette betyr at $p-1|q-1$, som igjen betyr at $p-1\le q-1$, men det er en motsigelse ettersom $q\le p-2$. Dermed finnes ingen løsninger når $p>2$.

$\mathbf{\text{Claim}}$: Eneste løsning er $(p,q)=(2,5)$

$\mathbf{\text{Bevis}}$: Vi vet at om en løsning eksisterer må $p=2$, og setter vi det inn i $(1)$ får vi
$$\begin{array}{rl}{2}^q& =q^2+q+2\end{array}$$
Det er lett å se at $q=5$ oppfyller denne likningen, og at det er eneste løsning, ettersom venstresiden vokser eksponensielt, og høyresiden vokser kvadratisk.

[popdit]

$\underset{―}{\text{Ny oppgave:}}$
Bestem alle par av positive heltall $(m,n)$ slik at for alle positive heltall $x$ og $y$ slik at $x|n$ og $y|m$ har vi at
$$\text{gcd}(x+y,mn)>1$$

[Lil_Flip39]

Det holder for ingen $m,n$
Anta for motstigelse vi har et slikt par $m,n$ som oppfyller oppgaven.
hvis $Rad(n)=Rad(m)$ funker $x=1,y=n$ åpenbart
Anta nå $m$ har en primdivisorer som $n$ ikke har.
Vi definerer $S$ som produktet av alle primtall som deler $m$, men ikke deler $n$.
nå plugger vi inn $x=S,y=n$, og da får vi:
$$1<(S+n,mn)=(S+n,Sm)$$
Da har vi et primtall $p$ slik at
$$p\mid S+n$$
$$p\mid Sm$$
Den andre linja impliserer $p\mid m$ siden $S\mid m$
Og av måten $S$ er definert på er det lett å se at $p$ deler presist 1 av $n,S$(primfaktorer til $m$ er fordelt mellom $S$ og $n$), som er en motstigelse.

[Lil_Flip39]

Ny oppgave:
Finn alle par av primtall $(p,q)$ slik at $p-q$ and $pq-q$ er begge kvadratall.

[lfe]

Den eneste løsningen er $(3,2)$.
Vi ser at $q\mid pq-q=q(p-1)$. Dermed må $p-1=q{a}^2$ for et positivt heltall $a$. La $b^2=p-q$. Videre uttrykker vi $p$ og $q$ i $a$ og $b$. Først kombinerer likningene vi har
$$q{a}^2+1=b^2+q$$
Det gir
$$q=\frac{b^2-1}{a^2-1}$$
Videre substiturerer vi for $q$:
$$p=q+b^2=\frac{a^2{b}^2-b^2+b^2-1}{a^2-1}=\frac{(ab-1)(ab+1)}{a^2-1}$$
Vi vet at $a^2-1\mid b^2-1$. Vi får dermed tre tilfeller:
$\mathbf{\text{b=1:}}$ $p-q=1$ impliserer $(3,2)$
$\mathbf{\text{b=a:}}$ Dette gir $p=a^2+1$ som impliserer $q=1$, en motsigelse.
$\mathbf{\text{b>a:}}$ Dette gir oss at $ab-1,ab+1>a^2-1$. Dermed må $\frac{(ab-1)(ab+1)}{a^2-1}$ være et sammensatt tall, motsigelse.

[lfe]

Ny oppgave:
Finn alle positive heltall $m$ og $n$ slik at $mn$ deler både $3^m+1$ og $3^n+1$.

[Lil_Flip39]

løsningene er $(m,n)=(1,1),(1,2),(2,1)$.
Først ser vi på når $m$ eller $n$ er lik $1$.
anta $m=1$, så $n\mid 4$, og det er lett å se at det eneste som går er $(m,n)=(1,1),(1,2),(2,1)$
Anta nå at ingen av $m,n$ er lik $1$.
Påstand: $m,n$ er begge partall.
Da ser vi på det minste primtallet $p$ som deler $m$. Da har vi $p\mid 3^m+1$, som impliserer:
$3^{2m}\equiv 1(modp)$
Nå har vi av fermat og egenskaper av ordne
$or{d}_p(3)\mid gcd(2m,p-1)=1,2$ siden alle tall under $p$ er relativt primisk med tanke på at det er minste primtallsfaktor i $m$.
Da har vi $or{d}_p(3)=1,2$,
$or{d}_p(3)=1$ gir $p=2$,
$or{d}_p(3)=2$ er en motstigelse siden vi får $p\mid 9-1$, som gir $p=2$ som ikke går når $or{d}_p(3)=2$
På lik måte får vi at den minste primtallsfaktoren til $n$ også er $2$, som beviser påstanden.
Nå skriver vi $m=2a,n=2b$ som gir
$4ab\mid 9^a+1$, men siden $9\equiv 1(mod4)$ har vi $9^a+1\equiv 2(mod4)$ som er en motstigelse.

[Lil_Flip39]

Vi ser på mengden $S=\{2^n-3\mid n=1,2,3\cdots \}$. Vis at det eksisterer en uendelig delmengde $X$ av $S$ slik at alle tallene i $X$ er parvis ip
(ip betyr innbyrdes primisk)

[lfe]

Anta for motsigelsens skyld at $X$ ikke eksisterer. Det impliserer at det eksisterer en maksimal delmengde $Y$ av $S$ der alle elementen er ip. La $P(Y)$ være mengden primtall som deler et av tallene i $Y$. Vi konstrurer en $n$ med CRT slik at $n\equiv 0(\mathrm{mod}p-1)$ for alle $p\in P(Y)$. Det følger at $2^n-3\equiv -2\not\equiv 0(\mathrm{mod}p)$ for alle $p\in P(Y)$ siden $2\notin P(Y)$. Det betyr at $2^n-3$ er ip med alle tallene i $Y$ som motsier maksimaliteten.

[lfe]

Ny oppgave:
Vis at for alle $n\in \mathbb{N}$, eksisterer det ip tall $k_0$, $k_1$,$\dots$, $k_n$, alle strengt større enn 1, slik at
$$\left(\prod _{i=0}^n{k}_i\right)-1$$
er produktet av to påfølgende heltall.

[Lil_Flip39]

lemma: antall forskjellige primtallsfaktorer til $n^2+n+1$ er ubegrenset.
Bevis: Anta $n^2+n+1$ har $m$ primfaktorer. Vi viser at det eksisterer et tall som har mer enn $m$ primtallsfaktorer.
Påstand: $n^4+n^2+1$ har flere primtallsfaktorer enn $n^2+n+1$
Først ser vi faktoriseringen $n^4+n^2+1=(n^2+n+1)(n^2-n+1)$
Nå har vi $gcd(n^2+n+1,n^2-n+1)=gcd(n^2+n+1,2n)=gcd(n^2+n+1,2)=1$
så siden $n^2-n+1$ er større enn 1 for $n\ne 1$ er påstanden vist pga gcd greia.

Nå kan vi konstruere $k_i$ slik:
vi vet vi kan konstruere mer enn $n$ primfaktorer, la oss si $m$. Da setter vi hver $k$ til en primtallspotens, også putter vi de resterende primtallspotensene inn i den siste $k$en. Da er vi ferdige

[Lil_Flip39]

ny oppgave:
finn alle $n⩾3$ slik at hvis vi lar $1=d_1<d_2<\cdots <d_k=n!$ være divisorer, har vi
$$d_2-d_1\le d_3-d_2\le \cdots \le d_k-d_{k-1}.$$

[lfe]

Eneste $n$ som tilfredsstiller oppgaven er 3.

AFMS at det eksisterer en $n$, hvor $2n-3>n$, som tilfredsstiller oppgaven. Vi har at $2n-2$ og $2n$ er divisorer av $n!$. Videre har vi av å se på modulo 3 at en av $2n-3$, $2n-1$ og $2n+1$ er divisor av $n!$ siden $\frac{2n+1}{3}<3$. Det impliserer at alle tall mindre eller lik $2n-2$ er en divisor av $n!$ Av Bertrands postulat vet vi det eksisterer et primtall $p$, der $n<p<2n-2$, en motsigelse.

[lfe]

La $p$ være et primtall. Vis at det eksisterer et primtall $q$ slik at $q\nmid n^p-p$ for alle naturlige tall $n$.

[Lil_Flip39]

Påstand:
Vi har en primdivisor $q$ av ${\mathrm{\Phi }}_p(p)$ slik at $v_p(q-1)=1$.
Bevis:
Dette følger av at ${\mathrm{\Phi }}_p(p)\equiv p+1(\mathrm{mod}{p}^2)$
Vi velger nå $q$ som vårt primtall.
Vi har også noen andre ting som kommer opp med syklotomiske polynomer.
Det er velkjent at $or{d}_q(p)=p$, som impliserer:
$p\mid q-1$
$p^p\equiv 1(\mathrm{mod}q)$
så anta for motstigelse at det eksisterer $n$ slik at $n^p\equiv p(\mathrm{mod}q)$.
Hvis vi opphøyer begge sider med $\frac{q-1}{p}$ får vi:
$1\equiv n^{q-1}\equiv p^{\frac{q-1}{p}}\not\equiv 1(\mathrm{mod}q)$. siden vi må ellers må vi ha $p\mid \frac{q-1}{p}$ pga ordere, men det går ikke av påstand 1.