matematikk.net

Hei,

Jeg sitter å regner på primtallfaktorisering i Kalkulus boken.
Finnes det noen triks når man får høye tall?
Slik som tallet 17 017? og 773?

Tenkte at det kanskje bare var å prøve seg fram og dele på de ulike primtallene. Kom frem til at svaret på 17 017 var 7*11*13*17.

Neste oppgave var da tallet 773. Jeg ser i fasiten at dette er jo et primtall, og det ville da tatt meg uendelig lang tid å prøve meg frem for å dele på primtall her. Finnes det noen lur måte å se at dette er et primtall på?

Det finnes flere triks her som du sikkert kommer til å lære hvis du tar tallteori.

En enkel metode er å finne et primtall som tallet ditt er delelig med, utføre divisjonen, og så sjekke videre på resultatet fra divisjonen.

Her er noen "regler":
- Et partall er alltid delelig med 2.
- Ender tallet på 0 eller 5 kan du dele på 5.
- Er tverrsummen delelig med 3 er også tallet delelig med 3.
- Er den alternerende tverrsummen delelig med 11 er også tallet delelig med 11.

Tusen takk for svar.

De reglene skal jeg skrive ned, har fått med meg det med tverrsum og tallet 3, visste ikke det med tallet 11.

Men hva gjør jeg med tallet 773?

Ut fra reglene (som er ekvivalente, dvs tallet er delelig med 3 hvis og bare hvis tverrsummen er delelig med 3, osv) vet du at tallet ikke er delelig med 2, 3, 5 eller 11.
Den enkle metoden er da å prøve et annet primtall, og da er det 7, 13, osv som er kandidater.

Tja at det er vanskelig å faktorisere store tall er hva som gjør banker og sikkerhetssystemer sikkert.
Men da snakker vi gjerne om tall som faktoriseres til to store primtall

For små tall, trenger du bare å sjekke fra $2$ til $\sqrt{n}$, hvor $n$
er tallet ditt. Her blir det $28$ tall å sjekke som går raskt med kalkulator (den har gjerne en tabell-funksjon)

Ellers for primtall er det litt værre her må du enten gå igjennom de 28 mulighetene
eller bruke litt mer avansert matematikk (tallteori og sannsynlighetsregning)

Når det gjelder begrensning av hvor mange primtall du trenger å teste, så er det greit å se på hva de KAN være.

Eksempelvis ser vi umiddelbart at tallet ikke er partall, og derfor ikke delelig med 2.

Men, det finnes en mulighet for at tallet er delelig med 3. Det betyr at tallet/3 er det høyeste du trenger å gå. Ingen primtall i faktoriseringen av $n$ vil være større enn $n/3$.

Slik fortsetter det å skrenkes inn etter hvert som du utelukker 3, og går videre til 7, 11, 13 osv.

Mao, skal jeg faktorisere tallet 773 så må jeg gå gjennom rekken. Eller som Nebuchadnezzar sier, å ta kvadratroten av tallet for å prøve de 28 mulighetene.

Skal se på CASIO kalkulatoren min om jeg klarer å huske hvordan man setter opp en tabell.

Tusen takk for svar alle sammen.

P.S. det er jeg som regner oppgavene, skal ta Grunnkurs i Analyse I på NTNU til høsten. Har begynt med pensum allerede nå, fordi jeg ønsker å være litt i forkant, så jeg ikke trenger å jobbe meg ihjel i høst

cecmarber wrote:
P.S. det er jeg som regner oppgavene, skal ta Grunnkurs i Analyse I på NTNU til høsten. Har begynt med pensum allerede nå, fordi jeg ønsker å være litt i forkant, så jeg ikke trenger å jobbe meg ihjel i høst

You and me both ^^