matematikk.net

Lil_Flip39 wrote: 22/11-2024 20:02 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 $\fbox{$(p,q)=(2,5)$}$.

$\textbf{Claim}$: $1+\dfrac{p^q-q^p}{p+q}=p$

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

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

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

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

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

$\textbf{Bevis}$: Vi vet at om en løsning eksisterer må $p=2$, og setter vi det inn i $(1)$ får vi
\begin{align*}
2^q &= q^2 + q + 2
\end{align*}
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.

$\underline{\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
\]

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.

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

Den eneste løsningen er \((3, 2)\).
Vi ser at \(q\mid pq-q=q(p-1)\). Dermed må \(p-1=qa^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
\[qa^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^2b^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:
\(\textbf{b=1:}\) \(p-q=1\) impliserer \((3,2)\)
\(\textbf{b=a:}\) Dette gir \(p=a^2+1\) som impliserer \(q=1\), en motsigelse.
\(\textbf{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.

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

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 (mod p)\)
Nå har vi av fermat og egenskaper av ordne
\(ord_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 \(ord_p(3)=1,2\),
\(ord_p(3)=1\) gir \(p=2\),
\(ord_p(3)=2\) er en motstigelse siden vi får \(p\mid 9-1\), som gir \(p=2\) som ikke går når \(ord_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 (mod 4)\) har vi \(9^a+1\equiv 2 (mod4)\) som er en motstigelse.

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)

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 \pmod{p-1}\) for alle \(p\in P(Y)\). Det følger at \(2^n-3\equiv -2\not \equiv 0 \pmod{p}\) for alle \(p\in P(Y)\) siden \(2\not \in P(Y)\). Det betyr at \(2^n-3\) er ip med alle tallene i \(Y\) som motsier maksimaliteten.

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.

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\neq 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

ny oppgave:
finn alle \(n\geqslant 3\) slik at hvis vi lar \(1 = d_1 < d_2 < \dots < d_k = n!\) være divisorer, har vi
\[ d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}. \]

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.

La \(p\) være et primtall. Vis at det eksisterer et primtall \(q\) slik at \(q\not \mid n^p-p\) for alle naturlige tall \(n\).

Påstand:
Vi har en primdivisor \(q\) av \(\Phi_p(p)\) slik at \(v_p(q-1)=1\).
Bevis:
Dette følger av at \(\Phi_p(p)\equiv p+1 \pmod{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 \(ord_q(p)=p\), som impliserer:
\(p\mid q-1\)
\(p^p\equiv 1\pmod{q}\)
så anta for motstigelse at det eksisterer \(n\) slik at \(n^p\equiv p\pmod{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 \pmod{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.