Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Ef p og q eru frumtölur og r = pq, eru þá p og q einu tölurnar sem ganga upp í r (fyrir utan 1 og r)?

Svarið er já. Ef náttúrleg tala r er þáttuð (skrifuð sem margfeldi) og vitað er að tiltekin frumtala s gengur upp í henni, þá gildir almennt að s gengur upp í einhverjum þættinum. Ef frumtalan s gengur upp í r í þessu dæmi vitum við samkvæmt þessu að hún gengur annaðhvort upp í p eða q. Þar sem þær eru báðar frumtölur samkvæmt forsendum getur engin önnur tala gengið upp í þeim og því er annaðhvort s = p eða s = q.

Spurningin heggur nærri grundvallarsetningu talnafræðinnar eða reiknilistarinnar (number theory, arithmetic) sem segir að allar náttúrlegar tölur sé hægt að þátta í frumtölur á einn og aðeins einn hátt, með öðrum orðum að slíkt þáttun sé einrætt ákvörðuð. Þetta er kallað að fullþátta töluna. Við höfum tekið saman meiri fróðleik hér á eftir til að skýra þetta betur og undirbyggja.

1. Um stærsta samdeili

Með stærsta samdeili eða stærsta sameiginlega deili er átt við stærstu náttúrlega tölu sem gengur upp í tveimur tilteknum tölum. Ef tölurnar eru a og b er d stærsti samdeilir þá og því aðeins að d gangi upp í bæði a og b en engin stærri tala geri það. Venslin „m gengur upp í n“ eru táknuð með m|n og því má skrifa hér d|a og d|b. -- Sem dæmi má taka tölurnar a = 12 og b = 18, en þá er stærsti samdeilirinn d = 6.

Ef stærsti samdeilir d er til á annað borð er ljóst að hann er einrætt ákveðinn því að við tökum stærri töluna ef tvær mismunandi tölur koma til greina.

Við ætlum að sýna að minnsta heila plústalan sem hægt er að skrifa sem
d = a x + b y      (1)
sé stærsti samdeilir a og b. Tölurnar x og y eru hér heilar plústölur, mínustölur eða 0 (þær eru í menginu sem oft er kallað Z).

Við getum deilt minnstu heilu plústölunni d upp í töluna a og fáum þá út heila tölu q og tiltekinn afgang r sem er á bilinu frá 0 upp í d - 1:
a = dq + r      (2)
Þá má skrifa, með því að tengja saman (1) og (2):
r = a - dq = a(1 - xq) - byq = ax1 + by1      (3)
sem er á sama formi og d. En við höfðum skilgreint d þannig að hún væri minnsta plústalan á þessu formi svo að þá hlýtur að gilda að r = 0. Með öðrum orðum gengur talan d, sem lýst er með jöfnu (1) og textanum á undan henni, upp í a og á sama hátt má sýna að hún gengur upp í b. Hún er því samdeilir a og b og af jöfnu (1) sést að allar tölur sem ganga upp í a og b ganga líka upp í d. Þannig höfum við sannað að d er stærsti samdeilir. Hann er oft táknaður með d = (a, b). (Dæmi: (2, 3) = 1; (4, 6) = 2; (15, 21) = 3; (27, 36) = 9; (41, 43) = 1).

Með svipuðum rökum má sýna að mengi allra talna sem unnt er að skrifa á forminu ax + by fyrir einhverjar heilar tölur x og y er einmitt mengi allra heiltölumargfelda af d. Jafnan ax + by = n á sér því lausn í heilum tölum x og y þá og því aðeins að (a, b) gangi upp í n. Ef (a, b) = 1 gengur engin eiginleg tala upp bæði í a og b og þá er sagt að þær séu ósamþátta. Þá hefur jafnan ax + by = n heiltölulausn fyrir öll gildi á tölunni n. (Dæmi: Jafnan 2x + 3y = n hefur heiltölulausnir fyrir öll n en jafnan 2x + 4y = n hefur aðeins slíkar lausnir ef n er slétt tala).

Fyrir tilteknar tölur a og b blasir ekki endilega við hvaða tölur x og y eru lausnir á jöfnu (1). Sem dæmi má taka frumtölurnar 41 og 43. Um þær gildir að (41, 43) = 1 en 21 . 41 – 20 . 43 þannig að x = 21 og y = -20. Hægt er að beita svokölluðu algrími Evklíðs til að greiða úr þessu en ekki verður sagt nánar frá því hér.

