Aritmetikkens fundamentalteorem

[Betelgeuse]

God morgen! Jeg sitter og arbeider litt med aritmetikkens fundamentalteorem og har forstått at dette er en veldig sentral del av tallteori etc, men jeg har litt problem med å utføre slike primtallsfaktoriseringer selv. Plukket opp et triks som sier at hvis tverrsummen av et tall er delelig på 3 så er tallet også delelig på 3. Er det noen andre ting man kan benytte seg av i primtallsfaktorisering? Hvordan går dere frem når dere skal faktorisere et stort tall fullstendig inn i primtallsfaktorer?

[=)]

Hvor store tall snakker vi her?

[Gustav]

Noen ganger kan man benytte:

[tex]m^2-n^2=(m-n)(m+n)[/tex]
[tex]n^3+m^3=(n+m)(n^2-mn+m^2)[/tex]
[tex]n^3-m^3=(n-m)(n^2+nm+m^2)[/tex]

Eksempel:

[tex]9991=10000-9=100^2-3^2=(100-3)(100+3)=97*103[/tex]

[tex]124973=125000-27=50^3-3^3=(50-3)(50^2+50*3+3^2)[/tex]

Får man spørsmål om å faktorisere store tall på typiske mattekonkurranser, vil det ofte være lagt opp til at slike triks kan benyttes.

I andre sammenheng vil det være nødvendig med datamaskin og noen av disse algoritmene:

http://members.tripod.com/irish_ronan/r ... ation.html

[Betelgeuse]

Hvor store tall snakker vi her?

Tall som er så store at det er vanskelig å gjennkjenne faktorene i tallet. Dette er selvfølgelig individuelt

[kenewbie]

Plukket opp et triks som sier at hvis tverrsummen av et tall er delelig på 3 så er tallet også delelig på 3. Er det noen andre ting man kan benytte seg av i primtallsfaktorisering?

Det finnes vel slik regler for alle tall lavere enn 13, bortsett fra 7. 7 er det primeste av alle primtall

Når faktorene blir store så er det variasjoner av erastothenes(sp?) sin algorithme som brukes.

Kort sagt så finnes det ikke noen god metode for faktorisering av store tall, mye moderne kryptering er basert på det faktum at faktorisering er vanskelig/tidkrevende.

k

[=)]

Det finnes da sånne "modulære" triks for alle primtall?

Noen er bare mer effektive enn andre da de beste bare sjekker det siste sifferet (2,5) mens andre reduserer tallet logaritmisk (3,9), de 'dårligste' fjerner bare et fast antall siffer fra hovedtallet (7,23).

Her er triks for de første tusen primtallene.

http://uk.arxiv.org/ftp/math/papers/0001/0001012.pdf

[Karl_Erik]

Wikipedia har en artikkel med diverse lignende 'triks'. Den er ikke like lang som artikkelen =) linket til, men den har et par alternativer på noen av primtallene som kanskje er lettere å ta i hodet.

[Betelgeuse]

knewbie; Etter litt research så har jeg forstått det slik også. Kredittkortnummere baserer seg vel på et det faktum?

Siden jeg er relativt ny innenfor matematikk synes jeg det er facinerende at vi faktisk ikke vet hvordan vårt eget tallsystem fungerer... at vi har vært på jakt etter "the music of the primes" i årtusner.