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)?

Nafn þitt

Netfang þitt

Netfang móttakanda

Ruslpóstvörn =

Svar

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 = ax₁ + by₁      (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 = p₁p₂ ... p_r = q₁q₂ ... q_s

Þá gildir að p₁|n og þess vegna p₁|q_i fyrir eitthvert i. En þá er p₁ = q_i 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...