Primtalsproblem

Jag har fått en uppgift att redovisa en uppgift. Det går ut på att man ska bevisa att ett tal som följer en regelbunden följd aldrig kan vara ett primtal. Jag vill inte visa formen exakt då jag gärna vill lösa uppgiften själv i så stor utsträckning som möjligt. Kan nämna att talen som produceras inte har någon gemensam faktor (t.ex att alla tal i följden skulle ha 3 eller 5 som faktor). Man bör också kunna lösa det utan att använda sig av induktion, men är inte helt säker. Tack på förhand.

Har du följden på en rekursiv form, eller som ett slutet uttryck?

Enklaste sättet som kan funka är väl att visa att alla tal i uttrycken är delbara med ett visst fixt heltal, t.ex.

Definiera talserien a_n rekursivt genom a_1 = 2, a_2 = 4, a_{n+1} = a_n + a_{n-1} för n ≥ 2. Visa att a_n inte är ett primtal för något n ≥ 2.

Bevis (skiss): Av t.ex. induktion följer att alla a_n är jämna, vidare är (igen t.ex. induktion) a_n ≥ 4 för n ≥ 2, alltså är, för n ≥ 2, a_n ett jämnt tal större än 2 och alltså inte ett primtal.

Det näst enklaste fallet är väl om du får ett explicit uttryck som kan faktoriseras, t.ex.

Visa att n⁴ + 4 aldrig är ett primtal för något heltal n ≥ 2

Bevis (skiss): n⁴ + 4 = (n² + 2n + 2)(n² - 2n + 2), och om n ≥ 2 gäller

1 < n² - 2n + 2 < n² + 2n + 2

och därmed gäller att n² + 2n + 2 > 1, n² - 2n + 2 > 1 så n² - 2n + 2 är en äkta delare till n⁴ + 4.

I svårare fall får man faktiskt ta till andra egenskaper som primtal har som inte gäller för andra tal:

Visa att (4^p - 1)/3 aldrig är ett primtal för något primtal p ≥ 5.

Bevis (skiss): Låt N = (4^p - 1)/3. Av Fermats sats gäller att p | (4^p - 4), och eftersom p inte är 2 och inte 3 så gäller p | (4^p - 4)/6, och eftersom (4^p - 4)/6 är jämnt gäller (2p) | (4^p - 4)/6.

Notera nu att 2^(2p) ≡ 1 (mod N), vilket då medför att 2^((4^p - 4)/6) ≡ 1 (mod N). Så långt allt väl. Betrakta nu a = 2^((4^p-4)/12). Vi har att a² ≡ 2^((4^p-4)/6) ≡ 1 (mod N).

Dessutom är (4^p - 4)/12 ≡ p (mod 2p) (eftersom p delar (4^p - 4)/12 samma resonemang som i första stycket, men det gör inte 2p ty (4^p - 4)/12 är udda).

Detta betyder att a ≡ 2^p (mod N). Men 1 < 2^p < N-1, vilket gör att a varken är kongruent med 1 eller -1 mod N. Men detta gör att ekvationen x² - 1 ≡ 0 (mod N) har minst tre olika lösningar mod N, vilket inte kan ske om N är ett primtal (ty då är Z_N en kropp). Alltså är inte N ett primtal.