getallentheorie

Moderators: dirkwb, Xilvo

Reageer
Gebruikersavatar
Berichten: 866

getallentheorie

een mooi probleem uit de getallentheorie, het probleem is mooi uitgelegd in de foto in bijlage.
Bijlagen
DSCN0217.JPG

Berichten: 232

Re: getallentheorie

Ik heb mijn computer aan geslingerd en heb er nog eentje gevonden:

1322413225 -sqrt-> 36365

Gebruikersavatar
Moderator
Berichten: 7.574

Re: getallentheorie

...en dat zijn inderdaad de enige twee oplossingen.

Gebruikersavatar
Berichten: 4.022

Re: getallentheorie

Oplossen kan met de computer, maar wat als men de getallen tienmaal zo lang maakt?

Berichten: 524

Re: getallentheorie

Moeten alle vijf cijfers met één verhoogd worden??

Gebruikersavatar
Berichten: 866

Re: getallentheorie

efdee schreef: do 09 dec 2021, 16:57 Moeten alle vijf cijfers met één verhoogd worden??
Aleen laatste zie voorbeeld in foto

Gebruikersavatar
Berichten: 4.022

Re: getallentheorie

Ze vinden is één ding, het aantal ligt wat anders.

Er is een formule voor de dichtheid van de zuivere kwadraten.

Gebruikersavatar
Berichten: 866

Re: getallentheorie

tempelier schreef: do 09 dec 2021, 18:15 Ze vinden is één ding, het aantal ligt wat anders.

Er is een formule voor de dichtheid van de zuivere kwadraten.
ik beschik over een uitwerking die in feite weinig computer rekenkracht behoeft alleen een online bezout coefficienten berekening is aangewezen. Ik zet alles mooi op papier en zet het online morgen.

Berichten: 380

Re: getallentheorie

tempelier schreef: do 09 dec 2021, 13:00 Oplossen kan met de computer, maar wat als men de getallen tienmaal zo lang maakt?
Ik wil Rik niet in de weg zitten ("uitwerking morgen"),
maar voor getallen van 100 cijfers kom ik uit op deze 72 oplossingen:

Code: Selecteer alles

