Kommer inte vidare med induktionsbevis

God eftermiddag!

Jag har lite svårt att se vad det är du har gjort hittills, har du lust att ta det från början? :)

(framförallt, definiera m och p)

Ja, inga problem! Uppgiften lyder:

Visa att varje tal i talföljden $\displaystyle a_n=2^{2^n}+1$ är relativt prima med varandra, då $n\ge 0$.

Jag tänkte att man kunde visa detta med hjälp av induktion. Beviset skulle då gå ut på att visa att $\displaystyle \gcd(a_n, a_{n+k})=1$, oavsett vilket k man väljer. $a_{n+k}$ kan man ju skriva om som $\displaystyle (a_{n}-1)^{2^{k}}+1$, så påståendet som ska bevisas är att:

$\gcd(a_n, a_{n+k})=\gcd(a_n, (a_{n}-1)^{2^{k}}+1)=1$, oberoende av vilket heltal k man väljer.

För överskådlighetens skull ansatte jag substitutionen $m=2^{2^n}$. 

Basfallet i beviset är då k=1 och det är trivialt att visa. Mitt induktionsantagande är sedan att mitt påstående är sant då k=p. Då vill jag på något sätt använda det antagandet för att visa att det stämmer då k=p+1. Mitt antagande säger alltså att:

$\displaystyle \gcd(a_n, a_{n+p})=\gcd(a_n, (a_{n}-1)^{2^{p}}+1)=\gcd(m+1,(m-1)^{2^{p}}+1 )=1$

Intressant!

Två inledande saker jag tänker på:

1. Jag kan inte riktigt se hur basfallet är trivialt, du får gärna skriva ut det lite tydligare (kan vara att det är jag som är lite långsam bara)
2. I sista likheten bör väl a_n-1=m och inte a_n-1=m-1

Det kanske inte är lika trivialt som jag tänkte. Jag tänkte att då k=1 ska vi visa att:

$\displaystyle \gcd(a_n, a_{n+1})=1$

Med samma substitution $\displaystyle m=2^{2^n}$ får vi:

$\displaystyle \gcd(m+1, m^2+1)$, och eftersom dessa polynom är irreducibla måste $\displaystyle \gcd(m+1, m^2+1)=1$

I sista likheten bör väl an-1=m och inte an=m-1

Jo, det har du rätt i. Tänkte fel där. Det borde förstås stå:

$\displaystyle \gcd(m+1, m^{2^p}+1)=1$

naytte skrev:

Med samma substitution $\displaystyle m=2^{2^n}$ får vi:

$\displaystyle \gcd(m+1, m^2+1)$, och eftersom dessa polynom är irreducibla måste $\displaystyle \gcd(m+1, m^2+1)=1$

Gäller det även då $m=2^{2^n}$ för alla $n\ge 0$? Oavsett var det nog bra med en liten förklaring där.

Förutsatt att basfallet gäller, har vi alltså vidare att $gcd(m+1,m^{2^p}+1)=1$ och vi vill med detta visa att $gcd(m+1,m^{2^{p+1}}+1)=1$gäller.

Spontant funderar jag och vi kan se detta tydligare genom att skriva hypotesen som $gcd(2^{2^n}+1,2^{2^{n+p}}+1)=1$ och det vi vill visa som $gcd(2^{2^n}+1,2^{2^{n+p+1}}+1)=1$. Vad tror du?

Vad tror du?

Om det gör det tydligare att se hur man kan gå vidare är det givetvis bättre att skriva det så! Men oavsett hur vi väljer att skriva upp påståendet ser jag inte hur man kan utnyttja induktionsantagandet (men det känns som det borde gå att använda, påståendena är ju så lika).

Det finns ju en sats som säger att om $\displaystyle \gcd(a, b) = d$, så finns det åtminstone ett heltalspar $(x, y)$ som satisfierar ekvationen $ax+by=d$. Det kanske man kan använda sig av här?

