Faktorisering: Heltall

Grunnleggende metode:

Ofte vil vi faktorisere et heltall i primtallsfaktorer. Den enkleste metoden er å først trekke ut så mange 2-tall som mulig, deretter 3-tall, deretter 5-tall og så videre. Hvis vi vil faktorisere tallet 112200 kan utregningen settes opp slik:

112200   2

56100     2

28050     2

14025     3

4675       5

935         5

187         11

17           17

1

Konklusjonen her er at tallet 112200 kan faktoriseres som 2^3 \cdot 3 \cdot 5^2 \cdot 11 \cdot 17. Ulempen med denne metoden er at den tar ganske lang tid, men her er noen tips for å bli mer effektiv:

  • Du kan begynne med å trekke ut 10-tall. Da får vi faktoriseringen 1122 \cdot 100 der tallet 100 er veldig lett å faktorisere, og tallet 1122 ikke heller er altfor ille.
  • Et viktig begrep et tverrsum. Tverrsummen til et tall er summen av sifrene i tallet. Tverrsummen til 128200 er 1+1+2+2+0+0 som blir 6
  • Et tall er delbart med 2 hvis og bare hvis siste siffer er delbart med 2 (dvs. siste siffer må være 0, 2, 4, 6, eller 8)
  • Et tall er delbart med 3 hvis og bare hvis tverrsummen er delbar med 3. Vi ser for eksempel at 112200 må være delbart med 3, siden tverrsummen 6 er delbar med 3.
  • Et tall er delbart med 5 hvis og bare hvis siste siffer er delbart med 5 (dvs. siste siffer må være 0 eller 5).
  • Et tall er delbart med 11 hvis og bare hvis den alternerende tverrsummen er delbar med 11. Alternerende tverrsum betyr at annenhvert siffer regnes positivt og annenhvert negativt. I vårt eksempel får vi 1-1+2-2+0-0 som blir 0. Tallet 0 er delelig med 11 og dermed er tallet 112200 også det.
  • Det finnes lignende “test” for delbarhet med 7, med 13, og så videre. Det er også mulig å sette opp en del enkle regler for tall som ikke er primtall, f.eks. delbarhet med 4, 6, 8, og 9. Et viktig prinsipp er at et tall er delbart med n hvis og bare hvis det er delbart med alle primtallspotenser i faktoriseringen av n. Eksempel: For å sjekke om et tall er delbart med 12 sjekker vi om det er delbart med 4 og delbart med 3.

Andre tips for å faktorisere tall

  • Av og til kan vi bruke tredje kvadratsetning. For eksempel, tallene 899 og 391 kan faktoriseres veldig fort på denne måten.
  • Av og til kan vi bruke “kubikksetninger” eller enda høyere versjoner. Eksempel: faktoriser tallet 1007^4 - 1005^4 og tallet 1001 på denne måten (det siste tallet er summen av to kubikktall). Se denne siden.
  • Hvis du kan Euklids algoritme for største felles deler til to tall, kan du fort og enkelt sjekke om et gitt tall har noen felles faktor med et annet. Dette kan av og til brukes til faktorisering.
  • Du kan lære deg utenat alle kvadrat-tall opp til 1024 og alle primtall under 100. Dette kan spare tid og er uansett litt gøy å kunne.
  • For å faktorisere et tall når du har internett-tilgang, gå til Wolfram Alpha og skriv inn f.eks. “factor 9125”.
  • I Abelkonkurransen er det ofte en oppgave der du må faktorisere dagens årstall. Dette kan du ha i bakhodet. For eksempel har vi 2013 = 3 \cdot 11 \cdot 61 og 2014 = 2 \cdot 19 \cdot 53.

Abeloppgaver fra Runde 2

Oppgave 1, Runde 2, 2012-2013

Oppgave 1, Runde 2, 2006-2007

Oppgave 4, Runde 2, 2007-2008

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s