Knowledge

User:Virginia-American/Sandbox/Euclid's lemma

Source 📝

2177:
has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
491:
The logic of this proof is basically Euclid's, but the notation and some of the concepts (zero, negative) would be foreign to him. It relies on the fact that a set of non-negative integers has a smallest member.
458: 401: 333: 1408:
is finite, therefore their intersection is finite and has a largest member. It must be positive because 1 is a positive common divisor of
76:
The lemma is not true for composite numbers. For example, 8 does not divide 4 and 8 does not divide 6, yet 8 does divide their product 24.
2283: 2338: 2307: 2236: 70: 2299: 2188: 2196: 21: 2229:
Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
2173: 61:. It states that if a prime divides the product of two numbers, it must divide one of the factors. For example since 2275: 1315: 271: 17: 1055: 35: 253: 2095: 54: 31: 416: 2334: 2303: 2279: 2245: 2232: 2205: 2192: 368: 300: 206: 2257: 2217: 58: 42: 89: 257:. It is included in practically every book that covers elementary number theory. 2183:
Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986),
65:
is divisible by 19, one or both of 133 or 143 must be as well (In fact,
2331:
Prime Numbers and Computer Methods for Factorization (second edition)
1287:
is non-negative and is less than the least positive common multiple
2227:
Gauss, Carl Friedrich; Maser, H. (translator into German) (1965),
971:− 1 the corresponding remainder would be greater than or equal to 2296:
A Classical Introduction to Modern Number Theory (Second edition)
483:. This is the generalization of Euclid's lemma mentioned above. 270:
The easiest proof of Euclid's lemma uses another lemma called
913:
an integer} contains both positive and negative numbers. Let
1382:≠ 0, and their common divisors are simply the divisors of 1118:| so it is not empty and therefore has a smallest member. 1372:≠ 0 they have a greatest common divisor. It is positive. 251:
The lemma first appears as proposition 30 in Book VII of
2272:
An Introduction to the Theory of Numbers (Fifth edition)
2185:
Disquisitiones Arithemeticae (Second, corrected edition)
1129:≠ 0 their least positive common multiple is written lcm( 1114:
Proof. The set of positive common multiples contains |
851:
is an integer then there is a unique pair of integers
925:
be the smallest non-negative number in the set. Then
419: 371: 303: 284:are relatively prime integers there exist integers 57:that captures one of the fundamental properties of 452: 395: 327: 1867:is defined to be the greatest common divisor, so 1427:≠ 0 their greatest common divisor is written gcd( 1112:≠ 0 they have a least positive common multiple. 190:A generalization is also called Euclid's lemma: 8: 463:The first term on the left is divisible by 2294:Ireland, Kenneth; Rosen, Michael (1990), 418: 370: 302: 2107: 901:Proof. (existence) The set of numbers { 508:be any integer. If there is an integer 2253: 2243: 2213: 2203: 835:only has a finite number of divisors. 467:, and the second term is divisible by 223:(This is a generalization because if 346:be relatively prime, and assume that 7: 2270:Hardy, G. H.; Wright, E. M. (1980), 471:which by hypotheses is divisible by 96:divides the product of two integers 1374:Proof. Every integer divides 0. If 1404:is finite, the set of divisors of 955:were replaced by a smaller value, 28: 1579:. The proof has two steps i) if 1015:the remainder would be negative: 71:fundamental theorem of arithmetic 2132:Ireland & Rosen, prop. 1.1.1 104:. (In symbols this is written 1: 1745:ii) Since any common divisor 1887:Relation between gcd and lcm 1400:≠ 0. The set of divisors of 69:It used in the proof of the 2174:Disquisitiones Arithmeticae 1832:is an integer. Similarly, 1663:It is a common multiple of 1567:, i.e. there is an integer 1386:. The largest of these is | 2373: 2123:Hardy & Wright, Thm. 3 1462:be any common divisor of 1164:be any common multiple of 453:{\displaystyle rnb+sab=b.} 133:Equivalent statements are 29: 1275:is a commmon multiple of 1183:Proof. There are numbers 839:Division with a remainder 2320:Elementary Number Theory 2054:is a common multiple of 1551:is a common multiple of 396:{\displaystyle rn+sa=1.} 328:{\displaystyle rx+sy=1.} 265: 30:Not to be confused with 2318:Landau, Edmund (1966), 2276:Oxford University Press 1855:is a common divisor of 1613:be a common divisor of 1316:Greatest common divisor 479:, is also divisible by 475:. Therefore their sum, 406:Multiply both sides by 354:. By Bézout, there are 274:. This states that if 239:is relatively prime to 2333:, Boston: Birkhäuser, 2062:, it is a multiple of 2004:, 0) = 1 implies that 454: 397: 329: 51:Euclid's first theorem 18:User:Virginia-American 2329:Riesel, Hans (1994), 2231:, New York: Chelsea, 1952: 1648:Consider the number 1621:. There are integers 1583:is common divisor of 1527:Now assume that both 1517:trivially imply that 1392:Now assume that both 1056:Least common multiple 831:|. This implies that 455: 398: 330: 266:Via Bézout's identity 417: 369: 301: 2322:, New York: Chelsea 2096:Euclidean algorithm 1211:. It follows from 733:is an integer then 500:Definition. Assume 130:(or perhaps both). 2256:has generic name ( 2216:has generic name ( 2114:Gauss, DA, Art. 14 1489:≠ 0. In this case 797:are integers then 450: 393: 325: 36:Euclid's algorithm 2150:Riesel, Thm. A2.1 1772:In particular, 1683:. Multiplying by 272:Bézout's identity 254:Euclid's Elements 227:is prime, either 63:133 × 143 = 19019 2364: 2343: 2323: 2312: 2288: 2261: 2255: 2251: 2249: 2241: 2221: 2215: 2211: 2209: 2201: 2160: 2157: 2151: 2148: 2142: 2139: 2133: 2130: 2124: 2121: 2115: 2112: 2008:= ±1 . But then 1850: 1823: 1800: 1790: 1771: 1743: 1721:and dividing by 1720: 1701: 1671:, so there is a 1662: 1647: 1438:Theorem. Assume 1140:Theorem. Assume 951:(uniqueness) If 459: 457: 456: 451: 402: 400: 399: 394: 334: 332: 331: 326: 293: 283: 207:relatively prime 166:does not divide 156:does not divide 148:does not divide 140:does not divide 68: 64: 32:Euclid's theorem 2372: 2371: 2367: 2366: 2365: 2363: 2362: 2361: 2359: 2356: 2353: 2350: 2347: 2341: 2328: 2317: 2310: 2293: 2286: 2269: 2265: 2252: 2242: 2239: 2226: 2212: 2202: 2199: 2182: 2169: 2164: 2163: 2158: 2154: 2149: 2145: 2141:Landau, Thm. 15 2140: 2136: 2131: 2127: 2122: 2118: 2113: 2109: 2104: 2092: 2017: 1955: 1937:) = 1 then lcm( 1920: 1889: 1833: 1806: 1792: 1773: 1762: 1744: 1726: 1707: 1702:Multiplying by 1688: 1649: 1630: 1608: 1526: 1391: 1373: 1341:is any integer 1321:Definition. If 1319: 1113: 1081:is any integer 1071:common multiple 1061:Definition. If 1059: 950: 841: 810: 772: 742: 720: 694: 672: 654: 612: 602: 498: 489: 487:Euclidean proof 415: 414: 367: 366: 299: 298: 285: 275: 268: 263: 249: 222: 189: 161: 113: 82: 66: 62: 39: 26: 25: 24: 12: 11: 5: 2370: 2368: 2345: 2344: 2339: 2325: 2324: 2314: 2313: 2308: 2290: 2289: 2285:978-0198531715 2284: 2263: 2262: 2237: 2223: 2222: 2197: 2168: 2165: 2162: 2161: 2152: 2143: 2134: 2125: 2116: 2106: 2105: 2103: 2100: 2099: 2098: 2091: 2088: 1954: 1953:Euclid's lemma 1951: 1921:Corollary. If 1891:Corollary. If 1888: 1885: 1875:|. Therefore, 1331:common divisor 1318: 1313: 1295:= 0. But then 1058: 1053: 1007:Similarly, if 840: 837: 497: 494: 488: 485: 461: 460: 449: 446: 443: 440: 437: 434: 431: 428: 425: 422: 404: 403: 392: 389: 386: 383: 380: 377: 374: 336: 335: 324: 321: 318: 315: 312: 309: 306: 267: 264: 262: 259: 248: 245: 81: 78: 67:19 × 7 = 133.) 47:Euclid's lemma 27: 15: 14: 13: 10: 9: 6: 4: 3: 2: 2369: 2360: 2357: 2354: 2351: 2348: 2342: 2340:0-8176-3743-5 2336: 2332: 2327: 2326: 2321: 2316: 2315: 2311: 2309:0-387-97329-X 2305: 2301: 2297: 2292: 2291: 2287: 2281: 2277: 2273: 2268: 2267: 2266: 2259: 2254:|first2= 2247: 2240: 2238:0-8284-0191-8 2234: 2230: 2225: 2224: 2219: 2214:|first2= 2207: 2200: 2194: 2190: 2186: 2181: 2180: 2179: 2176: 2175: 2166: 2159:Landau, ch. 1 2156: 2153: 2147: 2144: 2138: 2135: 2129: 2126: 2120: 2117: 2111: 2108: 2101: 2097: 2094: 2093: 2089: 2087: 2085: 2081: 2077: 2073: 2069: 2065: 2061: 2057: 2053: 2049: 2045: 2041: 2037: 2034:). Since gcd( 2033: 2029: 2025: 2021: 2015: 2011: 2007: 2003: 1999: 1995: 1991: 1987: 1984:Proof. Since 1982: 1980: 1976: 1972: 1968: 1964: 1960: 1950: 1948: 1944: 1940: 1936: 1932: 1928: 1924: 1918: 1914: 1910: 1906: 1902: 1899:≠ 0 then lcm( 1898: 1894: 1886: 1884: 1882: 1878: 1874: 1870: 1866: 1862: 1858: 1854: 1848: 1844: 1840: 1836: 1831: 1827: 1821: 1817: 1813: 1809: 1804: 1799: 1795: 1788: 1784: 1780: 1776: 1769: 1765: 1760: 1756: 1752: 1748: 1741: 1737: 1733: 1729: 1724: 1718: 1714: 1710: 1705: 1699: 1695: 1691: 1686: 1682: 1678: 1674: 1670: 1666: 1660: 1656: 1652: 1645: 1641: 1637: 1633: 1628: 1624: 1620: 1616: 1612: 1606: 1602: 1598: 1594: 1590: 1586: 1582: 1578: 1574: 1570: 1566: 1562: 1558: 1554: 1550: 1546: 1542: 1538: 1535:≠ 0, and let 1534: 1530: 1524: 1520: 1516: 1512: 1508: 1504: 1500: 1496: 1492: 1488: 1484: 1479: 1477: 1473: 1469: 1465: 1461: 1457: 1453: 1449: 1445: 1441: 1436: 1434: 1430: 1426: 1422: 1419:Notation. If 1417: 1415: 1411: 1407: 1403: 1399: 1395: 1389: 1385: 1381: 1377: 1371: 1367: 1362: 1360: 1356: 1352: 1348: 1344: 1340: 1336: 1332: 1328: 1324: 1317: 1314: 1312: 1310: 1306: 1302: 1298: 1294: 1290: 1286: 1282: 1278: 1274: 1270: 1266: 1262: 1258: 1254: 1250: 1246: 1242: 1238: 1234: 1230: 1226: 1222: 1218: 1214: 1210: 1206: 1202: 1198: 1194: 1190: 1186: 1181: 1179: 1175: 1171: 1167: 1163: 1159: 1155: 1151: 1147: 1143: 1138: 1136: 1132: 1128: 1124: 1121:Notation. If 1119: 1117: 1111: 1107: 1102: 1100: 1096: 1092: 1088: 1084: 1080: 1076: 1072: 1068: 1064: 1057: 1054: 1052: 1050: 1046: 1042: 1038: 1034: 1030: 1026: 1022: 1018: 1014: 1010: 1006: 1002: 998: 994: 990: 986: 982: 978: 974: 970: 966: 962: 958: 954: 948: 944: 940: 936: 932: 928: 924: 920: 916: 912: 908: 904: 899: 897: 893: 889: 885: 880: 878: 874: 870: 866: 862: 858: 854: 850: 846: 838: 836: 834: 830: 826: 822: 818: 814: 808: 804: 800: 796: 792: 788: 784: 780: 776: 770: 766: 762: 758: 754: 750: 746: 740: 736: 732: 728: 724: 718: 714: 710: 706: 702: 698: 692: 688: 684: 680: 676: 670: 666: 662: 658: 652: 648: 644: 640: 636: 632: 628: 624: 620: 616: 610: 606: 600: 596: 592: 588: 584: 580: 575: 573: 569: 565: 561: 556: 554: 550: 546: 542: 538: 534: 530: 527: 523: 519: 515: 511: 507: 503: 495: 493: 486: 484: 482: 478: 474: 470: 466: 447: 444: 441: 438: 435: 432: 429: 426: 423: 420: 413: 412: 411: 409: 390: 387: 384: 381: 378: 375: 372: 365: 364: 363: 361: 357: 353: 349: 345: 341: 322: 319: 316: 313: 310: 307: 304: 297: 296: 295: 292: 288: 282: 278: 273: 260: 258: 256: 255: 246: 244: 242: 238: 234: 230: 226: 220: 216: 212: 208: 204: 200: 196: 191: 187: 185: 181: 177: 173: 169: 165: 159: 155: 151: 147: 143: 139: 134: 131: 129: 125: 121: 117: 111: 107: 103: 99: 95: 92:, and assume 91: 87: 79: 77: 74: 72: 60: 59:prime numbers 56: 52: 49:(also called 48: 44: 43:number theory 37: 33: 23: 19: 2358: 2355: 2352: 2349: 2346: 2330: 2319: 2298:, New York: 2295: 2271: 2264: 2228: 2187:, New York: 2184: 2172: 2170: 2155: 2146: 2137: 2128: 2119: 2110: 2083: 2079: 2075: 2071: 2067: 2063: 2059: 2055: 2051: 2047: 2043: 2039: 2035: 2031: 2027: 2023: 2019: 2013: 2009: 2005: 2001: 1997: 1993: 1989: 1985: 1983: 1978: 1974: 1970: 1966: 1962: 1958: 1957:Theorem. If 1956: 1946: 1942: 1938: 1934: 1930: 1929:≠ 0 and gcd( 1926: 1922: 1916: 1912: 1908: 1904: 1900: 1896: 1892: 1890: 1880: 1876: 1872: 1868: 1864: 1860: 1856: 1852: 1846: 1842: 1838: 1834: 1829: 1825: 1819: 1815: 1811: 1807: 1802: 1797: 1793: 1786: 1782: 1778: 1774: 1767: 1763: 1758: 1754: 1750: 1746: 1739: 1735: 1731: 1727: 1722: 1716: 1712: 1708: 1703: 1697: 1693: 1689: 1684: 1680: 1676: 1672: 1668: 1664: 1658: 1654: 1650: 1643: 1639: 1635: 1631: 1626: 1622: 1618: 1614: 1610: 1604: 1600: 1596: 1592: 1588: 1584: 1580: 1576: 1572: 1568: 1564: 1560: 1556: 1552: 1548: 1544: 1540: 1536: 1532: 1528: 1522: 1518: 1514: 1510: 1506: 1502: 1498: 1494: 1490: 1486: 1482: 1480: 1475: 1471: 1467: 1463: 1459: 1455: 1451: 1447: 1443: 1439: 1437: 1432: 1428: 1424: 1420: 1418: 1413: 1409: 1405: 1401: 1397: 1393: 1387: 1383: 1379: 1375: 1369: 1365: 1363: 1358: 1354: 1350: 1346: 1342: 1338: 1334: 1330: 1326: 1322: 1320: 1308: 1304: 1300: 1296: 1292: 1291:. Therefore 1288: 1284: 1280: 1276: 1272: 1268: 1264: 1260: 1256: 1252: 1248: 1247:. Similarly 1244: 1240: 1236: 1232: 1228: 1224: 1220: 1216: 1212: 1208: 1204: 1200: 1196: 1192: 1188: 1184: 1182: 1177: 1173: 1169: 1165: 1161: 1157: 1153: 1149: 1145: 1141: 1139: 1134: 1130: 1126: 1122: 1120: 1115: 1109: 1105: 1103: 1098: 1094: 1090: 1086: 1082: 1078: 1074: 1070: 1066: 1062: 1060: 1048: 1044: 1040: 1036: 1032: 1028: 1024: 1020: 1016: 1012: 1008: 1004: 1000: 996: 992: 988: 984: 980: 976: 972: 968: 964: 960: 956: 952: 946: 942: 938: 934: 930: 926: 922: 918: 914: 910: 906: 902: 900: 895: 891: 887: 883: 882:Definition. 881: 876: 872: 868: 864: 860: 856: 852: 848: 844: 843:Theorem. If 842: 832: 828: 824: 820: 816: 812: 806: 802: 798: 794: 790: 786: 782: 778: 774: 768: 764: 760: 756: 752: 748: 744: 738: 734: 730: 726: 722: 716: 712: 708: 704: 700: 696: 690: 686: 682: 678: 674: 668: 664: 660: 656: 650: 646: 642: 638: 634: 630: 626: 622: 618: 614: 608: 604: 598: 594: 590: 586: 582: 578: 576: 571: 567: 566:is writtten 563: 559: 557: 552: 548: 544: 540: 536: 532: 528: 525: 521: 517: 513: 509: 505: 504:≠ 0 and let 501: 499: 496:Divisibility 490: 480: 476: 472: 468: 464: 462: 407: 405: 359: 355: 351: 347: 343: 339: 337: 290: 286: 280: 276: 269: 252: 250: 240: 236: 232: 228: 224: 218: 214: 210: 202: 198: 194: 192: 188: 183: 179: 175: 171: 167: 163: 157: 153: 149: 145: 141: 137: 135: 132: 127: 123: 119: 115: 109: 105: 101: 97: 93: 90:prime number 85: 83: 80:Formulations 75: 50: 46: 40: 2070:|. That is 1973:) = 1 then 1629:such that 1271:. That is, 1263:imply that 847:> 0 and 524:is said to 2274:, Oxford: 2198:0387962549 2167:References 1791:Dividing 1675:such that 1571:such that 1481:Proof. If 1458:) and let 1364:Lemma. If 1345:such that 1191:such that 1160:) and let 1104:Lemma. If 1085:such that 859:such that 811:Lemma. If 773:Lemma. If 743:Lemma. If 721:Lemma. If 695:Lemma. If 673:Lemma. If 655:Lemma. If 613:Lemma. If 577:Lemma. If 558:Notation. 512:such that 294:such that 2050:|. Since 2022:≠ 0, let 2000:= 0, gcd( 1547:). Since 1493:= gcd(0, 1485:= 0 then 1446:≠ 0. Let 1378:= 0 then 1148:≠ 0. Let 929:≥ 0, and 896:remainder 685:≠ 0 then 603:Lemma. 1| 581:≠ 0 then 2300:Springer 2246:citation 2206:citation 2189:Springer 2090:See also 1996:≠ 0. If 1965:and gcd( 1925:≠ 0 and 1895:≠ 0 and 1757:divides 1531:≠ 0 and 1396:≠ 0 and 1203:, 0 ≤ 1144:≠ 0 and 1125:≠ 0 and 1108:≠ 0 and 1065:≠ 0 and 1051:< 0. 949:< 0. 888:quotient 871:and 0 ≤ 815:≠ 0 and 562:divides 549:multiple 362:making 182:divides 174:divides 126:divides 118:divides 20:‎ | 2042:) = 1, 1805:gives 1734:, i.e. 1725:gives 1706:gives 1687:gives 1609:i) Let 1470:. Then 1442:≠ 0 or 1423:≠ 0 or 1368:≠ 0 or 1329:≠ 0 a 1325:≠ 0 or 1303:, i.e. 1172:. Then 894:is the 886:is the 645:, and | 607:and −1| 537:divisor 247:History 213:, then 178:, then 152:, then 53:) is a 22:Sandbox 2337:  2306:  2282:  2235:  2195:  2026:= lcm( 1863:. But 1777:= gcd( 1599:; ii) 1539:= lcd( 1501:|, so 1450:= gcd( 1152:= lcm( 1069:≠ 0 a 823:then | 621:then − 526:divide 261:Proofs 201:, and 2102:Notes 1945:) = | 1915:) = | 1907:)gcd( 1785:) ≤ | 1591:then 1497:) = | 1239:that 1207:< 1023:+ 1, 1011:> 959:< 875:< 827:| ≤ | 759:then 711:then 663:then 547:is a 535:is a 114:Then 88:be a 55:lemma 16:< 2335:ISBN 2304:ISBN 2280:ISBN 2258:help 2233:ISBN 2218:help 2193:ISBN 2171:The 2058:and 1859:and 1824:and 1753:and 1717:abte 1713:gmte 1690:eres 1667:and 1625:and 1617:and 1587:and 1555:and 1509:and 1466:and 1412:and 1353:and 1337:and 1279:and 1255:and 1231:and 1187:and 1168:and 1093:and 1077:and 1039:+ 1) 991:− 1) 945:+ 1) 890:and 855:and 793:and 789:and 781:and 751:and 729:and 703:and 681:and 593:and 585:|0, 543:and 358:and 342:and 338:Let 289:and 279:and 170:and 144:and 100:and 84:Let 2078:so 2066:= | 2046:= | 2018:If 1949:|. 1919:|. 1883:|. 1879:= | 1871:≥ | 1851:so 1849:), 1822:), 1801:by 1789:|. 1770:|. 1766:≤ | 1761:, 1749:of 1709:abg 1698:mte 1677:ers 1651:ers 1607:|. 1603:= | 1435:). 1390:|. 1333:of 1137:). 1073:of 1035:− ( 999:+ a 987:− ( 941:− ( 653:|. 649:||| 637:, − 555:. 551:of 539:of 520:, 243:.) 235:or 209:to 205:is 193:If 162:If 136:If 122:or 41:In 34:or 2302:, 2278:, 2250:: 2248:}} 2244:{{ 2210:: 2208:}} 2204:{{ 2191:, 2086:. 2076:bc 2072:ab 2068:ab 2052:bc 2048:ab 2038:, 2030:, 2016:. 1992:, 1990:bc 1981:. 1969:, 1963:bc 1947:ab 1941:, 1933:, 1917:ab 1903:, 1837:= 1810:= 1798:gm 1796:= 1794:ab 1781:, 1732:te 1730:= 1723:ab 1719:, 1715:= 1711:= 1700:. 1696:= 1694:ab 1692:= 1681:mt 1679:= 1661:. 1659:br 1657:= 1655:as 1653:= 1646:. 1644:es 1642:= 1638:, 1636:er 1634:= 1577:gm 1575:= 1573:ab 1565:ab 1559:, 1549:ab 1543:, 1525:. 1478:. 1454:, 1431:, 1416:. 1361:. 1311:. 1301:qm 1299:= 1283:. 1223:, 1221:qm 1219:− 1215:= 1199:+ 1197:qm 1195:= 1180:. 1156:, 1133:, 1116:ab 1101:. 1047:− 1043:= 1031:≤ 1029:ua 1027:− 1019:≥ 1001:≥ 995:= 983:≥ 981:ua 979:− 975:: 967:≤ 963:, 937:= 933:− 923:qa 921:− 917:= 909:: 907:ua 905:− 898:. 879:. 867:+ 865:qa 863:= 809:. 807:cy 805:± 803:bx 771:. 767:± 741:. 739:bx 719:. 693:. 691:bc 687:ac 671:. 661:bc 657:ac 641:|− 633:|− 629:, 611:. 601:. 597:|− 574:. 531:; 518:aq 516:= 469:ab 410:: 391:1. 352:ab 323:1. 199:ab 186:. 176:ab 158:ab 112:.) 110:ab 73:. 45:, 2260:) 2220:) 2084:c 2082:| 2080:a 2074:| 2064:m 2060:b 2056:a 2044:m 2040:b 2036:a 2032:b 2028:a 2024:m 2020:b 2014:c 2012:| 2010:a 2006:a 2002:a 1998:b 1994:a 1988:| 1986:a 1979:c 1977:| 1975:a 1971:b 1967:a 1961:| 1959:a 1943:b 1939:a 1935:b 1931:a 1927:b 1923:a 1913:b 1911:, 1909:a 1905:b 1901:a 1897:b 1893:a 1881:g 1877:d 1873:g 1869:d 1865:d 1861:b 1857:a 1853:g 1847:a 1845:/ 1843:m 1841:( 1839:g 1835:b 1830:b 1828:/ 1826:m 1820:b 1818:/ 1816:m 1814:( 1812:g 1808:a 1803:b 1787:g 1783:b 1779:a 1775:d 1768:g 1764:e 1759:g 1755:b 1751:a 1747:e 1742:. 1740:g 1738:| 1736:e 1728:g 1704:g 1685:e 1673:t 1669:b 1665:a 1640:b 1632:a 1627:s 1623:r 1619:b 1615:a 1611:e 1605:g 1601:d 1597:g 1595:| 1593:e 1589:b 1585:a 1581:e 1569:g 1563:| 1561:m 1557:b 1553:a 1545:b 1541:a 1537:m 1533:b 1529:a 1523:d 1521:| 1519:k 1515:b 1513:| 1511:k 1507:a 1505:| 1503:k 1499:b 1495:b 1491:d 1487:b 1483:a 1476:d 1474:| 1472:e 1468:b 1464:a 1460:e 1456:b 1452:a 1448:d 1444:b 1440:a 1433:b 1429:a 1425:b 1421:a 1414:b 1410:a 1406:b 1402:a 1398:b 1394:a 1388:b 1384:b 1380:b 1376:a 1370:b 1366:a 1359:b 1357:| 1355:k 1351:a 1349:| 1347:k 1343:k 1339:b 1335:a 1327:b 1323:a 1309:n 1307:| 1305:m 1297:n 1293:r 1289:m 1285:r 1281:b 1277:a 1273:r 1269:r 1267:| 1265:b 1261:n 1259:| 1257:b 1253:m 1251:| 1249:b 1245:r 1243:| 1241:a 1237:n 1235:| 1233:a 1229:m 1227:| 1225:a 1217:n 1213:r 1209:m 1205:r 1201:r 1193:n 1189:r 1185:q 1178:n 1176:| 1174:m 1170:b 1166:a 1162:n 1158:b 1154:a 1150:m 1146:b 1142:a 1135:b 1131:a 1127:b 1123:a 1110:b 1106:a 1099:k 1097:| 1095:b 1091:k 1089:| 1087:a 1083:k 1079:b 1075:a 1067:b 1063:a 1049:a 1045:r 1041:a 1037:q 1033:b 1025:b 1021:q 1017:u 1013:q 1009:u 1005:. 1003:a 997:r 993:a 989:q 985:b 977:b 973:a 969:q 965:u 961:q 957:u 953:q 947:a 943:q 939:b 935:a 931:r 927:r 919:b 915:r 911:u 903:b 892:r 884:q 877:a 873:r 869:r 861:b 857:r 853:q 849:b 845:a 833:b 829:b 825:a 821:b 819:| 817:a 813:b 801:| 799:a 795:y 791:x 787:c 785:| 783:a 779:b 777:| 775:a 769:c 765:b 763:| 761:a 757:c 755:| 753:a 749:b 747:| 745:a 737:| 735:a 731:x 727:b 725:| 723:a 717:c 715:| 713:a 709:c 707:| 705:b 701:b 699:| 697:a 689:| 683:c 679:b 677:| 675:a 669:b 667:| 665:a 659:| 651:b 647:a 643:b 639:a 635:b 631:a 627:b 625:| 623:a 619:b 617:| 615:a 609:a 605:a 599:a 595:a 591:a 589:| 587:a 583:a 579:a 572:b 570:| 568:a 564:b 560:a 553:a 545:b 541:b 533:a 529:b 522:a 514:b 510:q 506:b 502:a 481:n 477:b 473:n 465:n 448:. 445:b 442:= 439:b 436:a 433:s 430:+ 427:b 424:n 421:r 408:b 388:= 385:a 382:s 379:+ 376:n 373:r 360:s 356:r 350:| 348:n 344:n 340:a 320:= 317:y 314:s 311:+ 308:x 305:r 291:s 287:r 281:y 277:x 241:a 237:n 233:a 231:| 229:n 225:n 221:. 219:b 217:| 215:n 211:a 203:n 197:| 195:n 184:b 180:p 172:p 168:a 164:p 160:. 154:p 150:b 146:p 142:a 138:p 128:b 124:p 120:a 116:p 108:| 106:p 102:b 98:a 94:p 86:p 38:.

Index

User:Virginia-American
Sandbox
Euclid's theorem
Euclid's algorithm
number theory
lemma
prime numbers
fundamental theorem of arithmetic
prime number
relatively prime
Euclid's Elements
Bézout's identity
Least common multiple
Greatest common divisor
Euclidean algorithm
Disquisitiones Arithmeticae
Springer
ISBN
0387962549
citation
help
ISBN
0-8284-0191-8
citation
help
Oxford University Press
ISBN
978-0198531715
Springer
ISBN

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.