Bestäm SGD

Ja ,men du ska hitta ett förhållandevis enkellt algebraiskt uttryck involverandes n som möjliggör för dig att beräkna denna storhet.

Tänk formeln för algebraisk summa.

1 + 2 + ... + n = n(n + 1)/2

Vänsterledet är klumpigt och tidskrävande att beräkna för stora n. Högerledet är enkelt att beräkna öven för enorma n. 

Du ska hitta en "enkel" formel som inte kräver att man beräknar n! och sedan applicerar euklides algoritm på två tal med fem miljoner siffror. 

Kan ett tal i fakultet bli udda? När då i så fall? 

EDIT: fast du kan bortse från det här inlägget för att lösa uppgiften märkte jag nu. 

nej, det är väl alltid jämnt?

Säg att d är en gemensam divisor till n! + 1 och (n + 1)!. Kan du då visa att d är relativt prim till alla heltal mindre än eller lika med n?

nja jag är inte helt med på det tyvärr.

Om p är ett primtal och p | (n! + 1) så måste p > n eftersom annars vet vi att p | n! och då kan det inte dela n! + 1. Om p | (n + 1)! så måste p <= n + 1, så om p | n! + 1 och p | (n + 1)! så måste p = n + 1. Vi ser också att p^2 inte kan dela (n + 1)! i detta fall. Sedan vet vi att om n + 1 är ett primtal så gäller det att

$n!\hspace{0.17em}+ 1 \equiv 0 (mod n + 1)$ så vi har alltså två fall. Antingen är n + 1 ett primtal och så är sgd(n! + 1, (n + 1)!) = n + 1, eller om n + 1 inte är ett primtal så måste sgd(n! + 1, (n + 1)!) = 1.