2195:
3733:
3123:
1582:
2190:{\displaystyle {\begin{array}{rcl}\varphi (n)&=&\varphi (p_{1}^{k_{1}})\,\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\&=&p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\&=&p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\&=&n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{array}}}
3728:{\displaystyle {\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}}
4312:
4651:
3981:
4323:
5477:
4307:{\displaystyle {\tfrac {1}{20}},\,{\tfrac {2}{20}},\,{\tfrac {3}{20}},\,{\tfrac {4}{20}},\,{\tfrac {5}{20}},\,{\tfrac {6}{20}},\,{\tfrac {7}{20}},\,{\tfrac {8}{20}},\,{\tfrac {9}{20}},\,{\tfrac {10}{20}},\,{\tfrac {11}{20}},\,{\tfrac {12}{20}},\,{\tfrac {13}{20}},\,{\tfrac {14}{20}},\,{\tfrac {15}{20}},\,{\tfrac {16}{20}},\,{\tfrac {17}{20}},\,{\tfrac {18}{20}},\,{\tfrac {19}{20}},\,{\tfrac {20}{20}}.}
47:
4646:{\displaystyle {\tfrac {1}{20}},\,{\tfrac {1}{10}},\,{\tfrac {3}{20}},\,{\tfrac {1}{5}},\,{\tfrac {1}{4}},\,{\tfrac {3}{10}},\,{\tfrac {7}{20}},\,{\tfrac {2}{5}},\,{\tfrac {9}{20}},\,{\tfrac {1}{2}},\,{\tfrac {11}{20}},\,{\tfrac {3}{5}},\,{\tfrac {13}{20}},\,{\tfrac {7}{10}},\,{\tfrac {3}{4}},\,{\tfrac {4}{5}},\,{\tfrac {17}{20}},\,{\tfrac {9}{10}},\,{\tfrac {19}{20}},\,{\tfrac {1}{1}}}
7522:
5454:
8306:
7905:
9980:
10294:
5207:
7279:
8505:
The following property, which is part of the « folklore » (i.e., apparently unpublished as a specific result: see the introduction of this article in which it is stated as having « long been known ») has important consequences. For instance it rules out uniform distribution of the
6575:
8073:
8080:
7689:
12776:
has been translated from Latin into
English and German. The German edition includes all of Gauss's 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.
2409:
7683:
6460:
11554:
6758:
9791:
4980:
9685:
10806:
2880:
817:
7273:
7019:
2712:
10153:
2577:
1282:
9769:
2414:
In words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.
8906:
8464:
9072:
10540:
is a natural number which is not a totient number. Every odd integer exceeding 1 is trivially a nontotient. There are also infinitely many even nontotients, and indeed every positive integer has a multiple which is an even nontotient.
7517:{\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}
7140:
2986:
10399:
9377:
10657:
10091:
5449:{\displaystyle {\begin{aligned}\varphi (20)&=\mu (1)\cdot 20+\mu (2)\cdot 10+\mu (4)\cdot 5+\mu (5)\cdot 4+\mu (10)\cdot 2+\mu (20)\cdot 1\\&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}}
8301:{\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)}
7900:{\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}
6833:
6469:
7912:
9471:
604:
10483:
9257:
3118:
3051:
2262:
1511:
11837:, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (The work was presented at the Saint-Petersburg Academy on October 9, 1775).
909:
7529:
6645:
10158:
6294:
5212:
627:
11415:
As stated in the main article, if there is a single counterexample to this conjecture, there must be infinitely many counterexamples, and the smallest one has at least ten billion digits in base 10.
6349:
11769:(1763), 74–104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in:
11433:
9570:
9181:
9975:{\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,}
5200:
2421:
375:
introduced the function in 1763. However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter
6653:
5143:
9997:. By a combination of van der Corput's and Vinogradov's methods, H.-Q. Liu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) improved the error term to
6075:
4864:
9581:
5965:
3810:
10682:
2752:
358:
7147:
992:
6343:
10289:{\displaystyle {\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}}
8741:
6936:
2600:
2249:
1139:
9696:
8640:
5075:
8944:
8533:
137:
5033:
8804:
8340:
166:
8715:
8959:
8579:
8689:
8765:
8660:
8603:
8553:
7049:
933:
2891:
11673:
10955:, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of numbers; if the sum equals
10313:
9296:
10554:
12861:
Dickson, Leonard Eugene, "History Of The Theory Of
Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
10003:
6570:{\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}
13305:
8068:{\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)}
8768:
6764:
224:
are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since
9398:
529:
11022:, and only five are known: 3, 5, 17, 257, and 65537. Fermat and Gauss knew of these. Nobody has been able to prove whether there are any more.
10414:
9202:
10951:
A perfect totient number is an integer that is equal to the sum of its iterated totients. That is, we apply the totient function to a number
11061:
3056:
2404:{\displaystyle \varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.}
11366:
10930:
2994:
13323:
7678:{\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}
1421:
822:
11641:
11048:
6111:
5470:
315:
308:
13056:
6581:
12030:
6455:{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}
6241:
17:
11549:{\displaystyle {\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}}
13174:
13069:
12751:
12478:
12307:
389:, and which have no common divisor with it". This definition varies from the current definition for the totient function at
11801:(... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), which is the phi function, φ(N).
9525:
9133:
6092:
9778:. Ribenboim says "The method of proof is interesting, in that the inequality is shown first under the assumption that the
6753:{\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}
12958:
Untersuchungen uber hohere
Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition)
11629:
4975:{\displaystyle \varphi (n)=\sum _{d\mid n}\mu \left(d\right)\cdot {\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}},}
9680:{\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}
5148:
13473:
13360:
13230:
13196:
13148:
13030:
12997:
12965:
12944:
12845:
12815:
10801:{\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}
5968:
2875:{\displaystyle \varphi (n)={\mathcal {F}}\{\mathbf {x} \}=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.}
1408:
6026:
5093:
812:{\displaystyle \varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),}
13140:
5923:
3761:
8747:
This is an elementary consequence of the fact that the sum of the reciprocals of the primes congruent to 1 modulo
7268:{\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1}
11624:
12290:
Ribenboim (1989). "How are the Prime
Numbers Distributed? §I.C The Distribution of Values of Euler's Function".
328:
938:
10118:
13284:
11007:
is a power of an odd prime number the formula for the totient says its totient can be a power of two only if
9481:
8315:
7014:{\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}
6300:
2707:{\displaystyle {\mathcal {F}}\{\mathbf {x} \}=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}
2204:
8329:
6210:. The owner of the private key knows the factorization, since an RSA private key is constructed by choosing
13393:
13291:
455:
8720:
2572:{\displaystyle \varphi (20)=\varphi (2^{2}5^{1})=2^{2-1}(2{-}1)\,5^{1-1}(5{-}1)=2\cdot 1\cdot 1\cdot 4=8.}
1587:
1277:{\displaystyle \varphi \left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\tfrac {1}{p}}\right).}
13468:
13279:
12772:
11249:
10983:
3950:
413:
13314:
11654:
10912:
9990:
9764:{\displaystyle \varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.}
6085:
3735:
Unlike the Euler product and the divisor sum formula, this one does not require knowing the factors of
2587:
2210:
13274:
3824:
618:
11936:
1111:
6496:
3949:, the formula follows. Equivalently, the formula can be derived by the same argument applied to the
13222:
12397:
8608:
5038:
8914:
8901:{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}
8459:{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),}
4832:
fractions with denominator 5, etc. Thus the set of twenty fractions is split into subsets of size
13488:
13447:
13442:
13097:
13061:
11941:
11634:
8509:
4994:
3958:
2591:
265:
188:
113:
5000:
4683:. The fractions with 20 as denominator are those with numerators relatively prime to 20, namely
13483:
10946:
10908:
10304:
9067:{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}
6165:
435:
11921:
142:
13437:
13353:
12875:
11612:
10977:
8795:
8694:
7039:
7031:
6836:
6227:
13320:
13214:
8558:
12987:
12953:
12928:
12912:
11833:
9509:
6107:
304:
13240:
13206:
13158:
13040:
13007:
12920:
12855:
12719:
12669:
12496:
12428:
12038:
10672:
If counted accordingly to multiplicity, the number of totient numbers up to a given limit
8665:
7135:{\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}
8:
13411:
13215:
12936:
11786:
11607:
11578:
912:
12121:
Pollack, P. (2023), "Two problems on the distribution of
Carmichael's lambda function",
4855:
2203:
An alternative proof that does not require the multiplicative property instead uses the
12900:
12807:
12456:
12130:
12053:
11424:
9779:
9775:
8750:
8645:
8588:
8538:
6003:
918:
361:
319:
4990:
3128:
2981:{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.}
13333:
13226:
13192:
13170:
13144:
13121:
13101:
13065:
13026:
12993:
12961:
12940:
12892:
12841:
12811:
12801:
12793:
12747:
12707:
12657:
12484:
12474:
12416:
12303:
10394:{\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}}
9372:{\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,}
13478:
13346:
13236:
13202:
13154:
13036:
13003:
12916:
12884:
12851:
12715:
12665:
12492:
12466:
12424:
12406:
12295:
12258:
12140:
12101:
12068:
12034:
11617:
10652:{\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}
10300:
9274:
8780:
8471:
6125:
6017:
1561:
corresponds to the empty product.) Repeatedly using the multiplicative property of
99:
11306:
exists, it must be odd, square-free, and divisible by at least seven primes (i.e.
10086:{\displaystyle O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}
13327:
13309:
13188:
13132:
13022:
12908:
12829:
12797:
12246:
11770:
11072:
9090:
Both of these are proved by elementary series manipulations and the formulae for
6121:
12470:
12299:
13014:
12982:
12575:
12022:
11895:
11868:
are seen in the literature. These are two forms of the lower-case Greek letter
10097:
9986:
8950:
5090:. This formula may also be derived from the product formula by multiplying out
372:
323:
39:
12626:
Cohen, Graeme L.; Hagis, Peter Jr. (1980). "On the number of prime factors of
12106:
12089:
11758:
11033:
is a product of distinct Fermat primes and any power of 2. The first few such
6828:{\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}
13462:
13117:
12974:
12896:
12837:
12711:
12661:
12488:
12420:
12263:
11649:
9994:
3968:
The formula can also be derived from elementary arithmetic. For example, let
3739:. However, it does involve the calculation of the greatest common divisor of
87:
12072:
11062:
Prime number theorem § Prime number theorem for arithmetic progressions
9262:
These two formulae can be proved by using little more than the formulae for
13432:
13051:
12978:
12411:
12392:
11274:
11041:
2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (sequence
11019:
11018:
is a power of 2. The primes that are one more than a power of 2 are called
9466:{\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.}
3842:
1539:
610:
599:{\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),}
489:
13249:
13183:
Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006),
10104:
stands for a quantity that is bounded by a constant times the function of
13047:
12744:
Equivalents of the
Riemann Hypothesis, Volume One: Arithmetic Equivalents
10478:{\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}}
6203:
5909:
9252:{\displaystyle {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}
13427:
10536:
417:, although Gauss did not use parentheses around the argument and wrote
12904:
12145:
12029:. Mathematische Forschungsberichte (in German). Vol. 16. Berlin:
12825:
11592:
10405:
10119:
the probability of two randomly chosen numbers being relatively prime
1093:
13292:
Euler's Phi
Function and the Chinese Remainder Theorem — proof that
11765:(New Memoirs of the Saint-Petersburg Imperial Academy of Sciences),
3113:{\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}}
13338:
13315:
Euler's totient function calculator in JavaScript — up to 20 digits
13250:"The Fourier transform of functions of the greatest common divisor"
12888:
12836:, MIT Press Series in the Foundations of Computing, Cambridge, MA:
12135:
11055:
10915:. Indeed, each multiplicity that occurs, does so infinitely often.
3904:
3046:{\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}}
207:
12461:
11912:
J. J. Sylvester (1879) "On certain ternary cubic-form equations",
2251:, excluding the sets of integers divisible by the prime divisors.
484:. It counts the number of positive integers less than or equal to
13105:
11216:
The security of an RSA system would be compromised if the number
3975:
and consider the positive fractions up to 1 with denominator 20:
1506:{\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},}
1061:
13125:
11763:
9290:
In fact, during the proof of the second formula, the inequality
6230:
we have the guarantee that no one else knows the factorization.
904:{\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}
11077:
Setting up an RSA system involves choosing large prime numbers
11785:, series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915),
10096:(this is currently the best known estimate of this type). The
5476:
13021:, Problem Books in Mathematics (3rd ed.), New York, NY:
12294:(2nd ed.). New York: Springer-Verlag. pp. 172–175.
8500:
6640:{\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}
408:
10408:
in the positive real numbers. They also proved that the set
9989:, its proof exploiting estimates on exponential sums due to
997:
The proof of these formulae depends on two important facts.
12604:
Gauss, DA, art. 366. This list is the last sentence in the
11834:
Speculationes circa quasdam insignes proprietates numerorum
11043:
6563:
6289:{\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}
5465:
46:
12247:"Approximate formulas for some functions of prime numbers"
12222:, thm.7) and Mertens' third theorem is all that is needed.
10907:
solutions; this result had previously been conjectured by
3841:
is also equal to the number of possible generators of the
1117:
11869:
10992:-gon can be constructed with straightedge and compass if
107:
32:
13321:
The Euler
Totient, the Möbius, and the Divisor Functions
13182:
12933:
12834:
Algorithmic Number Theory (Vol I: Efficient Algorithms)
12027:
Weylsche Exponentialsummen in der neueren Zahlentheorie
11920: : 357-393; Sylvester coins the term "totient" on
11137:(the "encryption key") are released to the public, and
8767:
diverges, which itself is a corollary of the proof of
7320:
7224:
6767:
5151:
5096:
4632:
4616:
4600:
4584:
4568:
4552:
4536:
4520:
4504:
4488:
4472:
4456:
4440:
4424:
4408:
4392:
4376:
4360:
4344:
4328:
4290:
4274:
4258:
4242:
4226:
4210:
4194:
4178:
4162:
4146:
4130:
4114:
4098:
4082:
4066:
4050:
4034:
4018:
4002:
3986:
3747:, which suffices to provide the factorization anyway.
3664:
3625:
3586:
3544:
3472:
3430:
3388:
3349:
3313:
3263:
3219:
3175:
3087:
3067:
3020:
3005:
2956:
2384:
2369:
2345:
2320:
1255:
11436:
10685:
10557:
10417:
10316:
10156:
10006:
9794:
9699:
9584:
9565:{\displaystyle \lim \inf {\frac {\varphi (n)}{n}}=0.}
9528:
9401:
9299:
9205:
9176:{\displaystyle \lim \sup {\frac {\varphi (n)}{n}}=1,}
9136:
8962:
8917:
8807:
8753:
8723:
8697:
8668:
8648:
8611:
8591:
8561:
8541:
8512:
8343:
8083:
7915:
7692:
7532:
7282:
7150:
7052:
6939:
6656:
6584:
6472:
6352:
6303:
6244:
6214:
as the product of two (randomly chosen) large primes
6146:
is the (public) encryption exponent, is the function
6029:
5926:
5210:
5041:
5003:
4867:
4326:
3984:
3764:
3126:
3059:
2997:
2894:
2755:
2603:
2424:
2265:
2213:
2200:
This gives both versions of Euler's product formula.
1585:
1424:
1142:
941:
921:
825:
630:
532:
499:
396:
but is otherwise the same. The now-standard notation
367:
331:
145:
116:
12973:
12447:
Ford, Kevin (1998). "The distribution of totients".
11029:-gon has a straightedge-and-compass construction if
10500:
is a value of Euler's totient function: that is, an
13112:Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970),
10108:inside the parentheses (which is small compared to
1402:
1000:
94:counts the positive integers up to a given integer
12865:Ford, Kevin (1999), "The number of solutions of φ(
12087:
11933:
11809:
11807:
11761:" (An arithmetic theorem proved by a new method),
11548:
10800:
10651:
10544:The number of totient numbers up to a given limit
10477:
10393:
10288:
10085:
9974:
9782:is true, secondly under the contrary assumption."
9763:
9679:
9564:
9465:
9371:
9251:
9175:
9066:
8938:
8900:
8759:
8735:
8709:
8683:
8654:
8634:
8597:
8573:
8547:
8527:
8458:
8300:
8067:
7899:
7677:
7516:
7267:
7134:
7013:
6827:
6752:
6639:
6569:
6454:
6337:
6288:
6069:
5959:
5448:
5194:
5137:
5069:
5027:
4974:
4645:
4306:
3804:
3727:
3112:
3045:
2980:
2874:
2706:
2571:
2403:
2243:
2189:
1505:
1276:
986:
927:
903:
811:
598:
352:
160:
131:
13254:Electronic Journal of Combinatorial Number Theory
13111:
11732:
11708:
10725:
10688:
9109:In the words of Hardy & Wright, the order of
8401:
8400:
8399:
8398:
7216:
7215:
5195:{\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}
27:Number of integers coprime to and not exceeding n
13460:
12792:
12322:Sándor, Mitrinović & Crstici (2006) pp.24–25
12244:
11793:as the number of integers that are smaller than
11231:could be efficiently computed without factoring
11056:Prime number theorem for arithmetic progressions
10228:
10225:
10164:
10161:
9532:
9529:
9405:
9402:
9140:
9137:
8402:
8352:
4849:dividing 20. A similar argument applies for any
3288:
3238:
3194:
3150:
2931:
2822:
442:for this function, so it is also referred to as
12245:Rosser, J. Barkley; Schoenfeld, Lowell (1962).
11804:
11759:Theoremata arithmetica nova methodo demonstrata
10911:, and it had been obtained as a consequence of
10534:is the number of solutions to this equation. A
5138:{\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}
1294:is a prime number, the only possible values of
172:. In other words, it is the number of integers
12960:, translated by Maser, H., New York: Chelsea,
12746:(First ed.). Cambridge University Press.
11192:. Euler's Theorem can be used to show that if
10142:
8769:Dirichlet's theorem on arithmetic progressions
6124:is based on this theorem: it implies that the
6070:{\displaystyle a^{\varphi (n)}\equiv 1\mod n.}
13354:
13212:
12992:(2nd ed.), Reading, MA: Addison-Wesley,
12935:, translated by Clarke, Arthur A., New York:
11900:A History Of Mathematical Notations Volume II
11375:with the property that for all other numbers
10608:
10583:
7037:(the product of all distinct primes dividing
5960:{\displaystyle \varphi (n)\geq {\sqrt {n/2}}}
3805:{\displaystyle \sum _{d\mid n}\varphi (d)=n,}
12360:Sándor, Mitrinović & Crstici (2006) p.16
11779:Leonhardi Euleri Commentationes Arithmeticae
10720:
10693:
6164:, the (private) decryption exponent, is the
5916:other than one, and attained if and only if
4656:These twenty fractions are all the positive
3815:where the sum is over all positive divisors
2786:
2778:
2619:
2611:
2238:
2214:
13046:
12824:
12442:
12440:
12438:
12331:
12231:
12219:
12206:
12194:
12182:
12170:
12158:
11995:
5920:is a prime number. A simple lower bound is
2418:The alternative formula uses only integers:
1060:be the sets of positive integers which are
31:"φ(n)" redirects here. For other uses, see
13361:
13347:
13213:Sándor, Jozsef; Crstici, Borislav (2004).
13078:Liu, H.-Q. (2016), "On Euler's function",
12683:Hagis, Peter Jr. (1988). "On the equation
12625:
12017:
12015:
12013:
11630:Generalizations of Fermat's little theorem
11360:
11335:. Further, Hagis showed that if 3 divides
10940:
10448:
10447:
10364:
10363:
9616:
9519:goes to infinity, this formula shows that
8501:Divisibility by any fixed positive integer
6258:
6254:
5473:) are shown in the table and graph below:
518:
353:{\displaystyle \mathbb {Z} /n\mathbb {Z} }
206:of this form are sometimes referred to as
13131:
12526:
12524:
12460:
12410:
12368:
12366:
12289:
12285:
12283:
12262:
12144:
12134:
12105:
11277:asked if there are any composite numbers
8135:
7967:
6060:
6059:
4858:applied to the divisor sum formula gives
4630:
4614:
4598:
4582:
4566:
4550:
4534:
4518:
4502:
4486:
4470:
4454:
4438:
4422:
4406:
4390:
4374:
4358:
4342:
4288:
4272:
4256:
4240:
4224:
4208:
4192:
4176:
4160:
4144:
4128:
4112:
4096:
4080:
4064:
4048:
4032:
4016:
4000:
2505:
2334:
2309:
1640:
987:{\displaystyle p_{1},p_{2},\ldots ,p_{r}}
698:
504:There are several formulae for computing
346:
333:
13164:
13094:Elementary Introduction to Number Theory
13057:An Introduction to the Theory of Numbers
12741:
12435:
12356:
12354:
12344:
12342:
12340:
11991:
11989:
11745:
11642:Multiplicative group of integers modulo
11367:Carmichael's totient function conjecture
11141:(the "decryption key") is kept private.
10931:Carmichael's totient function conjecture
10307:strengthened this, proving that the set
9508:Proving this does not quite require the
6112:multiplicative group of integers modulo
5475:
4676:≤ 1 whose denominators are the divisors
3755:The property established by Gauss, that
385:for "the multitude of numbers less than
309:multiplicative group of integers modulo
253:the only integer in the range from 1 to
45:
13247:
13221:. Dordrecht: Kluwer Academic. pp.
13167:The early mathematics of Leonhard Euler
12384:
12316:
12120:
12083:
12081:
12054:"The scientific work of Arnold Walfisz"
12051:
12031:VEB Deutscher Verlag der Wissenschaften
12021:
12010:
11954:
11409:
11317:). In 1980 Cohen and Hagis proved that
11066:
10933:is the statement that there is no such
8911:where the left-hand side converges for
8774:
6338:{\displaystyle m\mid \varphi (a^{m}-1)}
1118:Value of phi for a prime power argument
609:where the product is over the distinct
106:. It is written using the Greek letter
61:. The points on the top line represent
14:
13461:
12726:
12570:satisfies certain conditions then the
12521:
12363:
12280:
11902:. Open Court Publishing Company. §409.
11894:
11427:is true if and only if the inequality
11243:
10117:This result can be used to prove that
8535:in the arithmetic progressions modulo
5967:, which is rather loose: in fact, the
3823:, can be proven in several ways. (See
13342:
12952:
12927:
12682:
12557:Gauss, DA. The 7th § is arts. 336–366
12542:
12533:
12512:
12503:
12390:
12375:
12351:
12337:
11986:
11418:
11144:A message, represented by an integer
10846:It is known that the multiplicity of
6226:is publicly disclosed, and given the
6194:without knowing the factorization of
3743:and every positive integer less than
13368:
13137:The New Book of Prime Number Records
13091:
12864:
12446:
12078:
11720:
11696:
11371:This states that there is no number
11238:
11220:could be efficiently factored or if
10871:
8736:{\displaystyle x\rightarrow \infty }
6198:is thus the difficulty of computing
2581:
1393:numbers are all relatively prime to
360:). It is also used for defining the
13077:
13013:
12990:: a foundation for computer science
11302:In 1933 he proved that if any such
9774:The second inequality was shown by
8323:
5897:In the graph at right the top line
4825:fractions with denominator 10, and
2911:
2802:
2635:
24:
13019:Unsolved Problems in Number Theory
12803:Handbook of Mathematical Functions
12007:Dineva (in external refs), prop. 1
10889:: that is, for which the equation
10491:
10276:
9966:
9243:
8979:
8918:
8824:
8730:
7156:
6228:difficulty to factor large numbers
5997:
2773:
2606:
500:Computing Euler's totient function
368:History, terminology, and notation
25:
13500:
13334:Summing Up The Euler Phi Function
13267:
13080:Proc. Roy. Soc. Edinburgh Sect. A
12574:-gon can be constructed. In 1837
12548:Sándor & Crstici (2004) p.228
12539:Sándor & Crstici (2004) p.229
12381:Sándor & Crstici (2004) p.230
10866:
8585:For every fixed positive integer
6233:
6206:which can be solved by factoring
2885:The real part of this formula is
2244:{\displaystyle \{1,2,\ldots ,n\}}
1409:fundamental theorem of arithmetic
12784:are of the form Gauss, DA, art.
12292:The Book of Prime Number Records
10504:for which there is at least one
10488:is dense in the interval (0,1).
5971:of the graph is proportional to
4818:fractions. Similarly, there are
2782:
2615:
1403:Proof of Euler's product formula
1377:such multiples not greater than
1001:Phi is a multiplicative function
458:is a generalization of Euler's.
12735:
12676:
12619:
12610:
12598:
12589:
12586:must satisfy Gauss's conditions
12560:
12551:
12451:. Developments in Mathematics.
12325:
12271:
12237:
12225:
12212:
12200:
12188:
12176:
12164:
12152:
12114:
12090:"On an error term of Landau II"
12088:Sitaramachandrarao, R. (1985).
12045:
12001:
11977:
11968:
11959:
11948:
11927:
11914:American Journal of Mathematics
11906:
11888:
11875:
11840:
11825:
11655:Totient summatory function (𝛷)
10966:
10215:
9954:
9785:For the average order, we have
9749:
9662:
8794:may be written in terms of the
8334:In 1965 P. Kesava Menon proved
7250:
6419:
6055:
5463:The first 100 values (sequence
12277:Bach & Shallit, thm. 8.8.7
11974:Gauss, DA art. 39, arts. 52-54
11816:
11774:
11751:
11738:
11733:Pettofrezzo & Byrkit (1970
11726:
11714:
11709:Pettofrezzo & Byrkit (1970
11702:
11690:
11666:
11529:
11502:
11452:
11446:
10874:proved that for every integer
10795:
10789:
10771:
10765:
10757:
10751:
10745:
10739:
10711:
10705:
10638:
10613:
10603:
10597:
10435:
10429:
10354:
10348:
10340:
10328:
10263:
10257:
10249:
10237:
10199:
10193:
10185:
10173:
10064:
10045:
10031:
10018:
9963:
9935:
9916:
9902:
9889:
9840:
9834:
9819:
9813:
9804:
9798:
9709:
9703:
9594:
9588:
9547:
9541:
9420:
9414:
9344:
9338:
9332:
9326:
9240:
9218:
9212:
9155:
9149:
9104:
9052:
9039:
8996:
8990:
8927:
8921:
8892:
8886:
8878:
8866:
8841:
8835:
8727:
8678:
8672:
8629:
8623:
8616:
8522:
8516:
8450:
8444:
8438:
8432:
8423:
8405:
8367:
8355:
8274:
8261:
8145:
8139:
8120:
8114:
8046:
8033:
7977:
7971:
7952:
7946:
7878:
7859:
7845:
7832:
7771:
7765:
7726:
7720:
7656:
7637:
7623:
7610:
7563:
7557:
7495:
7476:
7462:
7449:
7372:
7366:
7313:
7307:
7247:
7241:
7202:
7190:
7126:
7120:
7102:
7096:
7088:
7082:
7005:
6999:
6988:
6985:
6979:
6970:
6952:
6946:
6810:
6798:
6786:
6774:
6747:
6741:
6732:
6726:
6717:
6714:
6702:
6693:
6684:
6681:
6669:
6660:
6634:
6628:
6542:
6536:
6511:
6505:
6485:
6476:
6449:
6437:
6413:
6407:
6392:
6386:
6380:
6374:
6365:
6356:
6332:
6313:
6283:
6277:
6268:
6262:
6255:
6183:. The difficulty of computing
6044:
6038:
5936:
5930:
5458:
5348:
5342:
5327:
5321:
5306:
5300:
5285:
5279:
5264:
5258:
5243:
5237:
5224:
5218:
5180:
5174:
5132:
5113:
5058:
5045:
5013:
5007:
4960:
4954:
4877:
4871:
3790:
3784:
3750:
3705:
3699:
3687:
3660:
3648:
3621:
3609:
3579:
3567:
3537:
3516:
3507:
3495:
3465:
3453:
3423:
3411:
3384:
3372:
3345:
3303:
3291:
3253:
3241:
3209:
3197:
3165:
3153:
3140:
3134:
2946:
2934:
2904:
2898:
2837:
2825:
2795:
2789:
2765:
2759:
2628:
2622:
2536:
2522:
2502:
2488:
2466:
2443:
2434:
2428:
2356:
2335:
2331:
2310:
2300:
2284:
2275:
2269:
1703:
1678:
1669:
1644:
1637:
1612:
1599:
1593:
1227:
1215:
803:
782:
748:
727:
695:
674:
640:
634:
542:
536:
268:, meaning that if two numbers
264:Euler's totient function is a
217:For example, the totatives of
155:
149:
126:
120:
13:
1:
12764:
12218:In fact Chebyshev's theorem (
11822:Graham et al. p. 133 note 111
11789:. On page 531, Euler defines
11177:It is decrypted by computing
10963:is a perfect totient number.
8635:{\displaystyle q|\varphi (n)}
8493:is the number of divisors of
5480:Graph of the first 100 values
5070:{\displaystyle \mu (p^{k})=0}
3827:for notational conventions.)
2205:inclusion-exclusion principle
1418:there is a unique expression
994:are distinct prime numbers).
624:An equivalent formulation is
50:The first thousand values of
13217:Handbook of number theory II
12582:-gon is constructible, then
12578:proved the converse, if the
11783:Leonhardi Euleri Opera Omnia
11159:, is encrypted by computing
10988:Gauss proves that a regular
10971:
8939:{\displaystyle \Re (s)>2}
6870:distinct odd prime factors,
6761:Compare this to the formula
4317:Put them into lowest terms:
3951:multiplicative group of the
202:is equal to 1. The integers
76:is a prime number, which is
7:
13414:(reduced totient function)
13280:Encyclopedia of Mathematics
13185:Handbook of number theory I
13096:(2nd ed.), Lexington:
12773:Disquisitiones Arithmeticae
12471:10.1007/978-1-4757-4507-8_8
12300:10.1007/978-1-4684-0507-1_5
11883:Disquisitiones Arithmeticae
11625:Duffin–Schaeffer conjecture
11601:
10982:In the last section of the
10922:is known with multiplicity
10143:Ratio of consecutive values
8528:{\displaystyle \varphi (n)}
1321:, and the only way to have
423:. Thus, it is often called
414:Disquisitiones Arithmeticae
276:are relatively prime, then
132:{\displaystyle \varphi (n)}
10:
13505:
13248:Schramm, Wolfgang (2008),
13165:Sandifer, Charles (2007),
13139:(3rd ed.), New York:
13060:(Fifth ed.), Oxford:
11674:"Euler's totient function"
11613:Dedekind psi function (𝜓)
11364:
11247:
11110:, and finding two numbers
11070:
11059:
10975:
10944:
10881:there is a totient number
10147:In 1950 Somayajulu proved
9190:goes to infinity, for all
8327:
6001:
5028:{\displaystyle \mu (p)=-1}
3927:is generated by precisely
3830:One proof is to note that
2588:discrete Fourier transform
2254:
303:. This function gives the
29:
13394:Jordan's totient function
13374:
13332:Plytage, Loomis, Polhill
13114:Elements of Number Theory
12107:10.1216/RMJ-1985-15-2-579
11983:Graham et al. pp. 134-135
11937:Oxford English Dictionary
10856:infinitely often for any
9752:for infinitely many
8316:Euler–Mascheroni constant
3892:. Since every element of
3884:is a generator for every
3855: ; specifically, if
1112:Chinese remainder theorem
226:gcd(9, 3) = gcd(9, 6) = 3
168:, and may also be called
13474:Multiplicative functions
13379:Euler's totient function
13092:Long, Calvin T. (1972),
12742:Broughan, Kevin (2017).
12518:Sándor et al (2006) p.21
12509:Sándor et al (2006) p.22
12398:Journal of Number Theory
11797:and relatively prime to
11660:
11250:Lehmer's totient problem
4811:; by definition this is
1076:, respectively, so that
444:Euler's totient function
161:{\displaystyle \phi (n)}
92:Euler's totient function
38:Not to be confused with
13448:Sparsely totient number
13443:Highly cototient number
13098:D. C. Heath and Company
13062:Oxford University Press
12821:. See paragraph 24.3.2.
12391:Zhang, Mingzhi (1993).
12332:Hardy & Wright 1979
12232:Hardy & Wright 1979
12220:Hardy & Wright 1979
12207:Hardy & Wright 1979
12195:Hardy & Wright 1979
12183:Hardy & Wright 1979
12171:Hardy & Wright 1979
12159:Hardy & Wright 1979
12073:10.4064/aa-10-3-227-237
11996:Hardy & Wright 1979
11942:Oxford University Press
11635:Highly composite number
11608:Carmichael function (λ)
11361:Carmichael's conjecture
10941:Perfect totient numbers
10913:Schinzel's hypothesis H
9575:In fact, more is true.
8953:generating function is
8710:{\displaystyle n\leq x}
6202:: this is known as the
6086:Fermat's little theorem
6080:The special case where
4995:multiplicative function
1383:. Therefore, the other
1092:, etc. Then there is a
519:Euler's product formula
488:that have at least one
379:to denote it: he wrote
266:multiplicative function
189:greatest common divisor
12412:10.1006/jnth.1993.1014
12264:10.1215/ijm/1255631807
12094:Rocky Mountain J. Math
11550:
10947:Perfect totient number
10802:
10653:
10479:
10395:
10290:
10087:
9976:
9765:
9681:
9566:
9467:
9373:
9253:
9177:
9068:
8983:
8940:
8902:
8828:
8761:
8737:
8711:
8685:
8662:, meaning for all but
8656:
8636:
8599:
8575:
8574:{\displaystyle q>1}
8549:
8529:
8460:
8302:
8104:
8069:
7936:
7901:
7758:
7713:
7679:
7553:
7518:
7362:
7303:
7269:
7136:
7015:
6829:
6754:
6641:
6571:
6456:
6339:
6290:
6166:multiplicative inverse
6071:
5961:
5481:
5450:
5196:
5139:
5071:
5029:
4976:
4647:
4308:
3806:
3729:
3114:
3047:
2982:
2930:
2876:
2821:
2708:
2654:
2594:, evaluated at 1. Let
2573:
2405:
2245:
2191:
1507:
1278:
988:
929:
905:
813:
600:
354:
239:. As another example,
162:
133:
83:
18:Euler totient function
13438:Highly totient number
12954:Gauss, Carl Friedrich
12929:Gauss, Carl Friedrich
12876:Annals of Mathematics
12616:Ribenboim, pp. 36–37.
11551:
11011:is a first power and
10978:Constructible polygon
10811:where the error term
10803:
10654:
10480:
10396:
10291:
10088:
9977:
9766:
9682:
9567:
9468:
9374:
9254:
9178:
9069:
8963:
8941:
8903:
8808:
8796:Riemann zeta function
8762:
8738:
8712:
8686:
8657:
8642:holds for almost all
8637:
8600:
8576:
8550:
8530:
8461:
8303:
8084:
8070:
7916:
7902:
7738:
7693:
7680:
7533:
7519:
7342:
7283:
7270:
7137:
7016:
6837:least common multiple
6830:
6755:
6642:
6572:
6457:
6340:
6291:
6084:is prime is known as
6072:
5962:
5479:
5451:
5197:
5140:
5072:
5030:
4977:
4648:
4309:
3825:Arithmetical function
3807:
3730:
3115:
3048:
2983:
2910:
2877:
2801:
2709:
2634:
2574:
2406:
2246:
2192:
1508:
1279:
989:
930:
906:
814:
619:Arithmetical function
617:. (For notation, see
601:
362:RSA encryption system
355:
163:
134:
49:
13116:, Englewood Cliffs:
12988:Concrete Mathematics
12052:Lomadse, G. (1964),
11618:Divisor function (σ)
11593:product of the first
11434:
11067:The RSA cryptosystem
11003:is a power of 2. If
10815:is of order at most
10683:
10555:
10530:of a totient number
10415:
10314:
10154:
10004:
9792:
9697:
9582:
9526:
9510:prime number theorem
9399:
9297:
9275:divisor sum function
9203:
9134:
9077:which converges for
8960:
8915:
8805:
8775:Generating functions
8751:
8721:
8695:
8684:{\displaystyle o(x)}
8666:
8646:
8609:
8589:
8559:
8539:
8510:
8341:
8081:
7913:
7690:
7530:
7280:
7148:
7050:
6937:
6765:
6654:
6582:
6470:
6350:
6301:
6242:
6027:
6008:This states that if
5924:
5208:
5149:
5094:
5039:
5001:
4865:
4681:= 1, 2, 4, 5, 10, 20
4324:
3982:
3907:, and each subgroup
3762:
3124:
3057:
2995:
2892:
2753:
2601:
2422:
2263:
2211:
1583:
1565:and the formula for
1422:
1140:
939:
919:
823:
628:
530:
425:Euler's phi function
329:
170:Euler's phi function
143:
114:
13412:Carmichael function
11244:Lehmer's conjecture
10918:However, no number
9120:is "always 'nearly
5505:
3903:generates a cyclic
2991:For example, using
2586:The totient is the
2207:applied to the set
1962:
1937:
1915:
1850:
1792:
1737:
1702:
1668:
1636:
1499:
1474:
1452:
1005:This means that if
913:prime factorization
900:
875:
853:
781:
726:
673:
13469:Modular arithmetic
13326:2021-01-16 at the
13308:2021-02-28 at the
13275:"Totient function"
12808:Dover Publications
12780:References to the
12595:Gauss, DA, art 366
11546:
11425:Riemann hypothesis
11419:Riemann hypothesis
11299:. None are known.
10798:
10649:
10475:
10391:
10286:
10284:
10083:
9972:
9780:Riemann hypothesis
9776:Jean-Louis Nicolas
9761:
9677:
9562:
9463:
9369:
9249:
9173:
9064:
8936:
8898:
8757:
8733:
8707:
8681:
8652:
8632:
8595:
8571:
8545:
8525:
8456:
8397:
8298:
8203:
8065:
7897:
7675:
7514:
7329:
7265:
7233:
7214:
7132:
7068:
7011:
6825:
6750:
6637:
6567:
6562:
6452:
6335:
6286:
6095:and the fact that
6093:Lagrange's theorem
6091:This follows from
6067:
5957:
5486:
5482:
5446:
5444:
5192:
5167:
5135:
5112:
5067:
5025:
4972:
4947:
4898:
4643:
4641:
4625:
4609:
4593:
4577:
4561:
4545:
4529:
4513:
4497:
4481:
4465:
4449:
4433:
4417:
4401:
4385:
4369:
4353:
4337:
4304:
4299:
4283:
4267:
4251:
4235:
4219:
4203:
4187:
4171:
4155:
4139:
4123:
4107:
4091:
4075:
4059:
4043:
4027:
4011:
3995:
3802:
3780:
3725:
3723:
3685:
3646:
3607:
3565:
3493:
3451:
3409:
3370:
3327:
3277:
3233:
3189:
3110:
3108:
3081:
3043:
3041:
3014:
2978:
2973:
2872:
2704:
2569:
2401:
2393:
2378:
2354:
2329:
2241:
2187:
2185:
1941:
1916:
1894:
1829:
1771:
1716:
1681:
1647:
1615:
1503:
1478:
1453:
1431:
1274:
1264:
984:
925:
901:
879:
854:
832:
809:
754:
699:
646:
596:
566:
350:
158:
129:
84:
13456:
13455:
13303:is multiplicative
13191:, pp. 9–36,
13176:978-0-88385-559-1
13071:978-0-19-853171-5
12753:978-1-107-19704-6
12700:Nieuw Arch. Wiskd
12650:Nieuw Arch. Wiskd
12480:978-1-4419-5058-1
12309:978-1-4684-0509-5
12185:, intro to § 18.4
12146:10.1112/mtk.12222
11965:Gauss, DA, art 39
11544:
11543:
11456:
11239:Unsolved problems
10909:Wacław Sierpiński
10839:for any positive
10775:
10574:
10442:
10358:
10267:
10219:
10203:
10075:
10042:
9958:
9946:
9913:
9873:
9753:
9747:
9666:
9660:
9657:
9554:
9427:
9358:
9315:
9238:
9162:
9062:
9028:
8896:
8855:
8760:{\displaystyle q}
8655:{\displaystyle n}
8598:{\displaystyle q}
8548:{\displaystyle q}
8394:
8344:
8292:
8285:
8241:
8200:
8189:
8164:
8124:
8057:
8020:
7996:
7956:
7889:
7856:
7816:
7792:
7778:
7733:
7667:
7634:
7584:
7524: ( cited in)
7506:
7473:
7423:
7388:
7328:
7254:
7232:
7212:
7151:
7130:
7106:
7053:
7009:
6959:
6558:
6550:
6527:
6519:
6423:
6417:
5955:
5893:
5892:
5187:
5152:
5130:
5097:
4967:
4932:
4924:
4883:
4640:
4624:
4608:
4592:
4576:
4560:
4544:
4528:
4512:
4496:
4480:
4464:
4448:
4432:
4416:
4400:
4384:
4368:
4352:
4336:
4298:
4282:
4266:
4250:
4234:
4218:
4202:
4186:
4170:
4154:
4138:
4122:
4106:
4090:
4074:
4058:
4042:
4026:
4010:
3994:
3963:th roots of unity
3955:th roots of unity
3765:
3684:
3672:
3645:
3633:
3606:
3594:
3564:
3552:
3530:
3492:
3480:
3450:
3438:
3408:
3396:
3369:
3357:
3326:
3276:
3232:
3188:
3107:
3095:
3080:
3040:
3028:
3013:
2972:
2865:
2700:
2582:Fourier transform
2392:
2377:
2353:
2328:
2173:
2137:
2104:
2058:
2022:
1989:
1877:
1819:
1764:
1337:is a multiple of
1263:
1064:to and less than
928:{\displaystyle n}
586:
551:
411:'s 1801 treatise
257:is 1 itself, and
16:(Redirected from
13496:
13424:
13408:
13390:
13369:Totient function
13363:
13356:
13349:
13340:
13339:
13319:Dineva, Rosica,
13302:
13288:
13261:
13244:
13220:
13209:
13179:
13161:
13133:Ribenboim, Paulo
13128:
13108:
13087:
13074:
13043:
13010:
12970:
12949:
12923:
12858:
12830:Shallit, Jeffrey
12820:
12759:
12757:
12739:
12733:
12732:Guy (2004) p.142
12730:
12724:
12723:
12697:
12680:
12674:
12673:
12647:
12640:
12629:
12623:
12617:
12614:
12608:
12602:
12596:
12593:
12587:
12585:
12581:
12573:
12569:
12566:Gauss proved if
12564:
12558:
12555:
12549:
12546:
12540:
12537:
12531:
12530:Guy (2004) p.145
12528:
12519:
12516:
12510:
12507:
12501:
12500:
12464:
12444:
12433:
12432:
12414:
12393:"On nontotients"
12388:
12382:
12379:
12373:
12372:Guy (2004) p.144
12370:
12361:
12358:
12349:
12346:
12335:
12329:
12323:
12320:
12314:
12313:
12287:
12278:
12275:
12269:
12268:
12266:
12251:Illinois J. Math
12241:
12235:
12229:
12223:
12216:
12210:
12204:
12198:
12192:
12186:
12180:
12174:
12168:
12162:
12156:
12150:
12149:
12148:
12138:
12118:
12112:
12111:
12109:
12085:
12076:
12075:
12061:Acta Arithmetica
12058:
12049:
12043:
12042:
12019:
12008:
12005:
11999:
11993:
11984:
11981:
11975:
11972:
11966:
11963:
11957:
11952:
11946:
11945:
11940:(2nd ed.).
11931:
11925:
11910:
11904:
11903:
11892:
11886:
11879:
11873:
11867:
11856:
11844:
11838:
11829:
11823:
11820:
11814:
11813:Sandifer, p. 203
11811:
11802:
11800:
11796:
11792:
11781:, volume 1, in:
11776:
11755:
11749:
11742:
11736:
11730:
11724:
11718:
11712:
11706:
11700:
11694:
11688:
11687:
11685:
11684:
11670:
11645:
11597:
11590:
11579:Euler's constant
11576:
11572:
11559:is true for all
11555:
11553:
11552:
11547:
11545:
11533:
11532:
11501:
11500:
11490:
11470:
11469:
11457:
11455:
11438:
11407:
11388:
11378:
11374:
11356:
11345:
11338:
11334:
11323:
11316:
11305:
11298:
11291:
11280:
11272:
11257:
11234:
11230:
11219:
11212:
11202:
11191:
11173:
11158:
11147:
11140:
11136:
11132:
11128:
11117:
11113:
11109:
11094:
11084:
11080:
11046:
11036:
11028:
11025:Thus, a regular
11017:
11010:
11006:
11002:
10991:
10936:
10928:
10921:
10906:
10902:
10888:
10885:of multiplicity
10884:
10880:
10862:
10855:
10849:
10842:
10838:
10837:
10835:
10834:
10827:
10824:
10814:
10807:
10805:
10804:
10799:
10776:
10774:
10760:
10734:
10729:
10728:
10692:
10691:
10675:
10668:
10658:
10656:
10655:
10650:
10648:
10647:
10646:
10645:
10612:
10611:
10587:
10586:
10575:
10573:
10559:
10547:
10533:
10521:
10507:
10503:
10484:
10482:
10481:
10476:
10474:
10470:
10443:
10438:
10424:
10400:
10398:
10397:
10392:
10390:
10386:
10359:
10357:
10343:
10323:
10295:
10293:
10292:
10287:
10285:
10268:
10266:
10252:
10232:
10220:
10217:
10204:
10202:
10188:
10168:
10138:
10136:
10135:
10134:
10130:
10127:
10113:
10107:
10101:
10092:
10090:
10089:
10084:
10082:
10078:
10077:
10076:
10068:
10044:
10043:
10035:
9991:I. M. Vinogradov
9981:
9979:
9978:
9973:
9959:
9956:
9953:
9949:
9948:
9947:
9939:
9915:
9914:
9906:
9874:
9872:
9871:
9862:
9861:
9860:
9847:
9770:
9768:
9767:
9762:
9754:
9751:
9748:
9746:
9730:
9729:
9716:
9686:
9684:
9683:
9678:
9667:
9664:
9661:
9659:
9658:
9656:
9636:
9615:
9614:
9601:
9571:
9569:
9568:
9563:
9555:
9550:
9536:
9518:
9504:
9497:
9490:
9489:= 0.577215665...
9482:Euler's constant
9479:
9472:
9470:
9469:
9464:
9459:
9458:
9428:
9423:
9409:
9388:
9378:
9376:
9375:
9370:
9359:
9357:
9356:
9347:
9321:
9316:
9314:
9313:
9301:
9286:
9272:
9258:
9256:
9255:
9250:
9239:
9237:
9236:
9221:
9207:
9196:
9182:
9180:
9179:
9174:
9163:
9158:
9144:
9123:
9119:
9100:
9086:
9084:
9073:
9071:
9070:
9065:
9063:
9061:
9060:
9059:
9034:
9029:
9027:
9026:
9025:
9009:
9008:
9007:
8985:
8982:
8977:
8945:
8943:
8942:
8937:
8907:
8905:
8904:
8899:
8897:
8895:
8881:
8861:
8856:
8854:
8853:
8844:
8830:
8827:
8822:
8793:
8781:Dirichlet series
8766:
8764:
8763:
8758:
8742:
8740:
8739:
8734:
8716:
8714:
8713:
8708:
8690:
8688:
8687:
8682:
8661:
8659:
8658:
8653:
8641:
8639:
8638:
8633:
8619:
8604:
8602:
8601:
8596:
8580:
8578:
8577:
8572:
8555:for any integer
8554:
8552:
8551:
8546:
8534:
8532:
8531:
8526:
8496:
8492:
8465:
8463:
8462:
8457:
8396:
8395:
8393:
8376:
8350:
8330:Menon's identity
8324:Menon's identity
8313:
8307:
8305:
8304:
8299:
8297:
8293:
8288:
8287:
8286:
8278:
8259:
8247:
8243:
8242:
8240:
8227:
8226:
8216:
8205:
8202:
8201:
8198:
8165:
8163:
8162:
8161:
8148:
8130:
8125:
8123:
8106:
8103:
8098:
8074:
8072:
8071:
8066:
8064:
8060:
8059:
8058:
8050:
8021:
8016:
8005:
7997:
7995:
7994:
7993:
7980:
7962:
7957:
7955:
7938:
7935:
7930:
7906:
7904:
7903:
7898:
7896:
7892:
7891:
7890:
7882:
7858:
7857:
7849:
7817:
7815:
7814:
7802:
7797:
7793:
7785:
7779:
7774:
7760:
7757:
7752:
7734:
7729:
7715:
7712:
7707:
7684:
7682:
7681:
7676:
7674:
7670:
7669:
7668:
7660:
7636:
7635:
7627:
7595:
7594:
7585:
7583:
7582:
7570:
7552:
7547:
7523:
7521:
7520:
7515:
7513:
7509:
7508:
7507:
7499:
7475:
7474:
7466:
7434:
7433:
7424:
7422:
7421:
7409:
7404:
7400:
7399:
7398:
7393:
7389:
7381:
7361:
7356:
7330:
7321:
7302:
7297:
7274:
7272:
7271:
7266:
7255:
7252:
7234:
7225:
7213:
7211:
7179:
7141:
7139:
7138:
7133:
7131:
7129:
7112:
7107:
7105:
7091:
7081:
7080:
7070:
7067:
7042:
7035:
7029:
7020:
7018:
7017:
7012:
7010:
7008:
6991:
6965:
6960:
6955:
6941:
6930:
6915:
6906:there exists an
6905:
6898:
6891:
6881:
6869:
6865:
6859:
6852:
6834:
6832:
6831:
6826:
6759:
6757:
6756:
6751:
6646:
6644:
6643:
6638:
6624:
6623:
6605:
6601:
6600:
6576:
6574:
6573:
6568:
6566:
6565:
6559:
6556:
6551:
6548:
6528:
6525:
6520:
6517:
6461:
6459:
6458:
6453:
6424:
6421:
6418:
6416:
6399:
6344:
6342:
6341:
6336:
6325:
6324:
6295:
6293:
6292:
6287:
6225:
6221:
6217:
6213:
6209:
6201:
6197:
6193:
6182:
6171:
6163:
6159:
6145:
6141:
6128:of the function
6122:RSA cryptosystem
6115:
6105:
6083:
6076:
6074:
6073:
6068:
6048:
6047:
6018:relatively prime
6015:
6011:
5993:
5992:
5990:
5989:
5983:
5980:
5966:
5964:
5963:
5958:
5956:
5951:
5943:
5919:
5915:
5907:
5506:
5504:
5496:
5485:
5468:
5455:
5453:
5452:
5447:
5445:
5360:
5201:
5199:
5198:
5193:
5188:
5183:
5169:
5166:
5144:
5142:
5141:
5136:
5131:
5123:
5111:
5089:
5082:
5076:
5074:
5073:
5068:
5057:
5056:
5034:
5032:
5031:
5026:
4988:
4981:
4979:
4978:
4973:
4968:
4963:
4949:
4946:
4925:
4917:
4912:
4897:
4856:Möbius inversion
4848:
4842:
4831:
4824:
4817:
4810:
4808:
4807:
4804:
4801:
4794:
4792:
4791:
4788:
4785:
4778:
4776:
4775:
4772:
4769:
4762:
4760:
4759:
4756:
4753:
4746:
4744:
4743:
4740:
4737:
4730:
4728:
4727:
4724:
4721:
4714:
4712:
4711:
4708:
4705:
4698:
4696:
4695:
4692:
4689:
4682:
4675:
4673:
4672:
4667:
4664:
4652:
4650:
4649:
4644:
4642:
4633:
4626:
4617:
4610:
4601:
4594:
4585:
4578:
4569:
4562:
4553:
4546:
4537:
4530:
4521:
4514:
4505:
4498:
4489:
4482:
4473:
4466:
4457:
4450:
4441:
4434:
4425:
4418:
4409:
4402:
4393:
4386:
4377:
4370:
4361:
4354:
4345:
4338:
4329:
4313:
4311:
4310:
4305:
4300:
4291:
4284:
4275:
4268:
4259:
4252:
4243:
4236:
4227:
4220:
4211:
4204:
4195:
4188:
4179:
4172:
4163:
4156:
4147:
4140:
4131:
4124:
4115:
4108:
4099:
4092:
4083:
4076:
4067:
4060:
4051:
4044:
4035:
4028:
4019:
4012:
4003:
3996:
3987:
3974:
3962:
3954:
3948:
3937:
3926:
3902:
3891:
3887:
3883:
3877:
3870:
3854:
3840:
3822:
3818:
3811:
3809:
3808:
3803:
3779:
3746:
3742:
3738:
3734:
3732:
3731:
3726:
3724:
3711:
3686:
3680:
3673:
3668:
3665:
3647:
3641:
3634:
3629:
3626:
3608:
3602:
3595:
3590:
3587:
3566:
3560:
3553:
3548:
3545:
3528:
3523:
3522:
3494:
3488:
3481:
3476:
3473:
3452:
3446:
3439:
3434:
3431:
3410:
3404:
3397:
3392:
3389:
3371:
3365:
3358:
3353:
3350:
3332:
3328:
3322:
3314:
3278:
3272:
3264:
3234:
3228:
3220:
3190:
3184:
3176:
3119:
3117:
3116:
3111:
3109:
3103:
3096:
3091:
3088:
3082:
3076:
3068:
3052:
3050:
3049:
3044:
3042:
3036:
3029:
3024:
3021:
3015:
3006:
2987:
2985:
2984:
2979:
2974:
2968:
2957:
2929:
2924:
2881:
2879:
2878:
2873:
2868:
2867:
2866:
2858:
2820:
2815:
2785:
2777:
2776:
2745:
2734:
2713:
2711:
2710:
2705:
2703:
2702:
2701:
2696:
2688:
2686:
2664:
2663:
2653:
2648:
2618:
2610:
2609:
2578:
2576:
2575:
2570:
2532:
2521:
2520:
2498:
2487:
2486:
2465:
2464:
2455:
2454:
2410:
2408:
2407:
2402:
2394:
2385:
2379:
2370:
2355:
2346:
2330:
2321:
2296:
2295:
2250:
2248:
2247:
2242:
2196:
2194:
2193:
2188:
2186:
2179:
2175:
2174:
2172:
2171:
2159:
2143:
2139:
2138:
2136:
2135:
2123:
2110:
2106:
2105:
2103:
2102:
2090:
2068:
2064:
2060:
2059:
2057:
2056:
2044:
2028:
2024:
2023:
2021:
2020:
2008:
1995:
1991:
1990:
1988:
1987:
1975:
1961:
1960:
1959:
1949:
1936:
1935:
1934:
1924:
1914:
1913:
1912:
1902:
1887:
1883:
1879:
1878:
1876:
1875:
1863:
1849:
1848:
1847:
1837:
1825:
1821:
1820:
1818:
1817:
1805:
1791:
1790:
1789:
1779:
1770:
1766:
1765:
1763:
1762:
1750:
1736:
1735:
1734:
1724:
1709:
1701:
1700:
1699:
1689:
1667:
1666:
1665:
1655:
1635:
1634:
1633:
1623:
1575:
1564:
1560:
1553:
1537:
1512:
1510:
1509:
1504:
1498:
1497:
1496:
1486:
1473:
1472:
1471:
1461:
1451:
1450:
1449:
1439:
1417:
1398:
1392:
1382:
1376:
1371:, and there are
1370:
1340:
1336:
1332:
1320:
1305:
1293:
1283:
1281:
1280:
1275:
1270:
1266:
1265:
1256:
1242:
1241:
1214:
1213:
1195:
1194:
1176:
1175:
1163:
1159:
1158:
1132:
1125:
1109:
1105:
1091:
1075:
1071:
1067:
1059:
1055:
1051:
1043:
1016:
993:
991:
990:
985:
983:
982:
964:
963:
951:
950:
934:
932:
931:
926:
910:
908:
907:
902:
899:
898:
897:
887:
874:
873:
872:
862:
852:
851:
850:
840:
818:
816:
815:
810:
799:
794:
793:
780:
773:
772:
762:
744:
739:
738:
725:
718:
717:
707:
691:
686:
685:
672:
665:
664:
654:
616:
605:
603:
602:
597:
592:
588:
587:
579:
565:
514:
495:
487:
483:
468:
456:Jordan's totient
438:coined the term
422:
406:
395:
388:
384:
378:
359:
357:
356:
351:
349:
341:
336:
312:
302:
275:
271:
260:
256:
252:
245:
238:
231:
227:
223:
213:
205:
201:
186:
175:
167:
165:
164:
159:
138:
136:
135:
130:
105:
100:relatively prime
97:
82:
75:
71:
60:
43:
36:
21:
13504:
13503:
13499:
13498:
13497:
13495:
13494:
13493:
13459:
13458:
13457:
13452:
13415:
13401:
13396:
13381:
13370:
13367:
13328:Wayback Machine
13310:Wayback Machine
13293:
13273:
13270:
13265:
13233:
13199:
13189:Springer-Verlag
13177:
13151:
13072:
13033:
13023:Springer-Verlag
13015:Guy, Richard K.
13000:
12983:Patashnik, Oren
12968:
12947:
12848:
12818:
12767:
12762:
12754:
12740:
12736:
12731:
12727:
12684:
12681:
12677:
12642:
12631:
12627:
12624:
12620:
12615:
12611:
12603:
12599:
12594:
12590:
12583:
12579:
12571:
12567:
12565:
12561:
12556:
12552:
12547:
12543:
12538:
12534:
12529:
12522:
12517:
12513:
12508:
12504:
12481:
12455:(1–2): 67–151.
12445:
12436:
12389:
12385:
12380:
12376:
12371:
12364:
12359:
12352:
12348:Ribenboim, p.38
12347:
12338:
12330:
12326:
12321:
12317:
12310:
12288:
12281:
12276:
12272:
12242:
12238:
12230:
12226:
12217:
12213:
12205:
12201:
12193:
12189:
12181:
12177:
12169:
12165:
12157:
12153:
12119:
12115:
12086:
12079:
12056:
12050:
12046:
12023:Walfisz, Arnold
12020:
12011:
12006:
12002:
11994:
11987:
11982:
11978:
11973:
11969:
11964:
11960:
11953:
11949:
11932:
11928:
11911:
11907:
11896:Cajori, Florian
11893:
11889:
11885:article 38
11880:
11876:
11858:
11847:
11845:
11841:
11830:
11826:
11821:
11817:
11812:
11805:
11798:
11794:
11790:
11771:Ferdinand Rudio
11756:
11752:
11746:Euler's theorem
11743:
11739:
11731:
11727:
11719:
11715:
11707:
11703:
11695:
11691:
11682:
11680:
11672:
11671:
11667:
11663:
11643:
11604:
11595:
11588:
11582:
11574:
11570:
11560:
11496:
11492:
11491:
11489:
11465:
11461:
11442:
11437:
11435:
11432:
11431:
11421:
11390:
11380:
11376:
11372:
11369:
11363:
11347:
11340:
11336:
11325:
11318:
11307:
11303:
11293:
11282:
11278:
11259:
11258:is prime, then
11255:
11252:
11246:
11241:
11232:
11221:
11217:
11204:
11193:
11178:
11160:
11149:
11145:
11138:
11134:
11130:
11119:
11115:
11111:
11096:
11086:
11082:
11078:
11075:
11073:RSA (algorithm)
11069:
11064:
11058:
11042:
11034:
11026:
11012:
11008:
11004:
10993:
10989:
10980:
10974:
10969:
10949:
10943:
10934:
10923:
10919:
10904:
10890:
10886:
10882:
10875:
10869:
10857:
10851:
10847:
10840:
10828:
10825:
10820:
10819:
10817:
10816:
10812:
10761:
10735:
10733:
10724:
10723:
10687:
10686:
10684:
10681:
10680:
10673:
10663:
10662:for a constant
10641:
10637:
10607:
10606:
10582:
10581:
10580:
10576:
10563:
10558:
10556:
10553:
10552:
10545:
10531:
10509:
10505:
10501:
10494:
10492:Totient numbers
10425:
10423:
10422:
10418:
10416:
10413:
10412:
10344:
10324:
10322:
10321:
10317:
10315:
10312:
10311:
10283:
10282:
10269:
10253:
10233:
10231:
10222:
10221:
10216:
10205:
10189:
10169:
10167:
10157:
10155:
10152:
10151:
10145:
10132:
10131:
10128:
10125:
10124:
10122:
10109:
10105:
10099:
10067:
10063:
10034:
10030:
10014:
10010:
10005:
10002:
10001:
9955:
9938:
9934:
9905:
9901:
9885:
9881:
9867:
9863:
9856:
9852:
9848:
9846:
9793:
9790:
9789:
9750:
9725:
9721:
9720:
9715:
9698:
9695:
9694:
9663:
9640:
9635:
9610:
9606:
9605:
9600:
9583:
9580:
9579:
9537:
9535:
9527:
9524:
9523:
9513:
9503:= 0.56145948...
9499:
9492:
9485:
9477:
9451:
9447:
9410:
9408:
9400:
9397:
9396:
9383:
9352:
9348:
9322:
9320:
9309:
9305:
9300:
9298:
9295:
9294:
9277:
9263:
9226:
9222:
9208:
9206:
9204:
9201:
9200:
9191:
9145:
9143:
9135:
9132:
9131:
9121:
9110:
9107:
9091:
9080:
9078:
9055:
9051:
9038:
9033:
9021:
9017:
9010:
9003:
8999:
8986:
8984:
8978:
8967:
8961:
8958:
8957:
8916:
8913:
8912:
8882:
8862:
8860:
8849:
8845:
8831:
8829:
8823:
8812:
8806:
8803:
8802:
8784:
8777:
8752:
8749:
8748:
8722:
8719:
8718:
8696:
8693:
8692:
8667:
8664:
8663:
8647:
8644:
8643:
8615:
8610:
8607:
8606:
8605:, the relation
8590:
8587:
8586:
8560:
8557:
8556:
8540:
8537:
8536:
8511:
8508:
8507:
8503:
8494:
8485:
8470:
8377:
8351:
8349:
8348:
8342:
8339:
8338:
8332:
8326:
8311:
8277:
8273:
8260:
8258:
8254:
8222:
8218:
8217:
8206:
8204:
8197:
8193:
8170:
8166:
8157:
8153:
8149:
8131:
8129:
8110:
8105:
8099:
8088:
8082:
8079:
8078:
8049:
8045:
8032:
8028:
8006:
8004:
7989:
7985:
7981:
7963:
7961:
7942:
7937:
7931:
7920:
7914:
7911:
7910:
7881:
7877:
7848:
7844:
7831:
7827:
7810:
7806:
7801:
7784:
7780:
7761:
7759:
7753:
7742:
7716:
7714:
7708:
7697:
7691:
7688:
7687:
7659:
7655:
7626:
7622:
7606:
7602:
7590:
7586:
7578:
7574:
7569:
7548:
7537:
7531:
7528:
7527:
7498:
7494:
7465:
7461:
7445:
7441:
7429:
7425:
7417:
7413:
7408:
7394:
7380:
7376:
7375:
7357:
7346:
7335:
7331:
7319:
7298:
7287:
7281:
7278:
7277:
7251:
7223:
7180:
7157:
7155:
7149:
7146:
7145:
7116:
7111:
7092:
7076:
7072:
7071:
7069:
7057:
7051:
7048:
7047:
7038:
7033:
7023:
6992:
6966:
6964:
6942:
6940:
6938:
6935:
6934:
6917:
6907:
6900:
6893:
6886:
6871:
6867:
6863:
6854:
6843:
6766:
6763:
6762:
6655:
6652:
6651:
6613:
6609:
6596:
6592:
6588:
6583:
6580:
6579:
6561:
6560:
6555:
6547:
6545:
6530:
6529:
6524:
6516:
6514:
6492:
6491:
6471:
6468:
6467:
6420:
6403:
6398:
6351:
6348:
6347:
6320:
6316:
6302:
6299:
6298:
6243:
6240:
6239:
6236:
6223:
6219:
6215:
6211:
6207:
6199:
6195:
6184:
6173:
6169:
6161:
6147:
6143:
6129:
6113:
6096:
6081:
6034:
6030:
6028:
6025:
6024:
6013:
6009:
6006:
6004:Euler's theorem
6000:
5998:Euler's theorem
5984:
5981:
5976:
5975:
5973:
5972:
5947:
5942:
5925:
5922:
5921:
5917:
5913:
5898:
5498:
5487:
5464:
5461:
5443:
5442:
5358:
5357:
5227:
5211:
5209:
5206:
5205:
5170:
5168:
5156:
5150:
5147:
5146:
5122:
5101:
5095:
5092:
5091:
5084:
5078:
5077:for each prime
5052:
5048:
5040:
5037:
5036:
5002:
4999:
4998:
4991:Möbius function
4986:
4950:
4948:
4936:
4916:
4902:
4887:
4866:
4863:
4862:
4844:
4833:
4826:
4819:
4812:
4805:
4802:
4799:
4798:
4796:
4789:
4786:
4783:
4782:
4780:
4773:
4770:
4767:
4766:
4764:
4757:
4754:
4751:
4750:
4748:
4741:
4738:
4735:
4734:
4732:
4725:
4722:
4719:
4718:
4716:
4709:
4706:
4703:
4702:
4700:
4693:
4690:
4687:
4686:
4684:
4677:
4668:
4665:
4660:
4659:
4657:
4631:
4615:
4599:
4583:
4567:
4551:
4535:
4519:
4503:
4487:
4471:
4455:
4439:
4423:
4407:
4391:
4375:
4359:
4343:
4327:
4325:
4322:
4321:
4289:
4273:
4257:
4241:
4225:
4209:
4193:
4177:
4161:
4145:
4129:
4113:
4097:
4081:
4065:
4049:
4033:
4017:
4001:
3985:
3983:
3980:
3979:
3969:
3960:
3952:
3947:
3939:
3928:
3925:
3916:
3908:
3901:
3893:
3889:
3885:
3879:
3872:
3864:
3856:
3853:
3845:
3831:
3820:
3816:
3769:
3763:
3760:
3759:
3753:
3744:
3740:
3736:
3722:
3721:
3716:
3709:
3708:
3667:
3666:
3663:
3628:
3627:
3624:
3589:
3588:
3585:
3547:
3546:
3543:
3520:
3519:
3475:
3474:
3471:
3433:
3432:
3429:
3391:
3390:
3387:
3352:
3351:
3348:
3337:
3330:
3329:
3315:
3312:
3265:
3262:
3221:
3218:
3177:
3174:
3148:
3143:
3127:
3125:
3122:
3121:
3090:
3089:
3086:
3069:
3066:
3058:
3055:
3054:
3023:
3022:
3019:
3004:
2996:
2993:
2992:
2958:
2955:
2925:
2914:
2893:
2890:
2889:
2857:
2844:
2840:
2816:
2805:
2781:
2772:
2771:
2754:
2751:
2750:
2736:
2723:
2718:
2689:
2687:
2673:
2672:
2668:
2659:
2655:
2649:
2638:
2614:
2605:
2604:
2602:
2599:
2598:
2584:
2528:
2510:
2506:
2494:
2476:
2472:
2460:
2456:
2450:
2446:
2423:
2420:
2419:
2383:
2368:
2344:
2319:
2291:
2287:
2264:
2261:
2260:
2257:
2212:
2209:
2208:
2184:
2183:
2167:
2163:
2158:
2151:
2147:
2131:
2127:
2122:
2115:
2111:
2098:
2094:
2089:
2082:
2078:
2073:
2066:
2065:
2052:
2048:
2043:
2036:
2032:
2016:
2012:
2007:
2000:
1996:
1983:
1979:
1974:
1967:
1963:
1955:
1951:
1950:
1945:
1930:
1926:
1925:
1920:
1908:
1904:
1903:
1898:
1892:
1885:
1884:
1871:
1867:
1862:
1855:
1851:
1843:
1839:
1838:
1833:
1813:
1809:
1804:
1797:
1793:
1785:
1781:
1780:
1775:
1758:
1754:
1749:
1742:
1738:
1730:
1726:
1725:
1720:
1714:
1707:
1706:
1695:
1691:
1690:
1685:
1661:
1657:
1656:
1651:
1629:
1625:
1624:
1619:
1607:
1602:
1586:
1584:
1581:
1580:
1566:
1562:
1555:
1551:
1543:
1536:
1527:
1520:
1514:
1492:
1488:
1487:
1482:
1467:
1463:
1462:
1457:
1445:
1441:
1440:
1435:
1423:
1420:
1419:
1412:
1411:states that if
1405:
1394:
1384:
1378:
1372:
1342:
1338:
1334:
1322:
1307:
1295:
1291:
1254:
1247:
1243:
1237:
1233:
1203:
1199:
1184:
1180:
1171:
1167:
1154:
1150:
1146:
1141:
1138:
1137:
1127:
1123:
1120:
1107:
1097:
1077:
1073:
1069:
1065:
1057:
1053:
1049:
1018:
1006:
1003:
978:
974:
959:
955:
946:
942:
940:
937:
936:
920:
917:
916:
893:
889:
888:
883:
868:
864:
863:
858:
846:
842:
841:
836:
824:
821:
820:
795:
789:
785:
768:
764:
763:
758:
740:
734:
730:
713:
709:
708:
703:
687:
681:
677:
660:
656:
655:
650:
629:
626:
625:
614:
578:
571:
567:
555:
531:
528:
527:
521:
505:
502:
493:
492:in common with
485:
470:
466:
452:Euler's totient
436:J. J. Sylvester
418:
397:
390:
386:
380:
376:
370:
345:
337:
332:
330:
327:
326:
310:
277:
273:
269:
258:
254:
247:
240:
233:
229:
225:
218:
211:
203:
191:
177:
173:
144:
141:
140:
115:
112:
111:
103:
95:
77:
73:
62:
51:
44:
37:
30:
28:
23:
22:
15:
12:
11:
5:
13502:
13492:
13491:
13489:Leonhard Euler
13486:
13481:
13476:
13471:
13454:
13453:
13451:
13450:
13445:
13440:
13435:
13430:
13425:
13409:
13399:
13391:
13375:
13372:
13371:
13366:
13365:
13358:
13351:
13343:
13337:
13336:
13330:
13317:
13312:
13289:
13269:
13268:External links
13266:
13264:
13263:
13245:
13231:
13210:
13197:
13180:
13175:
13162:
13149:
13129:
13109:
13089:
13075:
13070:
13044:
13031:
13011:
12998:
12975:Graham, Ronald
12971:
12966:
12950:
12945:
12925:
12889:10.2307/121103
12883:(1): 283–311,
12869:) =
12862:
12859:
12846:
12822:
12816:
12794:Abramowitz, M.
12782:Disquisitiones
12768:
12766:
12763:
12761:
12760:
12758:Corollary 5.35
12752:
12734:
12725:
12706:(3): 255–261.
12675:
12652:. III Series.
12618:
12609:
12606:Disquisitiones
12597:
12588:
12576:Pierre Wantzel
12559:
12550:
12541:
12532:
12520:
12511:
12502:
12479:
12434:
12405:(2): 168–172.
12383:
12374:
12362:
12350:
12336:
12324:
12315:
12308:
12279:
12270:
12243:Theorem 15 of
12236:
12224:
12211:
12199:
12187:
12175:
12163:
12151:
12113:
12100:(2): 579–588.
12077:
12067:(3): 227–237,
12044:
12009:
12000:
11985:
11976:
11967:
11958:
11955:Schramm (2008)
11947:
11926:
11905:
11887:
11874:
11839:
11824:
11815:
11803:
11750:
11737:
11725:
11723:, p. 162)
11713:
11701:
11689:
11664:
11662:
11659:
11658:
11657:
11652:
11647:
11638:
11637:
11632:
11627:
11621:
11620:
11615:
11610:
11603:
11600:
11586:
11568:
11557:
11556:
11542:
11539:
11536:
11531:
11528:
11525:
11522:
11519:
11516:
11513:
11510:
11507:
11504:
11499:
11495:
11488:
11485:
11482:
11479:
11476:
11473:
11468:
11464:
11460:
11454:
11451:
11448:
11445:
11441:
11420:
11417:
11410:Ford's theorem
11365:Main article:
11362:
11359:
11248:Main article:
11245:
11242:
11240:
11237:
11129:. The numbers
11071:Main article:
11068:
11065:
11060:Main article:
11057:
11054:
11053:
11052:
10985:Disquisitiones
10976:Main article:
10973:
10970:
10968:
10965:
10945:Main article:
10942:
10939:
10868:
10867:Ford's theorem
10865:
10809:
10808:
10797:
10794:
10791:
10788:
10785:
10782:
10779:
10773:
10770:
10767:
10764:
10759:
10756:
10753:
10750:
10747:
10744:
10741:
10738:
10732:
10727:
10722:
10719:
10716:
10713:
10710:
10707:
10704:
10701:
10698:
10695:
10690:
10667:= 0.8178146...
10660:
10659:
10644:
10640:
10636:
10633:
10630:
10627:
10624:
10621:
10618:
10615:
10610:
10605:
10602:
10599:
10596:
10593:
10590:
10585:
10579:
10572:
10569:
10566:
10562:
10498:totient number
10493:
10490:
10486:
10485:
10473:
10469:
10466:
10463:
10460:
10457:
10454:
10451:
10446:
10441:
10437:
10434:
10431:
10428:
10421:
10402:
10401:
10389:
10385:
10382:
10379:
10376:
10373:
10370:
10367:
10362:
10356:
10353:
10350:
10347:
10342:
10339:
10336:
10333:
10330:
10327:
10320:
10297:
10296:
10281:
10278:
10275:
10272:
10270:
10265:
10262:
10259:
10256:
10251:
10248:
10245:
10242:
10239:
10236:
10230:
10227:
10224:
10223:
10214:
10211:
10208:
10206:
10201:
10198:
10195:
10192:
10187:
10184:
10181:
10178:
10175:
10172:
10166:
10163:
10160:
10159:
10144:
10141:
10094:
10093:
10081:
10074:
10071:
10066:
10062:
10059:
10056:
10053:
10050:
10047:
10041:
10038:
10033:
10029:
10026:
10023:
10020:
10017:
10013:
10009:
9987:Arnold Walfisz
9983:
9982:
9971:
9968:
9965:
9962:
9952:
9945:
9942:
9937:
9933:
9930:
9927:
9924:
9921:
9918:
9912:
9909:
9904:
9900:
9897:
9894:
9891:
9888:
9884:
9880:
9877:
9870:
9866:
9859:
9855:
9851:
9845:
9842:
9839:
9836:
9833:
9830:
9827:
9824:
9821:
9818:
9815:
9812:
9809:
9806:
9803:
9800:
9797:
9772:
9771:
9760:
9757:
9745:
9742:
9739:
9736:
9733:
9728:
9724:
9719:
9714:
9711:
9708:
9705:
9702:
9688:
9687:
9676:
9673:
9670:
9655:
9652:
9649:
9646:
9643:
9639:
9634:
9631:
9628:
9625:
9622:
9619:
9613:
9609:
9604:
9599:
9596:
9593:
9590:
9587:
9573:
9572:
9561:
9558:
9553:
9549:
9546:
9543:
9540:
9534:
9531:
9496:= 1.7810724...
9474:
9473:
9462:
9457:
9454:
9450:
9446:
9443:
9440:
9437:
9434:
9431:
9426:
9422:
9419:
9416:
9413:
9407:
9404:
9380:
9379:
9368:
9365:
9362:
9355:
9351:
9346:
9343:
9340:
9337:
9334:
9331:
9328:
9325:
9319:
9312:
9308:
9304:
9260:
9259:
9248:
9245:
9242:
9235:
9232:
9229:
9225:
9220:
9217:
9214:
9211:
9184:
9183:
9172:
9169:
9166:
9161:
9157:
9154:
9151:
9148:
9142:
9139:
9106:
9103:
9075:
9074:
9058:
9054:
9050:
9047:
9044:
9041:
9037:
9032:
9024:
9020:
9016:
9013:
9006:
9002:
8998:
8995:
8992:
8989:
8981:
8976:
8973:
8970:
8966:
8951:Lambert series
8935:
8932:
8929:
8926:
8923:
8920:
8909:
8908:
8894:
8891:
8888:
8885:
8880:
8877:
8874:
8871:
8868:
8865:
8859:
8852:
8848:
8843:
8840:
8837:
8834:
8826:
8821:
8818:
8815:
8811:
8776:
8773:
8756:
8745:
8744:
8732:
8729:
8726:
8706:
8703:
8700:
8680:
8677:
8674:
8671:
8651:
8631:
8628:
8625:
8622:
8618:
8614:
8594:
8570:
8567:
8564:
8544:
8524:
8521:
8518:
8515:
8502:
8499:
8483:
8467:
8466:
8455:
8452:
8449:
8446:
8443:
8440:
8437:
8434:
8431:
8428:
8425:
8422:
8419:
8416:
8413:
8410:
8407:
8404:
8392:
8389:
8386:
8383:
8380:
8375:
8372:
8369:
8366:
8363:
8360:
8357:
8354:
8347:
8328:Main article:
8325:
8322:
8321:
8320:
8296:
8291:
8284:
8281:
8276:
8272:
8269:
8266:
8263:
8257:
8253:
8250:
8246:
8239:
8236:
8233:
8230:
8225:
8221:
8215:
8212:
8209:
8196:
8192:
8188:
8185:
8182:
8179:
8176:
8173:
8169:
8160:
8156:
8152:
8147:
8144:
8141:
8138:
8134:
8128:
8122:
8119:
8116:
8113:
8109:
8102:
8097:
8094:
8091:
8087:
8076:
8063:
8056:
8053:
8048:
8044:
8041:
8038:
8035:
8031:
8027:
8024:
8019:
8015:
8012:
8009:
8003:
8000:
7992:
7988:
7984:
7979:
7976:
7973:
7970:
7966:
7960:
7954:
7951:
7948:
7945:
7941:
7934:
7929:
7926:
7923:
7919:
7908:
7895:
7888:
7885:
7880:
7876:
7873:
7870:
7867:
7864:
7861:
7855:
7852:
7847:
7843:
7840:
7837:
7834:
7830:
7826:
7823:
7820:
7813:
7809:
7805:
7800:
7796:
7791:
7788:
7783:
7777:
7773:
7770:
7767:
7764:
7756:
7751:
7748:
7745:
7741:
7737:
7732:
7728:
7725:
7722:
7719:
7711:
7706:
7703:
7700:
7696:
7685:
7673:
7666:
7663:
7658:
7654:
7651:
7648:
7645:
7642:
7639:
7633:
7630:
7625:
7621:
7618:
7615:
7612:
7609:
7605:
7601:
7598:
7593:
7589:
7581:
7577:
7573:
7568:
7565:
7562:
7559:
7556:
7551:
7546:
7543:
7540:
7536:
7525:
7512:
7505:
7502:
7497:
7493:
7490:
7487:
7484:
7481:
7478:
7472:
7469:
7464:
7460:
7457:
7454:
7451:
7448:
7444:
7440:
7437:
7432:
7428:
7420:
7416:
7412:
7407:
7403:
7397:
7392:
7387:
7384:
7379:
7374:
7371:
7368:
7365:
7360:
7355:
7352:
7349:
7345:
7341:
7338:
7334:
7327:
7324:
7318:
7315:
7312:
7309:
7306:
7301:
7296:
7293:
7290:
7286:
7275:
7264:
7261:
7258:
7249:
7246:
7243:
7240:
7237:
7231:
7228:
7222:
7219:
7210:
7207:
7204:
7201:
7198:
7195:
7192:
7189:
7186:
7183:
7178:
7175:
7172:
7169:
7166:
7163:
7160:
7154:
7143:
7128:
7125:
7122:
7119:
7115:
7110:
7104:
7101:
7098:
7095:
7090:
7087:
7084:
7079:
7075:
7066:
7063:
7060:
7056:
7045:
7007:
7004:
7001:
6998:
6995:
6990:
6987:
6984:
6981:
6978:
6975:
6972:
6969:
6963:
6958:
6954:
6951:
6948:
6945:
6932:
6883:
6841:
6824:
6821:
6818:
6815:
6812:
6809:
6806:
6803:
6800:
6797:
6794:
6791:
6788:
6785:
6782:
6779:
6776:
6773:
6770:
6749:
6746:
6743:
6740:
6737:
6734:
6731:
6728:
6725:
6722:
6719:
6716:
6713:
6710:
6707:
6704:
6701:
6698:
6695:
6692:
6689:
6686:
6683:
6680:
6677:
6674:
6671:
6668:
6665:
6662:
6659:
6649:
6648:
6647:
6636:
6633:
6630:
6627:
6622:
6619:
6616:
6612:
6608:
6604:
6599:
6595:
6591:
6587:
6577:
6564:
6554:
6549: if
6546:
6544:
6541:
6538:
6535:
6532:
6531:
6523:
6518: if
6515:
6513:
6510:
6507:
6504:
6501:
6498:
6497:
6495:
6490:
6487:
6484:
6481:
6478:
6475:
6463:In particular:
6451:
6448:
6445:
6442:
6439:
6436:
6433:
6430:
6427:
6415:
6412:
6409:
6406:
6402:
6397:
6394:
6391:
6388:
6385:
6382:
6379:
6376:
6373:
6370:
6367:
6364:
6361:
6358:
6355:
6345:
6334:
6331:
6328:
6323:
6319:
6315:
6312:
6309:
6306:
6296:
6285:
6282:
6279:
6276:
6273:
6270:
6267:
6264:
6261:
6257:
6253:
6250:
6247:
6235:
6234:Other formulae
6232:
6078:
6077:
6066:
6063:
6058:
6054:
6051:
6046:
6043:
6040:
6037:
6033:
6002:Main article:
5999:
5996:
5954:
5950:
5946:
5941:
5938:
5935:
5932:
5929:
5912:valid for all
5895:
5894:
5891:
5890:
5887:
5884:
5881:
5878:
5875:
5872:
5869:
5866:
5863:
5860:
5856:
5855:
5852:
5849:
5846:
5843:
5840:
5837:
5834:
5831:
5828:
5825:
5821:
5820:
5817:
5814:
5811:
5808:
5805:
5802:
5799:
5796:
5793:
5790:
5786:
5785:
5782:
5779:
5776:
5773:
5770:
5767:
5764:
5761:
5758:
5755:
5751:
5750:
5747:
5744:
5741:
5738:
5735:
5732:
5729:
5726:
5723:
5720:
5716:
5715:
5712:
5709:
5706:
5703:
5700:
5697:
5694:
5691:
5688:
5685:
5681:
5680:
5677:
5674:
5671:
5668:
5665:
5662:
5659:
5656:
5653:
5650:
5646:
5645:
5642:
5639:
5636:
5633:
5630:
5627:
5624:
5621:
5618:
5615:
5611:
5610:
5607:
5604:
5601:
5598:
5595:
5592:
5589:
5586:
5583:
5580:
5576:
5575:
5572:
5569:
5566:
5563:
5560:
5557:
5554:
5551:
5548:
5545:
5541:
5540:
5537:
5534:
5531:
5528:
5525:
5522:
5519:
5516:
5513:
5510:
5460:
5457:
5441:
5438:
5435:
5432:
5429:
5426:
5423:
5420:
5417:
5414:
5411:
5408:
5405:
5402:
5399:
5396:
5393:
5390:
5387:
5384:
5381:
5378:
5375:
5372:
5369:
5366:
5363:
5361:
5359:
5356:
5353:
5350:
5347:
5344:
5341:
5338:
5335:
5332:
5329:
5326:
5323:
5320:
5317:
5314:
5311:
5308:
5305:
5302:
5299:
5296:
5293:
5290:
5287:
5284:
5281:
5278:
5275:
5272:
5269:
5266:
5263:
5260:
5257:
5254:
5251:
5248:
5245:
5242:
5239:
5236:
5233:
5230:
5228:
5226:
5223:
5220:
5217:
5214:
5213:
5191:
5186:
5182:
5179:
5176:
5173:
5165:
5162:
5159:
5155:
5134:
5129:
5126:
5121:
5118:
5115:
5110:
5107:
5104:
5100:
5066:
5063:
5060:
5055:
5051:
5047:
5044:
5024:
5021:
5018:
5015:
5012:
5009:
5006:
4983:
4982:
4971:
4966:
4962:
4959:
4956:
4953:
4945:
4942:
4939:
4935:
4931:
4928:
4923:
4920:
4915:
4911:
4908:
4905:
4901:
4896:
4893:
4890:
4886:
4882:
4879:
4876:
4873:
4870:
4654:
4653:
4639:
4636:
4629:
4623:
4620:
4613:
4607:
4604:
4597:
4591:
4588:
4581:
4575:
4572:
4565:
4559:
4556:
4549:
4543:
4540:
4533:
4527:
4524:
4517:
4511:
4508:
4501:
4495:
4492:
4485:
4479:
4476:
4469:
4463:
4460:
4453:
4447:
4444:
4437:
4431:
4428:
4421:
4415:
4412:
4405:
4399:
4396:
4389:
4383:
4380:
4373:
4367:
4364:
4357:
4351:
4348:
4341:
4335:
4332:
4315:
4314:
4303:
4297:
4294:
4287:
4281:
4278:
4271:
4265:
4262:
4255:
4249:
4246:
4239:
4233:
4230:
4223:
4217:
4214:
4207:
4201:
4198:
4191:
4185:
4182:
4175:
4169:
4166:
4159:
4153:
4150:
4143:
4137:
4134:
4127:
4121:
4118:
4111:
4105:
4102:
4095:
4089:
4086:
4079:
4073:
4070:
4063:
4057:
4054:
4047:
4041:
4038:
4031:
4025:
4022:
4015:
4009:
4006:
3999:
3993:
3990:
3943:
3921:
3912:
3897:
3860:
3849:
3813:
3812:
3801:
3798:
3795:
3792:
3789:
3786:
3783:
3778:
3775:
3772:
3768:
3752:
3749:
3720:
3717:
3715:
3712:
3710:
3707:
3704:
3701:
3698:
3695:
3692:
3689:
3683:
3679:
3676:
3671:
3662:
3659:
3656:
3653:
3650:
3644:
3640:
3637:
3632:
3623:
3620:
3617:
3614:
3611:
3605:
3601:
3598:
3593:
3584:
3581:
3578:
3575:
3572:
3569:
3563:
3559:
3556:
3551:
3542:
3539:
3536:
3533:
3527:
3524:
3521:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3497:
3491:
3487:
3484:
3479:
3470:
3467:
3464:
3461:
3458:
3455:
3449:
3445:
3442:
3437:
3428:
3425:
3422:
3419:
3416:
3413:
3407:
3403:
3400:
3395:
3386:
3383:
3380:
3377:
3374:
3368:
3364:
3361:
3356:
3347:
3344:
3341:
3338:
3336:
3333:
3331:
3325:
3321:
3318:
3311:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3284:
3281:
3275:
3271:
3268:
3261:
3258:
3255:
3252:
3249:
3246:
3243:
3240:
3237:
3231:
3227:
3224:
3217:
3214:
3211:
3208:
3205:
3202:
3199:
3196:
3193:
3187:
3183:
3180:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3147:
3144:
3142:
3139:
3136:
3133:
3130:
3129:
3106:
3102:
3099:
3094:
3085:
3079:
3075:
3072:
3065:
3062:
3039:
3035:
3032:
3027:
3018:
3012:
3009:
3003:
3000:
2989:
2988:
2977:
2971:
2967:
2964:
2961:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2928:
2923:
2920:
2917:
2913:
2909:
2906:
2903:
2900:
2897:
2883:
2882:
2871:
2864:
2861:
2856:
2853:
2850:
2847:
2843:
2839:
2836:
2833:
2830:
2827:
2824:
2819:
2814:
2811:
2808:
2804:
2800:
2797:
2794:
2791:
2788:
2784:
2780:
2775:
2770:
2767:
2764:
2761:
2758:
2721:
2715:
2714:
2699:
2695:
2692:
2685:
2682:
2679:
2676:
2671:
2667:
2662:
2658:
2652:
2647:
2644:
2641:
2637:
2633:
2630:
2627:
2624:
2621:
2617:
2613:
2608:
2583:
2580:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2538:
2535:
2531:
2527:
2524:
2519:
2516:
2513:
2509:
2504:
2501:
2497:
2493:
2490:
2485:
2482:
2479:
2475:
2471:
2468:
2463:
2459:
2453:
2449:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2412:
2411:
2400:
2397:
2391:
2388:
2382:
2376:
2373:
2367:
2364:
2361:
2358:
2352:
2349:
2343:
2340:
2337:
2333:
2327:
2324:
2318:
2315:
2312:
2308:
2305:
2302:
2299:
2294:
2290:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2256:
2253:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2198:
2197:
2182:
2178:
2170:
2166:
2162:
2157:
2154:
2150:
2146:
2142:
2134:
2130:
2126:
2121:
2118:
2114:
2109:
2101:
2097:
2093:
2088:
2085:
2081:
2077:
2074:
2072:
2069:
2067:
2063:
2055:
2051:
2047:
2042:
2039:
2035:
2031:
2027:
2019:
2015:
2011:
2006:
2003:
1999:
1994:
1986:
1982:
1978:
1973:
1970:
1966:
1958:
1954:
1948:
1944:
1940:
1933:
1929:
1923:
1919:
1911:
1907:
1901:
1897:
1893:
1891:
1888:
1886:
1882:
1874:
1870:
1866:
1861:
1858:
1854:
1846:
1842:
1836:
1832:
1828:
1824:
1816:
1812:
1808:
1803:
1800:
1796:
1788:
1784:
1778:
1774:
1769:
1761:
1757:
1753:
1748:
1745:
1741:
1733:
1729:
1723:
1719:
1715:
1713:
1710:
1708:
1705:
1698:
1694:
1688:
1684:
1680:
1677:
1674:
1671:
1664:
1660:
1654:
1650:
1646:
1643:
1639:
1632:
1628:
1622:
1618:
1614:
1611:
1608:
1606:
1603:
1601:
1598:
1595:
1592:
1589:
1588:
1547:
1532:
1528:< ... <
1525:
1518:
1502:
1495:
1491:
1485:
1481:
1477:
1470:
1466:
1460:
1456:
1448:
1444:
1438:
1434:
1430:
1427:
1404:
1401:
1285:
1284:
1273:
1269:
1262:
1259:
1253:
1250:
1246:
1240:
1236:
1232:
1229:
1226:
1223:
1220:
1217:
1212:
1209:
1206:
1202:
1198:
1193:
1190:
1187:
1183:
1179:
1174:
1170:
1166:
1162:
1157:
1153:
1149:
1145:
1119:
1116:
1046:Proof outline:
1002:
999:
981:
977:
973:
970:
967:
962:
958:
954:
949:
945:
924:
896:
892:
886:
882:
878:
871:
867:
861:
857:
849:
845:
839:
835:
831:
828:
808:
805:
802:
798:
792:
788:
784:
779:
776:
771:
767:
761:
757:
753:
750:
747:
743:
737:
733:
729:
724:
721:
716:
712:
706:
702:
697:
694:
690:
684:
680:
676:
671:
668:
663:
659:
653:
649:
645:
642:
639:
636:
633:
607:
606:
595:
591:
585:
582:
577:
574:
570:
564:
561:
558:
554:
550:
547:
544:
541:
538:
535:
520:
517:
501:
498:
469:is defined as
427:or simply the
373:Leonhard Euler
369:
366:
348:
344:
340:
335:
187:for which the
157:
154:
151:
148:
128:
125:
122:
119:
40:Euler function
26:
9:
6:
4:
3:
2:
13501:
13490:
13487:
13485:
13484:Number theory
13482:
13480:
13477:
13475:
13472:
13470:
13467:
13466:
13464:
13449:
13446:
13444:
13441:
13439:
13436:
13434:
13431:
13429:
13426:
13422:
13418:
13413:
13410:
13406:
13402:
13395:
13392:
13388:
13384:
13380:
13377:
13376:
13373:
13364:
13359:
13357:
13352:
13350:
13345:
13344:
13341:
13335:
13331:
13329:
13325:
13322:
13318:
13316:
13313:
13311:
13307:
13304:
13300:
13296:
13290:
13286:
13282:
13281:
13276:
13272:
13271:
13259:
13255:
13251:
13246:
13242:
13238:
13234:
13232:1-4020-2546-7
13228:
13224:
13219:
13218:
13211:
13208:
13204:
13200:
13198:1-4020-4215-9
13194:
13190:
13187:, Dordrecht:
13186:
13181:
13178:
13172:
13168:
13163:
13160:
13156:
13152:
13150:0-387-94457-5
13146:
13142:
13138:
13134:
13130:
13127:
13123:
13119:
13118:Prentice Hall
13115:
13110:
13107:
13103:
13099:
13095:
13090:
13085:
13081:
13076:
13073:
13067:
13063:
13059:
13058:
13053:
13052:Wright, E. M.
13049:
13045:
13042:
13038:
13034:
13032:0-387-20860-7
13028:
13024:
13020:
13016:
13012:
13009:
13005:
13001:
12999:0-201-55802-5
12995:
12991:
12989:
12984:
12980:
12979:Knuth, Donald
12976:
12972:
12969:
12967:0-8284-0191-8
12963:
12959:
12955:
12951:
12948:
12946:0-387-96254-9
12942:
12938:
12934:
12930:
12926:
12922:
12918:
12914:
12910:
12906:
12902:
12898:
12894:
12890:
12886:
12882:
12878:
12877:
12872:
12868:
12863:
12860:
12857:
12853:
12849:
12847:0-262-02405-5
12843:
12839:
12838:The MIT Press
12835:
12831:
12827:
12823:
12819:
12817:0-486-61272-4
12813:
12809:
12805:
12804:
12799:
12798:Stegun, I. A.
12795:
12791:
12790:
12789:
12787:
12783:
12778:
12775:
12774:
12755:
12749:
12745:
12738:
12729:
12721:
12717:
12713:
12709:
12705:
12702:. IV Series.
12701:
12695:
12691:
12687:
12679:
12671:
12667:
12663:
12659:
12655:
12651:
12645:
12638:
12634:
12622:
12613:
12607:
12601:
12592:
12577:
12563:
12554:
12545:
12536:
12527:
12525:
12515:
12506:
12498:
12494:
12490:
12486:
12482:
12476:
12472:
12468:
12463:
12458:
12454:
12450:
12443:
12441:
12439:
12430:
12426:
12422:
12418:
12413:
12408:
12404:
12400:
12399:
12394:
12387:
12378:
12369:
12367:
12357:
12355:
12345:
12343:
12341:
12333:
12328:
12319:
12311:
12305:
12301:
12297:
12293:
12286:
12284:
12274:
12265:
12260:
12256:
12252:
12248:
12240:
12233:
12228:
12221:
12215:
12208:
12203:
12196:
12191:
12184:
12179:
12172:
12167:
12160:
12155:
12147:
12142:
12137:
12132:
12129:: 1195–1220,
12128:
12124:
12117:
12108:
12103:
12099:
12095:
12091:
12084:
12082:
12074:
12070:
12066:
12062:
12055:
12048:
12040:
12036:
12032:
12028:
12024:
12018:
12016:
12014:
12004:
11997:
11992:
11990:
11980:
11971:
11962:
11956:
11951:
11943:
11939:
11938:
11930:
11923:
11919:
11915:
11909:
11901:
11897:
11891:
11884:
11878:
11871:
11865:
11861:
11854:
11850:
11843:
11836:
11835:
11828:
11819:
11810:
11808:
11788:
11787:pages 531–555
11784:
11780:
11772:
11768:
11764:
11760:
11754:
11747:
11741:
11735:, p. 80)
11734:
11729:
11722:
11717:
11711:, p. 72)
11710:
11705:
11699:, p. 85)
11698:
11693:
11679:
11675:
11669:
11665:
11656:
11653:
11651:
11650:Ramanujan sum
11648:
11646:
11640:
11639:
11636:
11633:
11631:
11628:
11626:
11623:
11622:
11619:
11616:
11614:
11611:
11609:
11606:
11605:
11599:
11594:
11585:
11580:
11567:
11563:
11540:
11537:
11534:
11526:
11523:
11520:
11517:
11514:
11511:
11508:
11505:
11497:
11493:
11486:
11483:
11480:
11477:
11474:
11471:
11466:
11462:
11458:
11449:
11443:
11439:
11430:
11429:
11428:
11426:
11416:
11413:
11411:
11405:
11401:
11397:
11393:
11387:
11383:
11368:
11358:
11354:
11350:
11343:
11332:
11328:
11321:
11314:
11310:
11300:
11296:
11289:
11285:
11276:
11270:
11266:
11262:
11251:
11236:
11228:
11224:
11214:
11211:
11207:
11201:
11197:
11189:
11185:
11181:
11175:
11171:
11167:
11163:
11157:
11153:
11142:
11126:
11122:
11107:
11103:
11099:
11093:
11089:
11074:
11063:
11050:
11045:
11040:
11039:
11038:
11032:
11023:
11021:
11020:Fermat primes
11015:
11000:
10996:
10987:
10986:
10979:
10964:
10962:
10958:
10954:
10948:
10938:
10932:
10926:
10916:
10914:
10910:
10901:
10897:
10893:
10878:
10873:
10864:
10860:
10854:
10844:
10832:
10823:
10792:
10786:
10783:
10780:
10777:
10768:
10762:
10754:
10748:
10742:
10736:
10730:
10717:
10714:
10708:
10702:
10699:
10696:
10679:
10678:
10677:
10670:
10666:
10642:
10634:
10631:
10628:
10625:
10622:
10619:
10616:
10600:
10594:
10591:
10588:
10577:
10570:
10567:
10564:
10560:
10551:
10550:
10549:
10542:
10539:
10538:
10529:
10525:
10520:
10516:
10512:
10499:
10489:
10471:
10467:
10464:
10461:
10458:
10455:
10452:
10449:
10444:
10439:
10432:
10426:
10419:
10411:
10410:
10409:
10407:
10387:
10383:
10380:
10377:
10374:
10371:
10368:
10365:
10360:
10351:
10345:
10337:
10334:
10331:
10325:
10318:
10310:
10309:
10308:
10306:
10302:
10279:
10273:
10271:
10260:
10254:
10246:
10243:
10240:
10234:
10212:
10209:
10207:
10196:
10190:
10182:
10179:
10176:
10170:
10150:
10149:
10148:
10140:
10120:
10115:
10112:
10103:
10079:
10072:
10069:
10060:
10057:
10054:
10051:
10048:
10039:
10036:
10027:
10024:
10021:
10015:
10011:
10007:
10000:
9999:
9998:
9996:
9995:N. M. Korobov
9992:
9988:
9969:
9960:
9950:
9943:
9940:
9931:
9928:
9925:
9922:
9919:
9910:
9907:
9898:
9895:
9892:
9886:
9882:
9878:
9875:
9868:
9864:
9857:
9853:
9849:
9843:
9837:
9831:
9828:
9825:
9822:
9816:
9810:
9807:
9801:
9795:
9788:
9787:
9786:
9783:
9781:
9777:
9758:
9755:
9743:
9740:
9737:
9734:
9731:
9726:
9722:
9717:
9712:
9706:
9700:
9693:
9692:
9691:
9674:
9671:
9668:
9653:
9650:
9647:
9644:
9641:
9637:
9632:
9629:
9626:
9623:
9620:
9617:
9611:
9607:
9602:
9597:
9591:
9585:
9578:
9577:
9576:
9559:
9556:
9551:
9544:
9538:
9522:
9521:
9520:
9517:
9511:
9506:
9502:
9495:
9488:
9483:
9460:
9455:
9452:
9448:
9444:
9441:
9438:
9435:
9432:
9429:
9424:
9417:
9411:
9395:
9394:
9393:
9392:We also have
9390:
9389:, is proved.
9386:
9366:
9363:
9360:
9353:
9349:
9341:
9335:
9329:
9323:
9317:
9310:
9306:
9302:
9293:
9292:
9291:
9288:
9284:
9280:
9276:
9270:
9266:
9246:
9233:
9230:
9227:
9223:
9215:
9209:
9199:
9198:
9197:
9194:
9189:
9170:
9167:
9164:
9159:
9152:
9146:
9130:
9129:
9128:
9125:
9117:
9113:
9102:
9098:
9094:
9088:
9085:| < 1
9083:
9056:
9048:
9045:
9042:
9035:
9030:
9022:
9018:
9014:
9011:
9004:
9000:
8993:
8987:
8974:
8971:
8968:
8964:
8956:
8955:
8954:
8952:
8947:
8933:
8930:
8924:
8889:
8883:
8875:
8872:
8869:
8863:
8857:
8850:
8846:
8838:
8832:
8819:
8816:
8813:
8809:
8801:
8800:
8799:
8797:
8791:
8787:
8782:
8772:
8770:
8754:
8724:
8704:
8701:
8698:
8675:
8669:
8649:
8626:
8620:
8612:
8592:
8584:
8583:
8582:
8568:
8565:
8562:
8542:
8519:
8513:
8498:
8491:
8489:
8482:
8478:
8474:
8453:
8447:
8441:
8435:
8429:
8426:
8420:
8417:
8414:
8411:
8408:
8390:
8387:
8384:
8381:
8378:
8373:
8370:
8364:
8361:
8358:
8345:
8337:
8336:
8335:
8331:
8319:
8317:
8294:
8289:
8282:
8279:
8270:
8267:
8264:
8255:
8251:
8248:
8244:
8237:
8234:
8231:
8228:
8223:
8219:
8213:
8210:
8207:
8194:
8190:
8186:
8183:
8180:
8177:
8174:
8171:
8167:
8158:
8154:
8150:
8142:
8136:
8132:
8126:
8117:
8111:
8107:
8100:
8095:
8092:
8089:
8085:
8077:
8061:
8054:
8051:
8042:
8039:
8036:
8029:
8025:
8022:
8017:
8013:
8010:
8007:
8001:
7998:
7990:
7986:
7982:
7974:
7968:
7964:
7958:
7949:
7943:
7939:
7932:
7927:
7924:
7921:
7917:
7909:
7893:
7886:
7883:
7874:
7871:
7868:
7865:
7862:
7853:
7850:
7841:
7838:
7835:
7828:
7824:
7821:
7818:
7811:
7807:
7803:
7798:
7794:
7789:
7786:
7781:
7775:
7768:
7762:
7754:
7749:
7746:
7743:
7739:
7735:
7730:
7723:
7717:
7709:
7704:
7701:
7698:
7694:
7686:
7671:
7664:
7661:
7652:
7649:
7646:
7643:
7640:
7631:
7628:
7619:
7616:
7613:
7607:
7603:
7599:
7596:
7591:
7587:
7579:
7575:
7571:
7566:
7560:
7554:
7549:
7544:
7541:
7538:
7534:
7526:
7510:
7503:
7500:
7491:
7488:
7485:
7482:
7479:
7470:
7467:
7458:
7455:
7452:
7446:
7442:
7438:
7435:
7430:
7426:
7418:
7414:
7410:
7405:
7401:
7395:
7390:
7385:
7382:
7377:
7369:
7363:
7358:
7353:
7350:
7347:
7343:
7339:
7336:
7332:
7325:
7322:
7316:
7310:
7304:
7299:
7294:
7291:
7288:
7284:
7276:
7262:
7259:
7256:
7244:
7238:
7235:
7229:
7226:
7220:
7217:
7208:
7205:
7199:
7196:
7193:
7187:
7184:
7181:
7176:
7173:
7170:
7167:
7164:
7161:
7158:
7152:
7144:
7123:
7117:
7113:
7108:
7099:
7093:
7085:
7077:
7073:
7064:
7061:
7058:
7054:
7046:
7044:
7041:
7036:
7027:
7002:
6996:
6993:
6982:
6976:
6973:
6967:
6961:
6956:
6949:
6943:
6933:
6928:
6924:
6920:
6914:
6910:
6904:
6896:
6889:
6884:
6882:
6879:
6875:
6862:Moreover, if
6857:
6850:
6846:
6842:
6840:
6838:
6822:
6819:
6816:
6813:
6807:
6804:
6801:
6795:
6792:
6789:
6783:
6780:
6777:
6771:
6768:
6744:
6738:
6735:
6729:
6723:
6720:
6711:
6708:
6705:
6699:
6696:
6690:
6687:
6678:
6675:
6672:
6666:
6663:
6657:
6650:
6631:
6625:
6620:
6617:
6614:
6610:
6606:
6602:
6597:
6593:
6589:
6585:
6578:
6552:
6539:
6533:
6526: is even
6521:
6508:
6502:
6499:
6493:
6488:
6482:
6479:
6473:
6466:
6465:
6464:
6446:
6443:
6440:
6434:
6431:
6428:
6425:
6410:
6404:
6400:
6395:
6389:
6383:
6377:
6371:
6368:
6362:
6359:
6353:
6346:
6329:
6326:
6321:
6317:
6310:
6307:
6304:
6297:
6280:
6274:
6271:
6265:
6259:
6251:
6248:
6245:
6238:
6237:
6231:
6229:
6205:
6191:
6187:
6180:
6176:
6167:
6158:
6154:
6150:
6140:
6136:
6132:
6127:
6123:
6118:
6116:
6109:
6103:
6099:
6094:
6089:
6087:
6064:
6061:
6056:
6052:
6049:
6041:
6035:
6031:
6023:
6022:
6021:
6019:
6005:
5995:
5988:
5979:
5970:
5952:
5948:
5944:
5939:
5933:
5927:
5911:
5905:
5901:
5888:
5885:
5882:
5879:
5876:
5873:
5870:
5867:
5864:
5861:
5858:
5857:
5853:
5850:
5847:
5844:
5841:
5838:
5835:
5832:
5829:
5826:
5823:
5822:
5818:
5815:
5812:
5809:
5806:
5803:
5800:
5797:
5794:
5791:
5788:
5787:
5783:
5780:
5777:
5774:
5771:
5768:
5765:
5762:
5759:
5756:
5753:
5752:
5748:
5745:
5742:
5739:
5736:
5733:
5730:
5727:
5724:
5721:
5718:
5717:
5713:
5710:
5707:
5704:
5701:
5698:
5695:
5692:
5689:
5686:
5683:
5682:
5678:
5675:
5672:
5669:
5666:
5663:
5660:
5657:
5654:
5651:
5648:
5647:
5643:
5640:
5637:
5634:
5631:
5628:
5625:
5622:
5619:
5616:
5613:
5612:
5608:
5605:
5602:
5599:
5596:
5593:
5590:
5587:
5584:
5581:
5578:
5577:
5573:
5570:
5567:
5564:
5561:
5558:
5555:
5552:
5549:
5546:
5543:
5542:
5538:
5535:
5532:
5529:
5526:
5523:
5520:
5517:
5514:
5511:
5508:
5507:
5502:
5494:
5490:
5484:
5483:
5478:
5474:
5472:
5467:
5456:
5439:
5436:
5433:
5430:
5427:
5424:
5421:
5418:
5415:
5412:
5409:
5406:
5403:
5400:
5397:
5394:
5391:
5388:
5385:
5382:
5379:
5376:
5373:
5370:
5367:
5364:
5362:
5354:
5351:
5345:
5339:
5336:
5333:
5330:
5324:
5318:
5315:
5312:
5309:
5303:
5297:
5294:
5291:
5288:
5282:
5276:
5273:
5270:
5267:
5261:
5255:
5252:
5249:
5246:
5240:
5234:
5231:
5229:
5221:
5215:
5202:
5189:
5184:
5177:
5171:
5163:
5160:
5157:
5153:
5127:
5124:
5119:
5116:
5108:
5105:
5102:
5098:
5087:
5081:
5064:
5061:
5053:
5049:
5042:
5022:
5019:
5016:
5010:
5004:
4996:
4992:
4969:
4964:
4957:
4951:
4943:
4940:
4937:
4933:
4929:
4926:
4921:
4918:
4913:
4909:
4906:
4903:
4899:
4894:
4891:
4888:
4884:
4880:
4874:
4868:
4861:
4860:
4859:
4857:
4853:
4852:
4847:
4840:
4836:
4829:
4822:
4815:
4680:
4671:
4663:
4637:
4634:
4627:
4621:
4618:
4611:
4605:
4602:
4595:
4589:
4586:
4579:
4573:
4570:
4563:
4557:
4554:
4547:
4541:
4538:
4531:
4525:
4522:
4515:
4509:
4506:
4499:
4493:
4490:
4483:
4477:
4474:
4467:
4461:
4458:
4451:
4445:
4442:
4435:
4429:
4426:
4419:
4413:
4410:
4403:
4397:
4394:
4387:
4381:
4378:
4371:
4365:
4362:
4355:
4349:
4346:
4339:
4333:
4330:
4320:
4319:
4318:
4301:
4295:
4292:
4285:
4279:
4276:
4269:
4263:
4260:
4253:
4247:
4244:
4237:
4231:
4228:
4221:
4215:
4212:
4205:
4199:
4196:
4189:
4183:
4180:
4173:
4167:
4164:
4157:
4151:
4148:
4141:
4135:
4132:
4125:
4119:
4116:
4109:
4103:
4100:
4093:
4087:
4084:
4077:
4071:
4068:
4061:
4055:
4052:
4045:
4039:
4036:
4029:
4023:
4020:
4013:
4007:
4004:
3997:
3991:
3988:
3978:
3977:
3976:
3972:
3966:
3964:
3956:
3946:
3942:
3935:
3931:
3924:
3920:
3915:
3911:
3906:
3900:
3896:
3882:
3875:
3868:
3863:
3859:
3852:
3848:
3844:
3838:
3834:
3828:
3826:
3799:
3796:
3793:
3787:
3781:
3776:
3773:
3770:
3766:
3758:
3757:
3756:
3748:
3718:
3713:
3702:
3696:
3693:
3690:
3681:
3677:
3674:
3669:
3657:
3654:
3651:
3642:
3638:
3635:
3630:
3618:
3615:
3612:
3603:
3599:
3596:
3591:
3582:
3576:
3573:
3570:
3561:
3557:
3554:
3549:
3540:
3534:
3531:
3525:
3513:
3510:
3504:
3501:
3498:
3489:
3485:
3482:
3477:
3468:
3462:
3459:
3456:
3447:
3443:
3440:
3435:
3426:
3420:
3417:
3414:
3405:
3401:
3398:
3393:
3381:
3378:
3375:
3366:
3362:
3359:
3354:
3342:
3339:
3334:
3323:
3319:
3316:
3309:
3306:
3300:
3297:
3294:
3285:
3282:
3279:
3273:
3269:
3266:
3259:
3256:
3250:
3247:
3244:
3235:
3229:
3225:
3222:
3215:
3212:
3206:
3203:
3200:
3191:
3185:
3181:
3178:
3171:
3168:
3162:
3159:
3156:
3145:
3137:
3131:
3104:
3100:
3097:
3092:
3083:
3077:
3073:
3070:
3063:
3060:
3037:
3033:
3030:
3025:
3016:
3010:
3007:
3001:
2998:
2975:
2969:
2965:
2962:
2959:
2952:
2949:
2943:
2940:
2937:
2926:
2921:
2918:
2915:
2907:
2901:
2895:
2888:
2887:
2886:
2869:
2862:
2859:
2854:
2851:
2848:
2845:
2841:
2834:
2831:
2828:
2817:
2812:
2809:
2806:
2798:
2792:
2768:
2762:
2756:
2749:
2748:
2747:
2743:
2739:
2732:
2728:
2724:
2697:
2693:
2690:
2683:
2680:
2677:
2674:
2669:
2665:
2660:
2656:
2650:
2645:
2642:
2639:
2631:
2625:
2597:
2596:
2595:
2593:
2589:
2579:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2542:
2539:
2533:
2529:
2525:
2517:
2514:
2511:
2507:
2499:
2495:
2491:
2483:
2480:
2477:
2473:
2469:
2461:
2457:
2451:
2447:
2440:
2437:
2431:
2425:
2416:
2398:
2395:
2389:
2386:
2380:
2374:
2371:
2365:
2362:
2359:
2350:
2347:
2341:
2338:
2325:
2322:
2316:
2313:
2306:
2303:
2297:
2292:
2288:
2281:
2278:
2272:
2266:
2259:
2258:
2252:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2206:
2201:
2180:
2176:
2168:
2164:
2160:
2155:
2152:
2148:
2144:
2140:
2132:
2128:
2124:
2119:
2116:
2112:
2107:
2099:
2095:
2091:
2086:
2083:
2079:
2075:
2070:
2061:
2053:
2049:
2045:
2040:
2037:
2033:
2029:
2025:
2017:
2013:
2009:
2004:
2001:
1997:
1992:
1984:
1980:
1976:
1971:
1968:
1964:
1956:
1952:
1946:
1942:
1938:
1931:
1927:
1921:
1917:
1909:
1905:
1899:
1895:
1889:
1880:
1872:
1868:
1864:
1859:
1856:
1852:
1844:
1840:
1834:
1830:
1826:
1822:
1814:
1810:
1806:
1801:
1798:
1794:
1786:
1782:
1776:
1772:
1767:
1759:
1755:
1751:
1746:
1743:
1739:
1731:
1727:
1721:
1717:
1711:
1696:
1692:
1686:
1682:
1675:
1672:
1662:
1658:
1652:
1648:
1641:
1630:
1626:
1620:
1616:
1609:
1604:
1596:
1590:
1579:
1578:
1577:
1573:
1569:
1558:
1550:
1546:
1541:
1540:prime numbers
1535:
1531:
1524:
1517:
1500:
1493:
1489:
1483:
1479:
1475:
1468:
1464:
1458:
1454:
1446:
1442:
1436:
1432:
1428:
1425:
1415:
1410:
1400:
1397:
1391:
1387:
1381:
1375:
1368:
1364:
1361:
1357:
1353:
1349:
1345:
1330:
1326:
1319:
1315:
1311:
1303:
1299:
1289:
1271:
1267:
1260:
1257:
1251:
1248:
1244:
1238:
1234:
1230:
1224:
1221:
1218:
1210:
1207:
1204:
1200:
1196:
1191:
1188:
1185:
1181:
1177:
1172:
1168:
1164:
1160:
1155:
1151:
1147:
1143:
1136:
1135:
1134:
1130:
1126:is prime and
1115:
1113:
1104:
1100:
1095:
1089:
1085:
1081:
1063:
1047:
1041:
1037:
1033:
1029:
1025:
1021:
1014:
1010:
998:
995:
979:
975:
971:
968:
965:
960:
956:
952:
947:
943:
922:
914:
894:
890:
884:
880:
876:
869:
865:
859:
855:
847:
843:
837:
833:
829:
826:
806:
800:
796:
790:
786:
777:
774:
769:
765:
759:
755:
751:
745:
741:
735:
731:
722:
719:
714:
710:
704:
700:
692:
688:
682:
678:
669:
666:
661:
657:
651:
647:
643:
637:
631:
622:
620:
612:
611:prime numbers
593:
589:
583:
580:
575:
572:
568:
562:
559:
556:
552:
548:
545:
539:
533:
526:
525:
524:
516:
512:
508:
497:
491:
481:
477:
473:
464:
459:
457:
453:
449:
448:Euler totient
445:
441:
437:
432:
430:
426:
421:
416:
415:
410:
404:
400:
393:
383:
374:
365:
363:
342:
338:
325:
321:
317:
313:
306:
300:
296:
292:
288:
284:
280:
267:
262:
259:gcd(1, 1) = 1
250:
243:
236:
232:. Therefore,
230:gcd(9, 9) = 9
221:
215:
209:
199:
195:
190:
185:
181:
176:in the range
171:
152:
146:
123:
117:
109:
101:
93:
89:
88:number theory
80:
69:
65:
58:
54:
48:
41:
34:
19:
13433:Noncototient
13420:
13416:
13404:
13397:
13386:
13382:
13378:
13298:
13294:
13278:
13257:
13253:
13216:
13184:
13166:
13136:
13113:
13093:
13083:
13079:
13055:
13048:Hardy, G. H.
13018:
12986:
12957:
12932:
12880:
12874:
12870:
12866:
12833:
12806:, New York:
12802:
12785:
12781:
12779:
12771:
12769:
12743:
12737:
12728:
12703:
12699:
12693:
12689:
12685:
12678:
12653:
12649:
12643:
12636:
12632:
12621:
12612:
12605:
12600:
12591:
12562:
12553:
12544:
12535:
12514:
12505:
12452:
12448:
12402:
12396:
12386:
12377:
12327:
12318:
12291:
12273:
12257:(1): 64–94.
12254:
12250:
12239:
12227:
12214:
12202:
12190:
12178:
12166:
12154:
12126:
12122:
12116:
12097:
12093:
12064:
12060:
12047:
12026:
12003:
11979:
11970:
11961:
11950:
11935:
11929:
11917:
11913:
11908:
11899:
11890:
11882:
11877:
11863:
11859:
11852:
11848:
11842:
11832:
11827:
11818:
11782:
11778:
11766:
11762:
11753:
11740:
11728:
11716:
11704:
11692:
11681:. Retrieved
11678:Khan Academy
11677:
11668:
11583:
11565:
11561:
11558:
11422:
11414:
11403:
11399:
11395:
11391:
11385:
11381:
11370:
11352:
11348:
11341:
11330:
11326:
11319:
11312:
11308:
11301:
11294:
11287:
11283:
11275:D. H. Lehmer
11268:
11264:
11260:
11253:
11226:
11222:
11215:
11209:
11205:
11199:
11195:
11187:
11183:
11179:
11176:
11169:
11165:
11161:
11155:
11151:
11143:
11124:
11120:
11105:
11101:
11097:
11091:
11087:
11085:, computing
11076:
11030:
11024:
11013:
10998:
10994:
10984:
10981:
10967:Applications
10960:
10956:
10952:
10950:
10924:
10917:
10903:has exactly
10899:
10895:
10891:
10876:
10870:
10861:< 0.55655
10858:
10852:
10845:
10830:
10821:
10810:
10671:
10664:
10661:
10543:
10535:
10528:multiplicity
10527:
10523:
10518:
10514:
10510:
10497:
10495:
10487:
10403:
10298:
10146:
10116:
10110:
10095:
9984:
9784:
9773:
9689:
9574:
9515:
9507:
9500:
9493:
9486:
9475:
9391:
9384:
9381:
9289:
9282:
9278:
9268:
9264:
9261:
9192:
9187:
9185:
9126:
9115:
9111:
9108:
9096:
9092:
9089:
9081:
9076:
8948:
8910:
8789:
8785:
8778:
8746:
8504:
8487:
8480:
8476:
8472:
8468:
8333:
8309:
7025:
7021:
6926:
6922:
6918:
6912:
6908:
6902:
6894:
6887:
6877:
6873:
6861:
6855:
6853:is even for
6848:
6844:
6760:
6557: is odd
6462:
6189:
6185:
6178:
6174:
6156:
6152:
6148:
6138:
6134:
6130:
6119:
6101:
6097:
6090:
6079:
6007:
5986:
5977:
5903:
5899:
5896:
5500:
5492:
5488:
5462:
5203:
5085:
5079:
4984:
4854:
4850:
4845:
4838:
4834:
4827:
4820:
4813:
4678:
4669:
4661:
4655:
4316:
3970:
3967:
3944:
3940:
3938:elements of
3933:
3929:
3922:
3918:
3913:
3909:
3898:
3894:
3880:
3873:
3866:
3861:
3857:
3850:
3846:
3843:cyclic group
3836:
3832:
3829:
3814:
3754:
2990:
2884:
2741:
2737:
2730:
2726:
2719:
2716:
2585:
2417:
2413:
2202:
2199:
1571:
1567:
1556:
1554:. (The case
1548:
1544:
1533:
1529:
1522:
1515:
1413:
1406:
1395:
1389:
1385:
1379:
1373:
1366:
1362:
1359:
1355:
1351:
1347:
1343:
1328:
1324:
1317:
1313:
1309:
1301:
1297:
1287:
1286:
1128:
1121:
1102:
1098:
1087:
1083:
1079:
1045:
1039:
1035:
1031:
1027:
1023:
1019:
1012:
1008:
1004:
996:
623:
608:
522:
510:
506:
503:
490:prime factor
479:
475:
471:
462:
460:
451:
447:
443:
439:
433:
429:phi function
428:
424:
419:
412:
402:
398:
391:
381:
371:
298:
294:
290:
286:
282:
278:
263:
248:
241:
234:
219:
216:
197:
193:
183:
179:
169:
91:
85:
78:
67:
63:
56:
52:
12656:: 177–185.
12449:Ramanujan J
12123:Mathematika
11934:"totient".
10872:Ford (1999)
9105:Growth rate
8199: prime
7032:radical of
6422:where
6204:RSA problem
5969:lower limit
5910:upper bound
5459:Some values
5204:An example:
4997:defined by
3888:coprime to
3751:Divisor sum
2740:∈ {1, ...,
1341:, that is,
407:comes from
13463:Categories
13428:Nontotient
13241:1079.11001
13207:1151.11300
13159:0856.11001
13041:1058.11001
13008:0836.00001
12921:0978.11053
12856:0873.11070
12826:Bach, Eric
12765:References
12720:0668.10006
12670:0436.10002
12497:0914.11053
12429:0772.11001
12334:, thm. 332
12234:, thm. 436
12209:, thm. 327
12197:, thm. 326
12173:, thm. 309
12161:, thm. 288
12136:2303.14043
12039:0146.06003
11998:, thm. 328
11831:L. Euler,
11757:L. Euler "
11721:Long (1972
11697:Long (1972
11683:2016-02-26
11355:) ≥ 298848
11281:such that
11273:. In 1932
11118:such that
10537:nontotient
10508:for which
10305:Sierpiński
8691:values of
8506:values of
6916:such that
6899:such that
3959:primitive
935:(that is,
523:It states
246:since for
13285:EMS Press
13106:77-171950
12897:0003-486X
12712:0028-9825
12662:0028-9825
12489:1382-4090
12462:1104.3264
12421:0022-314X
11538:
11527:π
11521:
11515:−
11512:γ
11498:γ
11481:
11475:
11467:γ
11444:φ
11324:and that
11123:≡ 1 (mod
10972:Cyclotomy
10778:⋅
10763:ζ
10749:ζ
10737:ζ
10715:≤
10703:φ
10632:
10626:
10620:
10568:
10468:…
10427:φ
10384:…
10346:φ
10326:φ
10277:∞
10255:φ
10235:φ
10191:φ
10171:φ
10058:
10052:
10025:
9967:∞
9964:→
9929:
9923:
9896:
9865:π
9832:φ
9826:⋯
9811:φ
9796:φ
9741:
9735:
9727:γ
9701:φ
9665:for
9651:
9645:
9627:
9621:
9612:γ
9586:φ
9539:φ
9456:γ
9453:−
9439:
9433:
9412:φ
9382:true for
9336:σ
9324:φ
9307:π
9244:∞
9241:→
9234:δ
9231:−
9210:φ
9147:φ
9046:−
9015:−
8988:φ
8980:∞
8965:∑
8919:ℜ
8884:ζ
8873:−
8864:ζ
8833:φ
8825:∞
8810:∑
8731:∞
8728:→
8702:≤
8621:φ
8514:φ
8430:φ
8412:−
8388:≤
8382:≤
8346:∑
8268:
8229:−
8211:
8191:∑
8187:−
8184:γ
8175:
8155:π
8137:ζ
8112:φ
8086:∑
8040:
8011:
8002:−
7987:π
7969:ζ
7944:φ
7918:∑
7872:
7866:
7839:
7808:π
7763:μ
7740:∑
7718:φ
7695:∑
7650:
7644:
7617:
7576:π
7555:φ
7535:∑
7489:
7483:
7456:
7415:π
7364:μ
7344:∑
7305:φ
7285:∑
7253:for
7239:φ
7174:−
7168:≤
7162:≤
7153:∑
7118:φ
7094:φ
7074:μ
7062:∣
7055:∑
6997:
6977:
6968:φ
6944:φ
6820:⋅
6796:
6790:⋅
6772:
6739:φ
6736:⋅
6724:φ
6700:
6691:φ
6688:⋅
6667:
6658:φ
6626:φ
6618:−
6586:φ
6534:φ
6503:φ
6474:φ
6435:
6405:φ
6396:⋅
6384:φ
6372:φ
6354:φ
6327:−
6311:φ
6308:∣
6275:φ
6272:∣
6260:φ
6256:⟹
6249:∣
6050:≡
6036:φ
5940:≥
5928:φ
5431:⋅
5419:⋅
5407:⋅
5401:−
5395:⋅
5383:⋅
5377:−
5371:⋅
5352:⋅
5340:μ
5331:⋅
5319:μ
5310:⋅
5298:μ
5289:⋅
5277:μ
5268:⋅
5256:μ
5247:⋅
5235:μ
5216:φ
5172:μ
5161:∣
5154:∑
5120:−
5106:∣
5099:∏
5043:μ
5020:−
5005:μ
4952:μ
4941:∣
4934:∑
4914:⋅
4900:μ
4892:∣
4885:∑
4869:φ
4843:for each
3782:φ
3774:∣
3767:∑
3697:⋅
3658:⋅
3636:−
3619:⋅
3597:−
3583:−
3577:⋅
3541:−
3535:⋅
3511:−
3505:⋅
3469:−
3463:⋅
3441:−
3427:−
3421:⋅
3399:−
3382:⋅
3343:⋅
3320:π
3310:
3283:⋯
3270:π
3260:
3226:π
3216:
3182:π
3172:
3132:φ
3098:−
3074:π
3064:
3008:π
3002:
2963:π
2953:
2912:∑
2896:φ
2852:π
2846:−
2803:∑
2757:φ
2681:π
2675:−
2666:⋅
2636:∑
2558:⋅
2552:⋅
2546:⋅
2530:−
2515:−
2496:−
2481:−
2441:φ
2426:φ
2381:⋅
2366:⋅
2342:−
2317:−
2282:φ
2267:φ
2230:…
2156:−
2145:⋯
2120:−
2087:−
2041:−
2030:⋯
2005:−
1972:−
1939:⋯
1860:−
1827:⋯
1802:−
1747:−
1676:φ
1673:⋯
1642:φ
1610:φ
1591:φ
1542:and each
1476:⋯
1252:−
1222:−
1208:−
1189:−
1178:−
1144:φ
1094:bijection
969:…
877:⋯
797:−
775:−
752:⋯
742:−
720:−
689:−
667:−
632:φ
613:dividing
576:−
560:∣
553:∏
534:φ
463:cototient
434:In 1879,
208:totatives
147:ϕ
118:φ
98:that are
13324:Archived
13306:Archived
13141:Springer
13135:(1996),
13126:77-81766
13054:(1979),
13017:(2004),
12985:(1994),
12956:(1965),
12937:Springer
12931:(1986),
12832:(1996),
12800:(1964),
12641:divides
12025:(1963).
11922:page 361
11898:(1929).
11602:See also
11598:primes.
11292:divides
11148:, where
10850:exceeds
10301:Schinzel
10299:In 1954
9957:as
9514:log log
9512:. Since
9273:and the
7795:⌋
7782:⌊
7391:⌋
7378:⌊
6885:For any
6160:, where
6142:, where
5985:log log
3957:and the
3905:subgroup
1331:) > 1
1290:: Since
1096:between
13479:Algebra
13287:, 2001
13169:, MAA,
12913:1715326
11944:. 1989.
11881:Gauss,
11591:is the
11412:above.
11344:> 10
11322:> 10
11203:, then
11194:0 <
11150:0 <
11047:in the
11044:A003401
10959:, then
10836:
10818:
10524:valency
10137:
10123:
9985:due to
9186:but as
8314:is the
8310:(where
7030:is the
6222:. Only
6172:modulo
6126:inverse
6110:of the
6106:is the
5991:
5974:
5469:in the
5466:A000010
5145:to get
4989:is the
4809:
4797:
4793:
4781:
4777:
4765:
4761:
4749:
4745:
4733:
4729:
4717:
4713:
4701:
4697:
4685:
4674:
4658:
3878:, then
2746:. Then
2590:of the
2255:Example
1358:, ...,
1316:, ...,
1133:, then
1110:by the
1062:coprime
1017:, then
911:is the
440:totient
322:of the
307:of the
244:(1) = 1
237:(9) = 6
13260:(8(1))
13239:
13229:
13225:–327.
13205:
13195:
13173:
13157:
13147:
13124:
13104:
13068:
13039:
13029:
13006:
12996:
12964:
12943:
12919:
12911:
12905:121103
12903:
12895:
12854:
12844:
12814:
12750:
12718:
12710:
12668:
12660:
12495:
12487:
12477:
12427:
12419:
12306:
12037:
11596:120569
11587:120569
11573:where
11569:120569
11408:. See
11333:) ≥ 14
10522:. The
9387:> 1
9195:> 0
9127:First
9079:|
8469:where
8308:
8075:
7907:
7142:
7022:where
6897:> 6
6890:> 1
5908:is an
4993:, the
4985:where
3529:
2725:= gcd(
2717:where
1576:gives
1513:where
1416:> 1
1333:is if
819:where
446:, the
12901:JSTOR
12457:arXiv
12131:arXiv
12057:(PDF)
11846:Both
11661:Notes
11339:then
11315:) ≥ 7
11198:<
11186:(mod
11168:(mod
11154:<
10829:(log
10406:dense
10098:"Big
9491:, so
9476:Here
6835:(see
6108:order
6020:then
5503:≤ 100
3871:with
1521:<
1288:Proof
1015:) = 1
450:, or
409:Gauss
320:units
316:group
314:(the
305:order
72:when
13227:ISBN
13193:ISBN
13171:ISBN
13145:ISBN
13122:LCCN
13102:LCCN
13066:ISBN
13027:ISBN
12994:ISBN
12962:ISBN
12941:ISBN
12893:ISSN
12842:ISBN
12812:ISBN
12770:The
12748:ISBN
12708:ISSN
12692:) =
12658:ISSN
12485:ISSN
12475:ISBN
12417:ISSN
12304:ISBN
11857:and
11744:See
11581:and
11459:<
11423:The
11398:) ≠
11346:and
11267:) =
11133:and
11114:and
11095:and
11081:and
11049:OEIS
11037:are
10898:) =
10517:) =
10303:and
9993:and
9713:<
9690:and
9672:>
9598:>
9498:and
9361:<
9318:<
9124:'."
8949:The
8931:>
8798:as:
8783:for
8779:The
8566:>
8479:) =
7260:>
7024:rad(
6929:− 1)
6901:4 ∤
6892:and
6872:2 |
6866:has
6218:and
6155:mod
6137:mod
6120:The
6016:are
6012:and
5499:1 ≤
5497:for
5471:OEIS
5083:and
5035:and
4823:(10)
4816:(20)
3973:= 20
3053:and
2735:for
1538:are
1407:The
1323:gcd(
1306:are
1296:gcd(
1106:and
1082:| =
1048:Let
1034:) =
1007:gcd(
461:The
324:ring
285:) =
272:and
228:and
192:gcd(
178:1 ≤
81:− 1.
13258:A50
13237:Zbl
13223:179
13203:Zbl
13155:Zbl
13086:(4)
13084:146
13037:Zbl
13004:Zbl
12917:Zbl
12885:doi
12881:150
12873:",
12852:Zbl
12786:nnn
12716:Zbl
12698:".
12696:− 1
12688:·φ(
12666:Zbl
12648:".
12646:− 1
12630:if
12493:Zbl
12467:doi
12425:Zbl
12407:doi
12296:doi
12259:doi
12141:doi
12102:doi
12069:doi
12035:Zbl
11870:phi
11775:ed.
11577:is
11535:log
11518:log
11478:log
11472:log
11297:− 1
11271:− 1
11254:If
11016:− 1
10927:= 1
10879:≥ 2
10676:is
10629:log
10623:log
10617:log
10565:log
10548:is
10526:or
10404:is
10229:sup
10226:lim
10218:and
10165:inf
10162:lim
10121:is
10114:).
10055:log
10049:log
10022:log
9926:log
9920:log
9893:log
9738:log
9732:log
9648:log
9642:log
9624:log
9618:log
9533:inf
9530:lim
9480:is
9436:log
9430:log
9406:inf
9403:lim
9141:sup
9138:lim
8717:as
8581:.
8403:gcd
8353:gcd
8265:log
8208:log
8172:log
8133:315
8037:log
8008:log
7965:315
7869:log
7863:log
7836:log
7647:log
7641:log
7614:log
7486:log
7480:log
7453:log
6994:rad
6974:rad
6911:≥ 2
6858:≥ 3
6793:gcd
6769:lcm
6697:gcd
6664:lcm
6432:gcd
6168:of
6057:mod
5906:− 1
5889:40
5859:90
5854:24
5824:80
5819:32
5789:70
5784:24
5754:60
5749:16
5719:50
5714:20
5684:40
5679:16
5649:30
5614:20
5579:10
5539:10
5088:≥ 2
4830:(5)
3876:= 1
3865:= ⟨
3819:of
3307:cos
3289:gcd
3257:cos
3239:gcd
3213:cos
3195:gcd
3169:cos
3151:gcd
3061:cos
2999:cos
2950:cos
2932:gcd
2823:gcd
2592:gcd
1559:= 1
1552:≥ 1
1354:, 3
1350:, 2
1346:∈ {
1308:1,
1131:≥ 1
1122:If
915:of
621:.)
465:of
394:= 1
318:of
251:= 1
222:= 9
210:of
139:or
110:as
108:phi
102:to
86:In
33:Phi
13465::
13283:,
13277:,
13256:,
13252:,
13235:.
13201:,
13153:,
13143:,
13120:,
13100:,
13082:,
13064:,
13050:;
13035:,
13025:,
13002:,
12981:;
12977:;
12939:,
12915:,
12909:MR
12907:,
12899:,
12891:,
12879:,
12850:,
12840:,
12828:;
12810:,
12796:;
12788:.
12714:.
12664:.
12654:28
12523:^
12491:.
12483:.
12473:.
12465:.
12437:^
12423:.
12415:.
12403:43
12401:.
12395:.
12365:^
12353:^
12339:^
12302:.
12282:^
12253:.
12249:.
12139:,
12127:69
12125:,
12098:15
12096:.
12092:.
12080:^
12065:10
12063:,
12059:,
12033:.
12012:^
11988:^
11916:,
11806:^
11777:,
11773:,
11676:.
11564:≥
11389:,
11384:≠
11379:,
11357:.
11290:)
11235:.
11213:.
11208:=
11182:=
11174:.
11164:=
11121:ed
11100:=
11092:pq
11090:=
11051:).
10937:.
10929:.
10863:.
10843:.
10669:.
10496:A
10139:.
9560:0.
9505:.
9484:,
9287:.
9101:.
9087:.
8946:.
8771:.
8497:.
8318:).
7043:).
6921:|
6860:.
6839:).
6151:↦
6133:↦
6117:.
6088:.
5994:.
5902:=
5886:60
5883:42
5880:96
5877:32
5874:72
5871:46
5868:60
5865:44
5862:72
5851:88
5848:40
5845:56
5842:42
5839:64
5836:24
5833:82
5830:40
5827:54
5816:78
5813:24
5810:60
5807:36
5804:40
5801:36
5798:72
5795:24
5792:70
5781:44
5778:32
5775:66
5772:20
5769:48
5766:32
5763:36
5760:30
5757:60
5746:58
5743:28
5740:36
5737:24
5734:40
5731:18
5728:52
5725:24
5722:32
5711:42
5708:16
5705:46
5702:22
5699:24
5696:20
5693:42
5690:12
5687:40
5676:24
5673:18
5670:36
5667:12
5664:24
5661:16
5658:20
5655:16
5652:30
5644:8
5641:28
5638:12
5635:18
5632:12
5629:20
5623:22
5620:10
5617:12
5609:8
5606:18
5600:16
5588:12
5582:10
5574:4
5544:0
5509:+
5440:8.
5386:10
5374:20
5346:20
5325:10
5271:10
5250:20
5222:20
4851:n.
4806:20
4800:19
4795:,
4790:20
4784:17
4779:,
4774:20
4768:13
4763:,
4758:20
4752:11
4747:,
4742:20
4731:,
4726:20
4715:,
4710:20
4699:,
4694:20
4622:20
4619:19
4606:10
4590:20
4587:17
4542:10
4526:20
4523:13
4494:20
4491:11
4462:20
4430:20
4414:10
4366:20
4350:10
4334:20
4296:20
4293:20
4280:20
4277:19
4264:20
4261:18
4248:20
4245:17
4232:20
4229:16
4216:20
4213:15
4200:20
4197:14
4184:20
4181:13
4168:20
4165:12
4152:20
4149:11
4136:20
4133:10
4120:20
4104:20
4088:20
4072:20
4056:20
4040:20
4024:20
4008:20
3992:20
3965:.
3917:⊆
3719:4.
3694:10
3324:10
3317:20
3301:10
3295:10
3274:10
3251:10
3230:10
3207:10
3186:10
3163:10
3138:10
2567:8.
2432:20
2399:8.
2363:20
2307:20
2273:20
1399:.
1388:−
1365:=
1327:,
1312:,
1300:,
1114:.
1101:×
1074:mn
1072:,
1068:,
1056:,
1052:,
1044:.
1040:mn
1026:)
1011:,
515:.
496:.
474:−
454:.
431:.
420:φA
382:πD
364:.
283:mn
261:.
214:.
196:,
182:≤
90:,
13423:)
13421:n
13419:(
13417:λ
13407:)
13405:n
13403:(
13400:k
13398:J
13389:)
13387:n
13385:(
13383:φ
13362:e
13355:t
13348:v
13301:)
13299:n
13297:(
13295:φ
13262:.
13243:.
13088:.
12924:.
12887::
12871:m
12867:x
12756:.
12722:.
12704:6
12694:n
12690:n
12686:M
12672:.
12644:n
12639:)
12637:n
12635:(
12633:φ
12628:n
12584:n
12580:n
12572:n
12568:n
12499:.
12469::
12459::
12453:2
12431:.
12409::
12312:.
12298::
12267:.
12261::
12255:6
12143::
12133::
12110:.
12104::
12071::
12041:.
11924:.
11918:2
11872:.
11866:)
11864:n
11862:(
11860:ϕ
11855:)
11853:n
11851:(
11849:φ
11799:N
11795:N
11791:n
11767:8
11748:.
11686:.
11644:n
11589:#
11584:p
11575:γ
11571:#
11566:p
11562:n
11541:n
11530:)
11524:4
11509:+
11506:4
11503:(
11494:e
11487:+
11484:n
11463:e
11453:)
11450:n
11447:(
11440:n
11406:)
11404:n
11402:(
11400:φ
11396:m
11394:(
11392:φ
11386:n
11382:m
11377:m
11373:n
11353:n
11351:(
11349:ω
11342:n
11337:n
11331:n
11329:(
11327:ω
11320:n
11313:n
11311:(
11309:ω
11304:n
11295:n
11288:n
11286:(
11284:φ
11279:n
11269:p
11265:p
11263:(
11261:φ
11256:p
11233:n
11229:)
11227:n
11225:(
11223:φ
11218:n
11210:m
11206:t
11200:n
11196:t
11190:)
11188:n
11184:S
11180:t
11172:)
11170:n
11166:m
11162:S
11156:n
11152:m
11146:m
11139:d
11135:e
11131:n
11127:)
11125:k
11116:d
11112:e
11108:)
11106:n
11104:(
11102:φ
11098:k
11088:n
11083:q
11079:p
11035:n
11031:n
11027:n
11014:n
11009:n
11005:n
11001:)
10999:n
10997:(
10995:φ
10990:n
10961:n
10957:n
10953:n
10935:m
10925:k
10920:m
10905:k
10900:m
10896:n
10894:(
10892:φ
10887:k
10883:m
10877:k
10859:δ
10853:m
10848:m
10841:k
10833:)
10831:x
10826:/
10822:x
10813:R
10796:)
10793:x
10790:(
10787:R
10784:+
10781:x
10772:)
10769:6
10766:(
10758:)
10755:3
10752:(
10746:)
10743:2
10740:(
10731:=
10726:|
10721:}
10718:x
10712:)
10709:n
10706:(
10700::
10697:n
10694:{
10689:|
10674:x
10665:C
10643:2
10639:)
10635:x
10614:(
10609:)
10604:)
10601:1
10598:(
10595:o
10592:+
10589:C
10584:(
10578:e
10571:x
10561:x
10546:x
10532:m
10519:m
10515:n
10513:(
10511:φ
10506:n
10502:m
10472:}
10465:,
10462:2
10459:,
10456:1
10453:=
10450:n
10445:,
10440:n
10436:)
10433:n
10430:(
10420:{
10388:}
10381:,
10378:2
10375:,
10372:1
10369:=
10366:n
10361:,
10355:)
10352:n
10349:(
10341:)
10338:1
10335:+
10332:n
10329:(
10319:{
10280:.
10274:=
10264:)
10261:n
10258:(
10250:)
10247:1
10244:+
10241:n
10238:(
10213:0
10210:=
10200:)
10197:n
10194:(
10186:)
10183:1
10180:+
10177:n
10174:(
10133:π
10129:/
10126:6
10111:n
10106:n
10102:"
10100:O
10080:)
10073:3
10070:1
10065:)
10061:n
10046:(
10040:3
10037:2
10032:)
10028:n
10019:(
10016:n
10012:(
10008:O
9970:,
9961:n
9951:)
9944:3
9941:4
9936:)
9932:n
9917:(
9911:3
9908:2
9903:)
9899:n
9890:(
9887:n
9883:(
9879:O
9876:+
9869:2
9858:2
9854:n
9850:3
9844:=
9841:)
9838:n
9835:(
9829:+
9823:+
9820:)
9817:2
9814:(
9808:+
9805:)
9802:1
9799:(
9759:.
9756:n
9744:n
9723:e
9718:n
9710:)
9707:n
9704:(
9675:2
9669:n
9654:n
9638:3
9633:+
9630:n
9608:e
9603:n
9595:)
9592:n
9589:(
9557:=
9552:n
9548:)
9545:n
9542:(
9516:n
9501:e
9494:e
9487:γ
9478:γ
9461:.
9449:e
9445:=
9442:n
9425:n
9421:)
9418:n
9415:(
9385:n
9367:,
9364:1
9354:2
9350:n
9345:)
9342:n
9339:(
9333:)
9330:n
9327:(
9311:2
9303:6
9285:)
9283:n
9281:(
9279:σ
9271:)
9269:n
9267:(
9265:φ
9247:.
9228:1
9224:n
9219:)
9216:n
9213:(
9193:δ
9188:n
9171:,
9168:1
9165:=
9160:n
9156:)
9153:n
9150:(
9122:n
9118:)
9116:n
9114:(
9112:φ
9099:)
9097:n
9095:(
9093:φ
9082:q
9057:2
9053:)
9049:q
9043:1
9040:(
9036:q
9031:=
9023:n
9019:q
9012:1
9005:n
9001:q
8997:)
8994:n
8991:(
8975:1
8972:=
8969:n
8934:2
8928:)
8925:s
8922:(
8893:)
8890:s
8887:(
8879:)
8876:1
8870:s
8867:(
8858:=
8851:s
8847:n
8842:)
8839:n
8836:(
8820:1
8817:=
8814:n
8792:)
8790:n
8788:(
8786:φ
8755:q
8743:.
8725:x
8705:x
8699:n
8679:)
8676:x
8673:(
8670:o
8650:n
8630:)
8627:n
8624:(
8617:|
8613:q
8593:q
8569:1
8563:q
8543:q
8523:)
8520:n
8517:(
8495:n
8490:)
8488:n
8486:(
8484:0
8481:σ
8477:n
8475:(
8473:d
8454:,
8451:)
8448:n
8445:(
8442:d
8439:)
8436:n
8433:(
8427:=
8424:)
8421:n
8418:,
8415:1
8409:k
8406:(
8391:n
8385:k
8379:1
8374:1
8371:=
8368:)
8365:n
8362:,
8359:k
8356:(
8312:γ
8295:)
8290:n
8283:3
8280:2
8275:)
8271:n
8262:(
8256:(
8252:O
8249:+
8245:)
8238:1
8235:+
8232:p
8224:2
8220:p
8214:p
8195:p
8181:+
8178:n
8168:(
8159:4
8151:2
8146:)
8143:3
8140:(
8127:=
8121:)
8118:k
8115:(
8108:1
8101:n
8096:1
8093:=
8090:k
8062:)
8055:3
8052:2
8047:)
8043:n
8034:(
8030:(
8026:O
8023:+
8018:2
8014:n
7999:n
7991:4
7983:2
7978:)
7975:3
7972:(
7959:=
7953:)
7950:k
7947:(
7940:k
7933:n
7928:1
7925:=
7922:k
7894:)
7887:3
7884:4
7879:)
7875:n
7860:(
7854:3
7851:2
7846:)
7842:n
7833:(
7829:(
7825:O
7822:+
7819:n
7812:2
7804:6
7799:=
7790:k
7787:n
7776:k
7772:)
7769:k
7766:(
7755:n
7750:1
7747:=
7744:k
7736:=
7731:k
7727:)
7724:k
7721:(
7710:n
7705:1
7702:=
7699:k
7672:)
7665:3
7662:1
7657:)
7653:n
7638:(
7632:3
7629:2
7624:)
7620:n
7611:(
7608:n
7604:(
7600:O
7597:+
7592:2
7588:n
7580:2
7572:3
7567:=
7564:)
7561:k
7558:(
7550:n
7545:1
7542:=
7539:k
7511:)
7504:3
7501:4
7496:)
7492:n
7477:(
7471:3
7468:2
7463:)
7459:n
7450:(
7447:n
7443:(
7439:O
7436:+
7431:2
7427:n
7419:2
7411:3
7406:=
7402:)
7396:2
7386:k
7383:n
7373:)
7370:k
7367:(
7359:n
7354:1
7351:=
7348:k
7340:+
7337:1
7333:(
7326:2
7323:1
7317:=
7314:)
7311:k
7308:(
7300:n
7295:1
7292:=
7289:k
7263:1
7257:n
7248:)
7245:n
7242:(
7236:n
7230:2
7227:1
7221:=
7218:k
7209:1
7206:=
7203:)
7200:n
7197:,
7194:k
7191:(
7188:d
7185:c
7182:g
7177:1
7171:n
7165:k
7159:1
7127:)
7124:n
7121:(
7114:n
7109:=
7103:)
7100:d
7097:(
7089:)
7086:d
7083:(
7078:2
7065:n
7059:d
7040:n
7034:n
7028:)
7026:n
7006:)
7003:n
7000:(
6989:)
6986:)
6983:n
6980:(
6971:(
6962:=
6957:n
6953:)
6950:n
6947:(
6931:.
6927:a
6925:(
6923:φ
6919:l
6913:n
6909:l
6903:n
6895:n
6888:a
6880:)
6878:n
6876:(
6874:φ
6868:r
6864:n
6856:n
6851:)
6849:n
6847:(
6845:φ
6823:n
6817:m
6814:=
6811:)
6808:n
6805:,
6802:m
6799:(
6787:)
6784:n
6781:,
6778:m
6775:(
6748:)
6745:n
6742:(
6733:)
6730:m
6727:(
6721:=
6718:)
6715:)
6712:n
6709:,
6706:m
6703:(
6694:(
6685:)
6682:)
6679:n
6676:,
6673:m
6670:(
6661:(
6635:)
6632:n
6629:(
6621:1
6615:m
6611:n
6607:=
6603:)
6598:m
6594:n
6590:(
6553:m
6543:)
6540:m
6537:(
6522:m
6512:)
6509:m
6506:(
6500:2
6494:{
6489:=
6486:)
6483:m
6480:2
6477:(
6450:)
6447:n
6444:,
6441:m
6438:(
6429:=
6426:d
6414:)
6411:d
6408:(
6401:d
6393:)
6390:n
6387:(
6381:)
6378:m
6375:(
6369:=
6366:)
6363:n
6360:m
6357:(
6333:)
6330:1
6322:m
6318:a
6314:(
6305:m
6284:)
6281:b
6278:(
6269:)
6266:a
6263:(
6252:b
6246:a
6224:n
6220:q
6216:p
6212:n
6208:n
6200:d
6196:n
6192:)
6190:n
6188:(
6186:φ
6181:)
6179:n
6177:(
6175:φ
6170:e
6162:d
6157:n
6153:b
6149:b
6144:e
6139:n
6135:a
6131:a
6114:n
6104:)
6102:n
6100:(
6098:φ
6082:n
6065:.
6062:n
6053:1
6045:)
6042:n
6039:(
6032:a
6014:n
6010:a
5987:n
5982:/
5978:n
5953:2
5949:/
5945:n
5937:)
5934:n
5931:(
5918:n
5914:n
5904:n
5900:y
5626:8
5603:6
5597:8
5594:8
5591:6
5585:4
5571:6
5568:4
5565:6
5562:2
5559:4
5556:2
5553:2
5550:1
5547:1
5536:9
5533:8
5530:7
5527:6
5524:5
5521:4
5518:3
5515:2
5512:1
5501:n
5495:)
5493:n
5491:(
5489:φ
5437:=
5434:1
5428:0
5425:+
5422:2
5416:1
5413:+
5410:4
5404:1
5398:5
5392:0
5389:+
5380:1
5368:1
5365:=
5355:1
5349:)
5343:(
5337:+
5334:2
5328:)
5322:(
5316:+
5313:4
5307:)
5304:5
5301:(
5295:+
5292:5
5286:)
5283:4
5280:(
5274:+
5265:)
5262:2
5259:(
5253:+
5244:)
5241:1
5238:(
5232:=
5225:)
5219:(
5190:.
5185:d
5181:)
5178:d
5175:(
5164:n
5158:d
5133:)
5128:p
5125:1
5117:1
5114:(
5109:n
5103:p
5086:k
5080:p
5065:0
5062:=
5059:)
5054:k
5050:p
5046:(
5023:1
5017:=
5014:)
5011:p
5008:(
4987:μ
4970:,
4965:d
4961:)
4958:d
4955:(
4944:n
4938:d
4930:n
4927:=
4922:d
4919:n
4910:)
4907:d
4904:(
4895:n
4889:d
4881:=
4878:)
4875:n
4872:(
4846:d
4841:)
4839:d
4837:(
4835:φ
4828:φ
4821:φ
4814:φ
4803:/
4787:/
4771:/
4755:/
4739:/
4736:9
4723:/
4720:7
4707:/
4704:3
4691:/
4688:1
4679:d
4670:d
4666:/
4662:k
4638:1
4635:1
4628:,
4612:,
4603:9
4596:,
4580:,
4574:5
4571:4
4564:,
4558:4
4555:3
4548:,
4539:7
4532:,
4516:,
4510:5
4507:3
4500:,
4484:,
4478:2
4475:1
4468:,
4459:9
4452:,
4446:5
4443:2
4436:,
4427:7
4420:,
4411:3
4404:,
4398:4
4395:1
4388:,
4382:5
4379:1
4372:,
4363:3
4356:,
4347:1
4340:,
4331:1
4302:.
4286:,
4270:,
4254:,
4238:,
4222:,
4206:,
4190:,
4174:,
4158:,
4142:,
4126:,
4117:9
4110:,
4101:8
4094:,
4085:7
4078:,
4069:6
4062:,
4053:5
4046:,
4037:4
4030:,
4021:3
4014:,
4005:2
3998:,
3989:1
3971:n
3961:d
3953:n
3945:n
3941:C
3936:)
3934:d
3932:(
3930:φ
3923:n
3919:C
3914:d
3910:C
3899:n
3895:C
3890:d
3886:k
3881:g
3874:g
3869:⟩
3867:g
3862:d
3858:C
3851:d
3847:C
3839:)
3837:d
3835:(
3833:φ
3821:n
3817:d
3800:,
3797:n
3794:=
3791:)
3788:d
3785:(
3777:n
3771:d
3745:n
3741:n
3737:n
3714:=
3706:)
3703:1
3700:(
3691:+
3688:)
3682:4
3678:1
3675:+
3670:5
3661:(
3655:1
3652:+
3649:)
3643:4
3639:1
3631:5
3622:(
3616:2
3613:+
3610:)
3604:4
3600:1
3592:5
3580:(
3574:1
3571:+
3568:)
3562:4
3558:1
3555:+
3550:5
3538:(
3532:2
3526:+
3517:)
3514:1
3508:(
3502:5
3499:+
3496:)
3490:4
3486:1
3483:+
3478:5
3466:(
3460:2
3457:+
3454:)
3448:4
3444:1
3436:5
3424:(
3418:1
3415:+
3412:)
3406:4
3402:1
3394:5
3385:(
3379:2
3376:+
3373:)
3367:4
3363:1
3360:+
3355:5
3346:(
3340:1
3335:=
3304:)
3298:,
3292:(
3286:+
3280:+
3267:6
3254:)
3248:,
3245:3
3242:(
3236:+
3223:4
3210:)
3204:,
3201:2
3198:(
3192:+
3179:2
3166:)
3160:,
3157:1
3154:(
3146:=
3141:)
3135:(
3120::
3105:4
3101:1
3093:5
3084:=
3078:5
3071:2
3038:4
3034:1
3031:+
3026:5
3017:=
3011:5
2976:.
2970:n
2966:k
2960:2
2947:)
2944:n
2941:,
2938:k
2935:(
2927:n
2922:1
2919:=
2916:k
2908:=
2905:)
2902:n
2899:(
2870:.
2863:n
2860:k
2855:i
2849:2
2842:e
2838:)
2835:n
2832:,
2829:k
2826:(
2818:n
2813:1
2810:=
2807:k
2799:=
2796:]
2793:1
2790:[
2787:}
2783:x
2779:{
2774:F
2769:=
2766:)
2763:n
2760:(
2744:}
2742:n
2738:k
2733:)
2731:n
2729:,
2727:k
2722:k
2720:x
2698:n
2694:k
2691:m
2684:i
2678:2
2670:e
2661:k
2657:x
2651:n
2646:1
2643:=
2640:k
2632:=
2629:]
2626:m
2623:[
2620:}
2616:x
2612:{
2607:F
2564:=
2561:4
2555:1
2549:1
2543:2
2540:=
2537:)
2534:1
2526:5
2523:(
2518:1
2512:1
2508:5
2503:)
2500:1
2492:2
2489:(
2484:1
2478:2
2474:2
2470:=
2467:)
2462:1
2458:5
2452:2
2448:2
2444:(
2438:=
2435:)
2429:(
2396:=
2390:5
2387:4
2375:2
2372:1
2360:=
2357:)
2351:5
2348:1
2339:1
2336:(
2332:)
2326:2
2323:1
2314:1
2311:(
2304:=
2301:)
2298:5
2293:2
2289:2
2285:(
2279:=
2276:)
2270:(
2239:}
2236:n
2233:,
2227:,
2224:2
2221:,
2218:1
2215:{
2181:.
2177:)
2169:r
2165:p
2161:1
2153:1
2149:(
2141:)
2133:2
2129:p
2125:1
2117:1
2113:(
2108:)
2100:1
2096:p
2092:1
2084:1
2080:(
2076:n
2071:=
2062:)
2054:r
2050:p
2046:1
2038:1
2034:(
2026:)
2018:2
2014:p
2010:1
2002:1
1998:(
1993:)
1985:1
1981:p
1977:1
1969:1
1965:(
1957:r
1953:k
1947:r
1943:p
1932:2
1928:k
1922:2
1918:p
1910:1
1906:k
1900:1
1896:p
1890:=
1881:)
1873:r
1869:p
1865:1
1857:1
1853:(
1845:r
1841:k
1835:r
1831:p
1823:)
1815:2
1811:p
1807:1
1799:1
1795:(
1787:2
1783:k
1777:2
1773:p
1768:)
1760:1
1756:p
1752:1
1744:1
1740:(
1732:1
1728:k
1722:1
1718:p
1712:=
1704:)
1697:r
1693:k
1687:r
1683:p
1679:(
1670:)
1663:2
1659:k
1653:2
1649:p
1645:(
1638:)
1631:1
1627:k
1621:1
1617:p
1613:(
1605:=
1600:)
1597:n
1594:(
1574:)
1572:p
1570:(
1568:φ
1563:φ
1557:n
1549:i
1545:k
1534:r
1530:p
1526:2
1523:p
1519:1
1516:p
1501:,
1494:r
1490:k
1484:r
1480:p
1469:2
1465:k
1459:2
1455:p
1447:1
1443:k
1437:1
1433:p
1429:=
1426:n
1414:n
1396:p
1390:p
1386:p
1380:p
1374:p
1369:}
1367:p
1363:p
1360:p
1356:p
1352:p
1348:p
1344:m
1339:p
1335:m
1329:m
1325:p
1318:p
1314:p
1310:p
1304:)
1302:m
1298:p
1292:p
1272:.
1268:)
1261:p
1258:1
1249:1
1245:(
1239:k
1235:p
1231:=
1228:)
1225:1
1219:p
1216:(
1211:1
1205:k
1201:p
1197:=
1192:1
1186:k
1182:p
1173:k
1169:p
1165:=
1161:)
1156:k
1152:p
1148:(
1129:k
1124:p
1108:C
1103:B
1099:A
1090:)
1088:m
1086:(
1084:φ
1080:A
1078:|
1070:n
1066:m
1058:C
1054:B
1050:A
1042:)
1038:(
1036:φ
1032:n
1030:(
1028:φ
1024:m
1022:(
1020:φ
1013:n
1009:m
980:r
976:p
972:,
966:,
961:2
957:p
953:,
948:1
944:p
923:n
895:r
891:k
885:r
881:p
870:2
866:k
860:2
856:p
848:1
844:k
838:1
834:p
830:=
827:n
807:,
804:)
801:1
791:r
787:p
783:(
778:1
770:r
766:k
760:r
756:p
749:)
746:1
736:2
732:p
728:(
723:1
715:2
711:k
705:2
701:p
696:)
693:1
683:1
679:p
675:(
670:1
662:1
658:k
652:1
648:p
644:=
641:)
638:n
635:(
615:n
594:,
590:)
584:p
581:1
573:1
569:(
563:n
557:p
549:n
546:=
543:)
540:n
537:(
513:)
511:n
509:(
507:φ
494:n
486:n
482:)
480:n
478:(
476:φ
472:n
467:n
405:)
403:A
401:(
399:φ
392:D
387:D
377:π
347:Z
343:n
339:/
334:Z
311:n
301:)
299:n
297:(
295:φ
293:)
291:m
289:(
287:φ
281:(
279:φ
274:n
270:m
255:n
249:n
242:φ
235:φ
220:n
212:n
204:k
200:)
198:k
194:n
184:n
180:k
174:k
156:)
153:n
150:(
127:)
124:n
121:(
104:n
96:n
79:p
74:p
70:)
68:p
66:(
64:φ
59:)
57:n
55:(
53:φ
42:.
35:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.