Intro to Sage.sagews

5+8

13

2^2015

3762194662274677225006147833619028325244330646204236432925139720030670885330519044445501804761927745268763736929034118016031519410956059710016491867886889157890211484313592791062569915129529790346983079610400317269003975512764853909825684309294001486918614927217865484171497622917064676132001029225523861302285726809602736311578770958185727882065830756366057561021042715214545162477118465368433226000538225835881149829186249682400183653494069108786491864970103748052744856652666373379197565574074550935728305785527534076832933033391949562148135756886265861748671407745362911914163091988879273202451394592768

factorial(2015)

11536952290689937008944150226822847437145825120840741300794874799276862236497204005872364016688936735464494550719160093175479895774351383782211721410325759717835249680904640101615890067804536468156681135699419586145284897444844215931729090061927670108708348181973335237463182584517923960820352196337046977879865504052390815830708853411780148443385544344448704252890283923923179074356191421614698916915454209676228365551528110951374017036646603332113373256721456386412405492536736662429244698886840754406167110922210303304137505782272359403619603386517176337439072664677731028273860228351373427589901777801841216664021194824779560937646573473729289036906126053640524099457628788539996739424757518211293550002884788146802990941946816316658538567660419179324546130645974462055666341251596504439270459232604591026817757325616486215011235382853604273067705760478632460767269290326859748006626809016420096345535167255926693077263753206853596436958326018263076035404777311959754302826309896054355083437924850578689100748328114323505739863243274852603529909315674864293262296249274385413502934363839165932041070639049124613806341133706659204304303107429168107050114068129746652853971247682452830196556820965220860815746949793873442765360574453628448503618200156089265199045203470288671212639530039345884327078626996903884237395682362994851847813244191052746632249403553311708157833900814172837998737837288167251928963558150406670080124976770547507319900794519822588485892563939467843018961354651106529406588757178862262147442677961212530145575676105925109427514317188379701082342991651546084349396016096011016086057962062265773771153690559861305089231969972890432575560608923216028399156207530875796122781795868554151537284275699183329120971163993268607283482815039757087038814018981034101653358987509688468131083059974346382913804192990966115575323261409218527845286480389744130778715068597043072863636132215342306401227110726395195538545777180802307548239522788602231058943123688035226255668737212745391478077656957218053858891918580779539398885519402963162874701991649035421244413216166961906055631903114147012393421265729785418045171672279298509652575790248060922176219857257305819000222163307571786954879543709497077649133910621203280896557331730849181248519003443860988373540223120598517790676293165980382306062621756728187853676583051048757607501399699586128570829005645503264993162730522767549542833549686946488446498448061844893284649529132236860217546152902677055260113012227744150706420873641375690532768807714429802065499841778139174382483965991170471617873864198489766922862959637265606902580768284636416261531694080679674417328572002538997527680951922714397820144509314442039822158651517414373752346666113565176927181239573344433450060260286579277180250052657673281534937181131411114486039201561034106161751611058753666190123155122476361605886097839828971950001836646900528081867955195103363077729495033352263848458946942967985745002233123711530112460948832114287467226325742178171666532250196442436144693399377793784197344974741214982027070446397309225539289043516642662837704421588114654532031372161841990359942102032574844186945384278676804692788228661893177359159922491745445758536060081049282539266762603205302086714796196914493504509127346632848778311054905325827486276205643863806562197248297574178952169461616662097985917079590294353657143575509215939678464568593308145118313166540778881794752767439424918881378984700469183202267868197309862846173480042640630998691020429013967802020335402478709247716692055350802489114320285321470899362008511568082130424002431463959109270913482977503577883382880525231282447711940804125071899128693014732205095095963957292566080326585217946425831197503184962568189843891212868900163127724444195713352381924727956185993116238917117243570589074956108182267749306498133244506990780219838852279971724570816946399206523186589095920712144830228419490705381216703975663608645430421417137457041786904704555639115494803224871590421275406369086234407552011989642388216524497746191021164931651187315912344693717199871272289132442677460657900580793301321715349598352866604969934556290113041577929798997188904669320917101092551756861005753587962092842232044581096349434301978908151895858121743806968796208729465346017351291948911163285989319369970734260728607118172222840722235619593499850462080763762256525116369770108571418889362667362021807279425585844624610488903933286996086532205486341648243430934277737901421589931640044018026443204849045920278327146544867045485435242233786875754337885927437738134362789129694469327155145847181917756181831192951560161596480116596099761824536513427462174673666714303745128215264872097805005946935985636770880255410365469297200868750271115466502906241190500817232974262139186260554258979528472297391664631015370528842774165245586481051107875135944295382718424589330833372509109890202709564421924226046738327714108255521699173511019381198908084949271512335560062005647564586759562402974502121312860120330548404402979675584569057016052463979914943083545662377908066659502109762770824724982362384730927717677663403046894645760258776091389090247461778065430457119611043641813379592726345401540561659350662732400201813911108363817120234485245192327648334983680082521420020449339644240027613597885167250678680125440000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

