primtall og kvadratrot

[emi]

for å finne ut om et tall er et primtall tar man kvadratrota av tallet. Du får ett svar og trenger kun å finne ut om tallene under svaret er delelig med primtallene. eks [symbol:rot] 509=22,56
Så tar du primtallene under 22 og ser om de er delelig med 509.
Hvorfor er det slik at en kan ta kvadratrota av tallet og kun sjekke ut tallene under?

[mrcreosote]

Anta at tallet ikke har noen primfaktorer som er høyst kvadratrota av tallet, men allikevel ikke er et primtall. Da har det minst 2 primfaktorer som er ekte større enn kvadratrota av tallet. Hvorfor er dette umulig?

[Karl_Erik]

Fordi du vet at kvadratrot*kvadratrot = tallet. Det betyr at hvis et tall n kan faktoriserer til ab må en av faktorene være mindre enn kvadratroten til tallet. (Hadde begge vært større enn kvadratroten ville vi jo endt opp med et tall som var større enn det opprinnelige tallet.) Derfor holder det å sjekke (prim)tallene under kvadratroten for å finne ut om det er et primtall.

EDIT: Whoops, litt for sen der, ja.