10290755805687756102759541221391214194694161748848 10290755805687756102759541221391214194694161748849  =  32079207916792079208320792079167920792083207920793 ^ 2
10676690519333432831791176652419868351026545818224 10676690519333432831791176652419868351026545818225  =  32675205461226150998127713363914334318028114928615 ^ 2
11278429791437848449983333752293085271977444511743 11278429791437848449983333752293085271977444511744  =  33583373552157991100534872406219607103958490929088 ^ 2
12944020191085089029007133308648494202050595457608 12944020191085089029007133308648494202050595457609  =  35977798975319611717931824638733477274504870205853 ^ 2
13796778867740538164481148826830471590779413396968 13796778867740538164481148826830471590779413396969  =  37144015490709318522142525494585301534500139419437 ^ 2
14243085838927930157091502362075963496000378253080 14243085838927930157091502362075963496000378253081  =  37740013035143390311949446779331715060445046427259 ^ 2
14621282733008360289252115114819493374143580174024 14621282733008360289252115114819493374143580174025  =  38237785936176221406382377859361762214063823778595 ^ 2
14936819043539176652364819247136689788188762663823 14936819043539176652364819247136689788188762663824  =  38648181126075230414356605821636987846375422427732 ^ 2
15080627394189208980806372658958073791459271697888 15080627394189208980806372658958073791459271697889  =  38833783480610293196189299144108175740008730786417 ^ 2
15999999996800000000479999999936000000008000000000 15999999996800000000479999999936000000008000000001  =  39999999996000000000399999999960000000004000000001 ^ 2
18751146047003883032523096844313593561147751463120 18751146047003883032523096844313593561147751463121  =  43302593510093460720204111274779142956480755277239 ^ 2
19270862965726446987656072492669011727352023773720 19270862965726446987656072492669011727352023773721  =  43898591054527532510011032559525556482425662285061 ^ 2
20308368813136701161420892106827515731525636836024 20308368813136701161420892106827515731525636836025  =  45064807569917239314221733415377380742420931498645 ^ 2
21306143244023042554982330056563303563137515986808 21306143244023042554982330056563303563137515986809  =  46158578015384142198461585780153841421984615857803 ^ 2
23791581133699721372905957896367217756770977750915 23791581133699721372905957896367217756770977750916  =  48776614410698618487716680804428777835598452643554 ^ 2
26238352312302484397472596287509662085574072463808 26238352312302484397472596287509662085574072463809  =  51223385589301381512283319195571222164401547356447 ^ 2
28988987213254758158059158496255620719168284271203 28988987213254758158059158496255620719168284271204  =  53841421984615857801538414219846158578015384142198 ^ 2
30178753673302222532977425276072754246683773838735 30178753673302222532977425276072754246683773838736  =  54935192430082760685778266584622619257579068501356 ^ 2
32145959026816961592114874294755307648186240908643 32145959026816961592114874294755307648186240908644  =  56697406489906539279795888725220857043519244722762 ^ 2
37413060432968622588427774370741722311441810125055 37413060432968622588427774370741722311441810125056  =  61166216519389706803810700855891824259991269213584 ^ 2
37640456791388715823651607603862714095437917808360 37640456791388715823651607603862714095437917808361  =  61351818873924769585643394178363012153624577572269 ^ 2
38145710860655917476487359396095968946015932616835 38145710860655917476487359396095968946015932616836  =  61762214063823778593617622140638237785936176221406 ^ 2
38763059768641149533192608803412533375110285398563 38763059768641149533192608803412533375110285398564  =  62259986964856609688050553220668284939554953572742 ^ 2
39508747886321901120196097837659868521779134558095 39508747886321901120196097837659868521779134558096  =  62855984509290681477857474505414698465499860580564 ^ 2
40988422240445865593143484031181539653040855045903 40988422240445865593143484031181539653040855045904  =  64022201024680388282068175361266522725495129794148 ^ 2
44111682687121866248913588939853871064060462653568 44111682687121866248913588939853871064060462653569  =  66416626447842008899465127593780392896041509070913 ^ 2
45326279596881130835535749924591199714970315960995 45326279596881130835535749924591199714970315960996  =  67324794538773849001872286636085665681971885071386 ^ 2
45576536886920935676947909605356795451102367065040 45576536886920935676947909605356795451102367065041  =  67510396893308911783704979958556853575605193430071 ^ 2
46132339972103597686117957063055372610527745907263 46132339972103597686117957063055372610527745907264  =  67920792083207920791679207920832079207916792079208 ^ 2
47164772292878428918283442115159160275151511759024 47164772292878428918283442115159160275151511759025  =  68676613408698618587915680814408677835600462643655 ^ 2
47730147571027025313156535529757621537414351155263 47730147571027025313156535529757621537414351155264  =  69087008598597627595889908776683903467912061292792 ^ 2
47986946282640791860353864734755237146144448281528 47986946282640791860353864734755237146144448281529  =  69272610953132690377722602099155091361545369651477 ^ 2
52671603034596826783759265065402795210643831551224 52671603034596826783759265065402795210643831551225  =  72575204467226151097526713373974234318022124928715 ^ 2
54377971685353783179185989848385737830317861005400 54377971685353783179185989848385737830317861005401  =  73741420982615857901737414229826058578017394142299 ^ 2
54673340326941125619664521271681211257676244125800 54673340326941125619664521271681211257676244125801  =  73941422982615857701739414209826258578017374142099 ^ 2
55260517932657861384835130572198652450199378314640 55260517932657861384835130572198652450199378314641  =  74337418527049929691544335514572472103962301150121 ^ 2
56003058760777915177066878166742339753512751122848 56003058760777915177066878166742339753512751122849  =  74835191428082760785977266594602519257581078501457 ^ 2
56618983054841971928274267246806123324622954552835 56618983054841971928274267246806123324622954552836  =  75245586617981769793951494556877744889892677150594 ^ 2
56898642698075450081659922899448342885488995099840 56898642698075450081659922899448342885488995099841  =  75431188972516832575784187879348932783525985509279 ^ 2
58671625274787748361286259505227234324982934916768 58671625274787748361286259505227234324982934916769  =  76597405487906539379994888735200757043521254722863 ^ 2
62419844667520640405765632904199019101187781592048 62419844667520640405765632904199019101187781592049  =  79006230556533097015561147625243639320434305640743 ^ 2
63840098405196010119518800024023760099598020010200 63840098405196010119518800024023760099598020010201  =  79899999002000000099799000010019899999998010000101 ^ 2
64160101605204009879521199976024240100397980009800 64160101605204009879521199976024240100397980009801  =  80100001001999999899800999990020099999997989999901 ^ 2
64796054600035260287690562860946600980462844773928 64796054600035260287690562860946600980462844773929  =  80495996546434071889605921294766313525942917007923 ^ 2
66041981095836976248412479062226730402840805845224 66041981095836976248412479062226730402840805845225  =  81266217517389706704011700845871924259993259213485 ^ 2
66687170421547021721408091739906070215581669351048 66687170421547021721408091739906070215581669351049  =  81662213061823778693816622150618137785938186221507 ^ 2
67014222548282878981688920189736228791454900788248 67014222548282878981688920189736228791454900788249  =  81862215061823778493818622130618337785938166221307 ^ 2
68485528062589672988079451720009438187024271842224 68485528062589672988079451720009438187024271842225  =  82755983507290681578056474515394598465501870580665 ^ 2
72530446197726265347171685732596890734828437117024 72530446197726265347171685732596890734828437117025  =  85164808575917239213622733405437480742414921498545 ^ 2
74530458933158694870154157091979958832896147712640 74530458933158694870154157091979958832896147712641  =  86331025091306946017833434261289305002410190712129 ^ 2
74851268246026227512779609799188043849681386622595 74851268246026227512779609799188043849681386622596  =  86516627445842008799666127583760492896043499070814 ^ 2
75563072643146312867009316323706294970398823442400 75563072643146312867009316323706294970398823442401  =  86927022635741017807640355546035718528355097719951 ^ 2
75715058677262122572843408119459269837155904933903 75715058677262122572843408119459269837155904933904  =  87014400346874839894099058663790540049662276422148 ^ 2
76430948746467126913756291816658857368259331836368 76430948746467126913756291816658857368259331836369  =  87424795536773848902073286626065765681973875071287 ^ 2
77124913461291687029750658078743116868541925917480 77124913461291687029750658078743116868541925917481  =  87820791081207920891878207930811979207918802079309 ^ 2
77476600146448201609555355057278282017856734233880 77476600146448201609555355057278282017856734233881  =  88020793081207920691880207910812179207918782079109 ^ 2
79543226807835973016737438239457298935744355192248 79543226807835973016737438239457298935744355192249  =  89187009596597627496090908766664003467914051292693 ^ 2
83871592402783855938989502167808605699418162413763 83871592402783855938989502167808605699418162413764  =  91581435019759248113487860999177873638460430569458 ^ 2
84785805313204587785511224389765709244191745907263 84785805313204587785511224389765709244191745907264  =  92079207920792079207920792079207920792079207920792 ^ 2
85543266835731586217047343970466928589233593344760 85543266835731586217047343970466928589233593344761  =  92489603110691088215895020041483146424390806569931 ^ 2
85886937080218830465861123125319617558154775675455 85886937080218830465861123125319617558154775675456  =  92675205465226150997727713363954334318024114928616 ^ 2
86649290493254376176425125315303190987719576529008 86649290493254376176425125315303190987719576529009  =  93085600655125160005701941326229559950335713577753 ^ 2
88834050399441610737698400770662785701232082247568 88834050399441610737698400770662785701232082247569  =  94251817170514866809912642182081384210330982791337 ^ 2
88998836909176901805852551132550578537545523809155 88998836909176901805852551132550578537545523809156  =  94339194881648688896371345299836205731638161493534 ^ 2
89184262065502816692297349449747494542751310600483 89184262065502816692297349449747494542751310600484  =  94437419525049929591745335504552572103964291150022 ^ 2
90126907609773615688112899228241302257531773838735 90126907609773615688112899228241302257531773838736  =  94935192426082760686178266584582619257583068501356 ^ 2
90907810778368562050091007157088450284842978745024 90907810778368562050091007157088450284842978745025  =  95345587615981769694152494546857844889894667150495 ^ 2
96506625864278848851179163971121378717263932616835 96506625864278848851179163971121378717263932616836  =  98237785940176221405982377859401762214059823778594 ^ 2
97824422446939962903281811389635310605110401032335 97824422446939962903281811389635310605110401032336  =  98906229554533097115760147635223539320436315640844 ^ 2
98811557041861570854160933800092438531125169183683 98811557041861570854160933800092438531125169183684  =  99404002455565928210193078715253586474055092992178 ^ 2
99006931976544364217726526319820314727920471579555 99006931976544364217726526319820314727920471579556  =  99502227098967168905567068919969952846381222648666 ^ 2
99180893862320904420704431963247877312003230844768 99180893862320904420704431963247877312003230844769  =  99589604810100990992025772037724774367688401350863 ^ 2

