> with(numtheory); Warning, the protected name order has been redefined and unprotected [GIgcd, bigomega, cfrac, cfracpol, cyclotomic, divisors, factorEQ, factorset, fermat, imagunit, index, integral_basis, invcfrac, invphi, issqrfree, jacobi, kronecker, lambda, legendre, mcombine, mersenne, minkowski, mipolys, mlog, mobius, mroot, msqrt, nearestp, nthconver, nthdenom, nthnumer, nthpow, order, pdexpand, phi, pi, pprimroot, primroot, quadres, rootsunity, safeprime, sigma, sq2factor, sum2sqr, tau, thue] > 21 mod 39; > 5673 mod 39; > 109182988363676556383839930978336778835865635363567 mod 39; 21 18 15 > iquo(5,2); > iquo(80382726,17); > iquo(63676556383839930978336,982625343110); 2 4728395 64802477190 > igcd(7,0); > igcd(7,1); > igcd(467384978367,98938736276); > a:=987589496474674697645689779270788674667357357698738708868662698; > b:=7837034738309830979093737387338363863387387633636166; > igcd(a,b); 7 1 1 a := 98758949647467469764568977927078867466735735769873870886866\ 2698 b := 7837034738309830979093737387338363863387387633636166 6 > igcdex(7,0,'x','y'); x:=x; y:=y; > igcdex(7,1,'x','y'); x:=x; y:=y; > igcdex(467384978367,98938736276,'x','y'); x:=x; y:=y; > a:=987589496474674697645689779270788674667357357698738708868662698; > b:=7837034738309830979093737387338363863387387633636161; > igcdex(a,b,'x','y'); x:=x; y:=y; > a*x+b*y; 7 x := 1 y := 0 1 x := 0 y := 1 1 x := -13882588497 y := 65581121900 a := 98758949647467469764568977927078867466735735769873870886866\ 2698 b := 7837034738309830979093737387338363863387387633636161 1 x := -2032467753547668504563640846277614380167940188633667 y := 25612286691995014711402577986499178510594210717194426951071\ 4047 1 > phi(19); > phi(233); > phi(19*233); > phi(19)*phi(233); > > phi(404608249350926324364813614218311032); > phi(404608249350926324364813614218311031); > phi(404608249350926324364813614218311033); 18 232 4176 4176 202302930247283348108362464788642400 404608249350926324364813614218311030 269738832588105875420246044862207600 > a:=698738708868662698; > b:=979093737387338363; > igcdex(a,b,'x','y'); x:=x; x:=x mod b; > a^(-1) mod b; > a*x mod b; > > a:=987589496474674697645689779270788674667357357698738708868662698; > b:=7837034738309830979093737387338363863387387633636161; > igcdex(a,b,'x','y'); x:=x; x:=x mod b; > a^(-1) mod b; > a*x mod b; a := 698738708868662698 b := 979093737387338363 1 x := 240874389409751429 x := 240874389409751429 240874389409751429 1 a := 98758949647467469764568977927078867466735735769873870886866\ 2698 b := 7837034738309830979093737387338363863387387633636161 1 x := -2032467753547668504563640846277614380167940188633667 x := 5804566984762162474530096541060749483219447445002494 5804566984762162474530096541060749483219447445002494 1 > 7^(-1) mod 11; > > 6*7^(-1) mod 11; > 6/7 mod 11; 8 4 4 > n:=311; ifactor(n); L:=[seq(i^2 mod n,i=0..n-1)]; sort(L); > # try with n=311,313,317,319,315 n := 311 (311) L := [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 13, 50, 89, 130, 173, 218, 265, 3, 54, 107, 162, 219, 278, 28, 91, 156, 223, 292, 52, 125, 200, 277, 45, 126, 209, 294, 70, 159, 250, 32, 127, 224, 12, 113, 216, 10, 117, 226, 26, 139, 254, 60, 179, 300, 112, 237, 53, 182, 2, 135, 270, 96, 235, 65, 208, 42, 189, 27, 178, 20, 175, 21, 180, 30, 193, 47, 214, 72, 243, 105, 280, 146, 14, 195, 67, 252, 128, 6, 197, 79, 274, 160, 48, 249, 141, 35, 242, 140, 40, 253, 157, 63, 282, 192, 104, 18, 245, 163, 83, 5, 240, 166, 94, 24, 267, 201, 137, 75, 15, 268, 212, 158, 106, 56, 8, 273, 229, 187, 147, 109, 73, 39, 7, 288, 260, 234, 210, 188, 168, 150, 134, 120, 108, 98, 90, 84, 80, 78, 78, 80, 84, 90, 98, 108, 120, 134, 150, 168, 188, 210, 234, 260, 288, 7, 39, 73, 109, 147, 187, 229, 273, 8, 56, 106, 158, 212, 268, 15, 75, 137, 201, 267, 24, 94, 166, 240, 5, 83, 163, 245, 18, 104, 192, 282, 63, 157, 253, 40, 140, 242, 35, 141, 249, 48, 160, 274, 79, 197, 6, 128, 252, 67, 195, 14, 146, 280, 105, 243, 72, 214, 47, 193, 30, 180, 21, 175, 20, 178, 27, 189, 42, 208, 65, 235, 96, 270, 135, 2, 182, 53, 237, 112, 300, 179, 60, 254, 139, 26, 226, 117, 10, 216, 113, 12, 224, 127, 32, 250, 159, 70, 294, 209, 126, 45, 277, 200, 125, 52, 292, 223, 156, 91, 28, 278, 219, 162, 107, 54, 3, 265, 218, 173, 130, 89, 50, 13, 289, 256, 225, 196, 169, 144, 121, 100, 81, 64, 49, 36, 25, 16, 9, 4, 1] [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 18, 18, 20, 20, 21, 21, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 30, 30, 32, 32, 35, 35, 36, 36, 39, 39, 40, 40, 42, 42, 45, 45, 47, 47, 48, 48, 49, 49, 50, 50, 52, 52, 53, 53, 54, 54, 56, 56, 60, 60, 63, 63, 64, 64, 65, 65, 67, 67, 70, 70, 72, 72, 73, 73, 75, 75, 78, 78, 79, 79, 80, 80, 81, 81, 83, 83, 84, 84, 89, 89, 90, 90, 91, 91, 94, 94, 96, 96, 98, 98, 100, 100, 104, 104, 105, 105, 106, 106, 107, 107, 108, 108, 109, 109, 112, 112, 113, 113, 117, 117, 120, 120, 121, 121, 125, 125, 126, 126, 127, 127, 128, 128, 130, 130, 134, 134, 135, 135, 137, 137, 139, 139, 140, 140, 141, 141, 144, 144, 146, 146, 147, 147, 150, 150, 156, 156, 157, 157, 158, 158, 159, 159, 160, 160, 162, 162, 163, 163, 166, 166, 168, 168, 169, 169, 173, 173, 175, 175, 178, 178, 179, 179, 180, 180, 182, 182, 187, 187, 188, 188, 189, 189, 192, 192, 193, 193, 195, 195, 196, 196, 197, 197, 200, 200, 201, 201, 208, 208, 209, 209, 210, 210, 212, 212, 214, 214, 216, 216, 218, 218, 219, 219, 223, 223, 224, 224, 225, 225, 226, 226, 229, 229, 234, 234, 235, 235, 237, 237, 240, 240, 242, 242, 243, 243, 245, 245, 249, 249, 250, 250, 252, 252, 253, 253, 254, 254, 256, 256, 260, 260, 265, 265, 267, 267, 268, 268, 270, 270, 273, 273, 274, 274, 277, 277, 278, 278, 280, 280, 282, 282, 288, 288, 289, 289, 292, 292, 294, 294, 300, 300] > legendre(1,7); > legendre(1,8); > jacobi(1,7); > jacobi(1,8); > a:=987589496474674697645689779270788674667357357698738708868662698; > b:=7837034738309830979093737387338363863387387633636161; > jacobi(a,b); 1 Error, (in legendre) the 2nd argument should be of type `prime` 1 1 a := 98758949647467469764568977927078867466735735769873870886866\ 2698 b := 7837034738309830979093737387338363863387387633636161 -1 > 5^12 mod 6; > 2^989963 mod 17; > 2&^989963 mod 17; > 7^989963 mod 17; > 7&^989963 mod 17; > a:=987589496474674697645689779270788674667357357698738708868662698; > 7^a mod 17; > 7&^a mod 17; > 1 8 8 14 14 a := 98758949647467469764568977927078867466735735769873870886866\ 2698 Error, numeric exception: overflow 2 > isprime(404608249350926324364813614218311032); > isprime(404608249350926324364813614218311031); > isprime(404608249350926324364813614218311033); > > nextprime(404608249350926324364813614218311032); > nextprime(404608249350926324364813614218311031); > nextprime(404608249350926324364813614218311033); > > prevprime(404608249350926324364813614218311032); > prevprime(404608249350926324364813614218311031); > prevprime(404608249350926324364813614218311033); > > ifactor(404608249350926324364813614218311032); > ifactor(404608249350926324364813614218311031); > ifactor(404608249350926324364813614218311033); false true false 404608249350926324364813614218311199 404608249350926324364813614218311199 404608249350926324364813614218311199 404608249350926324364813614218311031 404608249350926324364813614218310977 404608249350926324364813614218311031 3 (2) (425009564558395464441631) (284899) (417691) (404608249350926324364813614218311031) (3) (156255837078148181445201191) (863132021) > s:=1000000050002286754868563745320005000228675486856374532454644464007 > 4874854946717600000454644464007487485494671760000000000000001; > p:=nextprime(s); > p mod 4; > q:=nextprime(p+1); > q mod 4; > sqrt_3_mod_p := msqrt(3,p); > sqrt_3_mod_q := msqrt(3,q); > sqrt_3_mod_n := msqrt(3,p*q); s := 10000000500022867548685637453200050002286754868563745324546\ 4446400748748549467176000004546444640074874854946717600000\ 00000000001 p := 10000000500022867548685637453200050002286754868563745324546\ 4446400748748549467176000004546444640074874854946717600000\ 00000000269 1 q := 10000000500022867548685637453200050002286754868563745324546\ 4446400748748549467176000004546444640074874854946717600000\ 00000000567 3 sqrt_3_mod_p := 181204090328452268535817299537023336788960155871\ 8605204686411970683155651931220746046214909107078196411423\ 362330196569057897193 sqrt_3_mod_q := 434712005958391082576456077871661777659116766671\ 2049388618165527639679264621978810566861815415944622854158\ 104937337059357470070 Error, (in ifactor/lenstra) non-integer ranges in array/table creation > p:=nextprime(1067548685634640001); > p mod 4; > q:=nextprime(p+1); > q mod 4; > sqrt_3_mod_p := msqrt(3,p); > sqrt_3_mod_q := msqrt(3,q); > sqrt_3_mod_n := msqrt(3,p*q); p := 1067548685634640009 1 q := 1067548685634640043 3 sqrt_3_mod_p := 709604203368059775 sqrt_3_mod_q := 633956015500622209 sqrt_3_mod_n := 404608249350926324364813614218311032 > s:=1000000050002286754868563745320005000228675486856374532454644464007 > 4874854946717600000454644464007487485494671760000000000000001; > p:=nextprime(s); > p mod 4; > q:=nextprime(p+1); > q mod 4; > sqrt_3_mod_p := msqrt(3,p); > sqrt_3_mod_q := msqrt(3,q); > > n:=p*q; > sqrt_3_mod_n := > sqrt_3_mod_p * q * (q^(-1) mod p) + sqrt_3_mod_q * p * (p^(-1) mod q) > mod n; > sqrt_3_mod_n^2 mod n; s := 10000000500022867548685637453200050002286754868563745324546\ 4446400748748549467176000004546444640074874854946717600000\ 00000000001 p := 10000000500022867548685637453200050002286754868563745324546\ 4446400748748549467176000004546444640074874854946717600000\ 00000000269 1 q := 10000000500022867548685637453200050002286754868563745324546\ 4446400748748549467176000004546444640074874854946717600000\ 00000000567 3 sqrt_3_mod_p := 181204090328452268535817299537023336788960155871\ 8605204686411970683155651931220746046214909107078196411423\ 362330196569057897193 sqrt_3_mod_q := 434712005958391082576456077871661777659116766671\ 2049388618165527639679264621978810566861815415944622854158\ 104937337059357470070 n := 10000001000045760099658082067442134324499849816931981076523\ 7537193329542828948684495109569598983938984854371041697516\ 7166894308065830623249527050331209956346040126720630964499\ 9289092048613271351707553676211361092743291340785953787354\ 5591360000000000152523 sqrt_3_mod_n := 629076978918826506152768128792043881913275125313\ 8295797338287478045965958431859616603801782422847264536450\ 3098863785099596163279723360222262410397262808022385651135\ 8718702510996809595602323636666118667799390549956209810997\ 7309866169693273146931841178381 3 >