SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
Chukchi
Topic Author
Posts: 915
Joined: December 15th, 2001, 3:43 am

1913

December 11th, 2013, 8:42 pm

Prove that A. 1910^1912 - 1912^1910 is divisible by 1913.B. (p-3)^(p-1) - (p-1)^(p-3) is divisible by p for all prime p>3.
 
User avatar
cm27874
Posts: 69
Joined: July 2nd, 2007, 12:10 pm

1913

December 12th, 2013, 12:07 pm

mod p:[$](p-3)^{p-1} - (p-1)^{p-3} = (-3)^{p-1} - (-1)^{p-3} = 3^{p-1} - 1 = 3^p / 3 - 1 = 3 / 3 - 1 = 0[$]in step 2: p is odd and p > 3in step 3: p > 3in step 4: Fermat
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

1913

December 12th, 2013, 12:08 pm

It follows from Fermat's little theorem: a^(p-1) = 1 mod p for p prime, a not divisible by p.(p-3)^(p-1) = 1 mod p (by setting a = p-3 in Fermat)(p-1)^(p-1) = 1 mod p (by setting a = p-1 in Fermat)Now expand:(p-1)^(p-1) = ((p-1)^(p-3)) * (p-1)^2 = ((p-1)^(p-3)) * (p^2 - 2p + 1) = (p-1)^(p-3) mod p = 1 mod pCombining the above, we get (p-3)^(p-1) - (p-1)^(p-3) = 0 mod p.
 
User avatar
yegulalp
Posts: 20
Joined: February 18th, 2008, 11:39 am

1913

December 12th, 2013, 12:08 pm

Doh! Took too long to type it in.
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

1913

December 21st, 2013, 6:06 am