plot(sin,0,pi)

Mod(5, 12)

5

mod(20,17)

3

mod(30,17)

13

a=mod(30,17)

a

13

a^2

16

b=mod(2,17)

b^2015

9

nick = 172

nick.is_prime()

False

nick.divides(344)

True

nick.factor()

2^2 * 43

1000.factorial()

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

2^994 * 3^498 * 5^249 * 7^164 * 11^98 * 13^81 * 17^61 * 19^54 * 23^44 * 29^35 * 31^33 * 37^27 * 41^24 * 43^23 * 47^21 * 53^18 * 59^16 * 61^16 * 67^14 * 71^14 * 73^13 * 79^12 * 83^12 * 89^11 * 97^10 * 101^9 * 103^9 * 107^9 * 109^9 * 113^8 * 127^7 * 131^7 * 137^7 * 139^7 * 149^6 * 151^6 * 157^6 * 163^6 * 167^5 * 173^5 * 179^5 * 181^5 * 191^5 * 193^5 * 197^5 * 199^5 * 211^4 * 223^4 * 227^4 * 229^4 * 233^4 * 239^4 * 241^4 * 251^3 * 257^3 * 263^3 * 269^3 * 271^3 * 277^3 * 281^3 * 283^3 * 293^3 * 307^3 * 311^3 * 313^3 * 317^3 * 331^3 * 337^2 * 347^2 * 349^2 * 353^2 * 359^2 * 367^2 * 373^2 * 379^2 * 383^2 * 389^2 * 397^2 * 401^2 * 409^2 * 419^2 * 421^2 * 431^2 * 433^2 * 439^2 * 443^2 * 449^2 * 457^2 * 461^2 * 463^2 * 467^2 * 479^2 * 487^2 * 491^2 * 499^2 * 503 * 509 * 521 * 523 * 541 * 547 * 557 * 563 * 569 * 571 * 577 * 587 * 593 * 599 * 601 * 607 * 613 * 617 * 619 * 631 * 641 * 643 * 647 * 653 * 659 * 661 * 673 * 677 * 683 * 691 * 701 * 709 * 719 * 727 * 733 * 739 * 743 * 751 * 757 * 761 * 769 * 773 * 787 * 797 * 809 * 811 * 821 * 823 * 827 * 829 * 839 * 853 * 857 * 859 * 863 * 877 * 881 * 883 * 887 * 907 * 911 * 919 * 929 * 937 * 941 * 947 * 953 * 967 * 971 * 977 * 983 * 991 * 997

gcd(10,45)

5

xgcd(25,7)

(1, 2, -7)

g,x,y = xgcd(25,7)

25*x+7*y

1

25*x+7*y==g

True

def repunit(n):
    #make a number with n 1s
    r=0
    for e in range(n):
        r = r + 10^e
    return r
        

def repunit(n):
    #make a number with n 1s
    r=0
    for e in range(n):
        r = r + 10^e
    return r
        

repunit(9)

111111111

range(12)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

myList = [10^k for k in range(6)]

myList

[1, 10, 100, 1000, 10000, 100000]

sum(myList)

111111

ans=gcd(repunit(2015),repunit(93))

ans

1111111111111111111111111111111

len(ans.digits())

31

xgcd(7,12)

(1, -5, 3)

repunit(9)

111111111

range(12)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

myList = [10^k for k in range(6)]

myList

[1, 10, 100, 1000, 10000, 100000]

sum(myList)

111111

ans=gcd(repunit(2015),repunit(93))

ans

1111111111111111111111111111111

