Tag Archives: faktorisering

Faktorisering: Polynom

Her er noen få rakse tips for å faktorisere polynom (opprinnelig skrevet med tanke på en deltaker i runde 2 av Abelkonkurransen).

Nullpunktsmetoden: Finner du et nullpunkt r så vet du at (x-r) er en faktor. Bruk polynomdivisjon for å faktorisere.

Hvis polynomet har heltallskoeffisienter kan du ofte gjette nullpunkt ved å prøve med tall (positive OG negative) som går opp i konstantleddet! Dette er nok det viktigste å vite for å kunne faktorisere polynom av høy grad i Abelkonkurransen.

Her er noen andre idéer som jeg kan si mere om ved anledning.

  • Trekke ut en bestemt faktor fra flere “deler” av polynomet.
  • Faktorisering ved hjelp av substitusjon
  • Prøve seg frem systematisk for å finne en faktorisering
  • Presis regel for gjetting av rasjonale nullpunkt (telleren er en faktor i konstantleddet, nevneren er en faktor i den ledende koeffisienten.)

Abeloppgaver fra Runde 2

Oppgave 5, Runde 2, 2011-2012

Oppgave 1, Runde 2, 2010-2011

Oppgave 7, Runde 2, 2010-2011

Advertisements

Faktorisering: Kvadratsetninger, “kubikksetninger”, og så videre…

Kvadratsetningene er veldig grunnleggende i mange sammenhenger, blant annet når du skal faktorisere uttrykk. Dette er de fire kvadratsetningene:

(a+b)^2 = a^2+2ab+b^2

(a-b)^2 = a^2-2ab+b^2

a^2 - b^2 = (a+b)(a-b)

a^2 + b^2 kan ikke faktoriseres! (ihvertfall ikke som produkt av to polynom)

I disse formlene har vi variabler opphøyd i 2, men vi kan også se på lignende formler for høyere ekponenter. Her er “kubikksetningene”:

(a+b)^3 = a^3+3a^2b+3ab^2+b^3

(a-b)^3 = a^3-3a^2b+3ab^2-b^3

a^3 - b^3 = (a-b)(a^2+ab+b^2)

a^3 + b^3 = (a+b)(a^2-ab+b^2)

Legg merke til den siste, som er helt forskjellig fra tilsvarende situasjon med kvadratsetningene.

Oppgaver:

1a) Faktoriser tallet 1001 ved hjelp av “fjerde kubikksetning”.

1b) Faktoriser tallet 1027.

1c) Regn ut (3x-2)^3

Du kan gå enda høyere. For å raskt regne ut (a+b)^4 og (a-b)^4 og så videre, kan du bruke binomialkoeffisienter. Dette begrepet er noe du bør kunne, og det er også lurt å lære seg om Pascals trekant i denne sammenhengen. Les mere på denne siden og denne siden, eller spør din lærer!

Det er også mulig å formulere regler for a^4-b^4, for a^4+b^4 og så videre. Kort fortalt så kan du alltid trekke ut faktoren (a-b) fra uttrykket a^n-b^n der n er et naturlig tall, MEN du kan trekke ut faktoren (a+b)fra uttrykket a^n+b^n KUN HVIS n er et (positivt) ODDETALL. Skriv selv ned disse formlene på samme måte som kubikksetningene!

Oppgaver:

Faktoriser disse uttrykkene, hvis mulig:

2a) x^3+1

2b) {}x^5+32

2c) {}8x^3-27

2d) {}x^4-4x^3+6x^2-4x+1

2e) {}x^4+1

Utfordring:

3) Uttrykket a^4+b^4 kan ikke faktoriseres. Men hva med uttrykket a^4+4b^4???

Litt om uttrykk i flere variabler

Så langt har vi bare sett på uttrykk med to variabler a og b. Det går selvfølgelig an å formulere andre regler med flere enn to variabler. Her er noen som du absolutt kan ha nytte av i Abelkonkurransen og mange andre ganger i dagliglivet:

(a+b+c)^2 = a^2+b^2+c^2 +2ab+2bc+2ca

{}(a+1)(b+1)(c+1) = abc+ 2ab+ 2bc+2ca + a+b+c+1

Oppgave:

4) Faktoriser uttrykket 8abc + 4ab+ 4bc+4ca + 2a+2b+2c+1

Abeloppgaver fra Runde 2

Oppgave 1, Runde 2, 2012-2013

Oppgave 10, Runde 2, 2012-2013

Oppgave 8, Runde 2, 2011-2012

Oppgave 5, Runde 2, 2011-2012

Oppgave 1, Runde 2, 2010-2011

Oppgave 7, Runde 2, 2010-2011

Oppgave 8, Runde 2, 2010-2011

Oppgave 5, Runde 2, 2009-2010

Oppgave 6, Runde 2, 2009-2010

Oppgave 8, Runde 2, 2009-2010

Oppgave 8, Runde 2, 2008-2009

Oppgave 9, Runde 2, 2007-2008

Oppgave 2, Runde 2, 2006-2007

 

 

Faktorisering: Andregradsuttrykk

