https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=1077400&feedformat=atom AoPS Wiki - User contributions [en] 2021-07-30T13:01:17Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=27120 Euler's totient function 2008-07-22T04:27:46Z <p>1077400: /* Formulas */</p> <hr /> <div>{{WotWAnnounce|week=July 18-July 24}}<br /> <br /> '''Euler's totient function''' &lt;math&gt;\phi(n)&lt;/math&gt; applied to a [[positive integer]] &lt;math&gt;n&lt;/math&gt; is defined to be the number of positive integers less than or equal to &lt;math&gt;n&lt;/math&gt; that are [[relatively prime]] to &lt;math&gt;n&lt;/math&gt;. &lt;math&gt;\phi(n)&lt;/math&gt; is read &quot;phi of n.&quot;<br /> <br /> == Formulas ==<br /> To derive the formula, let us first define the [[prime factorization]] of &lt;math&gt; n &lt;/math&gt; as &lt;math&gt; n =\prod_{i=1}^{m}p_i^{e_i} =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m} &lt;/math&gt; where the &lt;math&gt;p_i &lt;/math&gt; are distinct [[prime number]]s. Now, we can use a [[PIE]] argument to count the number of numbers less than or equal to &lt;math&gt; n &lt;/math&gt; that are relatively prime to it.<br /> <br /> First, let's count the complement of what we want (i.e. all the numbers less than &lt;math&gt; n &lt;/math&gt; that share a common factor with it). There are &lt;math&gt; p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} &lt;/math&gt; numbers less than &lt;math&gt; n &lt;/math&gt; that are divisible by &lt;math&gt; p_1 &lt;/math&gt;. If we do the same for each &lt;math&gt; p_k &lt;/math&gt; and add these up, we get <br /> <br /> &lt;center&gt;&lt;math&gt; p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} + p_1^{e_1}p_2^{e_2-1}\cdots p_m^{e_m} + \cdots + p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m - 1}.&lt;/math&gt;&lt;/center&gt;<br /> <br /> We can factor out, though:<br /> <br /> &lt;center&gt;&lt;math&gt; p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1+p_2+\cdots + p_m).&lt;/math&gt;&lt;/center&gt;<br /> <br /> But we are obviously overcounting. We then subtract out those divisible by two of the &lt;math&gt; p_k &lt;/math&gt;. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is<br /> <br /> &lt;center&gt;&lt;math&gt;p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}[(p_1+p_2+\cdots+p_m)-(p_1p_2+p_1p_3+\cdots+p_{m-1}p_m)+\cdots+(-1)^{m+1}(p_1p_2\cdots p_m)]&lt;/math&gt;&lt;/center&gt;<br /> <br /> which we can factor further as<br /> <br /> &lt;center&gt;&lt;math&gt;p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1-1)(p_2-1)\cdots(p_m-1).&lt;/math&gt;&lt;/center&gt;<br /> <br /> Making one small adjustment, we write this as<br /> <br /> &lt;center&gt;&lt;math&gt; \phi(n) = n\left(1-\frac 1{p_1}\right)\left(1-\frac 1{p_2}\right)\cdots\left(1-\frac 1{p_m}\right).&lt;/math&gt;&lt;/center&gt;<br /> <br /> Given the general [[prime factorization]] of &lt;math&gt;{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}&lt;/math&gt;, one can compute &lt;math&gt;\phi(n)&lt;/math&gt; using the formula &lt;cmath&gt;\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_m}\right)&lt;/cmath&gt;<br /> <br /> == Identities ==<br /> <br /> For [[prime]] p, &lt;math&gt;\phi(p)=p-1&lt;/math&gt;, because all numbers less than &lt;math&gt;{p}&lt;/math&gt; are relatively prime to it.<br /> <br /> For relatively prime &lt;math&gt;{a}, {b}&lt;/math&gt;, &lt;math&gt; \phi{(a)}\phi{(b)} = \phi{(ab)} &lt;/math&gt;.<br /> <br /> In fact, we also have for any &lt;math&gt;{a}, {b}&lt;/math&gt; that &lt;math&gt;\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})&lt;/math&gt;.<br /> <br /> For any &lt;math&gt;n&lt;/math&gt;, we have &lt;math&gt;\sum_{d|n}\phi(d)=n&lt;/math&gt; where the sum is taken over all divisors d of &lt;math&gt; n &lt;/math&gt;.<br /> <br /> ==Notation==<br /> Sometimes, instead of &lt;math&gt;\phi&lt;/math&gt;, &lt;math&gt;\varphi&lt;/math&gt; is used. This variation of the Greek letter ''phi'' is common in textbooks, and is standard usage on the English [[Wikipedia]]<br /> <br /> == See Also ==<br /> <br /> * [[Number theory]]<br /> * [[Prime]]<br /> * [[Euler's Totient Theorem]]<br /> <br /> [[Category:Functions]]<br /> [[Category:Number Theory]]</div> 1077400 https://artofproblemsolving.com/wiki/index.php?title=1983_AIME_Problems&diff=27087 1983 AIME Problems 2008-07-18T03:19:20Z <p>1077400: /* Problem 4 */ Corrected a square root</p> <hr /> <div>== Problem 1 ==<br /> Let &lt;math&gt;x&lt;/math&gt;,&lt;math&gt;y&lt;/math&gt;, and &lt;math&gt;z&lt;/math&gt; all exceed &lt;math&gt;1&lt;/math&gt;, and let &lt;math&gt;w&lt;/math&gt; be a positive number such that &lt;math&gt;\log_xw=24&lt;/math&gt;, &lt;math&gt;\log_y w = 40&lt;/math&gt;, and &lt;math&gt;\log_{xyz}w=12&lt;/math&gt;. Find &lt;math&gt;\log_zw&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 1|Solution]]<br /> <br /> == Problem 2 ==<br /> Let &lt;math&gt;f(x)=|x-p|+|x-15|+|x-p-15|&lt;/math&gt;, where &lt;math&gt;p \leq x \leq 15&lt;/math&gt;. Determine the minimum value taken by &lt;math&gt;f(x)&lt;/math&gt; by &lt;math&gt;x&lt;/math&gt; in the interval &lt;math&gt;0 &lt; p&lt;15&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 2|Solution]]<br /> <br /> == Problem 3 ==<br /> What is the product of the real roots of the equation &lt;math&gt;x^2 + 18x + 30 = 2 \sqrt{x^2 + 18x + 45}&lt;/math&gt;?<br /> <br /> [[1983 AIME Problems/Problem 3|Solution]]<br /> <br /> == Problem 4 ==<br /> A machine shop cutting tool is in the shape of a notched circle, as shown. The radius of the circle is &lt;math&gt;\sqrt{50}&lt;/math&gt; cm, the length of &lt;math&gt;AB&lt;/math&gt; is 6 cm, and that of &lt;math&gt;BC&lt;/math&gt; is 2 cm. The angle &lt;math&gt;ABC&lt;/math&gt; is a right angle. Find the square of the distance (in centimeters) from &lt;math&gt;B&lt;/math&gt; to the center of the circle.<br /> <br /> &lt;asy&gt;<br /> size(150); defaultpen(linewidth(0.65)+fontsize(11));<br /> real r=10;<br /> pair O=(0,0),A=r*dir(45),B=(A.x,A.y-r),C;<br /> path P=circle(O,r);<br /> C=intersectionpoint(B--(B.x+r,B.y),P);<br /> draw(P);<br /> draw(C--B--O--A--B);<br /> dot(O); dot(A); dot(B); dot(C);<br /> label(&quot;$O$&quot;,O,SW);<br /> label(&quot;$A$&quot;,A,NE);<br /> label(&quot;$B$&quot;,B,S);<br /> label(&quot;$C$&quot;,C,SE);<br /> &lt;/asy&gt;<br /> <br /> [[1983 AIME Problems/Problem 4|Solution]]<br /> <br /> == Problem 5 ==<br /> Suppose that the sum of the squares of two complex numbers &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; is &lt;math&gt;7&lt;/math&gt; and the sum of the cubes is &lt;math&gt;10&lt;/math&gt;. What is the largest real value of &lt;math&gt;x + y&lt;/math&gt; can have?<br /> <br /> [[1983 AIME Problems/Problem 5|Solution]]<br /> <br /> == Problem 6 ==<br /> Let &lt;math&gt;a_n&lt;/math&gt; equal &lt;math&gt;6^{n}+8^{n}&lt;/math&gt;. Determine the remainder upon dividing &lt;math&gt;a_ {83}&lt;/math&gt; by &lt;math&gt;49&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 6|Solution]]<br /> <br /> == Problem 7 ==<br /> Twenty five of King Arthur's knights are seated at their customary round table. Three of them are chosen - all choices being equally likely - and are sent off to slay a troublesome dragon. Let &lt;math&gt;P&lt;/math&gt; be the probability that at least two of the three had been sitting next to each other. If &lt;math&gt;P&lt;/math&gt; is written as a fraction in lowest terms, what is the sum of the numerator and the denominator?<br /> <br /> [[1983 AIME Problems/Problem 7|Solution]]<br /> <br /> == Problem 8 ==<br /> What is the largest 2-digit prime factor of the integer &lt;math&gt;{200\choose 100}&lt;/math&gt;?<br /> <br /> [[1983 AIME Problems/Problem 8|Solution]]<br /> <br /> == Problem 9 ==<br /> Find the minimum value of &lt;math&gt;\frac{9x^2\sin^2 x + 4}{x\sin x}&lt;/math&gt; for &lt;math&gt;0 &lt; x &lt; \pi&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 9|Solution]]<br /> <br /> == Problem 10 ==<br /> The numbers &lt;math&gt;1447&lt;/math&gt;, &lt;math&gt;1005&lt;/math&gt;, and &lt;math&gt;1231&lt;/math&gt; have something in common. Each is a four-digit number beginning with &lt;math&gt;1&lt;/math&gt; that has exactly two identical digits. How many such numbers are there?<br /> <br /> [[1983 AIME Problems/Problem 10|Solution]]<br /> <br /> == Problem 11 ==<br /> The solid shown has a square base of side length &lt;math&gt;s&lt;/math&gt;. The upper edge is parallel to the base and has length &lt;math&gt;2s&lt;/math&gt;. All edges have length &lt;math&gt;s&lt;/math&gt;. Given that &lt;math&gt;s=6\sqrt{2}&lt;/math&gt;, what is the volume of the solid?<br /> <br /> &lt;asy&gt;<br /> size(170);import three; pathpen = black+linewidth(0.65); pointpen = black;<br /> currentprojection = perspective(30,-20,10);real s = 6 * 2^.5;<br /> triple A=(0,0,0),B=(s,0,0),C=(s,s,0),D=(0,s,0),E=(-s/2,s/2,6),F=(3*s/2,s/2,6);<br /> D(A--B--C--D--A--E--D); D(B--F--C); D(E--F);<br /> MP(&quot;A&quot;,A);MP(&quot;B&quot;,B);MP(&quot;C&quot;,C);MP(&quot;D&quot;,D);MP(&quot;E&quot;,E,N);MP(&quot;F&quot;,F,N);<br /> &lt;/asy&gt;<br /> <br /> [[1983 AIME Problems/Problem 11|Solution]]<br /> <br /> == Problem 12 ==<br /> The length of diameter &lt;math&gt;AB&lt;/math&gt; is a two digit integer. Reversing the digits gives the length of a perpendicular chord &lt;math&gt;CD&lt;/math&gt;. The distance from their intersection point &lt;math&gt;H&lt;/math&gt; to the center &lt;math&gt;O&lt;/math&gt; is a positive rational number. Determine the length of &lt;math&gt;AB&lt;/math&gt;.<br /> <br /> &lt;asy&gt;pointpen=black; pathpen=black+linewidth(0.65);<br /> pair O=(0,0),A=(-65/2,0),B=(65/2,0);<br /> pair H=(-((65/2)^2-28^2)^.5,0),C=(H.x,28),D=(H.x,-28);<br /> D(CP(O,A));D(MP(&quot;A&quot;,A,W)--MP(&quot;B&quot;,B,E));D(MP(&quot;C&quot;,C,N)--MP(&quot;D&quot;,D));<br /> dot(MP(&quot;H&quot;,H,SE));dot(MP(&quot;O&quot;,O,SE));&lt;/asy&gt;<br /> <br /> [[1983 AIME Problems/Problem 12|Solution]]<br /> <br /> == Problem 13 ==<br /> For &lt;math&gt;\{1, 2, 3, \ldots, n\}&lt;/math&gt; and each of its non-empty subsets, an alternating sum is defined as follows. Arrange the number in the subset in decreasing order and then, beginning with the largest, alternately add and subtract succesive numbers. For example, the alternating sum for &lt;math&gt;\{1, 2, 3, 6,9\}&lt;/math&gt; is &lt;math&gt;9-6+3-2+1=6&lt;/math&gt; and for &lt;math&gt;\{5\}&lt;/math&gt; it is simply &lt;math&gt;5&lt;/math&gt;. Find the sum of all such alternating sums for &lt;math&gt;n=7&lt;/math&gt;.<br /> <br /> [[1983 AIME Problems/Problem 13|Solution]]<br /> <br /> == Problem 14 ==<br /> In the adjoining figure, two circles with radii &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;8&lt;/math&gt; are drawn with their centers &lt;math&gt;12&lt;/math&gt; units apart. At &lt;math&gt;P&lt;/math&gt;, one of the points of intersection, a line is drawn in sich a way that the chords &lt;math&gt;QP&lt;/math&gt; and &lt;math&gt;PR&lt;/math&gt; have equal length. (&lt;math&gt;P&lt;/math&gt; is the midpoint of &lt;math&gt;QR&lt;/math&gt;) Find the square of the length of &lt;math&gt;QP&lt;/math&gt;. <br /> <br /> [[Image:1983_AIME-14.png]]<br /> <br /> [[1983 AIME Problems/Problem 14|Solution]]<br /> <br /> == Problem 15 ==<br /> The adjoining figure shows two intersecting chords in a circle, with &lt;math&gt;B&lt;/math&gt; on minor arc &lt;math&gt;AD&lt;/math&gt;. Suppose that the radius of the circle is &lt;math&gt;5&lt;/math&gt;, that &lt;math&gt;BC=6&lt;/math&gt;, and that &lt;math&gt;AD&lt;/math&gt; is bisected by &lt;math&gt;BC&lt;/math&gt;. Suppose further that &lt;math&gt;AD&lt;/math&gt; is the only chord starting at &lt;math&gt;A&lt;/math&gt; which is bisected by &lt;math&gt;BC&lt;/math&gt;. It follows that the sine of the minor arc &lt;math&gt;AB&lt;/math&gt; is a rational number. If this fraction is expressed as a fraction &lt;math&gt;\frac{m}{n}&lt;/math&gt; in lowest terms, what is the product &lt;math&gt;mn&lt;/math&gt;?<br /> <br /> [[Image:1983_AIME-15.png]]<br /> <br /> [[1983 AIME Problems/Problem 15|Solution]]<br /> <br /> == See also ==<br /> * [[1983 AIME]]<br /> * [[American Invitational Mathematics Examination]]<br /> * [[AIME Problems and Solutions]]<br /> * [[Mathematics competition resources]]<br /> <br /> [[Category:AIME Problems]]</div> 1077400