primtalsdelare
Hej
jag har en uppgift där man ska ta fram den minsta primtalsdelaren och jag är inte riktigt med på vilken metod man ska använda sig av.
Uppgiften är:
Hitta det minsta primtalsdelaren till heltalen och
Ska man börja med att sätta och sedan ska man ta reda på vad värdet på n är? men jag förstår inte hur man ska göra för att ta fram värdet på n?
Båda talen är potentiella mersenneprimtal så möjligt att man kan googla lite på metoder för att avgöra om tal är meresenneprimtal eller om de inte är det metoder för att faktorisera dem.
Inga av talen går att faktorisera genom brute-force.
Såvida ni inte explicit jobbar med algoritmer för att avgöra om tal är meresenneprimtal eller ej så skulle jag nöja mig med att det är tabulerat att dessa två tal är mersenneprimtal (och såldes primtal) och därmed att de största primtalsdelarna är talen själva.
är inte ett mersenneprimtal.
Edit: det är inte ens ett primtal ...
233x1103x2089 = 536870911 = 2^29 - 1
men det var ju inte det du frågade om
Hmm, yes läste av tabellen fel. Ja, då går de nog att brute-forca med en for-loop helt enkellt.
kan man inte använda fermats lilla sats:
Om p är ett primtal så gäller
a^p ≡ a (mod p)
jag såg en lösning på problemet som var att man sätter som q=58k+1 och att k=4 vilket ger 233, men jag förstår inte hur man kommer fram till q=58k+1 eller att k=4, svaret stämmer dock.
Det där ser ju ut som en ledtråd som utelämnar allt det svåra!
Fermats lilla sats ger ju att måste vara ett heltal, om vi kallar det heltalet k så gäller:
Men jag har ingen aning om hur det ska hjälpa till med att hitta primtalsdelare!
Har lite brått nu, men jag tror du hittar fortsättningen här (sats 3):
https://en.wikipedia.org/wiki/Mersenne_prime#Theorems_about_Mersenne_numbers
okej då har vi att eftersom q är en faktor av så och p är 29 så då får vi och detta kan vi skriva som så då är vi en bit påväg men hur ska man få fram att k=4?