len(ans.digits())

31

xgcd(7,12)

(1, -5, 3)

big = 2^1000

︠9fed6eb6-7036-4b61-b81a-94049682138c︠
mod(big,13)

3

#attempt to brute force p 32:10 hw problem

prime_range(100)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

for p in prime_range(700):
    print p, mod(p,30)

2 2 3 3 5 5 7 7 11 11 13 13 17 17 19 19 23 23 29 29 31 1 37 7 41 11 43 13 47 17 53 23 59 29 61 1 67 7 71 11 73 13 79 19 83 23 89 29 97 7 101 11 103 13 107 17 109 19 113 23 127 7 131 11 137 17 139 19 149 29 151 1 157 7 163 13 167 17 173 23 179 29 181 1 191 11 193 13 197 17 199 19 211 1 223 13 227 17 229 19 233 23 239 29 241 1 251 11 257 17 263 23 269 29 271 1 277 7 281 11 283 13 293 23 307 7 311 11 313 13 317 17 331 1 337 7 347 17 349 19 353 23 359 29 367 7 373 13 379 19 383 23 389 29 397 7 401 11 409 19 419 29 421 1 431 11 433 13 439 19 443 23 449 29 457 7 461 11 463 13 467 17 479 29 487 7 491 11 499 19 503 23 509 29 521 11 523 13 541 1 547 7 557 17 563 23 569 29 571 1 577 7 587 17 593 23 599 29 601 1 607 7 613 13 617 17 619 19 631 1 641 11 643 13 647 17 653 23 659 29 661 1 673 13 677 17 683 23 691 1

n"

data =[mod(p,30) for p in prime_range(40000)]

data.count(2)

1

for k in range(30):
    print k, data.count(k)

0 0 1 513 2 1 3 1 4 0 5 1 6 0 7 531 8 0 9 0 10 0 11 531 12 0 13 531 14 0 15 0 16 0 17 520 18 0 19 514 20 0 21 0 22 0 23 529 24 0 25 0 26 0 27 0 28 0 29 531

13^52

8415003868347247618489696679505181495471801448798649088081

glop =13^52-1

glop/7

1202143409763892516927099525643597356495971635542664155440

(13^52-4)/11

765000351667931601680881516318652863224709222618059008007

mod(13^52,11)

4

looksmall=mod(13,11)

looksmall

2

looksmall^1389999

6

looksbig = 2^1389999

len(looksbig.digits())

418432

prime_pi(10^6)
prime_range(100)



P=Primes()

78498 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

P

Set of all prime numbers: 2, 3, 5, 7, ...

P.next(9)

11

P.unrank(2)

5

q=1225

q.is_square()

True

401.is_prime()

True

399.is_prime()

False

for i in range(5):
    print i, moebius(i)

0 0 1 1 2 -1 3 -1 4 0

for i in range(5):
    print i, moebius(i)

0 0 1 1 2 -1 3 -1 4 0

qr=[mod(n^2,401) for n in range(401)]

qr.count(400)

plot(sin,0,pi)

3

Error in lines 1-1 Traceback (most recent call last): File "/projects/cec84faa-0c9f-4d53-a7fe-4962a22dc313/.sagemathcloud/sage_server.py", line 873, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> NameError: name 'qr' is not defined

plot(sin,0,pi)

n = 314^164

n

31366227205797455391034247162873068187170407346268527539818904886622156172732744090583885200889925452335426682623186681128402948216590318005376743406788368078536756514568828484951188049645929055456236315076953255547576217321952757989819669326993945659966663589936832148834002235852761401464999571534721838744780860668698334132971212353259840040359208363004571904507589218140007729967273498195186270107982626816

mod(n,165)

31

7^355

1022831760466051670409848066539662073905087543301674648579658274804249423378253098383504632739938574586749061841502160063941822079560091329657596340325010895677552753218888726615955591342341233193279587163656384106958221982493551112468151234550629604561727268100420434285770519972365028810684127481943

mod(2^2015,17)

9

6.is_prime()

False

#function to say if perfect
def is_perfect(n):
    return 2*n ==sigma(n)

is_perfect(6)

True

is_perfect(9)

False

def duc(n):
    return n^72

duc(97)

111574478897742849177136197511285442432661298716331706733204593731410300884557578113685150976499394580506142057779342816269560527771563600874241

