matematikk.net

Can you find five prime numbers $p, q, r, s, t$ such that $p^3+q^3+r^3+s^3 =t^3$?

Nei.
Åpenbart kan ikke t være lik 2 eller 3. Av modulo 2 kan vi utag anta at $p=2$. Videre ser vi på modulo 9. q, r og s kan ikke alle være 3 fordi da er ikke venstresiden et kubikktall. Primtall i tredje potwns er kongruente med 1 eller -1 modulo 9. Dermed kan ikke 0 eller 2 av q, r og s være lik 3 siden venstresiden da er kongruent med et partall modulo 9. $2^3+3^4$ er ikke et kubikktall. Dermed kan vi utag anta at $q=3$. Likningen er nå $35+r^3+s^3=t^3$. Til slutt ser vi modulo 7. Vi har at primtall opphøyd i 3 er kongruent med -1 eller 1. Det følger at nøyaktig ett av primtallene på venstresiden er 7. Både r og s kan ikke være det fordi da må også t være delelig på 7, men dersom t er lik 7, så blir venstresiden for liten. Vi må nå løse $378+s^3=t^3$. La $t=s+a$. Vi må nå løse likningen $x^3+3sx^2+3s^2x=378$. Siden $8^3>378$, så kan vi anta at $0<x<8$. Modulo 3 gir oss at 3 deler x. De eneste mulighetene for x er da 3 og 6. Disse kan sjekkes med abc-formel.

Ny oppgave:
Vis at for alle heltall $d>59$ er $\gcd (2^{2^a}+d, 2^{2^b}+d)$ ubegrenset over alle positive heltall $a$ og $b$.

Vi løser oppgaven for alle \(d>2\), og det impliserer oppgaven siden \(2<59\). Vi ser på \(2^{2^i}+d\) som en følge.
Av kobayashi (eller et lett argument) får vi at vi bare trenger å tenke på tilfellet hvor uendelig mange primtall deler \(2^{2^a}+d\), la disse primtallene være i mengden \(P\). Anta at \(\gcd(2^{2^a}+d,2^{2^b}+d)\) er bundet over \(a,b\).

Påstand 1: Vi har \(p\mid 2^{2^a}+d\implies v_2(p)>a\) for alle primtall \(p\) som bare er delelig på \(2^{2^a}+d\) for nøyaktig en \(a\).
Bevis: Vi ser på en slik \(p\), som også oppfyller \(d\not\equiv -1\pmod p\). Da har vi for en \(a\) at \(2^{2^a}\equiv -d\pmod p\). Merk at da vil neste tallet i følgen være \(\equiv (-d)^2\pmod p\), og alle de neste tallene vil være \(\equiv (-d)^{2^k}\pmod p\). Hvis vi ser på likningen \(a^2\equiv a\pmod p\), har vi løsningene
\(a=0\) eller \(a=1\). Åpenbart vil vi aldri nå ha at \((-d)^{2^k}\equiv 0\pmod p\), så vi må ha at eventuelt \((-d)^{2^k}\equiv 1\pmod p\), siden ellers, vil følgen alltid gå til et nytt tall, og eventuelt bli periodisk og gå tilbake til \(-d\), en motstigelse.
Dermed har vi \[(2^{2^a})^{2^k}\equiv (-d)^{2^k}\equiv 1 \pmod p\]
For en \(k\). Hvis vi når ser på \(ord_p(2)\), så har vi \[ord_p(2)\mid 2^{a+k}\] men samtidig har vi \(2^{2^a}\equiv(-d)\not \equiv 1\pmod p\) som impliserer at \(ord_p(2)\nmid 2^a\implies 2^a\mid ord_p(2)\). Av FLT har vi også \(2\mid ord_p(2)\mid p-1\) som impliserer \(v_2(p-1)>a\).

Hvis vi nå ser på \(p\in P\), vet vi enten at \(p\) deler uendelig tall i følgen eller ikke. Merk at mengden primtall som deler flere ledd i følgen må være endelig, siden ellers ville vi kunne valgt et arbitrært stort tall som deler flere tall i følgen, som er en motstigelse.

Påstand 2: \(d=2^{k}\) hvor \(k>0\).
Bevis: \[2^{2^a}+d=C_a\prod_{i=1}^{l}p_i=C_a\prod_{i=1}^{l}(c_i2^{k_i}+1)\] Hvor \(k_i>a\). Her bruker vi påstand 1. Ser for deg nå at vi ganger ut høyre sida. Da vil vi eventuelt få et utrykk på denne formen:
\[C_aL+C_a\] hvor \(L=\prod_{i=1}^{l}(c_i2^{k_i}+1)-1\). Merk at \(2^a\mid L\), så vi har likningen \[2^{2^a}=C_aL+(C_a-d)\]. Hvis nå \(C_a\neq d\), så har vi at vi kan velge \(a\) slik at \[v_2(C_a-d)<a\leq v_2(C_aL)\], som betyr at \[v_2(C_aL+C_a-d)=v_2(C_a-d)<a<2^a\] som er en motstigelse. Da må vi ha \(C_a=d\). Merk også at siden \(C_aL=2^{2^a}\) har vi \(d=C_a=2^k\) som er det vi skulle vise.

