Två utmanande talteoretiska problem

Jag har kommit över ett par matematiska problem som jag själv har kommit en bit på men inte hela vägen. Jag är inte säker på att de är just talteoretiska, men någonstans åt det hållet är de i alla fall.

---

Problem ett

Visa att mängen av alla ändliga mängder av positiva hela tal är uppräknelig

(En ändlig mängd är ett särskilt antal element, så som tal eller andra mängder. Uppräknelighet innebär att varje element i mängden kan paras ihop med ett naturligt tal. En mängd kan vara uppräknelig och oändlig, eftersom att det finns oändligt många naturliga tal.)


Problem två

Bestäm alla primtal p för vilka det finns ett heltal så att

n^3 = 13p+1

---

Nå, har ni några ledtrådar eller idéer? Jag är inte i det här forumet så ofta, så jag vet inte vad för mattesnillen som bor här. Imponera gärna!

För att bevisa det bildar vi en bijektion från mängden ändliga delmängder av Z+ till någon uppräknelig mängd.

Denna bijektion skapas genom att avbilda varje delmängd (a_1, a_2, ... a_n) på talet

2^(a_1 - 1) + 2^(a_2 - 1) + ... + 2^(a_n - 1),

tomma mängden avbildas då alltså på 0. Vi ser då att alla delmängder avbildas på ett unikt tal, och betraktar vi bilden som ett binärt tal inser vi lätt att bilden blir mängden naturliga tal, som ju är uppräknelig.




Uppgiften blir betydligt enklare om man flyttar över ettan till vänstra ledet. Då får vi

n^3 - 1 = 13p.

Att kunna faktorisera uttryck på formen n^k - 1 är en användbar kunskap då man får

(n-1)(n^2+n+1) = 13p.

I högra ledet har vi en produkt av två primtal vilket betyder att något av följande gäller

(n-1) = 1, (n^2+n+1) = 13p

(n-1) = 13, (n^2+n+1) = p

(n-1) = p, (n^2+n+1) = 13
eller
(n-1) = 13p, (n^2+n+1) = 1

Första och sista ekvationssystemen försvinner snabbt, det andra ger p = 211 och det tredje ger p = 2.

Det gick pinsamt fort, jag ska nog stanna här i forumet ett tag.