b=2*3*7*43 +1

b

1807

b.is_prime()

False

factor(b)

13 * 139

def ar(n):
    return float(sigma(n)/n)

for i in [1..100000]:
    if ar(i)==2.:
        print i, factor(i)
    

6 2 * 3 28 2^2 * 7 496 2^4 * 31 8128 2^6 * 127

ar(6)

2.0

ar(139)

1.0071942446043165

for i in [1..60000]:
    if ar(i) >=4:
        print i, sigma(i)

27720 112320 30240 120960 32760 131040 50400 203112 55440 232128

u=2001^2001

mod(2001^2001,26)

25

P= Primes()

P.next(9)

11

P.unrank(9)

29

for i in range(100):
    P.unrank(i)

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

for k in [1..70]:
    x = 2^k-1
    if x.is_prime():
        print k, x, x*2^(k-1)

2 3 6 3 7 28 5 31 496 7 127 8128 13 8191 33550336 17 131071 8589869056 19 524287 137438691328 31 2147483647 2305843008139952128 61 2305843009213693951 2658455991569831744654692615953842176

purr = (2^19-1)*2^18

purr

137438691328

sigma(purr)

274877382656

2*purr

274877382656

n= 16*(1375)^2

n

30250000

sigma(n)

80526313

︠7009be5f-8917-414f-9f1a-e6a4448ff238︠
for k in [1..2000]:
    if mod(sigma(k),2)==1:
        print k, factor(k)

1 1 2 2 4 2^2 8 2^3 9 3^2 16 2^4 18 2 * 3^2 25 5^2 32 2^5 36 2^2 * 3^2 49 7^2 50 2 * 5^2 64 2^6 72 2^3 * 3^2 81 3^4 98 2 * 7^2 100 2^2 * 5^2 121 11^2 128 2^7 144 2^4 * 3^2 162 2 * 3^4 169 13^2 196 2^2 * 7^2 200 2^3 * 5^2 225 3^2 * 5^2 242 2 * 11^2 256 2^8 288 2^5 * 3^2 289 17^2 324 2^2 * 3^4 338 2 * 13^2 361 19^2 392 2^3 * 7^2 400 2^4 * 5^2 441 3^2 * 7^2 450 2 * 3^2 * 5^2 484 2^2 * 11^2 512 2^9 529 23^2 576 2^6 * 3^2 578 2 * 17^2 625 5^4 648 2^3 * 3^4 676 2^2 * 13^2 722 2 * 19^2 729 3^6 784 2^4 * 7^2 800 2^5 * 5^2 841 29^2 882 2 * 3^2 * 7^2 900 2^2 * 3^2 * 5^2 961 31^2 968 2^3 * 11^2 1024 2^10 1058 2 * 23^2 1089 3^2 * 11^2 1152 2^7 * 3^2 1156 2^2 * 17^2 1225 5^2 * 7^2 1250 2 * 5^4 1296 2^4 * 3^4 1352 2^3 * 13^2 1369 37^2 1444 2^2 * 19^2 1458 2 * 3^6 1521 3^2 * 13^2 1568 2^5 * 7^2 1600 2^6 * 5^2 1681 41^2 1682 2 * 29^2 1764 2^2 * 3^2 * 7^2 1800 2^3 * 3^2 * 5^2 1849 43^2 1922 2 * 31^2 1936 2^4 * 11^2

sigma(2^7*3^6*5^4)

217676415

︠faf3aa40-99aa-42e6-9942-e086cef014bb︠

a=1
b=23
n=100000
coun=0
for  k in range(n):
    p=a+b*k
    if p.is_prime():
        #print p
        coun +=1
print coun

7709

100000/22.

4545.45454545455

prime_pi(b*n)/22.

7705.04545454545

factor(5394826801)

7 * 13 * 17 * 23 * 31 * 67 * 73

300.divisors()

[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]

300.divisors()

[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]

#star maker!
def star(f,g,n):
    sum=0
    for d in n.divisors():
        sum += f(d)*g(n/d)
    return sum

def u(n):
    if n==1:
        return 1
    else:
        return 0

u(9)

0

u(1)

1

def one(n):
    return 1

def N(n):
    return n

sigma(10)

18

sigma(10,0)

4

star(one, one, 2327)

4