Jag försökte använda mig av det förut, men då ledde det ingenstans. Ska testa igen efter att jag har ätit. Kanske leder glukosöverskottet till någon insikt.

Jag tror det kan gå bra med Euklides algoritm, men jag har inte riktigt fått till det.

Om vi utför det hela med lagom stora tal kanske vi kommer på något:

gcd(2^16+1, 2^8+1):

2^16+1 = 2^8(2^8+1) - (2^8 - 1)

2^8+1 och 2^8-1 är relativt prima.

gcd(2^16+1, 2^4+1):

2^16+1 = 2^12(2^4+1) - (2^12 - 1)

2^12-1 = 2^8(2^4+1) - (2^8 + 1)

2^8 + 1 = 2^4(2^4+1) - (2^4 - 1)

2^4+1 och 2^4-1 är relativt prima.

gcd(2^16+1, 2^2+1):

2^16+1 = 2^14(2^2+1) - (2^14 - 1)

2^14+1 = 2^12(2^2+1) - (2^12 + 1)

2^12+1 = 2^10(2^2+1) - (2^10 - 1)

2^10+1 = 2^18(2^2+1) - (2^8 + 1)

2^8+1 = 2^6(2^2+1) - (2^6 - 1)

2^6+1 = 2^4(2^2+1) - (2^4 + 1)

2^4+1 = 2^2(2^2+1) - (2^2 - 1)

2^2+1 och 2^2-1 är relativt prima.

Så 2^16+1 är relativt prim med alla 2^k+1 som är mindre (2^1+1 får någon annan göra). Ovanstående kan formuleras som några bra lemman (hjälpsatser).

Nu har jag inte alls använt det som kunde vara en induktionshypotes, att alla 2^k+1 mindre än 2^n+1 är relativt prima med varandra, så det blir inget induktionsbevis av det här, men det kanske blir ett kortare bevis om man lyckas göra det.

Hej, igen! (och tack för ditt svar, Laguna!)

Jag tror jag kom på ett annat sätt att lösa uppgiften på. Postar mitt förslag här så får ni säga om det är rätt eller om jag tänker knasigt:

Om något tal som ges av $\displaystyle a_{n}=2^{2^{n}}+1$ ska ha någon delare $q$ kommer detta tal alltid kunna skrivas på formen $\displaystyle q=2k+1$, för något $\displaystyle k\in \mathbb{Z}$. För att detta tal ska dela $a_n$ måste resten som den variabla delen bli motsvara $2k$. Således kan vi säga att:

$\displaystyle 2^{2^{n}}\equiv _{2k+1}2k$.

Nu undersöker vi vad som händer då vi lägger till en godtycklig heltalskonstant i vår indexering. Om $2^2^n$ har resten $2k$ då man delar med $2k+1$, då kommer följande gälla:

$\displaystyle (2^{2^{n}})^{2^{p}}\equiv _{2k+1}(2k)^{2^{p}}$

Vi antar nu att detta också är kongruent med $2k$:

$\displaystyle (2k)^{2^{p}}\equiv_{2k+1}2k \implies (2k)^{2^{p}}=z(2k+1)+2k\implies k=\frac{1}{2}\cdot\frac{z}{2^{2^{p}}-z-1}\not\in\mathbb{Z}$

Som vi ser här kan $k$ inte vara ett heltal om båda de variabla delarna ska ha samma rest. Således kan inga tal i serien inte ha samma delare. Det gäller då att $\displaystyle (2^{2^{n}})^{2^{p}}\not\equiv _{2k+1}(2k)$.

Q.E.D.

Tillägg: 28 jan 2024 10:53

Nu när jag kollar på det här igen fattar jag inte vad jag gjorde. Ingen aningen hur jag löste ut k på det sättet. Det stämmer inte i alla fall...

Tillägg: 28 jan 2024 10:58

Men det vi faktiskt ser är att heltalslösningar bara finns då k=-1, eller 0, vilket är samma sak som att gcd(a_n, a_n+p)=1