how about proving it for p=1729 (the "dull" Hardy-Ramanujan #)? and how about p=286 or 24046?----- ----- ----- ----- -----spoiler/comments:(1) simply expand the powers using binomial theorem, one gets 3^(p-1)=1 (mod p). besides all primes (as indicated above by Fermat's little theorem), there are composite numbers that satisfy this relation: Fermat pseudo-primes to base 3;(2) one might consider the general form (p+m)^(p+n)-(p+n)^(p+m)=0 (mod p). if sufficiently large prime p satisfies the equation, seems one needs either m or n=-1 or m=-n
 
User avatar
ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

1913

December 21st, 2013, 7:36 pm

QuoteOriginally posted by: ChukchiProve that A. 1910^1912 - 1912^1910 is divisible by 1913.1910^1912 - 1912^1910=2166692594352408499924447933736491626283407649922349056989156738398908954448711039960410358002285823305151178931503746864208580476846758354923604808394430569155692524918947114669043346511848537297677188078148554948907472683648739741779177646396994065873077526260647064444388112891001920512965071311112000755698253366467898905569972225903368365546910855972284135643434032818102005387759858495178332194844318798525183468100517353225532661054748679306413232319280011069610439178387382008859948234384386515067616962829254371748951330534133005498194101189358597654442590611106373147306195497379217851556027851537367635475677553113719998379692661079736246392107773639437988185671410286922031695298445913761848984240867805158168266139403195756737923251527062567268381621460914819471230977805684147535843805466366652053013049109276584615738981452133431376364059312225865762881978555160421199453077967873465499185392346196010332520055488778244024952593142305779167742450831765601736869167751557359031574231185194790402898230358662455324730545007228751103093913894144436271037350176417758225259032641129457584669091470165347113905870106271806034332513533865995688556862795959445747122324324054727194637917983145211570595179259640641946655484867170859718467455274138098462363523907564782486037787129513290156783884869438709131137058791290364446307641776439787122842938318731584593655685400490320277052726993098974294817218332278686779682808952667770195966683558708011457228446883943061813885302811022465807272553592922448835066531060269440298199658010580220662678783366603514373231266683313815116317928825626853262472904879351234690820574555993186986473684564752625167769618548288165720595358514635836294444744506239167399711328410695743078231466646519429764312544033773607927862305156733494832266649836526000008241434598050972575384881201575448534764487977181166057458105723679960970625077583033256961217384193832487434047049377912900073804272237023530584735786861578751146715180716162042963068201799881710101835895144465043518153772269208364280933532809148745321604228304709352501131642394633621408136747192102428992170990939402137748435580057432553501618402326777732906725083555693781144675518651720030705949631977255940362910924404002915611702367526862482798230682055585888644619617154133680143839906631830088558304618041264726473350856412476763298846610742124416322230526051502331502271667588085994296736712227428647295804786392265403805610848337267337091987341577731044628464368417615444504502353821911093580577983931089231203176628135167621935762673150118323217149265006191042696512181666186715128644420165867390877969290778859830222046935263914487366490228733585682168640060183923110816308733890702726030493539859379001042119692908780713709295709778039014047181862139260254524258171370648726936180166912120150399376558023746026840196709728209574157212417615466152968238235551751637352641881581129274565525418276357092859452151291297439348906742948806233824128535238154728201365026196426068035266040855745801009220312114299149863470928887739208035659857845279200404648531169842382730236241925282203377565143657130222197907553046598593352888249255961071342200605899342139166258403753287085690030155217347621579055546889585333395373073854240736006995653037047724399199640984196680160942057617180790772663048036501088423869520607523401679418242033893936335274595698430569413832826243814864629580527772348496567187400971069678869877064686387300337319708703545217283771313976923642938736459386645945382057241216492489795910280159419694085404711385457444750330355531795814573548450134987523435280754781256763413067598851903555037883457820742796258656779951668231595439018619529973902099009887656955209207221828079832275760624038587096288767832892704901195314208656877083663250249208737779179292864644218553529981770308497336738253931134341116736599003385999994938338120287378518609447838926950753418183593924551047499305810810652277901301337835913235477118605299814055133450398192958314433956461646110020726457513205895043444815061867592897262955354936210982039371517264654284019466001999984573814574041649276208915498942362513289416385583192209073522209035709436889966428821435288952174470741037115537948030738755640889237468574381965414168789645136532220793338602081511148044900545083849181982549381104014564403881347047502523960083459016568583782980475974461834800791705278671644826277263264619661631981381052835553893391516454222978858447964088614231376907519118293980203014415486189281006891790866654528212556488489628512751279062473515821670373041729209803022984996658943565450249780438240376399569879419277286931446785562566916709678164081953077257097743763508406760801429627346199225024024315997067296391296368352299571832195265177900623768289161472383442532040785499410750649064981112433283662982547454844245273131273436500554016402580838217341134666703181383989333742598416858439777712623387097223914235346787530183007464728261363788241544519289289975138185927098692030344932294619364111044473754070583794673315876732887053018394884678901017793987403316596267579503291308491013894656894939912322686699914689449674448563023717007835047779669588284846093040215089505627084049740759785186513995331089842468273444881199038342677409168866834625254855860878385490435800612594320911794200302201059917048853725155986884048374869025948583219791356116413720859044736606121044389671602714255771773986179050768194462240172357279488983986220487781189807044209098986328727300534502383194305712614044240534837237637024074684169726197578972512327330604269802760429131080994078827273427178749951289980154338671537630927677995991592892509644645984168123457732859936456863526201721090913010517070992065680267559453213292897299591771141984643287648832216635727055759205097564059546043458577531063583344661604580565943253074876167258005596737251837526653797305309798890624695399750401418640226306114321932375493107603589645794145151851128037465749067003294542376167487613642249892093866320035739459903248008326946229586370353431054210128541044037456100608452757592937169887846869740361560755363486652577461852539119597646393857161722804080393595967696631920378822469850253340034765913265556253044115741557529096669982844252085340228463399276088119609084416677817841729652423987954928021223243776divide by 1913 and you get1132615051935393883912413974770774504068691923639492450072742675587511215080350778860643156300201684947805111830373103431368834540954918115485418091162796951989384487673260384040273573712414290275837526439178544144750377775038546650172074044117613207461096459101226902480077424407214804240964491014695243468739285607144745899409290238318540703370052721365543196886269750558338737787642372449126153787163784003410968880345278281874298306876502184687095259968259284406487422466485824364275979212955769218540312055843833963277026309740790907212856299628519915135620800110353566726244744117814541480165200131488430546511070336180721379184366262979475298689026541369282795706048829214282295711081257665322451115651263881420892977595087922507442719943296948545357230330089343867993325132151429245967508523505680424491904364406312903615127538657675604483201285578790311428584411163178474228673851525286704390583059250494516640104576836789463682672552609673695330759252917807423803904426425278284909343560473180758182382765477607138172885805022074621590744335543201482629920203960490202940543143042932283107511286706829768486098207060257086269907220874995293093861402402487948639373928031392957237134301088941563811079550057313456323395444258845195880014351946752795850686630375099206736036480464983424023410290051980506602789889592937984551127883835044321548794008530439929217802240146623272491925105589701502506438692280333866586347521668932446521676259047939368247375037576551522119124570209630144175260090743817275920055687956230758127652722431040366263815359836175386499336783420446322590861436918780372850221068938500384051657383458438675894654304529405449643371468138153771939673475438910526029505877943669193622431431474488104065986129977271003535971010995177003621464874624533975343579011937546262419363008153711956390687339885820934937148190265123453244881393478139028212558848710419893863678716253963663060139597165662781010875207651345285198502763649544564112240031738715129620004287401924574020823782093290665717801240077997053988987732780527310675172100525200916100957471194267444541629245787821447460622577595087369445078714091705464454583587206888516940264026950179707864440940225676963254547638252616801026090394356509626561266266349640607840162405674639774513653746552082425584861425317213846606536653445512141387010379724242949973260120617942716321082345034763372452834117923725036224117465879471326343860316984979301518876554279805194507050361514757472361978237541879479615526583283800885300877147899157988083207855794651135355861303267181559444406306851119206846059687227489134933948991200139775681113063658578060753814393760540767049916481303494867835149012119144333934296253994094472572134626167997386848990952905792322900834139978065349737157272419895585219162661458781352292828106070109853841806878214190291082172874923266897102567913024289677453339380842525686018108667841677613468648937938503446345766937423574197255047957631367607853700227516024426660410363929130197613834835784498589131845432365028306253774662251823945653768874984463774388211464281151271683343566087444957332757524128139164766287272894196860090375457007820737763826767328459037724128804889329370460026218095842980438607186037420456557957696735097091483008705194483912388499550958806419320931551289691997267466308435180913969612922429442447297134470482955533891936537218207302359557149108110227197898864491556976773229169352362613105006306683945269386994097597253119332865297426515234155115765492235204067986012136169623521124035629597330938528338413725794433000708589543029050469655062722176390632908929041695459000313043336934154669868176028644149846722400244762987683752545493974857343967531446395822899750040815385402906755900986459115926729165031312700111975251896018642577234296256026753420211523376138802917809884211885383300539014292272209408783787767901170066973490527192163851457881312469115621324581573992419919399273733548301778012459965099569847676581188737654704860529512971476192609328860439480636441822213823023949326642756349849950525319503911154924995956431931008607423941445150974685855540656669584683189943812487933290947826559892065974404448215833751400324848556692197841474666552816491390872323910553704897320638769165796544508696566764659351072703351358099791189275404695233951584476745721068416804520388146346096946689267424873486918962081460951799114102807969067578287122122144083628531653337979034705445088459476664112892884795729940882132314842645166238586244740868273336011953295623738921321740527189101557272594624057328997930856879144288021430558778654182043795315337363512582268384358226310217870132026616157698988019839559465288940806852277449451871211367589767393635293255131885201932236462258009321586651948719615142858944836583085484600515159127418007875055469123514721893647388836510858929050411134633568427904254164841157692996958381594006138315952356737991485950542131324576181571765567267646348524966734860554910883057652888206056417720173565261334184327947784131977916398632407043029731695184031896704069356456360582324831843489946460796284008620498638085151562944235591583855038917759774471000374808068503805368315883348715650922681393427644563377292098895198115698426472800979322990694740377771776878654905711058471437991837684493361532981871882798850131835368487741167655596438517537049069015132557877569971832939739079479736856310007522044747890358479756396329874944168563638354603909821737577742021840663777858969732873146224412197858015261006645381099968915231174927874581643580620071917915584070742605472975828765881380551008273535508195896472185039286115353652708273746992154517978311366777827583964170273319360406096981809577151548881608505484613528629147649353524776424250795160472892466099755471320296422247362831972848691083877980936259060817909882164435934789898001132910614530442891708064115942135551384678841973549268375022812454943081192855397539523054673102872004784030908540233010489808308699621624405443618531046572852232114866419186224782188680726391202484804523894473884497667253581081261242860918541499135844088009179694387604104849692552294364661602924128155631366482171247238733210622257617600549008541575936180483824491920604151363057551840032851151116225942740930097275546058068173903720774558103723987430699436081152QED
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On