667:
1633:
1863:
1445:
987:). Pairwise coprimality is a stronger condition than setwise coprimality; every pairwise coprime finite set is also setwise coprime, but the reverse is not true. For example, the integers 4, 5, 6 are (setwise) coprime (because the only positive integer dividing
100:
The numbers 8 and 9 are coprime, despite the fact that neither—considered individually—is a prime number, since 1 is their only common divisor. On the other hand, 6 and 9 are not coprime, because they are both divisible by 3. The numerator and denominator of a
1682:
There is no way to choose a positive integer at random so that each positive integer occurs with equal probability, but statements about "randomly chosen integers" such as the ones above can be formalized by using the notion of
1438:
If one makes the heuristic assumption that such reasoning can be extended to infinitely many divisibility events, one is led to guess that the probability that two numbers are coprime is given by a product over all primes,
1628:{\displaystyle \prod _{{\text{prime }}p}\left(1-{\frac {1}{p^{2}}}\right)=\left(\prod _{{\text{prime }}p}{\frac {1}{1-p^{-2}}}\right)^{-1}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}\approx 0.607927102\approx 61\%.}
871:
954:
414:
1851:
1381:
1332:
257:
of integers can also be called coprime if its elements share no common positive factor except 1. A stronger condition on a set of integers is pairwise coprime, which means that
1742:
1434:
1285:
2507:
2375:
2284:
2240:
1385:
Any finite collection of divisibility events associated to distinct primes is mutually independent. For example, in the case of two events, a number is divisible by primes
2765:
2416:
1785:
1124:
3034:
1184:
2149:
2049:
2006:
1963:
187:
2572:
2113:
2700:
1084:
2665:
2633:
2543:
2448:
2316:
2181:
2084:
2601:
121:
are coprime, the standard way of expressing this fact in mathematical notation is to indicate that their greatest common divisor is one, by the formula
968:
of all the elements of the set is 1. For example, the integers 6, 10, 15 are coprime because 1 is the only positive integer that divides all of them.
3142:
3124:
3097:
1870:
at (2, 1). The root (2, 1) is marked red, its three children are shown in orange, third generation is yellow, and so on in the rainbow order.
777:
2774:
2875:
1243:
2732:
combine rotors of different numbers of teeth. Such combinations work best when the entire set of lengths are pairwise coprime.
289:
The numbers 1 and −1 are the only integers coprime with every integer, and they are the only integers that are coprime with 0.
346:
3021:
698:
236:
888:
705:, in the sense that there is no point with integer coordinates anywhere on the line segment between the origin and
2713:
wear is achieved by choosing the tooth counts of the two gears meshing together to be relatively prime. When a 1:1
670:
Figure 1. The numbers 4 and 9 are coprime. Therefore, the diagonal of a 4 × 9 lattice does not intersect any other
1013:
of integers to be pairwise coprime. Notable examples include the set of all prime numbers, the set of elements in
1207:
1003:
467:
221:
384:
1289:
for example, every 7th integer is divisible by 7. Hence the probability that two numbers are both divisible by
1002:
The concept of pairwise coprimality is important as a hypothesis in many results in number theory, such as the
2054:
This scheme is exhaustive and non-redundant with no invalid members. This can be proved by remarking that, if
1813:
2967:
Saunders, Robert & Randall, Trevor (July 1994), "The family tree of the
Pythagorean triplets revisited",
597:
it is a product of invertible elements, and therefore invertible); this also follows from the first point by
3089:
1341:
1087:
1014:
965:
335:
74:
3181:
2994:
Mitchell, Douglas W. (July 2001), "An alternative characterisation of all primitive
Pythagorean triples",
1298:
1643:
478:
1703:
1402:
1258:
2865:
2795:
217:
147:
2453:
2321:
2248:
2186:
2790:
2778:
2745:
2383:
1761:
758:
429:
213:
1107:
1151:
419:
377:
373:
3047:
3138:
3120:
3093:
2950:
2871:
2717:
is desired, a gear relatively prime to the two equal-size gears may be inserted between them.
2122:
2013:
1970:
1927:
882:
598:
254:
166:
2548:
2089:
1249:
Informally, the probability that any number is divisible by a prime (or in fact any integer)
3003:
2976:
2670:
1054:
1041:
102:
2638:
2606:
2516:
2421:
2289:
2154:
2057:
3060:
2577:
1685:
1091:
2816:
1676:
1018:
739:
671:
160:
3158:
Lord, Nick (March 2008), "A uniform construction of some infinite coprime sequences",
1234:
are coprime. In this determination, it is convenient to use the characterization that
3175:
2729:
2725:
1672:
1654:
152:
31:
3081:
2721:
1897:
1010:
305:
281:
is coprime, but it is not pairwise coprime since 2 and 4 are not relatively prime.
156:
62:
197:
are relatively prime and that the term "prime" be used instead of coprime (as in
3077:
1867:
721:
17:
2770:
2714:
1030:
666:
470:); in fact the solutions are described by a single congruence relation modulo
971:
If every pair in a set of integers is coprime, then the set is said to be
212:
A fast way to determine whether two numbers are coprime is given by the
2728:
machines combined several loops of key tape of different lengths. Many
58:
35:
701:
would be "visible" via an unobstructed line of sight from the origin
1242:
are coprime if and only if no prime number divides both of them (see
3007:
2980:
1904:(for even–odd and odd–even pairs), and the other tree starting from
1862:
757:
are coprime. As a generalization of this, following easily from the
1210:
can be generalized to any commutative ring, using coprime ideals.
866:{\displaystyle \gcd \left(n^{a}-1,n^{b}-1\right)=n^{\gcd(a,b)}-1.}
762:
665:
2740:
This concept can be extended to other algebraic structures than
2710:
2574:
This process of "computing the father" can stop only if either
2635:
In these cases, coprimality, implies that the pair is either
663:. This can be viewed as a generalization of Euclid's lemma.
1336:
and the probability that at least one of them is not is
1700:
be the probability that two randomly chosen numbers in
227:
The number of integers coprime with a positive integer
1818:
1407:
1352:
1303:
1263:
685:
are coprime if and only if the point with coordinates
2748:
2673:
2641:
2609:
2580:
2551:
2519:
2456:
2424:
2386:
2324:
2292:
2251:
2189:
2157:
2125:
2092:
2060:
2016:
1973:
1930:
1816:
1764:
1758:
exactly, with work one can show that in the limit as
1706:
1448:
1405:
1344:
1301:
1261:
1154:
1110:
1057:
891:
780:
387:
169:
2863:Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989),
2821:. Boston: Thompson, Bigelow & Brown. p. 49
1646:, the identity relating the product over primes to
2759:
2694:
2659:
2627:
2595:
2566:
2537:
2501:
2442:
2410:
2369:
2310:
2278:
2234:
2175:
2143:
2107:
2078:
2043:
2000:
1957:
1845:
1808:randomly chosen integers being setwise coprime is
1779:
1736:
1627:
1428:
1375:
1326:
1279:
1178:
1118:
1078:
948:
865:
408:
181:
1908:(for odd–odd pairs). The children of each vertex
724:that two randomly chosen integers are coprime is
1226:, it is reasonable to ask how likely it is that
837:
781:
732:
3022:"Cryptology: Key Generators with Long Periods"
2925:
2913:
2901:
949:{\displaystyle S=\{a_{1},a_{2},\dots ,a_{n}\}}
73:, and vice versa. This is equivalent to their
3135:Elementary Number Theory and its Applications
8:
1731:
1707:
943:
898:
3106:Niven, Ivan; Zuckerman, Herbert S. (1966),
2954:
2850:
1896:) can be arranged in two disjoint complete
409:{\displaystyle \mathbb {Z} /a\mathbb {Z} }
277:of different integers in the set. The set
2750:
2749:
2747:
2672:
2640:
2608:
2579:
2550:
2518:
2455:
2423:
2385:
2323:
2291:
2250:
2188:
2156:
2124:
2091:
2059:
2015:
1972:
1929:
1817:
1815:
1763:
1705:
1599:
1590:
1566:
1554:
1537:
1521:
1511:
1510:
1484:
1475:
1454:
1453:
1447:
1406:
1404:
1361:
1351:
1343:
1312:
1302:
1300:
1262:
1260:
1153:
1112:
1111:
1109:
1056:
937:
918:
905:
890:
836:
812:
793:
779:
720:In a sense that can be made precise, the
402:
401:
393:
389:
388:
386:
292:A number of conditions are equivalent to
168:
3108:An Introduction to the Theory of Numbers
3086:An Introduction to the Theory of Numbers
3035:"German Cipher Machines of World War II"
1861:
1846:{\displaystyle {\tfrac {1}{\zeta (k)}}.}
620:As a consequence of the first point, if
512:As a consequence of the third point, if
61:of both of them is 1. Consequently, any
27:Two numbers without shared prime factors
2807:
749:are coprime if and only if the numbers
353:, meaning that there exists an integer
57:if the only positive integer that is a
1874:All pairs of positive coprime numbers
1376:{\displaystyle 1-{\tfrac {1}{p^{2}}}.}
601:, which states that if a prime number
239:, also known as Euler's phi function,
3110:(2nd ed.), John Wiley & Sons
2937:
7:
2709:In machine design, an even, uniform
1327:{\displaystyle {\tfrac {1}{p^{2}}},}
628:are coprime, then so are any powers
613:divides at least one of the factors
2889:
2868:/ A Foundation for Computer Science
1804:More generally, the probability of
1397:; the latter event has probability
1218:Given two randomly chosen integers
1771:
1619:
1393:if and only if it is divisible by
25:
2545:is a "smaller" coprime pair with
1737:{\displaystyle \{1,2,\ldots ,N\}}
1429:{\displaystyle {\tfrac {1}{pq}}.}
1244:Fundamental theorem of arithmetic
733:§ Probability of coprimality
163:proposed an alternative notation
3137:(3rd ed.), Addison-Wesley,
1280:{\displaystyle {\tfrac {1}{p}};}
991:of them is 1), but they are not
216:and its faster variants such as
2870:, Addison-Wesley, p. 115,
2835:prime when no whole number but
2686:
2674:
2654:
2642:
2532:
2520:
2502:{\displaystyle (m,n)=(b,2b-a)}
2496:
2475:
2469:
2457:
2437:
2425:
2370:{\displaystyle (m,n)=(b,a-2b)}
2364:
2343:
2337:
2325:
2305:
2293:
2279:{\displaystyle 2b<a<3b,}
2235:{\displaystyle (m,n)=(a-2b,b)}
2229:
2208:
2202:
2190:
2170:
2158:
2073:
2061:
2038:
2017:
1995:
1974:
1952:
1931:
1833:
1827:
1768:
1581:
1575:
852:
840:
368:. In ring-theoretic language,
1:
3117:Number Theory and Its History
2760:{\displaystyle \mathbb {Z} ;}
2411:{\displaystyle b<a<2b,}
1780:{\displaystyle N\to \infty ,}
1689:. For each positive integer
550:. That is, we may "divide by
77:(GCD) being 1. One says also
1858:Generating all coprime pairs
1119:{\displaystyle \mathbb {Z} }
1090:: with this definition, two
105:are coprime, by definition.
2949:This theorem was proved by
1190:is a third ideal such that
1179:{\displaystyle AB=A\cap B;}
1136:are coprime. If the ideals
1128:are coprime if and only if
699:Cartesian coordinate system
578:, then so is their product
265:are coprime for every pair
3198:
3133:Rosen, Kenneth H. (1992),
2953:in 1881. For a proof, see
2926:Niven & Zuckerman 1966
2914:Niven & Zuckerman 1966
2902:Niven & Zuckerman 1966
1920:are generated as follows:
1214:Probability of coprimality
1102:) in the ring of integers
1025:Coprimality in ring ideals
731:, which is about 61% (see
489:is equal to their product
145:. In their 1989 textbook
3048:"Origins of One-time pad"
1900:, one tree starting from
1208:Chinese remainder theorem
1004:Chinese remainder theorem
985:mutually relatively prime
977:pairwise relatively prime
468:Chinese remainder theorem
3061:"Vernam-Vigenère cipher"
2839:will divide each of them
2818:A Treatise on Arithmetic
2815:Eaton, James S. (1872).
2144:{\displaystyle a>3b,}
2044:{\displaystyle (m+2n,n)}
2001:{\displaystyle (2m+n,m)}
1958:{\displaystyle (2m-n,m)}
1744:are coprime. Although
1657:, and the evaluation of
237:Euler's totient function
182:{\displaystyle a\perp b}
3090:Oxford University Press
2955:Hardy & Wright 2008
2904:, p. 22, Theorem 2.3(b)
2851:Hardy & Wright 2008
2775:greatest common divisor
2567:{\displaystyle m>n.}
2108:{\displaystyle a>b,}
2086:is a coprime pair with
1047:are called coprime (or
966:greatest common divisor
432:for an unknown integer
75:greatest common divisor
3115:Ore, Oystein (1988) ,
2761:
2696:
2695:{\displaystyle (3,1).}
2661:
2629:
2597:
2568:
2539:
2503:
2444:
2412:
2371:
2312:
2280:
2236:
2177:
2145:
2109:
2080:
2045:
2002:
1959:
1871:
1847:
1781:
1738:
1629:
1430:
1377:
1328:
1281:
1180:
1120:
1080:
1079:{\displaystyle A+B=R.}
1009:It is possible for an
950:
867:
674:
574:are both coprime with
554:" when working modulo
410:
347:multiplicative inverse
222:Lehmer's GCD algorithm
183:
3059:Gustavus J. Simmons.
3037:. 2014. p. 16; p. 22.
2762:
2697:
2662:
2660:{\displaystyle (2,1)}
2630:
2628:{\displaystyle a=3b.}
2598:
2569:
2540:
2538:{\displaystyle (m,n)}
2504:
2445:
2443:{\displaystyle (a,b)}
2413:
2372:
2313:
2311:{\displaystyle (a,b)}
2281:
2237:
2178:
2176:{\displaystyle (a,b)}
2146:
2110:
2081:
2079:{\displaystyle (a,b)}
2046:
2003:
1960:
1865:
1848:
1782:
1739:
1644:Riemann zeta function
1630:
1431:
1378:
1329:
1282:
1181:
1121:
1081:
1017:, and the set of all
951:
868:
669:
479:least common multiple
411:
319:There exist integers
184:
3160:Mathematical Gazette
2996:Mathematical Gazette
2969:Mathematical Gazette
2866:Concrete Mathematics
2796:Superpartient number
2746:
2671:
2639:
2607:
2596:{\displaystyle a=2b}
2578:
2549:
2517:
2454:
2422:
2384:
2322:
2290:
2249:
2187:
2155:
2123:
2090:
2058:
2014:
1971:
1928:
1814:
1762:
1704:
1653:is an example of an
1446:
1403:
1342:
1299:
1259:
1152:
1108:
1055:
1015:Sylvester's sequence
889:
778:
651:divides the product
430:congruence relations
385:
218:binary GCD algorithm
167:
148:Concrete Mathematics
109:Notation and testing
3020:Klaus Pommerening.
2928:, p.7, Theorem 1.10
2916:, p. 6, Theorem 1.8
2779:coprime polynomials
956:can also be called
877:Coprimality in sets
759:Euclidean algorithm
214:Euclidean algorithm
2757:
2692:
2657:
2625:
2593:
2564:
2535:
2499:
2440:
2408:
2367:
2308:
2276:
2232:
2173:
2141:
2105:
2076:
2041:
1998:
1955:
1872:
1843:
1838:
1777:
1734:
1625:
1520:
1463:
1426:
1421:
1373:
1368:
1324:
1319:
1277:
1272:
1176:
1148:are coprime, then
1116:
1076:
946:
863:
717:. (See figure 1.)
675:
605:divides a product
558:. Furthermore, if
466:, has a solution (
406:
179:
113:When the integers
3144:978-0-201-57889-8
3126:978-0-486-65620-5
3099:978-0-19-921986-5
3046:Dirk Rijmenants.
1837:
1751:will never equal
1605:
1585:
1547:
1514:
1506:
1490:
1457:
1449:
1420:
1367:
1318:
1271:
1088:Bézout's identity
1086:This generalizes
995:coprime (because
677:The two integers
336:Bézout's identity
189:to indicate that
16:(Redirected from
3189:
3167:
3147:
3129:
3111:
3102:
3088:(6th ed.),
3064:
3057:
3051:
3044:
3038:
3031:
3025:
3018:
3012:
3010:
2991:
2985:
2983:
2964:
2958:
2947:
2941:
2935:
2929:
2923:
2917:
2911:
2905:
2899:
2893:
2887:
2881:
2880:
2860:
2854:
2848:
2842:
2841:
2831:Two numbers are
2828:
2826:
2812:
2791:Euclid's orchard
2777:is 1 are called
2768:
2766:
2764:
2763:
2758:
2753:
2720:In pre-computer
2701:
2699:
2698:
2693:
2666:
2664:
2663:
2658:
2634:
2632:
2631:
2626:
2602:
2600:
2599:
2594:
2573:
2571:
2570:
2565:
2544:
2542:
2541:
2536:
2508:
2506:
2505:
2500:
2449:
2447:
2446:
2441:
2417:
2415:
2414:
2409:
2376:
2374:
2373:
2368:
2317:
2315:
2314:
2309:
2285:
2283:
2282:
2277:
2241:
2239:
2238:
2233:
2182:
2180:
2179:
2174:
2150:
2148:
2147:
2142:
2114:
2112:
2111:
2106:
2085:
2083:
2082:
2077:
2050:
2048:
2047:
2042:
2007:
2005:
2004:
1999:
1964:
1962:
1961:
1956:
1919:
1907:
1903:
1895:
1885:
1854:
1852:
1850:
1849:
1844:
1839:
1836:
1819:
1807:
1800:
1793:
1787:the probability
1786:
1784:
1783:
1778:
1757:
1750:
1743:
1741:
1740:
1735:
1699:
1692:
1670:
1663:
1652:
1641:
1634:
1632:
1631:
1626:
1606:
1604:
1603:
1591:
1586:
1584:
1567:
1562:
1561:
1553:
1549:
1548:
1546:
1545:
1544:
1522:
1519:
1515:
1512:
1496:
1492:
1491:
1489:
1488:
1476:
1462:
1458:
1455:
1437:
1435:
1433:
1432:
1427:
1422:
1419:
1408:
1396:
1392:
1388:
1384:
1382:
1380:
1379:
1374:
1369:
1366:
1365:
1353:
1335:
1333:
1331:
1330:
1325:
1320:
1317:
1316:
1304:
1292:
1288:
1286:
1284:
1283:
1278:
1273:
1264:
1252:
1241:
1237:
1233:
1229:
1225:
1221:
1205:
1201:
1197:
1193:
1189:
1186:furthermore, if
1185:
1183:
1182:
1177:
1147:
1143:
1139:
1135:
1131:
1127:
1125:
1123:
1122:
1117:
1115:
1101:
1097:
1092:principal ideals
1085:
1083:
1082:
1077:
1046:
1042:commutative ring
1039:
1035:
998:
981:mutually coprime
973:pairwise coprime
955:
953:
952:
947:
942:
941:
923:
922:
910:
909:
872:
870:
869:
864:
856:
855:
828:
824:
817:
816:
798:
797:
770:
756:
752:
748:
744:
730:
716:
704:
696:
684:
680:
662:
658:
654:
650:
647:are coprime and
646:
642:
635:
631:
627:
623:
616:
612:
608:
604:
596:
592:
577:
573:
557:
553:
549:
534:
520:are coprime and
519:
515:
507:
492:
488:
484:
473:
465:
450:
435:
424:
417:
415:
413:
412:
407:
405:
397:
392:
371:
367:
356:
352:
344:
333:
322:
315:
311:
299:
295:
280:
276:
264:
260:
249:
234:
231:, between 1 and
230:
208:
200:
196:
192:
188:
186:
185:
180:
144:
132:
120:
116:
103:reduced fraction
96:
90:
86:
80:
72:
69:does not divide
68:
51:relatively prime
44:
40:
21:
3197:
3196:
3192:
3191:
3190:
3188:
3187:
3186:
3172:
3171:
3157:
3154:
3152:Further reading
3145:
3132:
3127:
3114:
3105:
3100:
3076:
3073:
3068:
3067:
3058:
3054:
3045:
3041:
3032:
3028:
3019:
3015:
3008:10.2307/3622017
2993:
2992:
2988:
2981:10.2307/3618576
2966:
2965:
2961:
2948:
2944:
2936:
2932:
2924:
2920:
2912:
2908:
2900:
2896:
2888:
2884:
2878:
2862:
2861:
2857:
2849:
2845:
2824:
2822:
2814:
2813:
2809:
2804:
2787:
2744:
2743:
2741:
2738:
2736:Generalizations
2707:
2669:
2668:
2637:
2636:
2605:
2604:
2576:
2575:
2547:
2546:
2515:
2514:
2509:along branch 1.
2452:
2451:
2420:
2419:
2382:
2381:
2377:along branch 2;
2320:
2319:
2288:
2287:
2247:
2246:
2242:along branch 3;
2185:
2184:
2153:
2152:
2121:
2120:
2088:
2087:
2056:
2055:
2012:
2011:
1969:
1968:
1926:
1925:
1909:
1905:
1901:
1887:
1875:
1860:
1823:
1812:
1811:
1809:
1805:
1795:
1792:
1788:
1760:
1759:
1752:
1749:
1745:
1702:
1701:
1698:
1694:
1690:
1686:natural density
1665:
1658:
1647:
1639:
1595:
1571:
1533:
1526:
1505:
1501:
1500:
1480:
1468:
1464:
1444:
1443:
1412:
1401:
1400:
1398:
1394:
1390:
1386:
1357:
1340:
1339:
1337:
1308:
1297:
1296:
1294:
1290:
1257:
1256:
1254:
1250:
1239:
1235:
1231:
1227:
1223:
1219:
1216:
1203:
1199:
1195:
1191:
1187:
1150:
1149:
1145:
1141:
1137:
1133:
1129:
1106:
1105:
1103:
1099:
1095:
1053:
1052:
1044:
1037:
1033:
1027:
996:
962:setwise coprime
933:
914:
901:
887:
886:
879:
832:
808:
789:
788:
784:
776:
775:
765:
754:
750:
746:
742:
740:natural numbers
725:
706:
702:
686:
682:
678:
660:
656:
652:
648:
644:
640:
633:
629:
625:
621:
614:
610:
606:
602:
594:
591:
585:
579:
575:
572:
565:
559:
555:
551:
536:
521:
517:
513:
494:
490:
486:
482:
471:
452:
437:
433:
422:
420:integers modulo
383:
382:
380:
369:
358:
354:
350:
342:
324:
320:
313:
309:
300:being coprime:
297:
293:
287:
278:
266:
262:
258:
240:
232:
228:
206:
198:
194:
190:
165:
164:
134:
122:
118:
114:
111:
94:
92:is coprime with
88:
84:
78:
70:
66:
42:
38:
28:
23:
22:
18:Coprime integer
15:
12:
11:
5:
3195:
3193:
3185:
3184:
3174:
3173:
3170:
3169:
3153:
3150:
3149:
3148:
3143:
3130:
3125:
3112:
3103:
3098:
3072:
3069:
3066:
3065:
3052:
3039:
3026:
3013:
2986:
2959:
2951:Ernesto Cesàro
2942:
2930:
2918:
2906:
2894:
2882:
2876:
2855:
2843:
2806:
2805:
2803:
2800:
2799:
2798:
2793:
2786:
2783:
2756:
2752:
2737:
2734:
2730:rotor machines
2706:
2703:
2691:
2688:
2685:
2682:
2679:
2676:
2656:
2653:
2650:
2647:
2644:
2624:
2621:
2618:
2615:
2612:
2592:
2589:
2586:
2583:
2563:
2560:
2557:
2554:
2534:
2531:
2528:
2525:
2522:
2511:
2510:
2498:
2495:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2459:
2450:is a child of
2439:
2436:
2433:
2430:
2427:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2378:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2318:is a child of
2307:
2304:
2301:
2298:
2295:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2243:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2183:is a child of
2172:
2169:
2166:
2163:
2160:
2140:
2137:
2134:
2131:
2128:
2104:
2101:
2098:
2095:
2075:
2072:
2069:
2066:
2063:
2052:
2051:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2008:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1965:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1859:
1856:
1842:
1835:
1832:
1829:
1826:
1822:
1790:
1776:
1773:
1770:
1767:
1747:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1696:
1677:Leonhard Euler
1642:refers to the
1636:
1635:
1624:
1621:
1618:
1615:
1612:
1609:
1602:
1598:
1594:
1589:
1583:
1580:
1577:
1574:
1570:
1565:
1560:
1557:
1552:
1543:
1540:
1536:
1532:
1529:
1525:
1518:
1509:
1504:
1499:
1495:
1487:
1483:
1479:
1474:
1471:
1467:
1461:
1452:
1425:
1418:
1415:
1411:
1372:
1364:
1360:
1356:
1350:
1347:
1323:
1315:
1311:
1307:
1276:
1270:
1267:
1215:
1212:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1114:
1075:
1072:
1069:
1066:
1063:
1060:
1026:
1023:
1019:Fermat numbers
945:
940:
936:
932:
929:
926:
921:
917:
913:
908:
904:
900:
897:
894:
878:
875:
874:
873:
862:
859:
854:
851:
848:
845:
842:
839:
835:
831:
827:
823:
820:
815:
811:
807:
804:
801:
796:
792:
787:
783:
672:lattice points
599:Euclid's lemma
593:(i.e., modulo
589:
583:
570:
563:
510:
509:
475:
436:, of the form
428:Every pair of
426:
404:
400:
396:
391:
339:
317:
286:
283:
235:, is given by
178:
175:
172:
161:Oren Patashnik
110:
107:
55:mutually prime
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3194:
3183:
3182:Number theory
3180:
3179:
3177:
3165:
3161:
3156:
3155:
3151:
3146:
3140:
3136:
3131:
3128:
3122:
3118:
3113:
3109:
3104:
3101:
3095:
3091:
3087:
3083:
3079:
3075:
3074:
3070:
3062:
3056:
3053:
3049:
3043:
3040:
3036:
3033:David Mowry.
3030:
3027:
3023:
3017:
3014:
3009:
3005:
3001:
2997:
2990:
2987:
2982:
2978:
2974:
2970:
2963:
2960:
2957:, Theorem 332
2956:
2952:
2946:
2943:
2939:
2934:
2931:
2927:
2922:
2919:
2915:
2910:
2907:
2903:
2898:
2895:
2891:
2886:
2883:
2879:
2877:0-201-14236-8
2873:
2869:
2867:
2859:
2856:
2852:
2847:
2844:
2840:
2838:
2834:
2820:
2819:
2811:
2808:
2801:
2797:
2794:
2792:
2789:
2788:
2784:
2782:
2780:
2776:
2772:
2769:for example,
2754:
2735:
2733:
2731:
2727:
2726:Vernam cipher
2723:
2718:
2716:
2712:
2704:
2702:
2689:
2683:
2680:
2677:
2651:
2648:
2645:
2622:
2619:
2616:
2613:
2610:
2590:
2587:
2584:
2581:
2561:
2558:
2555:
2552:
2529:
2526:
2523:
2513:In all cases
2493:
2490:
2487:
2484:
2481:
2478:
2472:
2466:
2463:
2460:
2434:
2431:
2428:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2379:
2361:
2358:
2355:
2352:
2349:
2346:
2340:
2334:
2331:
2328:
2302:
2299:
2296:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2244:
2226:
2223:
2220:
2217:
2214:
2211:
2205:
2199:
2196:
2193:
2167:
2164:
2161:
2138:
2135:
2132:
2129:
2126:
2118:
2117:
2116:
2102:
2099:
2096:
2093:
2070:
2067:
2064:
2035:
2032:
2029:
2026:
2023:
2020:
2009:
1992:
1989:
1986:
1983:
1980:
1977:
1966:
1949:
1946:
1943:
1940:
1937:
1934:
1923:
1922:
1921:
1917:
1913:
1899:
1898:ternary trees
1894:
1890:
1883:
1879:
1869:
1864:
1857:
1855:
1840:
1830:
1824:
1820:
1802:
1799:
1774:
1765:
1756:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1688:
1687:
1680:
1678:
1674:
1673:Basel problem
1668:
1661:
1656:
1655:Euler product
1650:
1645:
1622:
1616:
1613:
1610:
1607:
1600:
1596:
1592:
1587:
1578:
1572:
1568:
1563:
1558:
1555:
1550:
1541:
1538:
1534:
1530:
1527:
1523:
1516:
1507:
1502:
1497:
1493:
1485:
1481:
1477:
1472:
1469:
1465:
1459:
1450:
1442:
1441:
1440:
1423:
1416:
1413:
1409:
1370:
1362:
1358:
1354:
1348:
1345:
1321:
1313:
1309:
1305:
1274:
1268:
1265:
1247:
1245:
1213:
1211:
1209:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1093:
1089:
1073:
1070:
1067:
1064:
1061:
1058:
1050:
1043:
1032:
1024:
1022:
1020:
1016:
1012:
1007:
1005:
1000:
997:gcd(4, 6) = 2
994:
990:
986:
982:
978:
974:
969:
967:
963:
959:
938:
934:
930:
927:
924:
919:
915:
911:
906:
902:
895:
892:
884:
876:
860:
857:
849:
846:
843:
833:
829:
825:
821:
818:
813:
809:
805:
802:
799:
794:
790:
785:
774:
773:
772:
768:
764:
760:
741:
736:
734:
729:
723:
718:
714:
710:
700:
694:
690:
673:
668:
664:
637:
618:
600:
588:
582:
569:
562:
547:
543:
539:
532:
528:
524:
506:
502:
498:
480:
476:
469:
463:
459:
455:
448:
444:
440:
431:
427:
421:
398:
394:
379:
375:
365:
361:
348:
340:
337:
331:
327:
318:
308:divides both
307:
303:
302:
301:
290:
284:
282:
274:
270:
256:
251:
247:
243:
238:
225:
223:
219:
215:
210:
204:
176:
173:
170:
162:
158:
154:
153:Ronald Graham
150:
149:
142:
138:
130:
126:
108:
106:
104:
98:
93:
83:
76:
65:that divides
64:
60:
56:
52:
48:
37:
33:
32:number theory
19:
3163:
3159:
3134:
3116:
3107:
3085:
3082:Wright, E.M.
3055:
3042:
3029:
3016:
2999:
2995:
2989:
2972:
2968:
2962:
2945:
2933:
2921:
2909:
2897:
2885:
2864:
2858:
2846:
2836:
2832:
2830:
2823:. Retrieved
2817:
2810:
2739:
2722:cryptography
2719:
2708:
2705:Applications
2512:
2053:
1915:
1911:
1892:
1888:
1881:
1877:
1873:
1803:
1797:
1754:
1684:
1681:
1675:, solved by
1666:
1659:
1648:
1637:
1248:
1217:
1048:
1028:
1011:infinite set
1008:
1001:
992:
988:
984:
980:
976:
972:
970:
961:
957:
885:of integers
880:
766:
737:
727:
719:
712:
708:
692:
688:
676:
638:
619:
586:
580:
567:
560:
545:
541:
537:
530:
526:
522:
511:
504:
500:
496:
461:
457:
453:
446:
442:
438:
363:
359:
341:The integer
329:
325:
306:prime number
291:
288:
272:
268:
252:
245:
241:
226:
211:
202:
157:Donald Knuth
146:
140:
136:
128:
124:
112:
99:
91:
81:
63:prime number
54:
50:
46:
29:
3078:Hardy, G.H.
3002:: 273–275,
2975:: 190–193,
2771:polynomials
1868:tree rooted
1794:approaches
1611:0.607927102
1513:prime
1456:prime
722:probability
82:is prime to
3071:References
2938:Rosen 1992
2825:10 January
2715:gear ratio
2010:Branch 3:
1967:Branch 2:
1924:Branch 1:
735:, below).
357:such that
323:such that
285:Properties
279:{2, 3, 4}
3119:, Dover,
2491:−
2356:−
2215:−
1941:−
1825:ζ
1772:∞
1769:→
1723:…
1679:in 1735.
1620:%
1614:≈
1608:≈
1597:π
1573:ζ
1556:−
1539:−
1531:−
1508:∏
1473:−
1451:∏
1349:−
1202:contains
1194:contains
1168:∩
1049:comaximal
928:…
858:−
819:−
800:−
362:≡ 1 (mod
174:⊥
3176:Category
3084:(2008),
2940:, p. 140
2890:Ore 1988
2833:mutually
2785:See also
993:pairwise
659:divides
540:≡
525:≡
456:≡
441:≡
36:integers
3166:: 66–70
2892:, p. 47
2767:
2742:
2724:, some
1853:
1810:
1671:is the
1436:
1399:
1383:
1338:
1334:
1295:
1287:
1255:
1198:, then
1126:
1104:
1098:) and (
964:if the
958:coprime
655:, then
609:, then
535:, then
493:, i.e.
416:
381:
376:in the
349:modulo
59:divisor
47:coprime
3141:
3123:
3096:
2874:
2853:, p. 6
2773:whose
2151:then
2115:then
1906:(3, 1)
1902:(2, 1)
1886:(with
1693:, let
1660:ζ
1649:ζ
1640:ζ
1206:. The
1031:ideals
769:> 1
703:(0, 0)
345:has a
159:, and
34:, two
2802:Notes
2418:then
2286:then
1891:>
1638:Here
1051:) if
1040:in a
755:2 – 1
751:2 – 1
697:in a
544:(mod
529:(mod
460:(mod
445:(mod
372:is a
334:(see
203:prime
143:) = 1
131:) = 1
3139:ISBN
3121:ISBN
3094:ISBN
2872:ISBN
2827:2022
2711:gear
2556:>
2397:<
2391:<
2265:<
2259:<
2130:>
2097:>
1866:The
1389:and
1238:and
1230:and
1222:and
1140:and
1132:and
1036:and
1029:Two
975:(or
763:base
753:and
745:and
738:Two
681:and
643:and
632:and
624:and
615:b, c
516:and
503:) =
495:lcm(
485:and
477:The
451:and
378:ring
374:unit
321:x, y
312:and
296:and
261:and
193:and
123:gcd(
117:and
45:are
41:and
3004:doi
2977:doi
2837:one
2667:or
2603:or
2380:if
2245:if
2119:if
1664:as
1662:(2)
1651:(2)
1293:is
1253:is
1246:).
1144:of
999:).
989:all
983:or
960:or
883:set
838:gcd
782:gcd
761:in
639:If
481:of
418:of
332:= 1
304:No
255:set
220:or
209:).
205:to
201:is
133:or
87:or
53:or
30:In
3178::
3164:92
3162:,
3092:,
3080:;
3000:85
2998:,
2973:78
2971:,
2829:.
2781:.
1914:,
1880:,
1801:.
1796:6/
1753:6/
1669:/6
1617:61
1395:pq
1196:BC
1021:.
1006:.
979:,
881:A
861:1.
771::
726:6/
711:,
691:,
653:bc
636:.
617:.
607:bc
566:,
527:bs
523:br
505:ab
499:,
491:ab
472:ab
360:by
338:).
330:by
328:+
326:ax
271:,
253:A
250:.
224:.
155:,
151:,
139:,
127:,
97:.
49:,
3168:.
3063:.
3050:.
3024:.
3011:.
3006::
2984:.
2979::
2755:;
2751:Z
2690:.
2687:)
2684:1
2681:,
2678:3
2675:(
2655:)
2652:1
2649:,
2646:2
2643:(
2623:.
2620:b
2617:3
2614:=
2611:a
2591:b
2588:2
2585:=
2582:a
2562:.
2559:n
2553:m
2533:)
2530:n
2527:,
2524:m
2521:(
2497:)
2494:a
2488:b
2485:2
2482:,
2479:b
2476:(
2473:=
2470:)
2467:n
2464:,
2461:m
2458:(
2438:)
2435:b
2432:,
2429:a
2426:(
2406:,
2403:b
2400:2
2394:a
2388:b
2365:)
2362:b
2359:2
2353:a
2350:,
2347:b
2344:(
2341:=
2338:)
2335:n
2332:,
2329:m
2326:(
2306:)
2303:b
2300:,
2297:a
2294:(
2274:,
2271:b
2268:3
2262:a
2256:b
2253:2
2230:)
2227:b
2224:,
2221:b
2218:2
2212:a
2209:(
2206:=
2203:)
2200:n
2197:,
2194:m
2191:(
2171:)
2168:b
2165:,
2162:a
2159:(
2139:,
2136:b
2133:3
2127:a
2103:,
2100:b
2094:a
2074:)
2071:b
2068:,
2065:a
2062:(
2039:)
2036:n
2033:,
2030:n
2027:2
2024:+
2021:m
2018:(
1996:)
1993:m
1990:,
1987:n
1984:+
1981:m
1978:2
1975:(
1953:)
1950:m
1947:,
1944:n
1938:m
1935:2
1932:(
1918:)
1916:n
1912:m
1910:(
1893:n
1889:m
1884:)
1882:n
1878:m
1876:(
1841:.
1834:)
1831:k
1828:(
1821:1
1806:k
1798:π
1791:N
1789:P
1775:,
1766:N
1755:π
1748:N
1746:P
1732:}
1729:N
1726:,
1720:,
1717:2
1714:,
1711:1
1708:{
1697:N
1695:P
1691:N
1667:π
1623:.
1601:2
1593:6
1588:=
1582:)
1579:2
1576:(
1569:1
1564:=
1559:1
1551:)
1542:2
1535:p
1528:1
1524:1
1517:p
1503:(
1498:=
1494:)
1486:2
1482:p
1478:1
1470:1
1466:(
1460:p
1424:.
1417:q
1414:p
1410:1
1391:q
1387:p
1371:.
1363:2
1359:p
1355:1
1346:1
1322:,
1314:2
1310:p
1306:1
1291:p
1275:;
1269:p
1266:1
1251:p
1240:b
1236:a
1232:b
1228:a
1224:b
1220:a
1204:C
1200:A
1192:A
1188:C
1174:;
1171:B
1165:A
1162:=
1159:B
1156:A
1146:R
1142:B
1138:A
1134:b
1130:a
1113:Z
1100:b
1096:a
1094:(
1074:.
1071:R
1068:=
1065:B
1062:+
1059:A
1045:R
1038:B
1034:A
944:}
939:n
935:a
931:,
925:,
920:2
916:a
912:,
907:1
903:a
899:{
896:=
893:S
853:)
850:b
847:,
844:a
841:(
834:n
830:=
826:)
822:1
814:b
810:n
806:,
803:1
795:a
791:n
786:(
767:n
747:b
743:a
728:π
715:)
713:b
709:a
707:(
695:)
693:b
689:a
687:(
683:b
679:a
661:c
657:a
649:a
645:b
641:a
634:b
630:a
626:b
622:a
611:p
603:p
595:a
590:2
587:b
584:1
581:b
576:a
571:2
568:b
564:1
561:b
556:a
552:b
548:)
546:a
542:s
538:r
533:)
531:a
518:b
514:a
508:.
501:b
497:a
487:b
483:a
474:.
464:)
462:b
458:m
454:x
449:)
447:a
443:k
439:x
434:x
425:.
423:a
403:Z
399:a
395:/
390:Z
370:b
366:)
364:a
355:y
351:a
343:b
316:.
314:b
310:a
298:b
294:a
275:)
273:b
269:a
267:(
263:b
259:a
248:)
246:n
244:(
242:φ
233:n
229:n
207:b
199:a
195:b
191:a
177:b
171:a
141:b
137:a
135:(
129:b
125:a
119:b
115:a
95:b
89:a
85:b
79:a
71:b
67:a
43:b
39:a
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
