Aritmetikkens fundamentalteorem

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Post Reply
Betelgeuse
Ramanujan
Ramanujan
Posts: 260
Joined: 16/04-2009 21:41

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?
=)
Descartes
Descartes
Posts: 447
Joined: 09/05-2007 22:41

Hvor store tall snakker vi her?
[tex]\int_0^3 \frac{\left(x^3(3-x)\right)^{1/4}}{5-x}\, \mathrm{d}x = \frac{\pi}{2\sqrt{2}}\left(17-40^{3/4}\right)[/tex]
Gustav
Tyrann
Tyrann
Posts: 4563
Joined: 12/12-2008 12:44

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
Ramanujan
Ramanujan
Posts: 260
Joined: 16/04-2009 21:41

=) wrote:Hvor store tall snakker vi her?
Tall som er så store at det er vanskelig å gjennkjenne faktorene i tallet. Dette er selvfølgelig individuelt :P
kenewbie
Cayley
Cayley
Posts: 80
Joined: 02/11-2008 19:53

Betelgeuse wrote: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
=)
Descartes
Descartes
Posts: 447
Joined: 09/05-2007 22:41

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
[tex]\int_0^3 \frac{\left(x^3(3-x)\right)^{1/4}}{5-x}\, \mathrm{d}x = \frac{\pi}{2\sqrt{2}}\left(17-40^{3/4}\right)[/tex]
Karl_Erik
Guru
Guru
Posts: 1080
Joined: 22/10-2006 23:45

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
Ramanujan
Ramanujan
Posts: 260
Joined: 16/04-2009 21:41

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.
Post Reply