Nå trenger vi bare å se på tilfellet \(d=2^k\). Siden \(k>0\), så har \(2^a-k\) en odde primfaktor \(q\) større enn \(1\) for stor nok \(a\). Da vil \[2^{v_2(2^a-k)q}+1\mid 2^{2^a-k}+1\]og vi kan velge \(b=a+q-1\) som impliserer \(q\mid 2^b-k\), og dermed \[2^{v_2(2^b-k)q}+1\mid 2^{2^b-k}+1\]Hvis nå \(a,b>v_2(k)\), har vi \[v_2(2^a-k)=v_2(k)=v_2(2^b-k)\]. Da vil vi ha \[2^{v_2(2^b-k)q}+1\mid \gcd(2^{2^a}+d,2^{2^b}+d)\] og siden vi det er uendelig slik \(q\) er vi ferdig.

For hvilke positive heltall \(b>1\) finnes det uendelig positive heltall \(n\) slik at \(n^2\mid b^n+1\)?

Svaret er alle $b>2$.
Vi viser først at det går for alle $b>2$. La $p$ være et primtall som deler $b+1$. Av Zsigmondy eksisterer det et primtall $q\neq p$ som deler $b^p+1$. Av LTE følger det at $(pq)^2\mid b^{pq}+1$. Vi legger induktivt til flere primtallsfaktorer. Anta at $n^2\mid b^n+1$. Det betyr at $r\mid b^{n/r}+1$ for alle primtallsfaktorer $r$ av $n$. Av Zsigmondy eksisterer det dermed et primtall $p'$ som deler $b^n+1$, men ikke $n$. Av LTE følger det at $(np')^2\mid b^{np'}+1$. Slik kan legge til uendelig mange primtall. Dermed eksisterer det uendelig mange $n$ slik at $n^2 \mid b^n+1$.

Nå viser vi at det ikke er mulig for $b=2$. AFMS at det eksisterer uendelig mange $n$ slik at $n^2\mid 2^n+1$. Åpenbart kan ikke $n$ være et partall. Av LTE kan ikke $n$ være en potwns av 3. La $p$ være det minste primtallet ikke lik 3 som deler $n$. Vi har at $ord_p(2)\mid n$ og at $ord_p(2)\mid p-1$. Av minimaliteten til $p$ er dermed $\gcd(n, p-1)\mid 3$. Det følger at $p\mid 2^3+1=9$, en motsigelse.
$\blacksquare$

Ny oppgave:
Finn alle positive heltall $n$ og $k$ slik at $\prod_{i=1}^k (n+i) -k$ er et kvadrattall.

svaret er \((n,k)=(n^2+1,1), (1,2)\).
Gjennom løsningen bruker vi 2 lemmaer:
Lemma 1:\(n!\mid \prod^{k}_{i=1}(n+i)\) som er sant av binomialkoeffisienter.
Lemma 2: Hvis \(p,q\) er odde primtall og \(p\equiv 3\pmod 4\) og \(-p\) er en kvadratisk rest \(\pmod q\), så er \(q\) en kvadratisk rest \(\pmod p\).
Bevis: Vi har \[\left (\frac{p}{q}\right )\left (\frac{q}{p}\right )=(-1)^{\frac{q-1}{2}\frac{p-1}{2}}\]
Vi deler inn i \(2\) tilfeller:
(1) \(q\equiv 1\pmod 4\):
Da følger det at siden \(-1\) er en kvadratisk rest så er \(p\) også en kvadratisk rest. Dermed har vi
\[\left (\frac{q}{p}\right )=(-1)^{\frac{q-1}{2}\frac{p-1}{2}}=1\] som er det vi skulle vise.
(2) \(q\equiv 3\pmod 4\):
Da følger det at \(p\) ikke er en kvadratisk rest \(\pmod q\). Dette betyr
\[-\left (\frac{q}{p}\right )=(-1)^{\frac{q-1}{2}\frac{p-1}{2}}=-1\] som viser at \(q\) er en kvadratisk rest \(\pmod p\).
Da er begge lemmaene bevist.


Først, kan vi gjøre \(k=1,2,3\). \(k=1\) er trivielt, så når \(k=2\) trenger vi å løse:
\(n^2+3n=k^2\), men for \(n>1\) så har vi \[n^2+2n+1<n^2+3n<n^2+4n+4\] så vi er ferdig med dett tilfellet også.
Hvis \(k=3\), må vi løse \[(n+1)(n+2)(n+3)=m^2+3\]. Vi ser på en primdivisor \(p\) av \(m^2+3\). Av lemma 2 så må \(p\equiv 0,1\pmod 3\) hvis \(p\neq 2\).
Merk at det finnes en av \(n+1,n+2,n+3\) som må være \(\equiv 2\pmod 3\), og da må de ha en faktor av \(2\). Av \(\pmod 8\) kan ikke både \(n+1,n+3\) være partall,
så \(n+2\) er det eneste partallet og må ha en eksponent av \(2\) som er et oddetall. Hvis \[v_2(n+2)=1\]så får vi en motstigelse \(\pmod 4\), siden LHS er kongurent \(2\) og RHS
er kongurent \(0,3\) \(\pmod 4\). Da må \[v_2(n+2)\geq 3\] noe som impliserer \(8\mid n+2\), og når man tar \(\pmod 8\) får man motstigelse av kvadratiske rester.
Nå er vi ferdige med \(k=1,2,3\). Herifra deler vi inn i \(3\) cases.

1. anta \(k=a^2\), \(a>1\).
Da har vi på RHS \(m^2+a^2\). Av fermats juleteorem, har vi da at alle primtall som er \(\equiv 3\pmod 4\) som deler \(m^2+a^2\) må dele både \(m,a\).
Av lemma 1 har vi at alle primtall mindre enn \(a^2\) deler \(m^2+a^2\). Hvis vi nå lar \(a=2^sb\), kan vi se på \(b\). Hvis \(b=1\), får vi at \(a\) ikke er delelig på noen oddeprimtall,
en åpenbar motstigelse siden \(3<a^2\). Videre, hvis \(b=3\) så er \(7<a^2\) og \(7\nmid a\), en motstigelse. Hvis \(b>3\), kan vi da se på \(b^2-2\). Åpenbart har vi \[b^2-2<a^2\]og \[b^2-2\equiv 3\pmod 4\].
I tillegg så er \(\gcd(b^2-2,a)=1\), så \(b^2-2\) må ha en primdivisor på formen \(4l+3<a^2\), en motstigelse.

2. anta \(k=p\), \(p>3\) primtall.
Av lemma \(1\) har vi at for alle \(q<p\) så har vi \[q\mid m^2+p\]. Så har vi av lemma \(2\) at alle disse primtallene må være kvadratiske rester \(\pmod p\). Samtidig har vi av mod \(8\) at \[p\equiv \pm 1\pmod 8\](siden \(p\equiv 4\pmod 8\) ikke er mulig)
Det er velkjent at da er også \(2\) en kvadratisk rest \(\pmod p\). Nå, har vi av multiplisiteten til legendre symbolet at det alle tall under \(p\) må være kvadratiske rester, men dette er åpenbart ikke mulig siden \(-1\) ikke er en kvadratisk rest. Det finnes dessuten bare \(\frac{p+1}{2}\) kvadratiske rester. Motstigelse.

3. anta \(k\) ikke er primtall og ikke er et kvadrattall.
Da har \(k\) en primdivisor \(p\) slik at \[2\nmid v_p(k)\]så \[v_p\left (\prod_{i=1}^{k}(n+i)\right )>v_p(k)\](Dette holder fordi hvis \(v_p(k)=1\), så vil \(2p<k\), og hvis \(v_p(k)>1\) så vil både \(p\) og \(p^{v_p(k)}\) være faktorer i produktet.)
Da må vi ha at \[2\mid v_p(m)^2=v_p(LHS)=v_p(k)\]men dette impliserer \(2\mid v_p(k)\), en motsigelse.

Nå har vi gått gjennom alle muligheter, og vi er ferdige.

For each integer $n \geq 2$, let $F(n)$ denote the greatest prime factor of $n$. A strange pair is a pair of distinct primes $p$ and $q$ such that there is no integer $n \geq 2$ for which $F(n)F(n+1)=pq$.

Prove that there exist infinitely many strange pairs

AFMS at det er endelig mange merkelige par. La $p=2$. Da trenger vi kun å se på $2^n\pm 1$. Hvis det eksisterer uendelig mange par primtall $(r_1, r_2)$ slik at $ord_{r_1} (2) = ord_{r_2} (2)$, så får vi en motsigelse siden $r_1 < r_2$ (UTAG) og vi har at $r_1\mid 2^n-1 \iff r_2\mid 2^n-1$, dermed er aldri $f(n)f(n+1)=2r_1$. Det betyr at $ord_p (2)$ for store nok primtall $p$ er injektiv. Det følger at tettheten til mengden $\{ord_p {2} : p\in \mathbb{P} \}$ asymptotisk er lik tettheten til $2^n$, men vi vet jo at $|\{ord_p (2): p\in \mathbb{P}, p\leq n\}|\geq \pi (n)$, en motsigelse.

La $p$ være et primtall. Finn alle positive heltall $a$ slik at følgen $\{a_n\}$, definert rekursivt som $a_0 = a$ og $a_{n+1} = pa_n -(p-1)\lfloor \sqrt[p]{a_n} \rfloor ^p$, etter hvert blir konstant.