2327.divisors()

[1, 13, 179, 2327]

star(one,euler_phi,63218)

63218

star(moebius, euler_phi,8)

2

#star maker!
def star(f,g,n):
    sum=0
    for d in n.divisors():
        sum += f(d)*g(n/d)
    return sum

def u(n):
    if n==1:
        return 1
    else:
        return 0

u(9)

0

u(1)

1

def one(n):
    return 1

def N(n):
    return n

sigma(10)

18

sigma(10,0)

4

star(one, one, 2327)

4

2327.divisors()

[1, 13, 179, 2327]

star(one,euler_phi,63218)

63218

star(moebius, euler_phi,8)

2

prime_pi(10^6)

78498

#Mobius inversion formula
#Let F be the daughter
#we wanna find the mother, f
def mob_inversion(F,n):
    sum = 0
    for d in n.divisors():
        sum += moebius(d)*F(n/d)
    return sum

mob_inversion(moebius,1001000)

0

def odd(n):
    if mod(n,2)==1:
        return 1
    else:
        return 0

odd(10)

0

︠1d48bbe7-6383-410e-a278-dfd5ac8b63af︠
mob_inversion(odd,4)

0

for t in [1..20]:
    print t, mob_inversion(odd,t)

1 1 2 -1 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0

def sq(n):
    return n^2

mob_inversion(sq,10)

72

mob_inversion(sq,12)

96

is_square(9)

True

mob_inversion(is_square,8)

-1

mob_inversion(is_square,100)

1

#find x and y such that x^2+y^2=n
n = 1313
upper_bound = floor(sqrt(n/2))
for x in [0..upper_bound]:
    d = n-x^2
    if d.is_square():
        y=sqrt(d)
        print x, y, x^2+y^2

17 32 1313 23 28 1313

#get the primes
P = Primes()
n = 100
for k in range(n):
    p = P.unrank(k)   # kth prime
    if mod(p,4)==1:
        print p
        upper_bound = floor(sqrt(p/2))
        for x in [0..upper_bound]:
            d = p-x^2
            if d.is_square():
                y=sqrt(d)
                print x, y, x^2+y^2

5 1 2 5 13 2 3 13 17 1 4 17 29 2 5 29 37 1 6 37 41 4 5 41 53 2 7 53 61 5 6 61 73 3 8 73 89 5 8 89 97 4 9 97 101 1 10 101 109 3 10 109 113 7 8 113 137 4 11 137 149 7 10 149 157 6 11 157 173 2 13 173 181 9 10 181 193 7 12 193 197 1 14 197 229 2 15 229 233 8 13 233 241 4 15 241 257 1 16 257 269 10 13 269 277 9 14 277 281 5 16 281 293 2 17 293 313 12 13 313 317 11 14 317 337 9 16 337 349 5 18 349 353 8 17 353 373 7 18 373 389 10 17 389 397 6 19 397 401 1 20 401 409 3 20 409 421 14 15 421 433 12 17 433 449 7 20 449 457 4 21 457 461 10 19 461 509 5 22 509 521 11 20 521 541 10 21 541

#does 2281 have a "sqrt of -1"
p = 2281
h=(p-1)/2
for k in [1..h]:
    if mod(k^2,p)== p-1:
        print k

710

710^2

504100

504101/2281

221

#differences of squares
d = 3*5*7^2
n=1000
print sigma(d,0)
for x in range(n):
    for y in range(x):
        if x^2-y^2==d:
            print x,y,d

12 28 7 735 32 17 735 56 49 735 76 71 735 124 121 735 368 367 735

25+36^2

1321

37^2

1369

a=258
b=5
n=1000
for k in range(n):
    m = a*k + b
    if m.is_prime():
        print m

