6 svar
239 visningar
Jocke011 276 – Fd. Medlem
Postad: 14 jul 2017 15:45

Bestäm SGD

Hej

kan någon hjälpa mig med följande uppgift:

Låt n vara ett positivt heltal. Bestäm SGD(n!+1,(n+1)!)

 

Jag förstår inte hur dom menar, om jag sätter in olika värden på n får jag väl olika SGD

SeriousCephalopod 2696
Postad: 14 jul 2017 15:50

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. 

Dr. G 9479
Postad: 14 jul 2017 15:52 Redigerad: 14 jul 2017 16:02

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. 

Jocke011 276 – Fd. Medlem
Postad: 14 jul 2017 16:01

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

Stokastisk 3597 – Fd. Medlem
Postad: 14 jul 2017 16:31 Redigerad: 14 jul 2017 16:32

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?

Jocke011 276 – Fd. Medlem
Postad: 15 jul 2017 11:14

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

Stokastisk 3597 – Fd. Medlem
Postad: 15 jul 2017 11:42

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!+ 1  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.

Svara
Close