For å faktorisere andregradsuttrykk lærer vi i 1T følgende metoder:

  • Trekke ut en felles faktor fra alle ledd: 2x^2 + 8x blir 2x(x+4) når vi trekker ut 2x.
  • Bruke tredje kvadratsetning “baklengs”: 9-4x^2 kjenner vi igjen som tredje kvadratsetning, og faktoriserer slik: (3+2x)(3-2x). Vi kan bruke tredje kvadratsetning når vi har et uttrykk på formen “kvadrat minus kvadrat”.
  • Uttrykket 4a^2 - 20ax + 25x^2 kan vi faktorisere med andre kvadratsetning: (2a-5x)^2. For å undersøke om første eller andre kvadratsetning kan brukes, tar vi roten av første leddet (her får vi 2a) og roten av siste leddet (som her er 5x), ganger sammen svarene og dobler. Hvis dette er detsamme som midt-leddet (her 20ax), har vi et fullstendig kvadrat og kan faktorisere.
  • Noen ganger kan vi “se faktoriseringen i hodet”. For eksempel kan vi bruke “sum-produkt-metoden” hvis vi har et monisk andregradsuttrykk med nullpunkt som er heltall. (Ordet monisk betyr at tallet foran x^2 er lik 1). Eksempel: x^2 + 3x - 10 kan faktoriseres hvis finner to tall med sum 3 og produkt (-10). Tallen vi søker er 5 og (-2), og faktoriseringen blir (x+5)(x-2). En lenger forklaring av denne metoden finner du her.
  • Vi kan bruke fullstendige kvadraters metode. Dette betyr å legge til og trekke fra et bestemt uttrykk, for å ende opp med “kvadrat minus kvadrat”. Metoden er forklart i denne videoen.
  • Vi kan også bruke nullpunktsmetoden. Da må vi først finne nullpunktene (kan gjøres ved abc-formelen, eller ved å tegne grafen til uttrykket, eller ved å gjette seg frem). Når vi har funnet nullpunktene x_1 og x_2 til uttrykket ax^2 + bx + c blir faktoriseringen slik: a(x-x_1)(x-x_2).
  • Ikke alle andregradsuttrykk kan faktoriseres. Hvis uttrykket ikke har noen nullpunkt kan vi ikke faktorisere det. Detsamme gjelder hvis uttrykket kan skrives om som “kvadrat PLUSS kvadrat”.

Mere teori om andregradsuttrykk og andre polynom kommer senere, blant annet om hvordan finne summen av nullpunktene til et polynom, eller hvordan finne summen av koeffisientene.

Algoritmer for faktorisering av store tall

En av mine elever spurte om hvordan man programmerer en egen algoritme i Java for faktorisering av store tall. Her er mitt svar, som kanskje noen andre kan ha nytte av:

Hei!
Det finnes enormt mange ulike algoritmer for faktorisering av heltall, fra den aller enkleste (trekk ut alle 2-tall, så 3-tall, så 5-tall, …), som du sikkert kan forstå og programmere selv nå med en gang, til veldig avanserte metoder, som “quadratic sieve”, “elliptic curve factorization”, og “number field sieve”. For å forstå detaljene i de mest avanserte metodene trenger du flere år av studier, men hvis du er interessert så kan jeg gi deg ganske mye tips og veiledning på veien. Her er litt referenser, fra veldig enkle til veldig avanserte. Setter tall på linkene i tilfelle vi skal referere til dem senere.
Her er en ferdig superenkel faktoriseringsalgoritme i Java:
Her finner du en introduksjon/oversikt over mer moderne algoritmer. Les gjerne hele denne, selv om du ikke forstår alt med en gang.
En annen oversikt over ulike algoritmer finner du på Wikipedia:
(se også de ulike linkene til diverse algoritmer nederst på siden)
Hvis du vil begynne å forstå mer om disse mer avanserte algoritmene må du brette opp ermene og begynne å lære om tallteori. Her nedenfor er noen steder å begynne. Til å begynne med bør du lære om begrepene kongruente tall, største felles divisor (GCD på engelsk), minste felles multiplum (LCD på engelsk) og teori rundt kongruenser inkludert Euler’s teorem, Fermat’s lille teorem og “Chinese Remainder Theorem”. Deretter kan du evt. prøve deg på å forstå og programmere noen halv-avanserte faktoriseringsalgoritmer som Pollard’s rho method, og Pollard’s (p-1) method.
En del forklaring finner du på Wikipedia (klikk deg videre fra disse to sidene til andre)
Og her er litt teori fra Khan Academy:
Disse notatene skrev jeg selv når jeg underviste på universitetet i Nairobi.
Jeg ville begynt her, eller evt. i læreboken for faget Matematikk X. Evt. kan jeg kopiere litt fra denne boken og sende til deg per post – minn meg på dette hvis du er interessert i å ha en tekst som er på norsk.
Her er en liten “bok” av William Chen, som også har mange andre veldig gode ressurser på sin hjemmeside innenfor Calculus m.m. Disse notatene er veldig bra, men det er en utfordring å bli vant med å “lese” matte. Mye av dette stoffet er ikke så vanskelig egentlig, men å lese det på egen hånd, uten noen som forklarer, er ikke helt lett.
Hjemmesiden til William Stein finner du her:
Den inneholder enormt mye spennende stoff. Her er et utvalg:
William Stein er en av personene bak programmeringsspråket SAGE, som er utviklet spesielt for teoretisk matematikk, blant annet for å studere elliptiske kurver, som brukes i noen av de mest avanserte faktoriseringsalgoritmene vi kjenner til.
Her er en annen link som kan være interessant. Den beskriver den berømte “PRIMES is in P”-artikkelen som kom ut for noen år siden.
Nå har jeg prøvd å velge ut noen av de aller beste referansene på området, men selvfølgelig finnes det utrolig mye mere på nettet og i ulike bøker. Å surfe rundt på nettet kan være til stor inspirasjon, men for å virkelig lære ting skikkelig må du sette deg ned med en eller to bøker, lese teorien nøye og arbeide med oppgavene.
Mvh Andreas