5 263 521 1553 1811 2069 2843 3359 3617 4133 4391 4649 5939 6197 6971 7229 7487 9293 9551 10067 12647 13163 13421 13679 14969 15227 16001 17033 17291 17807 18839 20129 20903 21419 22193 22709 23741 25031 26321 27611 28643 28901 30449 30707 31223 31481 32771 33029 33287 34061 34319 36383 36899 38189 38447 40253 41543 41801 43607 44123 44381 45413 46187 46703 48767 51347 52121 52379 53411 53927 54443 54959 55217 55733 56249 58313 61151 61409 61667 63473 64763 65537 66569 67343 67601 68633 68891 69149 70181 70439 71471 71987 72503 73019 73277 74051 74567 75083 76631 78179 78437 81017 81533 82307 83339 83597 84629 85661 86693 86951 88241 88499 89273 90821 91079 92111 92369 92627 94433 94949 95723 96497 97787 98561 100109 101141 101399 103979 105269 105527 108107 108881 109139 109397 109913 111977 113783 114041 114299 115331 115589 117911 118169 120233 120749 121007 121523 122039 125651 126683 127973 128489 128747 129263 130553 130811 133391 133649 134681 135197 137519 137777 139067 141131 142421 143711 145259 145517 146033 146291 146807 151451 151967 155579 156353 157127 157901 159191 159707 160481 160739 160997 161771 162287 163061 164093 165383 166157 166931 168737 169769 170801 171317 172607 173897 174413 174929 175961 178799 179057 179573 180347 182927 183959 184733 186023 188603 188861 189377 190409 190667 191441 191699 193247 193763 195053 195311 197117 197891 199181 199697 200987 202277 203051 203309 204599 204857 207953 208469 210533 211049 212081 213887 215693 217241 217499 218531 222659 226013 227303 227561 228077 228593 231431 231947 234527 235043 235559 236333 238397 239171 239429 240203 240719 242009 244589 245621 247943 248201 249233 249749 250007 251297 253103 253361 256199 257489

mod(720,13)

5

mod(14.factorial(),29)

12

n=1000
for k in range(n):
    m = 2*k+1
    if sigma(m)>2*m:
        print m

945 1575

945.factor()

3^3 * 5 * 7

1575.factor()

3^2 * 5^2 * 7

2047.factor()

23 * 89

def aq(n):
    return float(sigma(n)/n)

aq(77^10)

1.2833333326798109

576^2+943^2==1105^2

True

n = 2690
ub = floor(sqrt(n/2))
for x in [1..ub]:
    d=n-x^2
    if d.is_square():
        y=sqrt(d)
        print x, y
   

17 49 29 43

legendre_symbol(233,409)

-1

for k in [1..12]:
    print k, mod(k^2,13)

1 1 2 4 3 9 4 3 5 12 6 10 7 10 8 12 9 3 10 9 11 4 12 1

a=43
e=17
d=33

a^e

5874403106360420018879553643

23^e

141050039560662968926103

29^e

7257147736730073114838109

(29^e)^d

25425928496101134597433619676290515126739648110193715162242777590961909909429508382892546466454898026164026346587964829932810854000268229499647533077424728489737294733673374276963921614796145249435091496562197670635998055104620133565223862648241424793802818504337420745514577563410966489783507434980714613497193960533345096797671479453778215782617921012860726438504677501231632189299510073989526523986295504431042733303757390624950884840662384101733190011934532943618223909274340436709842921554755580128530670582308158197918027091350448848015384657632291231396324719583317800985670175833738069310747261173521821865055409759295093760696378525339590937055028249758486883276399521109075323600601871373764396283617792091977240864318353723778320269883270195397665210212717909504869873421314480218462679127858802269266905924829

y=11^e

y^33

166454819351588442676588550466969998499311748095911128689125664120402945263506599280477528354799198759825586671962544572833541487992521882810908302862866676718404543544918302333232791334607439427823393430413638759819901158103453322361271038257033667945164358708707938073097308962738575982023755863880232036458846449730476858849635221283503871292022775599394962843578577857064131716750784837943548825410707165469163224470726068660056022519284105013610475978843821544397791426285100549706017544764965655080019500058365624025639842688812764664497462233949468428884692352344031773183953611

legendre_symbol(109,631)

-1

x=45
e=17
y=x^e

y

12723679885609870147705078125

d=33
y^d

2832828140759905018122893421388973373382450860266079416807541999555986123471446629213082143505018706186521374763711778871489244750289658822233900267964043514134462535901526853371313045802459047870402692217858640792110213795902234701425350982267209516689758554964210143156197436435421640681504744800520840143503673370803645324562652714064329307660671783087159639871201767197628842125363125765536864343074276497112641748060214793364415407964551021505194660057942075954481223554091904617554516371227465887354609097575215920946982863250255483675713047978642284874212385841527429954190386121785172817399786280443109075512826333694157240328216891357268587472171544798304614368061752088002140568910340309455135562074508819920033931998897798893496767921933709399935865646224725415328442349659967907774381145795547026415555491348596750342305604547638687700807691508911820558307518645537271945980713205859302661338006146252155303955078125

