import math def modular_sqrt(a, p): """ Find a quadratic residue (mod p) of 'a'. p must be an odd prime. Solve the congruence of the form: x^2 = a (mod p) And returns x. Note that p - x is also a root. 0 is returned is no square root exists for these a and p. The Tonelli-Shanks algorithm is used (except for some simple cases in which the solution is known from an identity). This algorithm runs in polynomial time (unless the generalized Riemann hypothesis is false). """ # Simple cases # if legendre_symbol(a, p) != 1: return 0 elif a == 0: return 0 elif p == 2: return 0 elif p % 4 == 3: return pow(a, (p + 1) // 4, p) # Partition p-1 to s * 2^e for an odd s (i.e. # reduce all the powers of 2 from p-1) # s = p - 1 e = 0 while s % 2 == 0: s //= 2 e += 1 # Find some 'n' with a legendre symbol n|p = -1. # Shouldn't take long. # n = 2 while legendre_symbol(n, p) != -1: n += 1 # Here be dragons! # Read the paper "Square roots from 1; 24, 51, # 10 to Dan Shanks" by Ezra Brown for more # information # # x is a guess of the square root that gets better # with each iteration. # b is the "fudge factor" - by how much we're off # with the guess. The invariant x^2 = ab (mod p) # is maintained throughout the loop. # g is used for successive powers of n to update # both a and b # r is the exponent - decreases with each update # x = pow(a, (s + 1) // 2, p) b = pow(a, s, p) g = pow(n, s, p) r = e while True: t = b m = 0 for m in range(r): if t == 1: break t = pow(t, 2, p) if m == 0: return x gs = pow(g, 2 ** (r - m - 1), p) g = (gs * gs) % p x = (x * gs) % p b = (b * g) % p r = m def legendre_symbol(a, p): """ Compute the Legendre symbol a|p using Euler's criterion. p is a prime, a is relatively prime to p (if p divides a, then a|p = 0) Returns 1 if a has a square root modulo p, -1 otherwise. """ ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else ls def inverse(x, p): return pow(x, p - 2, p) def solve(p): # solve 3 n^2 + 3 n + 1 ≡ 0 D = -3 % p sqrtD = modular_sqrt(D, p) if sqrtD == 0: return None else: n = (sqrtD - 3) * inverse(6, p) % p return (n, -(n+1) % p) def is_prime(n): return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1)) for P in range(5, 10000, 2): if not(is_prime(P)): continue s = solve(P) if s == None: print(P, "None") else: (s0, s1) = s print(P, s0, s1) if pow(s0, 3, P) != pow(s0 + 1, 3, P) or pow(s1, 3, P) != pow(s1 + 1, 3, P): print("Wrong")
Standard input is empty
5 None 7 1 5 11 None 13 5 7 17 None 19 16 2 23 None 29 None 31 8 22 37 33 3 41 None 43 16 26 47 None 53 None 59 None 61 56 4 67 54 12 71 None 73 51 21 79 18 60 83 None 89 None 97 20 76 101 None 103 15 87 107 None 109 51 57 113 None 127 120 6 131 None 137 None 139 78 60 149 None 151 39 111 157 100 56 163 143 19 167 None 173 None 179 None 181 76 104 191 None 193 100 92 197 None 199 35 163 211 65 145 223 135 87 227 None 229 31 197 233 None 239 None 241 155 85 251 None 257 None 263 None 269 None 271 9 261 277 53 223 281 None 283 203 79 293 None 307 96 210 311 None 313 71 241 317 None 331 320 10 337 267 69 347 None 349 273 75 353 None 359 None 367 94 272 373 29 343 379 143 235 383 None 389 None 397 11 385 401 None 409 118 290 419 None 421 287 133 431 None 433 222 210 439 203 235 443 None 449 None 457 412 44 461 None 463 161 301 467 None 479 None 487 77 409 491 None 499 46 452 503 None 509 None 521 None 523 194 328 541 317 223 547 13 533 557 None 563 None 569 None 571 36 534 577 263 313 587 None 593 None 599 None 601 392 208 607 334 272 613 430 182 617 None 619 290 328 631 616 14 641 None 643 273 369 647 None 653 None 659 None 661 121 539 673 309 363 677 None 683 None 691 606 84 701 None 709 548 160 719 None 727 578 148 733 630 102 739 599 139 743 None 751 476 274 757 261 495 761 None 769 376 392 773 None 787 660 126 797 None 809 None 811 43 767 821 None 823 332 490 827 None 829 594 234 839 None 853 779 73 857 None 859 659 199 863 None 877 386 490 881 None 883 770 112 887 None 907 476 430 911 None 919 17 901 929 None 937 829 107 941 None 947 None 953 None 967 919 47 971 None 977 None 983 None 991 698 292 997 895 101 1009 797 211 1013 None 1019 None 1021 803 217 1031 None 1033 409 623 1039 739 299 1049 None 1051 410 640 1061 None 1063 948 114 1069 327 741 1087 276 810 1091 None 1093 1042 50 1097 None 1103 None 1109 None 1117 412 704 1123 385 737 1129 623 505 1151 None 1153 985 167 1163 None 1171 530 640 1181 None 1187 None 1193 None 1201 590 610 1213 1140 72 1217 None 1223 None 1229 None 1231 778 452 1237 512 724 1249 801 447 1259 None 1277 None 1279 594 684 1283 None 1289 None 1291 1175 115 1297 986 310 1301 None 1303 900 402 1307 None 1319 None 1321 539 781 1327 326 1000 1361 None 1367 None 1373 None 1381 578 802 1399 802 596 1409 None 1423 214 1208 1427 None 1429 221 1207 1433 None 1439 None 1447 247 1199 1451 None 1453 715 737 1459 599 859 1471 406 1064 1481 None 1483 481 1001 1487 None 1489 831 657 1493 None 1499 None 1511 None 1523 None 1531 215 1315 1543 741 801 1549 424 1124 1553 None 1559 None 1567 1388 178 1571 None 1579 739 839 1583 None 1597 990 606 1601 None 1607 None 1609 1525 83 1613 None 1619 None 1621 1559 61 1627 630 996 1637 None 1657 23 1633 1663 660 1002 1667 None 1669 473 1195 1693 144 1548 1697 None 1699 132 1566 1709 None 1721 None 1723 560 1162 1733 None 1741 1279 461 1747 1288 458 1753 1229 523 1759 169 1589 1777 1394 382 1783 64 1718 1787 None 1789 1243 545 1801 1776 24 1811 None 1823 None 1831 834 996 1847 None 1861 151 1709 1867 900 966 1871 None 1873 1210 662 1877 None 1879 463 1415 1889 None 1901 None 1907 None 1913 None 1931 None 1933 1091 841 1949 None 1951 25 1925 1973 None 1979 None 1987 446 1540 1993 1224 768 1997 None 1999 1729 269 2003 None 2011 1942 68 2017 1246 770 2027 None 2029 1001 1027 2039 None 2053 1434 618 2063 None 2069 None 2081 None 2083 1538 544 2087 None 2089 1813 275 2099 None 2111 None 2113 1262 850 2129 None 2131 1264 866 2137 1357 779 2141 None 2143 2026 116 2153 None 2161 1638 522 2179 1411 767 2203 829 1373 2207 None 2213 None 2221 1299 921 2237 None 2239 98 2140 2243 None 2251 1264 986 2267 None 2269 2241 27 2273 None 2281 1299 981 2287 1256 1030 2293 434 1858 2297 None 2309 None 2311 1246 1064 2333 None 2339 None 2341 411 1929 2347 1210 1136 2351 None 2357 None 2371 635 1735 2377 2136 240 2381 None 2383 426 1956 2389 1822 566 2393 None 2399 None 2411 None 2417 None 2423 None 2437 28 2408 2441 None 2447 None 2459 None 2467 1572 894 2473 338 2134 2477 None 2503 425 2077 2521 1065 1455 2531 None 2539 948 1590 2543 None 2549 None 2551 833 1717 2557 278 2278 2579 None 2591 None 2593 1243 1349 2609 None 2617 517 2099 2621 None 2633 None 2647 1826 820 2657 None 2659 1471 1187 2663 None 2671 181 2489 2677 2332 344 2683 1576 1106 2687 None 2689 2558 130 2693 None 2699 None 2707 2264 442 2711 None 2713 2212 500 2719 484 2234 2729 None 2731 1969 761 2741 None 2749 198 2550 2753 None 2767 2657 109 2777 None 2789 None 2791 2760 30 2797 565 2231 2801 None 2803 796 2006 2819 None 2833 2399 433 2837 None 2843 None 2851 1288 1562 2857 835 2021 2861 None 2879 None 2887 729 2157 2897 None 2903 None 2909 None 2917 82 2834 2927 None 2939 None 2953 717 2235 2957 None 2963 None 2969 None 2971 1008 1962 2999 None 3001 2689 311 3011 None 3019 2092 926 3023 None 3037 248 2788 3041 None 3049 2871 177 3061 1207 1853 3067 324 2742 3079 1870 1208 3083 None 3089 None 3109 2434 674 3119 None 3121 666 2454 3137 None 3163 2287 875 3167 None 3169 32 3136 3181 913 2267 3187 438 2748 3191 None 3203 None 3209 None 3217 1140 2076 3221 None 3229 771 2457 3251 None 3253 2648 604 3257 None 3259 1370 1888 3271 809 2461 3299 None 3301 2725 575 3307 1121 2185 3313 2938 374 3319 1615 1703 3323 None 3329 None 3331 2708 622 3343 2703 639 3347 None 3359 None 3361 297 3063 3371 None 3373 1342 2030 3389 None 3391 2075 1315 3407 None 3413 None 3433 3343 89 3449 None 3457 911 2545 3461 None 3463 122 3340 3467 None 3469 1751 1717 3491 None 3499 2280 1218 3511 1422 2088 3517 1258 2258 3527 None 3529 3379 149 3533 None 3539 None 3541 2380 1160 3547 3159 387 3557 None 3559 3080 478 3571 3536 34 3581 None 3583 2042 1540 3593 None 3607 466 3140 3613 558 3054 3617 None 3623 None 3631 2532 1098 3637 980 2656 3643 1073 2569 3659 None 3671 None 3673 840 2832 3677 None 3691 1388 2302 3697 2291 1405 3701 None 3709 1402 2306 3719 None 3727 1638 2088 3733 2172 1560 3739 231 3507 3761 None 3767 None 3769 154 3614 3779 None 3793 1620 2172 3797 None 3803 None 3821 None 3823 2943 879 3833 None 3847 651 3195 3851 None 3853 2948 904 3863 None 3877 1217 2659 3881 None 3889 1926 1962 3907 1281 2625 3911 None 3917 None 3919 916 3002 3923 None 3929 None 3931 2826 1104 3943 378 3564 3947 None 3967 2348 1618 3989 None 4001 None 4003 1608 2394 4007 None 4013 None 4019 None 4021 2076 1944 4027 735 3291 4049 None 4051 1084 2966 4057 469 3587 4073 None 4079 None 4091 None 4093 3029 1063 4099 3426 672 4111 1018 3092 4127 None 4129 716 3412 4133 None 4139 None 4153 2825 1327 4157 None 4159 3307 851 4177 367 3809 4201 3175 1025 4211 None 4217 None 4219 37 4181 4229 None 4231 3027 1203 4241 None 4243 99 4143 4253 None 4259 None 4261 2291 1969 4271 None 4273 3385 887 4283 None 4289 None 4297 2394 1902 4327 1651 2675 4337 None 4339 2813 1525 4349 None 4357 3917 439 4363 4225 137 4373 None 4391 None 4397 None 4409 None 4421 None 4423 1496 2926 4441 300 4140 4447 4408 38 4451 None 4457 None 4463 None 4481 None 4483 168 4314 4493 None 4507 3268 1238 4513 4241 271 4517 None 4519 2660 1858 4523 None 4547 None 4549 581 3967 4561 2959 1601 4567 1151 3415 4583 None 4591 4487 103 4597 1406 3190 4603 3128 1474 4621 952 3668 4637 None 4639 4185 453 4643 None 4649 None 4651 1812 2838 4657 4334 322 4663 697 3965 4673 None 4679 None 4691 None 4703 None 4721 None 4723 2909 1813 4729 3831 897 4733 None 4751 None 4759 4250 508 4783 3770 1012 4787 None 4789 1036 3752 4793 None 4799 None 4801 2420 2380 4813 4183 629 4817 None 4831 1633 3197 4861 106 4754 4871 None 4877 None 4889 None 4903 805 4097 4909 1827 3081 4919 None 4931 None 4933 710 4222 4937 None 4943 None 4951 4054 896 4957 891 4065 4967 None 4969 3250 1718 4973 None 4987 3703 1283 4993 4109 883 4999 2553 2445 5003 None 5009 None 5011 2371 2639 5021 None 5023 3666 1356 5039 None 5051 None 5059 4421 637 5077 2235 2841 5081 None 5087 None 5099 None 5101 2238 2862 5107 1598 3508 5113 1680 3432 5119 1145 3973 5147 None 5153 None 5167 41 5125 5171 None 5179 2225 2953 5189 None 5197 2838 2358 5209 397 4811 5227 150 5076 5231 None 5233 110 5122 5237 None 5261 None 5273 None 5279 None 5281 3988 1292 5297 None 5303 None 5309 None 5323 427 4895 5333 None 5347 3724 1622 5351 None 5381 None 5387 None 5393 None 5399 None 5407 5059 347 5413 3200 2212 5417 None 5419 5376 42 5431 2321 3109 5437 2867 2569 5441 None 5443 4491 951 5449 491 4957 5471 None 5477 None 5479 925 4553 5483 None 5501 None 5503 1524 3978 5507 None 5519 None 5521 113 5407 5527 3392 2134 5531 None 5557 2461 3095 5563 2091 3471 5569 747 4821 5573 None 5581 819 4761 5591 None 5623 3077 2545 5639 None 5641 4959 681 5647 5362 284 5651 None 5653 4015 1637 5657 None 5659 3284 2374 5669 None 5683 2264 3418 5689 4882 806 5693 None 5701 1925 3775 5711 None 5717 None 5737 3001 2735 5741 None 5743 1847 3895 5749 2026 3722 5779 4828 950 5783 None 5791 2454 3336 5801 None 5807 None 5813 None 5821 2656 3164 5827 2392 3434 5839 2564 3274 5843 None 5849 None 5851 5658 192 5857 5435 421 5861 None 5867 None 5869 3653 2215 5879 None 5881 3828 2052 5897 None 5903 None 5923 1831 4091 5927 None 5939 None 5953 4258 1694 5981 None 5987 None 6007 1976 4030 6011 None 6029 None 6037 1842 4194 6043 1442 4600 6047 None 6053 None 6067 4266 1800 6073 2638 3434 6079 1508 4570 6089 None 6091 2278 3812 6101 None 6113 None 6121 2424 3696 6131 None 6133 316 5816 6143 None 6151 4031 2119 6163 2080 4082 6173 None 6197 None 6199 5014 1184 6203 None 6211 45 6165 6217 1252 4964 6221 None 6229 2386 3842 6247 3392 2854 6257 None 6263 None 6269 None 6271 5597 673 6277 769 5507 6287 None 6299 None 6301 992 5308 6311 None 6317 None 6323 None 6329 None 6337 3720 2616 6343 1928 4414 6353 None 6359 None 6361 619 5741 6367 256 6110 6373 1916 4456 6379 3128 3250 6389 None 6397 1367 5029 6421 5315 1105 6427 361 6065 6449 None 6451 4371 2079 6469 2648 3820 6473 None 6481 4347 2133 6491 None 6521 None 6529 2012 4516 6547 5769 777 6551 None 6553 2832 3720 6563 None 6569 None 6571 3387 3183 6577 2074 4502 6581 None 6599 None 6607 2708 3898 6619 2016 4602 6637 4881 1755 6653 None 6659 None 6661 449 6211 6673 464 6208 6679 2540 4138 6689 None 6691 5433 1257 6701 None 6703 6209 493 6709 2649 4059 6719 None 6733 6526 206 6737 None 6761 None 6763 718 6044 6779 None 6781 5805 975 6791 None 6793 389 6403 6803 None 6823 3169 3653 6827 None 6829 2031 4797 6833 None 6841 3624 3216 6857 None 6863 None 6869 None 6871 1801 5069 6883 2367 4515 6899 None 6907 5223 1683 6911 None 6917 None 6947 None 6949 6301 647 6959 None 6961 4471 2489 6967 127 6839 6971 None 6977 None 6983 None 6991 460 6530 6997 969 6027 7001 None 7013 None 7019 None 7027 174 6852 7039 4793 2245 7043 None 7057 48 7008 7069 3036 4032 7079 None 7103 None 7109 None 7121 None 7127 None 7129 6712 416 7151 None 7159 3346 3812 7177 679 6497 7187 None 7193 None 7207 1789 5417 7211 None 7213 867 6345 7219 6310 908 7229 None 7237 4214 3022 7243 3686 3556 7247 None 7253 None 7283 None 7297 6118 1178 7307 None 7309 6011 1297 7321 2337 4983 7331 None 7333 1423 5909 7349 None 7351 49 7301 7369 4059 3309 7393 572 6820 7411 7279 131 7417 5715 1701 7433 None 7451 None 7457 None 7459 2562 4896 7477 3828 3648 7481 None 7487 None 7489 6666 822 7499 None 7507 2704 4802 7517 None 7523 None 7529 None 7537 3166 4370 7541 None 7547 None 7549 4856 2692 7559 None 7561 5473 2087 7573 5734 1838 7577 None 7583 None 7589 None 7591 5878 1712 7603 3232 4370 7607 None 7621 1041 6579 7639 6084 1554 7643 None 7649 None 7669 4422 3246 7673 None 7681 2788 4892 7687 3320 4366 7691 None 7699 6942 756 7703 None 7717 6570 1146 7723 5454 2268 7727 None 7741 817 6923 7753 134 7618 7757 None 7759 586 7172 7789 2518 5270 7793 None 7817 None 7823 None 7829 None 7841 None 7853 None 7867 488 7378 7873 2159 5713 7877 None 7879 7423 455 7883 None 7901 None 7907 None 7919 None 7927 4031 3895 7933 7264 668 7937 None 7949 None 7951 5193 2757 7963 4767 3195 7993 1081 6911 8009 None 8011 2640 5370 8017 6225 1791 8039 None 8053 6534 1518 8059 1764 6294 8069 None 8081 None 8087 None 8089 3167 4921 8093 None 8101 3439 4661 8111 None 8117 None 8123 None 8147 None 8161 6408 1752 8167 6475 1691 8171 None 8179 365 7813 8191 2760 5430 8209 7120 1088 8219 None 8221 138 8082 8231 None 8233 1873 6359 8237 None 8243 None 8263 5428 2834 8269 52 8216 8273 None 8287 8097 189 8291 None 8293 7609 683 8297 None 8311 3192 5118 8317 2343 5973 8329 2425 5903 8353 2205 6147 8363 None 8369 None 8377 5313 3063 8387 None 8389 8158 230 8419 6266 2152 8423 None 8429 None 8431 2094 6336 8443 3159 5283 8447 None 8461 5048 3412 8467 7040 1426 8501 None 8513 None 8521 6355 2165 8527 4692 3834 8537 None 8539 6543 1995 8543 None 8563 4767 3795 8573 None 8581 141 8439 8597 None 8599 2464 6134 8609 None 8623 5233 3389 8627 None 8629 4650 3978 8641 6951 1689 8647 6029 2617 8663 None 8669 None 8677 8217 459 8681 None 8689 634 8054 8693 None 8699 None 8707 804 7902 8713 2058 6654 8719 7958 760 8731 7511 1219 8737 3668 5068 8741 None 8747 None 8753 None 8761 6418 2342 8779 8356 422 8783 None 8803 329 8473 8807 None 8819 None 8821 5068 3752 8831 None 8837 None 8839 1457 7381 8849 None 8861 None 8863 5421 3441 8867 None 8887 4371 4515 8893 5845 3047 8923 7640 1282 8929 7482 1446 8933 None 8941 2433 6507 8951 None 8963 None 8969 None 8971 6094 2876 8999 None 9001 4266 4734 9007 6369 2637 9011 None 9013 7904 1108 9029 None 9041 None 9043 7079 1963 9049 2734 6314 9059 None 9067 360 8706 9091 7961 1129 9103 1574 7528 9109 5032 4076 9127 8123 1003 9133 1778 7354 9137 None 9151 6492 2658 9157 8725 431 9161 None 9173 None 9181 336 8844 9187 1688 7498 9199 7388 1810 9203 None 9209 None 9221 None 9227 None 9239 None 9241 55 9185 9257 None 9277 200 9076 9281 None 9283 2146 7136 9293 None 9311 None 9319 5166 4152 9323 None 9337 1466 7870 9341 None 9343 7305 2037 9349 4456 4892 9371 None 9377 None 9391 2802 6588 9397 7139 2257 9403 7405 1997 9413 None 9419 None 9421 5487 3933 9431 None 9433 6597 2835 9437 None 9439 244 9194 9461 None 9463 202 9260 9467 None 9473 None 9479 None 9491 None 9497 None 9511 1163 8347 9521 None 9533 None 9539 None 9547 1089 8457 9551 None 9587 None 9601 4602 4998 9613 2175 7437 9619 1475 8143 9623 None 9629 None 9631 9090 540 9643 4746 4896 9649 1138 8510 9661 5889 3771 9677 None 9679 4197 5481 9689 None 9697 7128 2568 9719 None 9721 641 9079 9733 2727 7005 9739 2323 7415 9743 None 9749 None 9767 None 9769 6425 3343 9781 7956 1824 9787 8776 1010 9791 None 9803 None 9811 3069 6741 9817 318 9498 9829 9579 249 9833 None 9839 None 9851 None 9857 None 9859 8275 1583 9871 6363 3507 9883 9037 845 9887 None 9901 6567 3333 9907 2190 7716 9923 None 9929 None 9931 8520 1410 9941 None 9949 4527 5421 9967 9814 152 9973 6125 3847