Gebruikersavatar
Berichten: 866

Re: getallentheorie

hierbij een voorstel tot oplossing
Bijlagen
DSCN0219.JPG
DSCN0218.JPG

Berichten: 380

Re: getallentheorie

Rik Speybrouck schreef: vr 10 dec 2021, 12:11 hierbij een voorstel tot oplossing
Neem onderaan in je 2e Voorstel niet t=1 maar t=0.

Gebruikersavatar
Berichten: 866

Re: getallentheorie

RedCat schreef: vr 10 dec 2021, 13:38
Rik Speybrouck schreef: vr 10 dec 2021, 12:11 hierbij een voorstel tot oplossing
Neem onderaan in je 2e Voorstel niet t=1 maar t=0.
iderdaad zo werkt het ook

Berichten: 380

Re: getallentheorie

Rik Speybrouck schreef: vr 10 dec 2021, 12:11 hierbij een voorstel tot oplossing
Mooie oplossing!

Ik heb iets andere technieken uit de getaltheorie gebruikt:

Voor de gezochte n moeten er getallen a en b bestaan, zodanig dat
n = 100001*a + 1 = b²
ofwel
b² ≡ 1 mod 100001
Los hieruit b op (zie bijvoorbeeld https://en.wikipedia.org/wiki/Quadratic ... uare_roots):
Ontbindt eerst 100001 in factoren:
100001 = 11 * 9091
dit geeft het stelsel:
b² ≡ 1 mod 11
b² ≡ 1 mod 9091
en dus in beide gevallen: b = ±1
Vervolgens krijgen we met de Chinese reststelling (https://nl.wikipedia.org/wiki/Chinese_reststelling) deze 4 oplossingen:
(b ≡ 1 mod 11) ∧ (b ≡ 1 mod 9091) → (b ≡ 1 mod 100001)
(b ≡ -1 mod 11) ∧ (b ≡ 1 mod 9091) → (b ≡ 36365 mod 100001)
(b ≡ 1 mod 11) ∧ (b ≡ -1 mod 9091) → (b ≡ 63636 mod 100001)
(b ≡ -1 mod 11) ∧ (b ≡ -1 mod 9091) → (b ≡ 100000 mod 100001)
en met n = b² vinden we de bijbehorende n-waarden:
n = 1
n = 1322413225
n = 4049540496
n = 10000000000
Alleen de 2e en de 3e voldoen aan de overige eisen,
wat je direct kan zien aan n, of indirect via a = (b²-1)/100001.


Voor de 100-cijfers variant van Tempelier hebben we op dezelfde manier:
100000000000000000000000000000000000000000000000001 =
101 * 3541 * 27961 * 60101 * 7019801 * 14103673319201 * 1680588011350901
en geeft de Chinese reststelling 2^7 = 128 oplossingen, waarvan er 72 voldoen.

Noot: ik heb hierbij de eis gebruikt dat alleen het laatste cijfer 1 hoger mag zijn, en dus dat het getal a niet op 9 mag eindigen (anders zouden meerdere cijfers veranderen als we a met 1 verhogen).
Sta je dit laatste wel toe, en verruim je de opgave naar "de 2e helft van het getal is 1 meer dan de 1e helft", dan komen er nog 7 oplossingen bij:

Code: Selecteer alles

10555743100303112109537949688243088299891980204899 10555743100303112109537949688243088299891980204900  =  32489603106691088216295020041443146424394806569930 ^ 2
31473680856671381967634007373617898762500699203599 31473680856671381967634007373617898762500699203600  =  56101408945472467489988967440474443517574337714940 ^ 2
36000000004799999999680000000015999999999999999999 36000000004799999999680000000016000000000000000000  =  60000000003999999999600000000039999999996000000000 ^ 2
49253417472318071526711841624175198649330538802499 49253417472318071526711841624175198649330538802500  =  70180779044064530480129761141460364147475745651950 ^ 2
86812038976393642956961973576760096519309172002499 86812038976393642956961973576760096519309172002500  =  93172978366258982092160644443984381471642892279950 ^ 2
88062124793440130641431352623779328168829820839999 88062124793440130641431352623779328168829820840000  =  93841421980615857801938414219806158578019384142200 ^ 2
95531101488919199573620389617995022198810471107599 95531101488919199573620389617995022198810471107600  =  97740013039143390311549446779371715060441046427260 ^ 2

De limitatie van bovenstaande oplossingen ligt in de priemontbinding van 10k+1:
voor (niet eens zo heel veel) grotere k-waarden zal dit niet meer mogelijk zijn...

Berichten: 1

Re: getallentheorie

Beste forumleden,
Weet iemand het antwoord op het volgende?
Het betreft Sophie Germain-paren, P en 2P+1 zijn beide priem, bijv. 3 en 7, 5 en 11, 19391363 en 38782727 (het hoogste paar dat bij OEIS staat).
Voor zover mij bekend is wiskundig bewezen dat 2^p-1 deelbaar is door zijn S.G.-component 2P+1 als P bij deling door 4 een restwaarde 3 geeft. Bijvoorbeeld 2^11 is deelbaar door 23 omdat 11/4 een restwaarded 3 geeft.
Geeft P bij deling door 4 een restwaarde 1, dan is niet 2^P-1 maar 2^P+1 deelbaar door zijn S.G.-component. Bijvoorbeeld niet 2^29-1 maar 2^29+1 is deelbaar door 59.
Maar hoe werkt dat bij machten van 3?
Niet 3^3-1 maar 3^3+1 is deelbaar door 7, maar het lijkt erop dat voor alle hogere S.G.-paren geldt dat 3^P-1 deelbaar is door zijn S.G.-component: 3^11-1 is deelbaar door 23, 3^29-1 is deelbaar door 59, enz.
Ik heb dit voor alle S.G.-paren gecheckt voor zover mijn computer dat aankon, maar anders dan in de natuurkunde geldt empirisch onderzoek in de getallentheorie uiteraard niet als bewijs.
Mijn vraag is dus: bestaat dat bewijs, dus is 3^p-1 altijd deelbaar door zijn S.G.-component behalve voor P=3?
Overigens, voor hogere grondtallen zoals bijv. 5 en 7, lijkt het volkomen willekeurig of G^P-1 dan wel G^P+1 deelbar is door 2P+1. Maar mogelijk is hier meer van bekend?

Benieuwd naar reactie.

Berichten: 380

Re: getallentheorie

Definieer q = 2p + 1 met p en q beide priem.
Te bewijzen:
\(q \;|\; 3^p-1\)
ofwel
\(3^p-1 \equiv 0 \mod q\)
ofwel
\(3^p \equiv 1 \mod q\)

[1] Volgens de stelling van Euler (https://nl.wikipedia.org/wiki/Stelling_van_Euler) is voor q ≥ 5:
(merk op: als q ≥ 5 dan is altijd gcd(3, q) = 1):
\(3^{\varphi(q)} \equiv 3^{q-1} \equiv 3^{2p} \equiv (3^p)^2 \equiv 1 \mod q\)
Dus
\(3^p \equiv \pm 1 \mod q\)

[2] Met het Legendre symbool tonen we aan dat 3p een kwadratisch residu is mod q (q ≥ 5):
(https://nl.wikipedia.org/wiki/Legendre-symbool)
\(\left( \frac{3^p}{q}\right) = \left( \frac{3}{q}\right) = - \left( \frac{q}{3}\right) = -\left( \frac{2}{3}\right) = -(-1) = 1\)
tweede gelijkheid wegens:
p = 2k+1 → q = 2p+1 = 4k+3 ofwel: q ≡ 3 mod 4, en tevens (triviaal): 3 ≡ 3 mod 4
derde gelijkheid wegens:
- als p mod 3 = 0 dan is p niet priem
- als p mod 3 = 1 ofwel p = 3k+1, dan is q = 2p+1 = 2(3k+1) + 1 = 6k + 3 = deelbaar door 3 (dus q niet priem)
Dan moet p mod 3 = 2 zijn en is
q ≡ 2p + 1 ≡ 2*2 + 1 ≡ 5 ≡ 2 mod 3

[3] Via het criterium van Euler tonen we aan dat -1 géén kwadratisch residu is mod q:
(https://nl.wikipedia.org/wiki/Legendre- ... _van_Euler)
Onder [2], tweede gelijkheid, hadden we al gezien dat q ≡ 3 mod 4 ofwel q = 4k + 3.
Volgens het criterium van Euler geldt dan:
\(\left( \frac{-1}{q} \right) = (-1)^{(q-1)/2} = (-1)^{2k+1} = -1\)

[4] 1 is wèl een kwadratisch residu (triviaal):
\((-1)^2 \equiv 1^2 \equiv 1 \mod q\)

Conclusie uit [1] t/m [4]:
Voor q ≥ 5 moet 3p ≡ 1 mod q zijn, ofwel: q deelt 3p - 1

Reageer