d

33

y^d

2832828140759905018122893421388973373382450860266079416807541999555986123471446629213082143505018706186521374763711778871489244750289658822233900267964043514134462535901526853371313045802459047870402692217858640792110213795902234701425350982267209516689758554964210143156197436435421640681504744800520840143503673370803645324562652714064329307660671783087159639871201767197628842125363125765536864343074276497112641748060214793364415407964551021505194660057942075954481223554091904617554516371227465887354609097575215920946982863250255483675713047978642284874212385841527429954190386121785172817399786280443109075512826333694157240328216891357268587472171544798304614368061752088002140568910340309455135562074508819920033931998897798893496767921933709399935865646224725415328442349659967907774381145795547026415555491348596750342305604547638687700807691508911820558307518645537271945980713205859302661338006146252155303955078125

x=41

y=x^17

y

2614120267500775228203738281

y^33

59121251634106710896087233371881834121077235915762839702438412663277862050884236449017044422138484201802515211860168798550506898732856654533281551034432573870269177861948996543724839752720804307523786530140039473372264351448628782073561235015562352267867267129189846172259304538114892297132186454618352939610812969214915579960105111508792217290148360160744538226820789525362731395662966969463598792047665888202344423106008852648813317867040067553639058156496692221074882946576519241953469796090625080145260320637561443248928655840195610112748123340717239518904208336716747276932643095381598180681852169288202366015672678064696367204882360750335120571752089764975102659303371668143400275898765372943649635292782070836270015292418502738231567477350848342023507699477495044542103979607955000931805319910079816572474259184213526977311074143115389519649302311195707165039132397803043554749973527925967076310441

x= 15
e=5
y=x^e
y

759375

y^29

341375668080717029918663962887964780066858964406758634250665662247913586860389331896085330658637772213251400888570527078014213233879414755023162797442637383937835693359375

mod(y,91)

71

mod(y^29,91)

15

#not rel prime to 91
x=14
y=x^5
y

537824

mod(y,91)

14

mod(y^29,91)

14

xgcd(5,72)

(1, 29, -2)

#medium rsa example
p=1303
q=1723
n=p*q
n

2245069

x=1234567
e=1657

#y is the encoded version of x
y=mod(x^e,n)
y

1236567

#how to find the decoder
f = euler_phi(n)

f

2242044

f==(p-1)*(q-1)

True

xgcd(e,f)

(1, -966095, 714)

d=mod(-966095,f)

d

1275949

mod(y^d,n)

1234567

mod(y^(-966095),n)

1234567

mod(9^(-1),13)

3

mod(17^(-1),60)

53

mod(1853^801, 2003)

10

p=11
q=13
n=p*q
f=(p-1)*(q-1)

p^f

92709068817830061978520606494193845859707401497097037749844778027824097442147966967457359038488841338006006032592594389655201

mod(q^(f+1),n)

13

xgcd(17,60)

(1, -7, 2)

P=Primes()
p=P.unrank(1000)
q=P.unrank(1001)

p,q

(7927, 7933)

p*q

62884891

P.unrank(1002)

7937

continued_fraction(144/89)

[1; 1, 1, 1, 1, 1, 1, 1, 1, 2]

continued_fraction(pi,2000)

[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]

continued_fraction(e)

[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, ...]

p=11
q=23
n=p*q
f= euler_phi(n)

f

220

n

253

e=109

x=137
y=mod(137^e,n)

y

229

d=mod(e^(-1),f)

d

109

109^109

1200848653752901194754604890537140910893177693553105089822454370295424235318532130268902601684731948577328529967578102721671251247048795073017876239156407942964445733272548301056518040243255020745772665926018963223710135389

109*109

11881

mod(y^d,n)

137

gcd(123,37)

1

xgcd(123,37)

(1, -3, 10)

xgcd(e,f)

(1, 109, -54)

p=73
a=35
h=(p-1)/2
for x in [1..h]:
    if mod(x^2,p)==a:
        print x

20

mod(400,73)

35

xx