2. Deiling með frumtölu í margfeldi

Rifjum upp að frumtala er náttúrlega tala sem er aðeins deilanleg með 1 og sjálfri sér. (Talan 1 er þó ekki talin með af tæknilegum ástæðum þannig að minnsta frumtalan er 2 sem er jafnframt sú eina sem er slétt). Hugsum okkur að frumtalan p gangi upp í margfeldi tveggja náttúrulegra talna mn. Þá gildir að p|m eða p|n.

Sönnun:

Ef p gengur ekki upp í m er (p, m) = 1 og til eru heilar tölur x og y þannig að px + my = 1. Þar af leiðir með margföldun að pxn + myn = n. Þar sem p|mn felst í þessu að p|n sem er það sem við ætluðum að sanna.

Sama gildir ef upphaflegu þættirnir eru fleiri en tveir: Ef p gengur upp í margfeldinu þá gengur hún upp í einhverjum þættinum.

Þetta dugir í sjálfu sér til að svara upphaflegu spurningunni eins og fram kemur í inngangi svarsins.

3. Einræðni frumtöluþáttunar

Allar náttúrulegar tölur er hægt að þátta í frumtölur, það er að segja að skrifa þær sem margfeldi eintómra frumtalna þar sem sumar koma að vísu fyrir meira en einu sinni.

Hugsum okkur að hægt sé að þátta náttúrulegu töluna n á tvo vegu í frumtölur:
n = p1p2 ... pr = q1q2 ... qs
Þá gildir að p1|n og þess vegna p1|qi fyrir eitthvert i. En þá er p1 = qi af því að báðar eru frumtölur. Við getum stytt þessa frumtölu út og haldið þannig áfram þar til við höfum sýnt fram á að þáttunin er einræð: Sömu frumtölur koma fyrir báðum megin jafnaðarmerkisins, og jafnoft.

Ef við fáum það verkefni að þátta tiltekna tölu n getum við byrjað á að athuga hvort 2 ganga upp í henni. Ef svo er lítum við á töluna n/2. Kannski er hún slétt líka og þá deilum við 2 aftur út. Þannig höldum við áfram þar til talan er ekki lengur slétt. Þá athugum við hvort 3 ganga upp og höldum áfram að deila með 3 þar til sú deiling gengur ekki lengur upp. Ef talan er ekki mjög stór verður þetta ekki ýkja mikið verk því að við þurfum til dæmis ekki að prófa tölur sem eru stærri en ferningsrótin af n. En þessi aðferð gefur einræða niðurstöðu þar sem n er skrifuð sem 2 í einhverju tilteknu veldi sinnum 3 í einhverju öðru veldi sinnum 5 ... og svo framvegis.




Mynd: HB

Útgáfudagur

23.10.2001

Spyrjandi

Nína Rut

Höfundar

Robert Magnus

prófessor í stærðfræði við HÍ

Þorsteinn Vilhjálmsson

prófessor emeritus, ritstjóri Vísindavefsins 2000-2010 og ritstjóri Evrópuvefsins 2011

Tilvísun

Robert Magnus og Þorsteinn Vilhjálmsson. „Ef p og q eru frumtölur og r = pq, eru þá p og q einu tölurnar sem ganga upp í r (fyrir utan 1 og r)?“ Vísindavefurinn, 23. október 2001. Sótt 18. október 2018. http://visindavefur.is/svar.php?id=1921.

Robert Magnus og Þorsteinn Vilhjálmsson. (2001, 23. október). Ef p og q eru frumtölur og r = pq, eru þá p og q einu tölurnar sem ganga upp í r (fyrir utan 1 og r)? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=1921

Robert Magnus og Þorsteinn Vilhjálmsson. „Ef p og q eru frumtölur og r = pq, eru þá p og q einu tölurnar sem ganga upp í r (fyrir utan 1 og r)?“ Vísindavefurinn. 23. okt. 2001. Vefsíða. 18. okt. 2018. <http://visindavefur.is/svar.php?id=1921>.

Chicago | APA | MLA

Sendu inn spurningu
eða

Vísindadagatalið

Stefán Sigurðsson

1972

Stefán Sigurðsson er dósent í lífefna- og sameindalíffræði við Læknadeild HÍ og forstöðumaður Rannsóknastofu í Krabbameinsfræðum. Stefán hefur mestan hluta starfsferils síns stundað grunnrannsóknir á krabbameinum.