https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Greenpepper9999&feedformat=atom AoPS Wiki - User contributions [en] 2020-10-19T22:12:02Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=Trigonometric_identities&diff=82634 Trigonometric identities 2017-01-30T20:48:48Z <p>Greenpepper9999: /* See also */ added external link section</p> <hr /> <div>'''Trigonometric identities''' are used to manipulate [[trigonometry]] [[equation]]s in certain ways. Here is a list of them:<br /> <br /> == Basic Definitions ==<br /> The six basic trigonometric functions can be defined using a right triangle:<br /> &lt;center&gt;[[Image:righttriangle.png]]&lt;/center&gt;<br /> <br /> The six trig functions are sine, cosine, tangent, cosecant, secant, and cotangent. They are abbreviated by using the first three letters of their name (except for cosecant which uses &lt;math&gt;\csc&lt;/math&gt;). They are defined as follows:<br /> {| class=&quot;wikitable&quot;<br /> |+ Basic Definitions<br /> |- &lt;!-- Start of a new row --&gt;<br /> | &lt;math&gt;\sin A = \frac ac&lt;/math&gt; || &lt;math&gt;\csc A = \frac ca&lt;/math&gt; || &lt;math&gt; \cos A = \frac bc&lt;/math&gt; || &lt;math&gt;\sec A = \frac cb&lt;/math&gt; || &lt;math&gt; \tan A = \frac ab&lt;/math&gt; || &lt;math&gt; \cot A = \frac ba&lt;/math&gt;<br /> |}<br /> <br /> == Even-Odd Identities ==<br /> *&lt;math&gt;\sin (-\theta) = -\sin (\theta) &lt;/math&gt;<br /> <br /> *&lt;math&gt;\cos (-\theta) = \cos (\theta) &lt;/math&gt;<br /> <br /> *&lt;math&gt;\tan (-\theta) = -\tan (\theta) &lt;/math&gt;<br /> <br /> *&lt;math&gt;\sec (-\theta) = \sec (\theta) &lt;/math&gt;<br /> <br /> *&lt;math&gt;\csc (-\theta) = -\csc (\theta) &lt;/math&gt;<br /> <br /> *&lt;math&gt;\cot (-\theta) = -\cot (\theta) &lt;/math&gt;<br /> <br /> ===Further Conclusions===<br /> <br /> Based on the above identities, we can also claim that<br /> <br /> *&lt;math&gt;\sin(\cos(-\theta)) = \sin(\cos(\theta))&lt;/math&gt;<br /> <br /> *&lt;math&gt;\cos(\sin(-\theta)) = \cos(-\sin(\theta)) = \cos(\sin(\theta))&lt;/math&gt;<br /> <br /> This is only true when &lt;math&gt;\sin(\theta)&lt;/math&gt; is in the domain of &lt;math&gt;\cos(\theta)&lt;/math&gt;.<br /> <br /> == Reciprocal Relations ==<br /> From the first section, it is easy to see that the following hold:<br /> <br /> *&lt;math&gt; \sin A = \frac 1{\csc A}&lt;/math&gt; <br /> <br /> *&lt;math&gt; \cos A = \frac 1{\sec A}&lt;/math&gt;<br /> <br /> *&lt;math&gt; \tan A = \frac 1{\cot A}&lt;/math&gt;<br /> <br /> Another useful identity that isn't a reciprocal relation is that &lt;math&gt; \tan A =\frac{\sin A}{\cos A} &lt;/math&gt;.<br /> <br /> Note that &lt;math&gt;\sin^{-1} A \neq \csc A&lt;/math&gt;; the former refers to the [[inverse trigonometric function]]s.<br /> <br /> == Pythagorean Identities ==<br /> Using the [[Pythagorean Theorem]] on our triangle above, we know that &lt;math&gt;a^2 + b^2 = c^2 &lt;/math&gt;. If we divide by &lt;math&gt;c^2 &lt;/math&gt; we get &lt;math&gt;\left(\frac{a}{c}\right)^2 + \left(\frac{b}{c}\right)^2 = 1 &lt;/math&gt;, which is just &lt;math&gt;\sin^2 A + \cos^2 A =1 &lt;/math&gt;. Dividing by &lt;math&gt; a^2 &lt;/math&gt; or &lt;math&gt; b^2 &lt;/math&gt; instead produces two other similar identities. The Pythagorean Identities are listed below:<br /> <br /> *&lt;math&gt;\sin^2x + \cos^2x = 1&lt;/math&gt;<br /> *&lt;math&gt;1 + \cot^2x = \csc^2x&lt;/math&gt;<br /> *&lt;math&gt;\tan^2x + 1 = \sec^2x&lt;/math&gt;<br /> <br /> (Note that the last two are easily derived by dividing the first by &lt;math&gt;\sin^2x&lt;/math&gt; and &lt;math&gt;\cos^2x&lt;/math&gt;, respectively.)<br /> <br /> == Angle Addition/Subtraction Identities ==<br /> Once we have formulas for angle addition, angle subtraction is rather easy to derive. For example, we just look at &lt;math&gt; \sin(\alpha+(-\beta))&lt;/math&gt; and we can derive the sine angle subtraction formula using the sine angle addition formula.<br /> <br /> *&lt;math&gt; \sin(\alpha \pm \beta) = \sin \alpha\cos \beta \pm\sin \beta \cos \alpha&lt;/math&gt;<br /> *&lt;math&gt; \cos(\alpha \pm \beta) = \cos \alpha \cos \beta \mp \sin \alpha \sin \beta &lt;/math&gt;<br /> *&lt;math&gt;\tan(\alpha \pm \beta) = \frac{\tan \alpha \pm \tan \beta}{1\mp\tan \alpha \tan \beta} &lt;/math&gt;<br /> <br /> We can prove &lt;math&gt; \cos(\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta &lt;/math&gt; easily by using &lt;math&gt; \sin(\alpha + \beta) = \sin \alpha\cos \beta +\sin \beta \cos \alpha&lt;/math&gt; and &lt;math&gt;\sin(x)=\cos(90-x)&lt;/math&gt;.<br /> <br /> &lt;math&gt;\cos (\alpha + \beta)&lt;/math&gt;<br /> <br /> &lt;math&gt; = \sin((90 -\alpha) - \beta) &lt;/math&gt;&lt;math&gt;= \sin (90- \alpha) \cos (\beta) - \sin ( \beta) \cos (90- \alpha) &lt;/math&gt;<br /> <br /> &lt;math&gt;=\cos \alpha \cos \beta - \sin \beta \sin \alpha &lt;/math&gt;<br /> <br /> == Double Angle Identities ==<br /> Double angle identities are easily derived from the angle addition formulas by just letting &lt;math&gt; \alpha = \beta &lt;/math&gt;. Doing so yields:<br /> <br /> &lt;cmath&gt;\begin{eqnarray*}<br /> \sin 2\alpha &amp;=&amp; 2\sin \alpha \cos \alpha\\<br /> \cos 2\alpha &amp;=&amp; \cos^2 \alpha - \sin^2 \alpha\\<br /> &amp;=&amp; 2\cos^2 \alpha - 1\\<br /> &amp;=&amp; 1-2\sin^2 \alpha\\<br /> \tan 2\alpha &amp;=&amp; \frac{2\tan \alpha}{1-\tan^2\alpha} \end{eqnarray*}&lt;/cmath&gt;<br /> <br /> =Further Conclusions=<br /> <br /> We can see from the above that<br /> <br /> *&lt;math&gt;\csc(2a) = \frac{\csc(a)\sec(a)}{2}&lt;/math&gt;<br /> *&lt;math&gt;\sec(2a) = \frac{1}{2\cos^2(a) - 1} = \frac{1}{\cos^2(a) - \sin^2(a)} = \frac{1}{1 - 2\sin^2(a)}&lt;/math&gt;<br /> *&lt;math&gt;\cot(2a) = \frac{1 - \tan^2(a)}{2\tan(a)}&lt;/math&gt;<br /> <br /> == Half Angle Identities ==<br /> Using the double angle identities, we can derive half angle identities. The double angle formula for cosine tells us &lt;math&gt;\cos 2\alpha = 2\cos^2 \alpha - 1 &lt;/math&gt;. Solving for &lt;math&gt;\cos \alpha &lt;/math&gt; we get &lt;math&gt;\cos \alpha =\pm \sqrt{\frac{1 + \cos 2\alpha}2}&lt;/math&gt; where we look at the quadrant of &lt;math&gt;\alpha &lt;/math&gt; to decide if it's positive or negative. Likewise, we can use the fact that &lt;math&gt;\cos 2\alpha = 1 - 2\sin^2 \alpha &lt;/math&gt; to find a half angle identity for sine. Then, to find a half angle identity for tangent, we just use the fact that &lt;math&gt;\tan \frac x2 =\frac{\sin \frac x2}{\cos \frac x2} &lt;/math&gt; and plug in the half angle identities for sine and cosine.<br /> <br /> To summarize:<br /> <br /> *&lt;math&gt; \sin \frac{\theta}2 = \pm \sqrt{\frac{1-\cos \theta}2} &lt;/math&gt;<br /> *&lt;math&gt; \cos \frac{\theta}2 = \pm \sqrt{\frac{1+\cos \theta}2} &lt;/math&gt;<br /> *&lt;math&gt; \tan \frac{\theta}2 = \pm \sqrt{\frac{1-\cos \theta}{1+\cos \theta}} &lt;/math&gt;<br /> <br /> == Prosthaphaeresis Identities ==<br /> (Otherwise known as sum-to-product identities)<br /> <br /> * &lt;math&gt;\sin \theta \pm \sin \gamma = 2 \sin \frac{\theta\pm \gamma}2 \cos \frac{\theta\mp \gamma}2&lt;/math&gt;<br /> * &lt;math&gt;\cos \theta + \cos \gamma = 2 \cos \frac{\theta+\gamma}2 \cos \frac{\theta-\gamma}2&lt;/math&gt;<br /> * &lt;math&gt;\cos \theta - \cos \gamma = -2 \sin \frac{\theta+\gamma}2 \sin \frac{\theta-\gamma}2&lt;/math&gt;<br /> <br /> == Law of Sines ==<br /> {{main|Law of Sines}}<br /> The extended [[Law of Sines]] states<br /> <br /> *&lt;math&gt;\frac a{\sin A} = \frac b{\sin B} = \frac c{\sin C} = 2R.&lt;/math&gt;<br /> <br /> == Law of Cosines ==<br /> {{main|Law of Cosines}}<br /> The [[Law of Cosines]] states <br /> <br /> *&lt;math&gt;a^2 = b^2 + c^2 - 2bc\cos A. &lt;/math&gt;<br /> <br /> == Law of Tangents ==<br /> {{main|Law of Tangents}}<br /> The [[Law of Tangents]] states that if &lt;math&gt;A&lt;/math&gt; and &lt;math&gt;B&lt;/math&gt; are angles in a triangle opposite sides &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; respectively, then<br /> <br /> &lt;math&gt; \frac{\tan{\left(\frac{A-B}{2}\right)}}{\tan{\left(\frac{A+B}{2}\right)}}=\frac{a-b}{a+b} . &lt;/math&gt;<br /> <br /> A further extension of the [[Law of Tangents]] states that if &lt;math&gt;A&lt;/math&gt;, &lt;math&gt;B&lt;/math&gt;, and &lt;math&gt;C&lt;/math&gt; are angles in a triangle, then<br /> &lt;math&gt;\tan(A)\cdot\tan(B)\cdot\tan(C)=\tan(A)+\tan(B)+\tan(C)&lt;/math&gt;<br /> <br /> == Other Identities ==<br /> *&lt;math&gt;\sin(90-\theta) = \cos(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\cos(90-\theta)=\sin(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\tan(90-\theta)=\cot(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\sin(180-\theta) = \sin(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\cos(180-\theta) = -\cos(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\tan(180-\theta) = -\tan(\theta)&lt;/math&gt;<br /> *&lt;math&gt;e^{i\theta} = \cos \theta + i\sin \theta&lt;/math&gt; (This is also written as &lt;math&gt;\text{cis }\theta&lt;/math&gt;)<br /> *&lt;math&gt;|1-e^{i\theta}|=2\sin\frac{\theta}{2}&lt;/math&gt;<br /> *&lt;math&gt;\left(\tan\theta + \sec\theta\right)^2 = \frac{1 + \sin\theta}{1 - \sin\theta}&lt;/math&gt;<br /> *&lt;math&gt;\sin(\theta) = \cos(\theta)\tan(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\cos(\theta) = \frac{\sin(\theta)}{\tan(\theta)}&lt;/math&gt;<br /> *&lt;math&gt;\sec(\theta) = \frac{\tan(\theta)}{\sin(\theta)}&lt;/math&gt;<br /> *&lt;math&gt;\sin^2(\theta) + \cos^2(\theta) + \tan^2(\theta) = \sec^2(\theta)&lt;/math&gt;<br /> *&lt;math&gt;\sin^2(\theta) + \cos^2(\theta) + \cot^2(\theta) = \csc^2(\theta)&lt;/math&gt;<br /> <br /> The two identities right above here were based on identites others posted on this site with a substitution.<br /> <br /> *&lt;math&gt;\cos(2\theta) = (\cos(\theta) + \sin(\theta))(\cos(\theta) - \sin(\theta))&lt;/math&gt;<br /> <br /> ==See also==<br /> * [[Trigonometry]]<br /> * [[Trigonometric substitution]]<br /> *<br /> <br /> ==External Links==<br /> [http://www.sosmath.com/trig/Trig5/trig5/trig5.html Trigonometric Identities]<br /> <br /> [[Category:Trigonometry]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Recursion&diff=78249 Recursion 2016-04-26T00:31:22Z <p>Greenpepper9999: Fixed link for real this time</p> <hr /> <div>'''Recursion''' is a method of defining something (usually a [[sequence]] or [[function]]) in terms of previously defined values. The most famous example of a recursive definition is that of the [[Fibonacci sequence]]. If we let &lt;math&gt;F_n&lt;/math&gt; be the &lt;math&gt;n&lt;/math&gt;th Fibonacci number, the sequence is defined recursively by the relations &lt;math&gt;F_0 = F_1 = 1&lt;/math&gt; and &lt;math&gt;F_{n+1}=F_{n}+F_{n-1}&lt;/math&gt;. (That is, each term is the sum of the previous two terms.) Then we can easily calculate early values of the sequence in terms of previous values: &lt;math&gt;F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8&lt;/math&gt;, and so on.<br /> <br /> Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by &lt;math&gt;a_0 = 1&lt;/math&gt; and &lt;math&gt;a_n = 2\cdot a_{n - 1}&lt;/math&gt; for &lt;math&gt;n &gt; 0&lt;/math&gt; also has the closed-form definition &lt;math&gt;a_n = 2^n&lt;/math&gt;.<br /> <br /> In [[computer science]], recursion also refers to the technique of having a function repeatedly call itself. The concept is very similar to recursively defined mathematical functions, but can also be used to simplify the implementation of a variety of other computing tasks.<br /> <br /> <br /> == Examples ==<br /> <br /> * [[Mock_AIME_2_2006-2007_Problems#Problem_8 | Mock AIME 2 2006-2007 Problem 8]] ([[number theory]])<br /> * A combinatorical use of recursion: [[2006_AIME_I_Problems#Problem_11|2006 AIME I Problem 11]]<br /> * Another combinatorical use of recursion: [[2001_AIME_I_Problems#Problem_14| 2001 AIME I Problem 14]]<br /> * Use of recursion to compute an explicit formula: [[2006_AIME_I_Problems#Problem_13| 2006 AIME I Problem 13]]<br /> * Use of recursion to count a type of number: [[2007_AMC_12A_Problems#Problem_25| 2007 AMC 12A Problem 25]]<br /> * Yet another use in combinatorics [[2008_AIME_I_Problems#Problem_11| 2008 AIME I Problem 11]]<br /> <br /> == See also ==<br /> <br /> * [[Combinatorics]]<br /> * [[Sequence]]<br /> * [[Induction]]<br /> * [http://artofproblemsolving.com/wiki/index.php?title=Recursion Recursion]<br /> <br /> [[Category:Combinatorics]]<br /> [[Category:Definition]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Recursion&diff=78248 Recursion 2016-04-26T00:30:26Z <p>Greenpepper9999: Fixed recursive link</p> <hr /> <div>'''Recursion''' is a method of defining something (usually a [[sequence]] or [[function]]) in terms of previously defined values. The most famous example of a recursive definition is that of the [[Fibonacci sequence]]. If we let &lt;math&gt;F_n&lt;/math&gt; be the &lt;math&gt;n&lt;/math&gt;th Fibonacci number, the sequence is defined recursively by the relations &lt;math&gt;F_0 = F_1 = 1&lt;/math&gt; and &lt;math&gt;F_{n+1}=F_{n}+F_{n-1}&lt;/math&gt;. (That is, each term is the sum of the previous two terms.) Then we can easily calculate early values of the sequence in terms of previous values: &lt;math&gt;F_0=1, F_1=1, F_2=2, F_3=3, F_4=5, F_5=8&lt;/math&gt;, and so on.<br /> <br /> Often, it is convenient to convert a recursive definition into a closed-form definition. For instance, the sequence defined recursively by &lt;math&gt;a_0 = 1&lt;/math&gt; and &lt;math&gt;a_n = 2\cdot a_{n - 1}&lt;/math&gt; for &lt;math&gt;n &gt; 0&lt;/math&gt; also has the closed-form definition &lt;math&gt;a_n = 2^n&lt;/math&gt;.<br /> <br /> In [[computer science]], recursion also refers to the technique of having a function repeatedly call itself. The concept is very similar to recursively defined mathematical functions, but can also be used to simplify the implementation of a variety of other computing tasks.<br /> <br /> <br /> == Examples ==<br /> <br /> * [[Mock_AIME_2_2006-2007_Problems#Problem_8 | Mock AIME 2 2006-2007 Problem 8]] ([[number theory]])<br /> * A combinatorical use of recursion: [[2006_AIME_I_Problems#Problem_11|2006 AIME I Problem 11]]<br /> * Another combinatorical use of recursion: [[2001_AIME_I_Problems#Problem_14| 2001 AIME I Problem 14]]<br /> * Use of recursion to compute an explicit formula: [[2006_AIME_I_Problems#Problem_13| 2006 AIME I Problem 13]]<br /> * Use of recursion to count a type of number: [[2007_AMC_12A_Problems#Problem_25| 2007 AMC 12A Problem 25]]<br /> * Yet another use in combinatorics [[2008_AIME_I_Problems#Problem_11| 2008 AIME I Problem 11]]<br /> <br /> == See also ==<br /> <br /> * [[Combinatorics]]<br /> * [[Sequence]]<br /> * [[Induction]]<br /> * [[Recursion]]<br /> <br /> [[Category:Combinatorics]]<br /> [[Category:Definition]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Aops_font&diff=77979 Aops font 2016-04-08T20:23:41Z <p>Greenpepper9999: /* Commonly Used */ removed downvote icon</p> <hr /> <div>The Aops font is a font that can be used to make certain special symbols in the forum. You enclose some text inside [aops] and [/aops] and the text is rendered in the aops font.<br /> <br /> = Purpose=<br /> The [aops][/aops] tags allow you to render items from the custom font that AoPS uses -- you'll recognize these icons from the rest of the site.<br /> <br /> For example, to type the symbol for the re-sort button &lt;span class=&quot;aops-font&quot;&gt;|&lt;/span&gt;, you would type <br /> :[aops]|[/aops]<br /> <br /> =Use=<br /> == In the Forums==<br /> To use the font in the forums, simply put [aops] before your text and [/aops] after it. The text will be converted as described in the tables below.<br /> == In the Wiki==<br /> Because bbcode does not work in the AoPS wiki, you need to use the following HTML code:<br /> :&lt;code&gt; &lt;nowiki&gt;&lt;span class=&quot;aops-font&quot;&gt;text here!&lt;/span&gt;&lt;/nowiki&gt;&lt;/code&gt;<br /> <br /> =Characters=<br /> ==Commonly Used==<br /> &lt;div style=&quot;font-size:large;&quot;&gt;<br /> {| class=&quot;wikitable&quot;<br /> ! Symbol<br /> ! What to type<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;Y&lt;/span&gt;<br /> | Y<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;a&lt;/span&gt;<br /> | _<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;f&lt;/span&gt;<br /> | f<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;h&lt;/span&gt;<br /> | h<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;j&lt;/span&gt;<br /> | j<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;3&lt;/span&gt;<br /> | 3<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;i&lt;/span&gt;<br /> | i<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;X&lt;/span&gt;<br /> | X<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;9&lt;/span&gt;<br /> | 9<br /> |-<br /> | &lt;span class=&quot;aops-font&quot;&gt;k&lt;/span&gt;<br /> | k<br /> |}<br /> <br /> ==Full List==<br /> &lt;div style=&quot;font-size:large;&quot;&gt;<br /> {| class=&quot;wikitable&quot;<br /> ! Character<br /> ! Aops font<br /> ! Character<br /> ! Aops font<br /> |-<br /> | a<br /> | &lt;span class=&quot;aops-font&quot;&gt;a&lt;/span&gt;<br /> | A<br /> | &lt;span class=&quot;aops-font&quot;&gt;A&lt;/span&gt;<br /> |-<br /> | b<br /> | &lt;span class=&quot;aops-font&quot;&gt;b&lt;/span&gt;<br /> | B<br /> | &lt;span class=&quot;aops-font&quot;&gt;B&lt;/span&gt;<br /> |-<br /> | c<br /> | &lt;span class=&quot;aops-font&quot;&gt;c&lt;/span&gt;<br /> | C<br /> | &lt;span class=&quot;aops-font&quot;&gt;C&lt;/span&gt;<br /> |-<br /> | d<br /> | &lt;span class=&quot;aops-font&quot;&gt;d&lt;/span&gt;<br /> | D<br /> | &lt;span class=&quot;aops-font&quot;&gt;D&lt;/span&gt;<br /> |-<br /> | e<br /> | &lt;span class=&quot;aops-font&quot;&gt;e&lt;/span&gt;<br /> | E<br /> | &lt;span class=&quot;aops-font&quot;&gt;E&lt;/span&gt;<br /> |-<br /> | f<br /> | &lt;span class=&quot;aops-font&quot;&gt;f&lt;/span&gt;<br /> | F<br /> | &lt;span class=&quot;aops-font&quot;&gt;F&lt;/span&gt;<br /> |-<br /> | g<br /> | &lt;span class=&quot;aops-font&quot;&gt;g&lt;/span&gt;<br /> | G<br /> | &lt;span class=&quot;aops-font&quot;&gt;G&lt;/span&gt;<br /> |-<br /> | h<br /> | &lt;span class=&quot;aops-font&quot;&gt;h&lt;/span&gt;<br /> | H<br /> | &lt;span class=&quot;aops-font&quot;&gt;H&lt;/span&gt;<br /> |-<br /> | i<br /> | &lt;span class=&quot;aops-font&quot;&gt;i&lt;/span&gt;<br /> | I<br /> | &lt;span class=&quot;aops-font&quot;&gt;I&lt;/span&gt;<br /> |-<br /> | j<br /> | &lt;span class=&quot;aops-font&quot;&gt;j&lt;/span&gt;<br /> | J<br /> | &lt;span class=&quot;aops-font&quot;&gt;J&lt;/span&gt;<br /> |-<br /> | k<br /> | &lt;span class=&quot;aops-font&quot;&gt;k&lt;/span&gt;<br /> | K<br /> | &lt;span class=&quot;aops-font&quot;&gt;K&lt;/span&gt;<br /> |-<br /> | l<br /> | &lt;span class=&quot;aops-font&quot;&gt;l&lt;/span&gt;<br /> | L<br /> | &lt;span class=&quot;aops-font&quot;&gt;L&lt;/span&gt;<br /> |-<br /> | m<br /> | &lt;span class=&quot;aops-font&quot;&gt;m&lt;/span&gt;<br /> | M<br /> | &lt;span class=&quot;aops-font&quot;&gt;M&lt;/span&gt;<br /> |-<br /> | n<br /> | &lt;span class=&quot;aops-font&quot;&gt;n&lt;/span&gt;<br /> | N<br /> | &lt;span class=&quot;aops-font&quot;&gt;N&lt;/span&gt;<br /> |-<br /> | o<br /> | &lt;span class=&quot;aops-font&quot;&gt;o&lt;/span&gt;<br /> | O<br /> | &lt;span class=&quot;aops-font&quot;&gt;O&lt;/span&gt;<br /> |-<br /> | p<br /> | &lt;span class=&quot;aops-font&quot;&gt;p&lt;/span&gt;<br /> | P<br /> | &lt;span class=&quot;aops-font&quot;&gt;P&lt;/span&gt;<br /> |-<br /> | q<br /> | &lt;span class=&quot;aops-font&quot;&gt;q&lt;/span&gt;<br /> | Q<br /> | &lt;span class=&quot;aops-font&quot;&gt;Q&lt;/span&gt;<br /> |-<br /> | r<br /> | &lt;span class=&quot;aops-font&quot;&gt;r&lt;/span&gt;<br /> | R<br /> | &lt;span class=&quot;aops-font&quot;&gt;R&lt;/span&gt;<br /> |-<br /> | s<br /> | &lt;span class=&quot;aops-font&quot;&gt;s&lt;/span&gt;<br /> | S<br /> | &lt;span class=&quot;aops-font&quot;&gt;S&lt;/span&gt;<br /> |-<br /> | t<br /> | &lt;span class=&quot;aops-font&quot;&gt;t&lt;/span&gt;<br /> | T<br /> | &lt;span class=&quot;aops-font&quot;&gt;T&lt;/span&gt;<br /> |-<br /> | u<br /> | &lt;span class=&quot;aops-font&quot;&gt;u&lt;/span&gt;<br /> | U<br /> | &lt;span class=&quot;aops-font&quot;&gt;U&lt;/span&gt;<br /> |-<br /> | v<br /> | &lt;span class=&quot;aops-font&quot;&gt;v&lt;/span&gt;<br /> | V<br /> | &lt;span class=&quot;aops-font&quot;&gt;V&lt;/span&gt;<br /> |-<br /> | w<br /> | &lt;span class=&quot;aops-font&quot;&gt;w&lt;/span&gt;<br /> | W<br /> | &lt;span class=&quot;aops-font&quot;&gt;W&lt;/span&gt;<br /> |-<br /> | x<br /> | &lt;span class=&quot;aops-font&quot;&gt;x&lt;/span&gt;<br /> | X<br /> | &lt;span class=&quot;aops-font&quot;&gt;X&lt;/span&gt;<br /> |-<br /> | y<br /> | &lt;span class=&quot;aops-font&quot;&gt;y&lt;/span&gt;<br /> | Y<br /> | &lt;span class=&quot;aops-font&quot;&gt;Y&lt;/span&gt;<br /> |-<br /> | z<br /> | &lt;span class=&quot;aops-font&quot;&gt;z&lt;/span&gt;<br /> | Z<br /> | &lt;span class=&quot;aops-font&quot;&gt;Z&lt;/span&gt;<br /> |-<br /> | 1<br /> | &lt;span class=&quot;aops-font&quot;&gt;1&lt;/span&gt;<br /> | !<br /> | &lt;span class=&quot;aops-font&quot;&gt;!&lt;/span&gt;<br /> |-<br /> | 2<br /> | &lt;span class=&quot;aops-font&quot;&gt;2&lt;/span&gt;<br /> | @<br /> | &lt;span class=&quot;aops-font&quot;&gt;@&lt;/span&gt;<br /> |-<br /> | 3<br /> | &lt;span class=&quot;aops-font&quot;&gt;3&lt;/span&gt;<br /> | #<br /> | &lt;span class=&quot;aops-font&quot;&gt;#&lt;/span&gt;<br /> |-<br /> | 4<br /> | &lt;span class=&quot;aops-font&quot;&gt;4&lt;/span&gt;<br /> | &amp;#36;<br /> | &lt;span class=&quot;aops-font&quot;&gt;&amp;#36;&lt;/span&gt;<br /> |-<br /> | 5<br /> | &lt;span class=&quot;aops-font&quot;&gt;5&lt;/span&gt;<br /> | %<br /> | &lt;span class=&quot;aops-font&quot;&gt;%&lt;/span&gt;<br /> |-<br /> | 6<br /> | &lt;span class=&quot;aops-font&quot;&gt;6&lt;/span&gt;<br /> | ^<br /> | &lt;span class=&quot;aops-font&quot;&gt;^&lt;/span&gt;<br /> |-<br /> | 7<br /> | &lt;span class=&quot;aops-font&quot;&gt;7&lt;/span&gt;<br /> | &amp;<br /> | &lt;span class=&quot;aops-font&quot;&gt;&amp;&lt;/span&gt;<br /> |-<br /> | 8<br /> | &lt;span class=&quot;aops-font&quot;&gt;8&lt;/span&gt;<br /> | *<br /> | &lt;span class=&quot;aops-font&quot;&gt;*&lt;/span&gt;<br /> |-<br /> | 9<br /> | &lt;span class=&quot;aops-font&quot;&gt;9&lt;/span&gt;<br /> | (<br /> | &lt;span class=&quot;aops-font&quot;&gt;(&lt;/span&gt;<br /> |-<br /> | 0<br /> | &lt;span class=&quot;aops-font&quot;&gt;0&lt;/span&gt;<br /> | )<br /> | &lt;span class=&quot;aops-font&quot;&gt;)&lt;/span&gt;<br /> |-<br /> | -<br /> | &lt;span class=&quot;aops-font&quot;&gt;-&lt;/span&gt;<br /> | _<br /> | &lt;span class=&quot;aops-font&quot;&gt;_&lt;/span&gt;<br /> |-<br /> | =<br /> | &lt;span class=&quot;aops-font&quot;&gt;=&lt;/span&gt; <br /> | +<br /> | &lt;span class=&quot;aops-font&quot;&gt;+&lt;/span&gt; <br /> |-<br /> | ,<br /> | &lt;span class=&quot;aops-font&quot;&gt;,&lt;/span&gt;<br /> | .<br /> | &lt;span class=&quot;aops-font&quot;&gt;.&lt;/span&gt;<br /> |-<br /> | /<br /> | &lt;span class=&quot;aops-font&quot;&gt;/&lt;/span&gt;<br /> | ?<br /> | &lt;span class=&quot;aops-font&quot;&gt;?&lt;/span&gt;<br /> |-<br /> | &lt;<br /> | &lt;span class=&quot;aops-font&quot;&gt;&amp;lt;&lt;/span&gt;<br /> | &gt;<br /> | &lt;span class=&quot;aops-font&quot;&gt;&gt;&lt;/span&gt;<br /> |-<br /> |;<br /> | &lt;span class=&quot;aops-font&quot;&gt;;&lt;/span&gt;<br /> |:<br /> | &lt;span class=&quot;aops-font&quot;&gt;:&lt;/span&gt;<br /> |-<br /> |'<br /> | &lt;span class=&quot;aops-font&quot;&gt;'&lt;/span&gt;<br /> |&quot;<br /> | &lt;span class=&quot;aops-font&quot;&gt;&quot;&lt;/span&gt;<br /> |-<br /> | {<br /> | &lt;span class=&quot;aops-font&quot;&gt;{&lt;/span&gt;<br /> | }<br /> | &lt;span class=&quot;aops-font&quot;&gt;}&lt;/span&gt;<br /> |-<br /> | –<br /> | &lt;span class=&quot;aops-font&quot;&gt;–&lt;/span&gt;<br /> | —<br /> | &lt;span class=&quot;aops-font&quot;&gt;—&lt;/span&gt;<br /> &lt;/div&gt; <br /> [[Category:AoPS forums]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Reference&diff=77790 Asymptote: Reference 2016-03-22T22:15:01Z <p>Greenpepper9999: /* Transforms */</p> <hr /> <div>{{Asymptote}}<br /> <br /> ==Points==<br /> A '''point''' is associated with a cartesian coordinate pair in Asymptote. There are two useful functions that allow one to use polar coordinates as well:<br /> dir(theta)<br /> returns the point (cos(theta),sin(theta)) where theta is in degrees, and<br /> expi(theta)<br /> returns the complex number &lt;math&gt;e^{i\theta}&lt;/math&gt;, i.e. (cos(theta),sin(theta)) where theta is measured in radians.<br /> <br /> ==Paths==<br /> A '''path''' (or ''guide'' - see [[Asymptote: Basics|Variables and Data Types]] for the difference) in Asymptote is simply a piecewise cubic function of a parameter &lt;math&gt;t&lt;/math&gt;, parameterized as &lt;math&gt;t&lt;/math&gt; ranges from &lt;math&gt;0&lt;/math&gt; to the number of nodes (say &lt;math&gt;n&lt;/math&gt;) that determine the path. The most basic way to make paths is by joining points (which can be thought of as paths with length 0) or paths &lt;tt&gt;p&lt;/tt&gt;, &lt;tt&gt;q&lt;/tt&gt; together with one of the following operators: <br /> &lt;tt&gt;p--q&lt;/tt&gt;<br /> &lt;tt&gt;p..q&lt;/tt&gt;<br /> &lt;tt&gt;p^^q&lt;/tt&gt;<br /> The first (&lt;tt&gt;--&lt;/tt&gt;) connects the end of path p to the beginning of q with a straight line. The second (&lt;tt&gt;..&lt;/tt&gt;) connects them with a Bezier cubic spline interpolation so that paths are joined smoothly. The third (&lt;tt&gt;^^&lt;/tt&gt;) actually does not connect the paths at all, but rather re-parameterizes so that the two paths are treated as one. The symbol &lt;tt&gt;cycle&lt;/tt&gt; connected to a path tells Asymptote to form a cyclic path by joining the endpoint with &lt;math&gt;t=n&lt;/math&gt; to that with &lt;math&gt;t=0&lt;/math&gt;.<br /> <br /> The following example includes the benefits of all three types of path joins:<br /> unitsize(1inch);<br /> path T,ct,tt;<br /> T=(0,0)--(1,0)--(1/2,sqrt(3)/2)--cycle;<br /> ct=(0,0)..(1,0)--(1/2,sqrt(3)/2)..cycle;<br /> tt=shift(sqrt(3)/6*dir(30))*(scale(1/2)*T);<br /> draw(T);<br /> draw(shift(2*right)*ct);<br /> fill(reverse(shift(4*right)*tt)^^(shift(4*right)*T),blue);<br /> <br /> outputs:<br /> &lt;asy&gt;<br /> unitsize(1inch);<br /> path T,ct,tt;<br /> T=(0,0)--(1,0)--(1/2,sqrt(3)/2)--cycle;<br /> ct=(0,0)..(1,0)--(1/2,sqrt(3)/2)..cycle;<br /> tt=shift(sqrt(3)/6*dir(30))*(scale(1/2)*T);<br /> draw(T);<br /> draw(shift(2*right)*ct);<br /> fill(reverse(shift(4*right)*tt)^^(shift(4*right)*T),blue);<br /> &lt;/asy&gt;<br /> <br /> ==Pens and Coloring==<br /> A '''pen''' is just that - the style with which Asymptote draws your paths or pictures. Pens can have various '''colors''', dash patterns ('''linetypes'''), and '''linewidths'''. The following table gives a variety of examples of pen types and their output:<br /> <br /> [[Image:Table2.gif]]<br /> <br /> We can also add pens with the + operator. For example, the command <br /> draw((0,0)--(100,100),orange+dashed+linewidth(1));<br /> will produce the image<br /> <br /> [[Image:Pen14.gif]]<br /> <br /> The default pen has linetype &lt;tt&gt;solid&lt;/tt&gt;=&quot;&quot;, linewidth .5, and color &lt;tt&gt;black&lt;/tt&gt;.<br /> <br /> ==Basic drawing commands==<br /> Asymptote has four basic drawing commands, draw, fill, clip, and label. The most important of these is draw.<br /> <br /> ===Draw===<br /> The function &lt;tt&gt;draw&lt;/tt&gt; can take many arguments. The following is the structure of a draw command, where anything with = denotes the default value:<br /> void draw(picture pic=currentpicture, Label L=&quot;&quot;, path g,<br /> align align=NoAlign, pen p=currentpen,<br /> arrowbar arrow=None, arrowbar bar=None, margin margin=NoMargin,<br /> Label legend=&quot;&quot;, marker marker=nomarker);<br /> So with &lt;tt&gt;draw&lt;/tt&gt;, you can draw path g to the picture pic along with a string label L, with pen p, etc. Of course, most of this is unnecessary for a basic diagram. The most important thing to notice is that the only non-optional argument of draw is the path g. The command &lt;tt&gt;draw(g);&lt;/tt&gt; where g is a path simply draws the path on top of your current picture.<br /> ===Fill===<br /> The structure of fill is much simpler than that of draw:<br /> void fill(picture pic=currentpicture, path g,pen p=currentpen);<br /> <br /> This fills a cyclic path g in picture pic (see the section on Paths above) with a specified pen p (most often a color - see Pens and Coloring above). For example, the command <br /> fill((0,0)--(0,1)--(1,1)--(1,0)--cycle,red);<br /> where unitsize is 1 inch outputs:<br /> <br /> [[Image:Fill1.gif]]<br /> <br /> ===Clip===<br /> The structure of clip is also simple: <br /> void clip(picture pic=currentpicture, path g, pen p=currentpen);<br /> <br /> This crops a picture so that the boundary is the given path g, with fill rule p. A ''fill rule'' tells when a point is inside the boundary of the path; the default fill rule, &lt;tt&gt;zerowinding&lt;/tt&gt; or &lt;tt&gt;fillrule(0)&lt;/tt&gt;, checks to see if the number of horizontal intersections from the point to the right is equal to the number of downward intersections with the path. Another useful fill rule is &lt;tt&gt;evenodd&lt;/tt&gt;, or &lt;tt&gt;fillrule(1)&lt;/tt&gt;, which checks if the total number of such intersections is even.<br /> <br /> For example, say we drew a smiley:<br /> import graph;<br /> unitsize(1inch);<br /> filldraw(Circle((0,0),1),yellow,black);<br /> fill(Circle((-.3,.4),.1),black);<br /> fill(Circle((.3,.4),.1),black);<br /> draw(Arc((0,0),.5,-140,-40),red);<br /> <br /> and we wanted to clip this to a star-shaped boundary. Then we add the lines:<br /> path star;<br /> star=expi(0)--(scale((3-sqrt(5))/2)*expi(pi/5))--expi(2*pi/5)--<br /> (scale((3-sqrt(5))/2)*expi(3*pi/5))--expi(4pi/5)--<br /> (scale((3-sqrt(5))/2)*expi(5*pi/5))--expi(6*pi/5)--<br /> (scale((3-sqrt(5))/2)*expi(7*pi/5))--expi(8*pi/5)--<br /> (scale((3-sqrt(5))/2)*expi(9*pi/5))--cycle;<br /> clip(currentpicture,scale(1.7)*rotate(18)*star);<br /> draw(scale(1.7)*rotate(18)*star);<br /> <br /> and we get:<br /> <br /> [[Image:Clip1.gif]]<br /> <br /> If we wanted to clip to a pattern in an alternating fashion, we could use the &lt;tt&gt;evenodd&lt;/tt&gt; fill rule:<br /> <br /> path zones[];<br /> zones=(Circle((0,0),.2)^^Circle((0,0),.6)^^Circle((0,0),.8)^^Circle((0,0),1));<br /> clip(currentpicture,zones,evenodd);<br /> <br /> This produces:<br /> <br /> [[Image:Clip2.gif]]<br /> <br /> ===Label===<br /> Label is used for, well, labeling your diagram. <br /> <br /> Structure:<br /> void label(picture pic=currentpicture, Label L, pair position,<br /> align align=NoAlign, pen p=nullpen, filltype filltype=NoFill);<br /> <br /> This places a label L (usually a string, which can include LaTeX code!) at the point position, aligned by default so that the center of the label is at the position, with optional pen and filltype for its bounding box. The alignment options, however, can be very useful; any pair can be given as a direction for alignment, and the built-in alignment directions are the compass directions N, E, S, W, NE, NW, SE, SW, ENE, etc. For example, the image below:<br /> <br /> [[Image:Label1.gif]]<br /> <br /> was produced by 8 double commands of the form<br /> label(&quot;S&quot;,(1,0),S);<br /> dot((1,0));<br /> <br /> See also: [[Asymptote:Labeling]]<br /> <br /> ==Pictures==<br /> The basic drawing commands all draw onto '''pictures''', the default picture being &lt;tt&gt;currentpicture&lt;/tt&gt;, which is the one that you see when you build your image. However, you can define a new picture in order to treat several drawn parts as a single object, which can be shifted and transformed as a whole relative to currentpicture. One picture (&lt;tt&gt;pic1&lt;/tt&gt;) can be added to another (&lt;tt&gt;pic2&lt;/tt&gt;) with the command &lt;tt&gt;add(pic2,pic1)&lt;/tt&gt;, and by default &lt;tt&gt;add(pic)&lt;/tt&gt; simply adds &lt;tt&gt;pic&lt;/tt&gt; to &lt;tt&gt;currentpicture&lt;/tt&gt;. For example:<br /> picture pic;<br /> size(3cm);<br /> draw(pic,unitsquare);<br /> draw(pic,unitcircle);<br /> add(shift(3*right)*pic);<br /> draw(unitsquare);<br /> draw(unitcircle);<br /> will display:<br /> <br /> [[Image:Picture1.gif]]<br /> <br /> ==Transforms==<br /> '''Transforms''' are objects that can be applied to pairs, paths, pictures, and other transforms by the &lt;tt&gt;*&lt;/tt&gt; operator. The most commonly used transforms are:<br /> [[Image:Transforms.gif]]<br /> <br /> Another useful transform that is not listed above:<br /> <br /> &lt;code&gt;reflect(pair a, pair b);<br /> reflects about the line a--b.&lt;/code&gt;<br /> <br /> [[Asymptote: Useful commands and their Output|Next: Examples]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=User_talk:Greenpepper9999&diff=77708 User talk:Greenpepper9999 2016-03-19T16:36:45Z <p>Greenpepper9999: Blanked the page</p> <hr /> <div></div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Asymptote:_Graphing&diff=77555 Asymptote: Graphing 2016-03-15T21:09:47Z <p>Greenpepper9999: Grammar/spelling</p> <hr /> <div>{{Asymptote}}<br /> <br /> &lt;b&gt;Note&lt;/b&gt; These example are for the AoPS forums, If you want to use them on your computer, you must &quot;import graph;&quot;.<br /> <br /> There are two parts to a graph. <br /> <br /> The axes' codes:<br /> <br /> &lt;pre&gt;&lt;nowiki&gt;Label f; <br /> f.p=fontsize(6); <br /> xaxis(-8,8,Ticks(f, 2.0)); <br /> yaxis(-8,8,Ticks(f, 2.0)); <br /> &lt;/nowiki&gt;&lt;/pre&gt;<br /> <br /> This means ticks at an interval of 2.0, between -8 and 8 for both the x and y axes.<br /> <br /> And the graph code:<br /> <br /> &lt;pre&gt;&lt;nowiki&gt;<br /> real f(real x) <br /> { <br /> return x^3; <br /> } <br /> draw(graph(f,-2,2));&lt;/nowiki&gt;&lt;/pre&gt;<br /> <br /> The return &lt;math&gt;x^3&lt;/math&gt; is the function of the graph, and the draw command draws the graph from the &lt;math&gt;x&lt;/math&gt; coordinate of &lt;math&gt;x = - 2&lt;/math&gt; to &lt;math&gt;x = 2&lt;/math&gt;.<br /> <br /> &lt;asy&gt;<br /> import graph; <br /> size(300); <br /> Label f; <br /> f.p=fontsize(6); <br /> xaxis(-8,8,Ticks(f, 2.0)); <br /> yaxis(-8,8,Ticks(f, 2.0)); <br /> real f(real x) <br /> { <br /> return x^3; <br /> } <br /> draw(graph(f,-2,2));<br /> &lt;/asy&gt;<br /> <br /> We can also alter the ticks code. For example, if we want intervals of 2 labeled, then 0.5 in between each one, we can use the following code:<br /> <br /> &lt;pre&gt;&lt;nowiki&gt;Label f; <br /> f.p=fontsize(6); <br /> xaxis(-8,8,Ticks(f, 2.0,0.5)); <br /> yaxis(-8,8,Ticks(f, 2.0,0.5)); <br /> &lt;/nowiki&gt;&lt;/pre&gt;<br /> <br /> &lt;asy&gt;<br /> Label f; <br /> f.p=fontsize(6); <br /> xaxis(-8,8,Ticks(f, 2.0,0.5)); <br /> yaxis(-8,8,Ticks(f, 2.0,0.5));<br /> &lt;/asy&gt;<br /> This graph, like with any draw command, can have several attributes fixed to it, such as color:<br /> <br /> &lt;asy&gt;<br /> import graph; <br /> size(300); <br /> Label f; <br /> f.p=fontsize(6); <br /> xaxis(-8,8,Ticks(f, 2.0)); <br /> yaxis(-8,8,Ticks(f, 2.0)); <br /> real f(real x) <br /> { <br /> return x^3; <br /> } <br /> draw(graph(f,-2,2),green+linewidth(1));<br /> &lt;/asy&gt;<br /> <br /> &lt;pre&gt;&lt;nowiki&gt;<br /> import graph; <br /> size(300); <br /> Label f; <br /> f.p=fontsize(6); <br /> xaxis(-8,8,Ticks(f, 2.0)); <br /> yaxis(-8,8,Ticks(f, 2.0)); <br /> real f(real x) <br /> { <br /> return x^3; <br /> } <br /> draw(graph(f,-2,2),green+linewidth(1));<br /> &lt;/nowiki&gt;&lt;/pre&gt;<br /> <br /> Remember, you can still draw normal functions, so you can create lines, circles and ellipses.</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=76470 Euler's totient function 2016-02-19T21:02:50Z <p>Greenpepper9999: Correcting</p> <hr /> <div>'''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 or equal to &lt;math&gt; n &lt;/math&gt; that share a common factor with it). There are &lt;math&gt; \frac{n}{p_1} &lt;/math&gt; positive integers less than or equal to &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_i &lt;/math&gt; and add these up, we get<br /> <br /> &lt;center&gt;&lt;cmath&gt; \frac{n}{p_1} + \frac{n}{p_2} + \cdots + \frac{n}{p_m} = \sum^m_{i=1}\frac{n}{p_i}.&lt;/cmath&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_i &lt;/math&gt;. There are &lt;math&gt;\sum_{1 \le i_1 &lt; i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}&lt;/math&gt; such numbers. 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;cmath&gt; \sum_{1 \le i \le m}\frac{n}{p_i}<br /> - \sum_{1 \le i_1 &lt; i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}<br /> + \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}. &lt;/cmath&gt;&lt;/center&gt;<br /> <br /> This sum represents the number of numbers less than &lt;math&gt;n&lt;/math&gt; sharing a common factor with &lt;math&gt;n&lt;/math&gt;, so<br /> <br /> &lt;math&gt;\phi(n) = n - \left(\sum_{1 \le i \le m}\frac{n}{p_i}- \sum_{1 \le i_1 &lt; i_2 \le m}\frac{n}{p_{i_1}p_{i_2}}<br /> + \cdots + (-1)^{m+1}\frac{n}{p_1p_2\ldots p_m}\right)&lt;/math&gt;<br /> <br /> &lt;math&gt;\phi(n)= n\left(1 - \sum_{1 \le i \le m}\frac{1}{p_i}<br /> + \sum_{1 \le i_1 &lt; i_2 \le m}\frac{1}{p_{i_1}p_{i_2}} - \cdots + (-1)^{m}\frac{1}{p_1p_2\ldots p_m}\right)&lt;/math&gt;<br /> <br /> &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;<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 /> (a) 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 /> (b) 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 /> (c) 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 /> (d) If &lt;math&gt;p&lt;/math&gt; is prime and &lt;math&gt;n\ge{1}&lt;/math&gt;,then &lt;math&gt;\phi(p^n)=p^n-p^{n-1}&lt;/math&gt;<br /> <br /> (e) 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 /> Proof. Split the set &lt;math&gt;\{1,2,\ldots,n\}&lt;/math&gt; into disjoint sets &lt;math&gt;A_d&lt;/math&gt; where for all &lt;math&gt;d\mid n&lt;/math&gt; we have<br /> &lt;cmath&gt;A_d=\{x:1\leq x\leq n\quad\text{and}\quad \operatorname{syt}(x,n)=d \}.&lt;/cmath&gt;<br /> Now &lt;math&gt;\operatorname{gcd}(dx,n)=d&lt;/math&gt; if and only if &lt;math&gt;\operatorname{gcd}(x,n/d)=1&lt;/math&gt;. Furthermore, &lt;math&gt;1\leq dx\leq n&lt;/math&gt; if and only if &lt;math&gt;1\leq x\leq n/d&lt;/math&gt;. Now one can see that the number of elements of &lt;math&gt;A_d&lt;/math&gt; equals the number of elements of<br /> &lt;cmath&gt;A_d^\prime=\{x:1\leq x \leq n/d\quad\text{and}\quad \operatorname{gcd}(x,n/d)=1 \}.&lt;/cmath&gt;<br /> Thus by the definition of Euler's phi we have that &lt;math&gt;|A_d^\prime|=\phi (n/d)&lt;/math&gt;. As every integer &lt;math&gt;i&lt;/math&gt; which satisfies &lt;math&gt;1\leq i\leq n&lt;/math&gt; belongs in exactly one of the sets &lt;math&gt;A_d&lt;/math&gt;, we have that<br /> &lt;cmath&gt;n=\sum_{d \mid n}\varphi \left (\frac{n}{d} \right )=\sum_{d \mid n}\phi (d).&lt;/cmath&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> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Indiana_MathCounts&diff=75834 Indiana MathCounts 2016-02-14T02:16:02Z <p>Greenpepper9999: /* External Links */</p> <hr /> <div>The Indiana Mathcounts team is from Indiana (the state).<br /> <br /> State Competition location alternates yearly between Purdue University and Rose-Hulman Institute of Technology.<br /> <br /> They won first place at MathCounts in 2015.<br /> <br /> <br /> <br /> == See also ==<br /> *[[MathCounts]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Triangular_number&diff=75833 Triangular number 2016-02-14T01:48:34Z <p>Greenpepper9999: Did some stuff, added some stuff, organized some stuff</p> <hr /> <div>The '''triangular numbers''' are the numbers &lt;math&gt;T_n&lt;/math&gt; which are the sum of the first &lt;math&gt;n&lt;/math&gt; [[natural number]]s from &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;n&lt;/math&gt;.<br /> <br /> ==Definition==<br /> The &lt;math&gt;n^{th}&lt;/math&gt; triangular number is the sum of all natural numbers from one to n.<br /> That is, the &lt;math&gt;n^{th}&lt;/math&gt; triangle number is <br /> &lt;math&gt;1 +2+3 + 4............. +(n-1)+(n)&lt;/math&gt;.<br /> <br /> For example, the first few triangular numbers can be calculated by adding <br /> 1, 1+2, 1+2+3, ... etc. <br /> giving the first few triangular numbers to be <br /> &lt;math&gt;1, 3, 6, 10, 15, 21&lt;/math&gt;. <br /> <br /> A rather simple recursive definition can be found by noting that &lt;math&gt;T_{n} = 1 + 2 + \ldots + (n-1) + n = (1 + 2 + \ldots + n-1) + n = T_{n-1} + n&lt;/math&gt;.<br /> <br /> They are called triangular because you can make a triangle out of dots, and the number of dots will be a triangular number:<br /> &lt;asy&gt;<br /> int draw_triangle(pair start, int n)<br /> {<br /> real rowStart = start.x;<br /> for (int row=1; row&lt;=n; ++row)<br /> {<br /> for (real j=rowStart; j&lt;(rowStart+row); ++j)<br /> {<br /> draw((j, start.y - row), linewidth(3));<br /> }<br /> rowStart -= 0.5;<br /> }<br /> return 0;<br /> }<br /> <br /> for (int n=1; n&lt;5; ++n)<br /> {<br /> real value= n*(n+1)/2;<br /> draw_triangle((value+5,n),n);<br /> label( (string) value, (value+5, -2));<br /> }<br /> &lt;/asy&gt;<br /> ==Formula==<br /> <br /> Using the sum of an [[arithmetic series]] formula, a formula can be calculated for &lt;math&gt;T_n&lt;/math&gt;:<br /> <br /> :&lt;math&gt;T_n =\sum_{k=1}^{n}k = 1 + 2 + \ldots + n = \frac{n(n+1)}2&lt;/math&gt;<br /> <br /> <br /> The formula for finding the &lt;math&gt;n^{th}&lt;/math&gt; triangular number can be written as &lt;math&gt;\dfrac{n(n+1)}{2}&lt;/math&gt;.<br /> <br /> It can also be expressed as the sum of the &lt;math&gt;n^{th}&lt;/math&gt; row in [[Pascal's Triangle]] and all the rows above it. Keep in mind that the triangle starts at Row 0.<br /> <br /> <br /> <br /> <br /> <br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=CSS_Tutorial&diff=73975 CSS Tutorial 2015-12-26T18:24:18Z <p>Greenpepper9999: Redirected page to CSS</p> <hr /> <div>#REDIRECT [[CSS]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=CSS_Tutorial&diff=73974 CSS Tutorial 2015-12-26T18:24:01Z <p>Greenpepper9999: </p> <hr /> <div># REDIRECT [[CSS]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Combination&diff=73561 Combination 2015-12-07T23:49:51Z <p>Greenpepper9999: /* Formula */</p> <hr /> <div>A '''combination''' is a way of choosing &lt;math&gt;r&lt;/math&gt; objects from a set of &lt;math&gt;n&lt;/math&gt; where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size &lt;math&gt;r&lt;/math&gt; from an original set of size &lt;math&gt;n&lt;/math&gt;<br /> <br /> <br /> == Notation ==<br /> <br /> The common forms of denoting the number of combinations of &lt;math&gt;{r}&lt;/math&gt; objects from a set of &lt;math&gt;{n}&lt;/math&gt; objects is:<br /> <br /> * &lt;math&gt;\binom{n}{r}&lt;/math&gt;<br /> * &lt;math&gt;{C}(n,r)&lt;/math&gt;<br /> * &lt;math&gt;\,_{n} C_{r}&lt;/math&gt;<br /> * &lt;math&gt; C_n^{r} &lt;/math&gt;<br /> <br /> == Formula ==<br /> <br /> &lt;math&gt;{{n}\choose {r}} = \frac {n!} {r!(n-r)!}&lt;/math&gt;<br /> <br /> == Derivation ==<br /> <br /> Consider the set of letters A, B, and C. There are &lt;math&gt;3!&lt;/math&gt; different [[permutations]] of those letters. Since order doesn't matter with combinations, there is only one combination of those three.(&lt;math&gt;ABC,ACB,BAC,BCA,CAB,CBA&lt;/math&gt; are all equivalent in combination but different in permutation.) <br /> <br /> In general, since for every permutation of &lt;math&gt;{r}&lt;/math&gt; objects from &lt;math&gt;{n}&lt;/math&gt; elements &lt;math&gt;P(n,r)&lt;/math&gt; which is &lt;math&gt;\frac{n!}{n-r!}&lt;/math&gt;.Now since in permutation the order of arrangement matters(&lt;math&gt;ABC&lt;/math&gt; is not same as &lt;math&gt;ACB&lt;/math&gt;) but in combinations the order of arrangement does not matter(&lt;math&gt;ABC&lt;/math&gt; is equivalent to &lt;math&gt;ACB&lt;/math&gt;).For its derivation see this [http://www.artofproblemsolving.com/Videos/external.php?video_id=181 video].<br /> <br /> Suppose &lt;math&gt;r&lt;/math&gt; elements are selected out.For permutation &lt;math&gt;r&lt;/math&gt; elements can be arranged in &lt;math&gt;r!&lt;/math&gt; ways.We have overcounted the number of combinations by &lt;math&gt;r!&lt;/math&gt; times.So We have &lt;math&gt;{r}!{C}({n},{r})=P(n,r)&lt;/math&gt;, or &lt;math&gt;{{n}\choose {r}} = \frac {n!} {r!(n-r)!}&lt;/math&gt;.<br /> <br /> ==Formulas/Identities==<br /> * &lt;math&gt;\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}&lt;/math&gt;<br /> <br /> * &lt;math&gt;\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}&lt;/math&gt;<br /> <br /> * &lt;math&gt;\sum_{x=0}^{n} \binom{n}{x} = 2^n&lt;/math&gt;<br /> <br /> One of the many proofs is by first inserting &lt;math&gt;a = b = 1&lt;/math&gt; into the [[binomial theorem]]. Because the combinations are the coefficients of &lt;math&gt;2^n&lt;/math&gt;, and a and b disappear because they are 1, the sum is &lt;math&gt;2^n&lt;/math&gt;.<br /> <br /> * &lt;math&gt;\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}&lt;/math&gt;<br /> <br /> * &lt;math&gt;\binom{n}{r}=\binom{n}{n-r}&lt;/math&gt;<br /> <br /> We can prove this by putting the combinations in their algebraic form.<br /> &lt;math&gt;\binom{n}{n-r}=\frac{n!}{(n-r)!(n-(n-r))!}&lt;/math&gt;. As we can see, &lt;math&gt;(n-(n-r))!=(n-n+r)=r!&lt;/math&gt;. By the [[commutative property]], &lt;math&gt;\frac{n!}{(n-r)!r!}=\frac{n!}{r!(n-r)!}&lt;/math&gt;. Because &lt;math&gt;\frac{n!}{r!(n-r)!}=\binom{n}{r}&lt;/math&gt;, by the [[transitive property]], we can conclude that this is true for all non-negative integers n and r where n is greater than or equal to r. Another reason this is true is because that choosing what you don't want is the same as choosing what you do want, because by choosing what you don't want, you imply that you choose the rest. This identity is also the reason why [[Pascal's Triangle]] is symmetrical.<br /> <br /> == Examples ==<br /> <br /> * [[2005_AIME_II_Problems/Problem_1 | 2005 AIME II Problem 1]]<br /> <br /> == See also ==<br /> <br /> * [[Combinatorics]]<br /> * [[Combinatorial identity]]<br /> * [[Permutations]]<br /> * [[Pascal's Triangle]]<br /> * [[Generating function]]<br /> <br /> [[Category:Combinatorics]]<br /> [[Category:Definition]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Distance_formula&diff=72565 Distance formula 2015-10-22T15:35:20Z <p>Greenpepper9999: Re added stub tag</p> <hr /> <div>The '''distance formula''' is a direct application of the [[Pythagorean Theorem]] in the setting of a [[Cartesian coordinate system]]. In the two-dimensional case, it says that the distance between two [[point]]s &lt;math&gt;P_1 = (x_1, y_1)&lt;/math&gt; and &lt;math&gt;P_2 = (x_2, y_2)&lt;/math&gt; is given by &lt;math&gt;d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}&lt;/math&gt;. In the &lt;math&gt;n&lt;/math&gt;-dimensional case, the distance between &lt;math&gt;(a_1,a_2,...,a_n)&lt;/math&gt; and &lt;math&gt;(b_1,b_2,...,b_n)&lt;/math&gt; is &lt;math&gt;\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\cdots+(a_n-b_n)^2}&lt;/math&gt;<br /> <br /> <br /> ==Shortest distance from a point to a line==<br /> the distance between the line &lt;math&gt;ax+by+c = 0&lt;/math&gt; and point &lt;math&gt;(x_1,y_1)&lt;/math&gt; is<br /> &lt;cmath&gt;\dfrac{|ax_1+by_1+c|}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> ===Proof===<br /> The equation &lt;math&gt;ax + by + c = 0&lt;/math&gt; can be written as &lt;math&gt;y = -\dfrac{a}{b}x - \dfrac{c}{a}&lt;/math&gt;<br /> Thus, the perpendicular line through &lt;math&gt;(x_1,y_1)&lt;/math&gt; is:<br /> &lt;cmath&gt;\dfrac{x-x_1}{a}=\dfrac{y-y_1}{b}=\dfrac{t}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> where &lt;math&gt;t&lt;/math&gt; is the parameter.<br /> <br /> &lt;math&gt;t&lt;/math&gt; will be the distance from the point &lt;math&gt;(x_1,y_1)&lt;/math&gt; along the perpendicular line to &lt;math&gt;(x,y)&lt;/math&gt;.<br /> So &lt;cmath&gt;x = x_1 + a \cdot \dfrac{t}{\sqrt{a^2+b^2}}&lt;/cmath&gt; and &lt;cmath&gt;y = y_1 + b \cdot \dfrac{t}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> This meets the given line &lt;math&gt;ax+by+c = 0&lt;/math&gt;, where:<br /> &lt;cmath&gt;a\left(x_1 + a \cdot \dfrac{t}{\sqrt{a^2+b^2}}\right) + b\left(y_1 + b \cdot \dfrac{t}{\sqrt{a^2+b^2}}\right) + c = 0&lt;/cmath&gt;<br /> &lt;cmath&gt;\implies ax_1 + by_1 + c + \dfrac{t(a^2+b^2)}{\sqrt{a^2+b^2}} + c = 0&lt;/cmath&gt;<br /> &lt;cmath&gt;\implies ax_1 + by_1 + c + t \cdot \sqrt{a^2+b^2} = 0&lt;/cmath&gt;<br /> <br /> , so:<br /> &lt;cmath&gt; t \cdot \sqrt{a^2+b^2} = -(ax_1+by_1+c)&lt;/cmath&gt;<br /> &lt;cmath&gt;\implies t = \dfrac{-(ax_1+by_1+c)}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> Therefore the perpendicular distance from &lt;math&gt;(x_1,y_1)&lt;/math&gt; to the line &lt;math&gt;ax+by+c = 0&lt;/math&gt; is:<br /> <br /> &lt;cmath&gt;|t| = \dfrac{|ax_1 + by_1 + c|}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> <br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Distance_formula&diff=72564 Distance formula 2015-10-22T15:34:36Z <p>Greenpepper9999: Cleaning up</p> <hr /> <div>The '''distance formula''' is a direct application of the [[Pythagorean Theorem]] in the setting of a [[Cartesian coordinate system]]. In the two-dimensional case, it says that the distance between two [[point]]s &lt;math&gt;P_1 = (x_1, y_1)&lt;/math&gt; and &lt;math&gt;P_2 = (x_2, y_2)&lt;/math&gt; is given by &lt;math&gt;d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}&lt;/math&gt;. In the &lt;math&gt;n&lt;/math&gt;-dimensional case, the distance between &lt;math&gt;(a_1,a_2,...,a_n)&lt;/math&gt; and &lt;math&gt;(b_1,b_2,...,b_n)&lt;/math&gt; is &lt;math&gt;\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\cdots+(a_n-b_n)^2}&lt;/math&gt;<br /> <br /> <br /> ==Shortest distance from a point to a line==<br /> the distance between the line &lt;math&gt;ax+by+c = 0&lt;/math&gt; and point &lt;math&gt;(x_1,y_1)&lt;/math&gt; is<br /> &lt;cmath&gt;\dfrac{|ax_1+by_1+c|}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> ===Proof===<br /> The equation &lt;math&gt;ax + by + c = 0&lt;/math&gt; can be written as &lt;math&gt;y = -\dfrac{a}{b}x - \dfrac{c}{a}&lt;/math&gt;<br /> Thus, the perpendicular line through &lt;math&gt;(x_1,y_1)&lt;/math&gt; is:<br /> &lt;cmath&gt;\dfrac{x-x_1}{a}=\dfrac{y-y_1}{b}=\dfrac{t}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> where &lt;math&gt;t&lt;/math&gt; is the parameter.<br /> <br /> &lt;math&gt;t&lt;/math&gt; will be the distance from the point &lt;math&gt;(x_1,y_1)&lt;/math&gt; along the perpendicular line to &lt;math&gt;(x,y)&lt;/math&gt;.<br /> So &lt;cmath&gt;x = x_1 + a \cdot \dfrac{t}{\sqrt{a^2+b^2}}&lt;/cmath&gt; and &lt;cmath&gt;y = y_1 + b \cdot \dfrac{t}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> This meets the given line &lt;math&gt;ax+by+c = 0&lt;/math&gt;, where:<br /> &lt;cmath&gt;a\left(x_1 + a \cdot \dfrac{t}{\sqrt{a^2+b^2}}\right) + b\left(y_1 + b \cdot \dfrac{t}{\sqrt{a^2+b^2}}\right) + c = 0&lt;/cmath&gt;<br /> &lt;cmath&gt;\implies ax_1 + by_1 + c + \dfrac{t(a^2+b^2)}{\sqrt{a^2+b^2}} + c = 0&lt;/cmath&gt;<br /> &lt;cmath&gt;\implies ax_1 + by_1 + c + t \cdot \sqrt{a^2+b^2} = 0&lt;/cmath&gt;<br /> <br /> , so:<br /> &lt;cmath&gt; t \cdot \sqrt{a^2+b^2} = -(ax_1+by_1+c)&lt;/cmath&gt;<br /> &lt;cmath&gt;\implies t = \dfrac{-(ax_1+by_1+c)}{\sqrt{a^2+b^2}}&lt;/cmath&gt;<br /> <br /> Therefore the perpendicular distance from &lt;math&gt;(x_1,y_1)&lt;/math&gt; to the line &lt;math&gt;ax+by+c = 0&lt;/math&gt; is:<br /> <br /> &lt;cmath&gt;|t| = \dfrac{|ax_1 + by_1 + c|}{\sqrt{a^2+b^2}}&lt;/cmath&gt;</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=AoPS_Wiki:Protected_page&diff=72446 AoPS Wiki:Protected page 2015-10-12T16:56:30Z <p>Greenpepper9999: </p> <hr /> <div>{{stub}}<br /> <br /> Some pages are protected on the AoPSWiki, since they serve to introduce new people to the AoPSWiki. Normally, the prima facie to a certain webpage serves whether or not that person will remain on that website. Therefore, in order to prevent frequent vandalism on important pages of the AoPSWiki, they have been locked. An example is the [[Main Page]].<br /> <br /> More examples at [https://www.artofproblemsolving.com/Wiki/index.php/Special:ProtectedPages]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Change_of_base_formula&diff=72440 Change of base formula 2015-10-12T14:44:39Z <p>Greenpepper9999: Proof</p> <hr /> <div>The '''change of base formula''' is a formula for expressing a [[logarithm]] in one base in terms of logarithms in other bases.<br /> <br /> For any [[positive]] [[real number]]s &lt;math&gt;d,a,b&lt;/math&gt; such that neither &lt;math&gt;d&lt;/math&gt; nor &lt;math&gt;b&lt;/math&gt; are &lt;math&gt;1&lt;/math&gt;, we have<br /> <br /> &lt;cmath&gt;\log_b a = \frac{\log_d a}{\log_d b}.&lt;/cmath&gt;<br /> <br /> This allows us to rewrite a logarithm in base &lt;math&gt;b&lt;/math&gt; in terms of logarithms in any base &lt;math&gt;d&lt;/math&gt;. This formula can also be written <br /> <br /> &lt;cmath&gt;\log_b a \cdot \log_d b = \log_d a.&lt;/cmath&gt;<br /> <br /> ==Proof==<br /> Let &lt;math&gt;\log_b a = y&lt;/math&gt;.<br /> <br /> Then &lt;math&gt;b^y = a&lt;/math&gt;.<br /> <br /> And, taking the &lt;math&gt;\log_d&lt;/math&gt; of both sides, we get <br /> &lt;cmath&gt;\log_d (b^y) = \log_d (a)&lt;/cmath&gt;<br /> <br /> By the properties of logarithms, <br /> &lt;cmath&gt;y\log_d b = \log_d a&lt;/cmath&gt;<br /> <br /> Substituting for y, <br /> &lt;cmath&gt;\log_b a \cdot \log_d b = \log_d a&lt;/cmath&gt;<br /> == Use for computations ==<br /> <br /> The change of base formula is useful for simplifying certain computations involving logarithms. For example, we have by the change of base formula that <br /> <br /> &lt;cmath&gt;\log_{\frac{1}{4}} 32\sqrt{2} = \frac{\log_2 32\sqrt{2}}{\log_2 \frac{1}{4}} = \frac{\frac{11}{2}}{-2} = -\frac{11}{4}.&lt;/cmath&gt;<br /> <br /> The formula can also be useful when calculating logarithms on a calculator. Many calculators have only functions for calculating base-10 and base-e logarithms. But you can still calculate logs in other bases, you just need to use the change of base formula to put in in base 10. For example, if you wanted to calculate &lt;math&gt;\log_{7} 19&lt;/math&gt;, you would first convert it to the form &lt;math&gt;\frac{\log_{10}{19}}{\log_{10}{7}}&lt;/math&gt;. Then you would evaluate it using the base-10 log function on the calculator.<br /> <br /> == Special cases and consequences ==<br /> <br /> Many other logarithm rules can be written in terms of the change of base formula. For example, we have that &lt;math&gt;\log_b a = \frac{\log_a a}{\log_a b} = \frac{1}{\log_a b}&lt;/math&gt;. Using the second form of the change of base formula gives &lt;math&gt;\log_b a^n = \log_b a \cdot \log_a a^n = n \log_b a&lt;/math&gt;.<br /> <br /> One consequence of the change of base formula is that for positive constants &lt;math&gt;a, b&lt;/math&gt;, the functions &lt;math&gt;f(x) = \log_a x&lt;/math&gt; and &lt;math&gt;g(x) = \log_b x&lt;/math&gt; differ by a constant factor, &lt;math&gt;f(x) = (\log_a b) g(x)&lt;/math&gt; for all &lt;math&gt;x &gt; 0&lt;/math&gt;.<br /> <br /> <br /> {{stub}}<br /> [[Category:Elementary Algebra]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Change_of_base_formula&diff=72439 Change of base formula 2015-10-12T14:24:11Z <p>Greenpepper9999: /* Use for computations */</p> <hr /> <div>The '''change of base formula''' is a formula for expressing a [[logarithm]] in one base in terms of logarithms in other bases.<br /> <br /> For any [[positive]] [[real number]]s &lt;math&gt;d,a,b&lt;/math&gt; such that neither &lt;math&gt;d&lt;/math&gt; nor &lt;math&gt;b&lt;/math&gt; are &lt;math&gt;1&lt;/math&gt;, we have<br /> <br /> &lt;cmath&gt;\log_b a = \frac{\log_d a}{\log_d b}.&lt;/cmath&gt;<br /> <br /> This allows us to rewrite a logarithm in base &lt;math&gt;b&lt;/math&gt; in terms of logarithms in any base &lt;math&gt;d&lt;/math&gt;. This formula can also be written <br /> <br /> &lt;cmath&gt;\log_b a \cdot \log_d b = \log_d a.&lt;/cmath&gt;<br /> <br /> === Use for computations ===<br /> <br /> The change of base formula is useful for simplifying certain computations involving logarithms. For example, we have by the change of base formula that <br /> <br /> &lt;cmath&gt;\log_{\frac{1}{4}} 32\sqrt{2} = \frac{\log_2 32\sqrt{2}}{\log_2 \frac{1}{4}} = \frac{\frac{11}{2}}{-2} = -\frac{11}{4}.&lt;/cmath&gt;<br /> <br /> The formula can also be useful when calculating logarithms on a calculator. Many calculators have only functions for calculating base-10 and base-e logarithms. But you can still calculate logs in other bases, you just need to use the change of base formula to put in in base 10. For example, if you wanted to calculate &lt;math&gt;\log_{7} 19&lt;/math&gt;, you would first convert it to the form &lt;math&gt;\frac{\log_{10}{19}}{\log_{10}{7}}&lt;/math&gt;. Then you would evaluate it using the base-10 log function on the calculator.<br /> <br /> === Special cases and consequences ===<br /> <br /> Many other logarithm rules can be written in terms of the change of base formula. For example, we have that &lt;math&gt;\log_b a = \frac{\log_a a}{\log_a b} = \frac{1}{\log_a b}&lt;/math&gt;. Using the second form of the change of base formula gives &lt;math&gt;\log_b a^n = \log_b a \cdot \log_a a^n = n \log_b a&lt;/math&gt;.<br /> <br /> One consequence of the change of base formula is that for positive constants &lt;math&gt;a, b&lt;/math&gt;, the functions &lt;math&gt;f(x) = \log_a x&lt;/math&gt; and &lt;math&gt;g(x) = \log_b x&lt;/math&gt; differ by a constant factor, &lt;math&gt;f(x) = (\log_a b) g(x)&lt;/math&gt; for all &lt;math&gt;x &gt; 0&lt;/math&gt;.<br /> <br /> <br /> {{stub}}<br /> [[Category:Elementary Algebra]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=British_Flag_Theorem&diff=72433 British Flag Theorem 2015-10-12T00:27:07Z <p>Greenpepper9999: Problems</p> <hr /> <div>The '''British flag theorem''' says that if a point P is chosen inside [[rectangle]] ABCD then &lt;math&gt;AP^{2}+CP^{2}=BP^{2}+DP^{2}&lt;/math&gt;. The theorem is called the British flag theorem due to the similarities between the British flag and a diagram of the points (shown below):<br /> [[File:UK.jpg|left|frame|British Flag]]<br /> &lt;asy&gt;<br /> size(200);<br /> pair A,B,C,D,P;<br /> A=(0,0);<br /> B=(200,0);<br /> C=(200,150);<br /> D=(0,150);<br /> P=(124,85);<br /> draw(A--B--C--D--cycle);<br /> draw(A--P);<br /> draw(B--P);<br /> draw(C--P);<br /> draw(D--P);<br /> label(&quot;$A$&quot;,A,(-1,0));<br /> dot(A);<br /> label(&quot;$B$&quot;,B,(0,-1));<br /> dot(B);<br /> label(&quot;$C$&quot;,C,(1,0));<br /> dot(C);<br /> label(&quot;$D$&quot;,D,(-1,0));<br /> dot(D);<br /> dot(P);<br /> label(&quot;$P$&quot;,P,NNE);<br /> draw((0,85)--(200,85));<br /> draw((124,0)--(124,150));<br /> label(&quot;$w$&quot;,(124,0),(0,-1));<br /> label(&quot;$x$&quot;,(200,85),(1,0));<br /> label(&quot;$y$&quot;,(124,150),(0,1));<br /> label(&quot;$z$&quot;,(0,85),(-1,0));<br /> dot((124,0));<br /> dot((200,85));<br /> dot((124,150));<br /> dot((0,85));<br /> &lt;/asy&gt;<br /> <br /> The theorem also applies if the point &lt;math&gt;P&lt;/math&gt; is selected outside or on the boundary of the rectangle, although the proof is harder to visualize in this case.<br /> <br /> == Proof ==<br /> <br /> Squares of lengths suggest right triangles. We build right triangles by drawing a line through &lt;math&gt;P&lt;/math&gt; perpendicular to two sides of the rectangle, as shown below. Both &lt;math&gt;AXYD&lt;/math&gt; and &lt;math&gt;BXYC&lt;/math&gt; are rectangles. <br /> &lt;asy&gt;<br /> pair A,B,C,D,P,X,Y;<br /> A = (0,0);<br /> B=(1,0);<br /> D = (0,0.7);<br /> C = B+D;<br /> P = (0.3,0.4);<br /> X = (0.3,0);<br /> Y=(0.3,0.7);<br /> draw(A--B--C--D--A--P--C);<br /> draw(X--Y);<br /> draw(B--P--D);<br /> draw(rightanglemark(P,X,A,1.5));<br /> draw(rightanglemark(B,X,P,1.5));<br /> draw(rightanglemark(P,Y,C,1.5));<br /> draw(rightanglemark(D,Y,P,1.5));<br /> label(&quot;$A$&quot;,A,SW);<br /> label(&quot;$B$&quot;,B,SE);<br /> label(&quot;$C$&quot;,C,NE);<br /> label(&quot;$D$&quot;,D,NW);<br /> label(&quot;$Y$&quot;,Y,N);<br /> label(&quot;$X$&quot;,X,S);<br /> label(&quot;$P$&quot;,P+(0,0.03),NE);&lt;/asy&gt;<br /> Applying the Pythagorean Theorem to each of the four right triangles in the diagram, we have<br /> &lt;cmath&gt; \begin{align*}PA^2 &amp;= AX^2+XP^2,\\ PB^2 &amp;= BX^2+XP^2,\\ PC^2 &amp;= CY^2+YP^2,\\ PD^2 &amp;= DY^2+YP^2.\end{align*} &lt;/cmath&gt;<br /> So, we have<br /> &lt;cmath&gt; \begin{align*}PA^2+PC^2 &amp;= AX^2+XP^2+CY^2+YP^2,\\ PB^2+PD^2 &amp;= BX^2+XP^2+DY^2+YP^2.\end{align*} &lt;/cmath&gt;<br /> From rectangles &lt;math&gt;AXYD&lt;/math&gt; and &lt;math&gt;BXYC&lt;/math&gt;, we have &lt;math&gt;AX = DY&lt;/math&gt; and &lt;math&gt;BX = CY&lt;/math&gt;, so the expressions above for &lt;math&gt;PA^2 + PC^2&lt;/math&gt; and &lt;math&gt;PB^2 + PD^2&lt;/math&gt; are equal, as desired.<br /> <br /> ==Problems==<br /> [http://artofproblemsolving.com/community/c3h579390 2014 MATHCOUNTS Chapter Sprint #29]<br /> [[Category:geometry]]<br /> <br /> [[Category:Theorems]]<br /> <br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Asymptote_(geometry)&diff=72432 Asymptote (geometry) 2015-10-11T20:21:52Z <p>Greenpepper9999: Added picture</p> <hr /> <div>:''For the vector graphics language, see [[Asymptote (Vector Graphics Language)]].''<br /> <br /> An '''asymptote''' is a [[line]] or [[curve]] that a certain [[function]] approaches.<br /> [[File:Asymptote_graph.png|thumb|300px|The function &lt;math&gt;y=\tfrac{2x}{x-2}&lt;/math&gt; has a vertical asymptote at x=2 and a horizontal asymptote at y=2]]<br /> <br /> Linear asymptotes can be of three different kinds: horizontal, vertical or slanted (oblique). <br /> <br /> <br /> == Vertical Asymptotes ==<br /> The vertical asymptote can be found by finding values of &lt;math&gt;x&lt;/math&gt; that make the function undefined. Generally, it is found by setting the denominator of a rational function to zero.<br /> <br /> If the numerator and denominator of a rational function share a factor, this factor is not a vertical asymptote. Instead, it appears as a hole in the graph.<br /> <br /> A rational function may have more than one vertical asymptote.<br /> <br /> ===Example Problems===<br /> Find the vertical asymptotes of 1) &lt;math&gt;y = \frac{1}{x^2-5x}&lt;/math&gt; 2) &lt;math&gt;\tan 3x&lt;/math&gt;.<br /> <br /> ====Solution====<br /> 1) To find the vertical asymptotes, let &lt;math&gt;x^2-5x=0&lt;/math&gt;. Solving the equation:<br /> <br /> &lt;cmath&gt;\begin{eqnarray*}x^2-5x&amp;=&amp;0\\x&amp;=&amp;\boxed{0,5}\end{eqnarray*}&lt;/cmath&gt;<br /> <br /> So the vertical asymptotes are &lt;math&gt;x=0,x=5&lt;/math&gt;.<br /> <br /> 2) Since &lt;math&gt;\tan 3x = \frac{\sin 3x}{\cos 3x}&lt;/math&gt;, we need to find where &lt;math&gt;\cos 3x = 0&lt;/math&gt;. The cosine function is zero at &lt;math&gt;\frac{\pi}{2} + n\pi&lt;/math&gt; for all [[integer]]s &lt;math&gt;n&lt;/math&gt;; thus the functions is undefined at &lt;math&gt;x=\frac{\pi}{6} + \frac{n\pi}{3}&lt;/math&gt;.<br /> <br /> == Horizontal Asymptotes ==<br /> For rational functions in the form of &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt; where &lt;math&gt;P(x), Q(x)&lt;/math&gt; are both [[polynomial]]s:<br /> <br /> 1. If the [[Degree of a polynomial | degree ]] of &lt;math&gt;Q(x)&lt;/math&gt; is greater than that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at &lt;math&gt;y = 0&lt;/math&gt;. This can be seen by noting that as &lt;math&gt;x&lt;/math&gt; increases, &lt;math&gt;Q(x)&lt;/math&gt; increases much faster than &lt;math&gt;P(x)&lt;/math&gt; does. Since the denominator increases faster than the numerator, as x approaches infinity, y gets smaller until it approaches zero. A similar trend can be seen as x decreases.<br /> <br /> 2. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is equal to that of the degree of &lt;math&gt;P(x)&lt;/math&gt;, then the horizontal asymptote is at the quotient of the leading coefficient of &lt;math&gt;P(x)&lt;/math&gt; over the leading coefficient of &lt;math&gt;Q(x)&lt;/math&gt;. <br /> <br /> 3. If the degree of &lt;math&gt;Q(x)&lt;/math&gt; is less than the degree of &lt;math&gt;P(x)&lt;/math&gt;, see below (slanted asymptotes)<br /> <br /> A function may not have more than one horizontal asymptote. Functions with a &quot;middle section&quot; may cross the horizontal asymptote at one point. To find this point, set y=horizontal asymptote and solve.<br /> <br /> ===Example Problem===<br /> Find the horizontal asymptote of &lt;math&gt;f(x) = \frac{x^2 - 3x + 2}{-2x^2 + 15x + 10000}&lt;/math&gt;.<br /> <br /> ====Solution====<br /> The numerator has the same degree as the denominator, so the horizontal asymptote is the quotient of the leading coefficients:<br /> &lt;math&gt;y= \frac {1} {-2}&lt;/math&gt;<br /> <br /> == Oblique (Slanted) Asymptotes ==<br /> For rational functions &lt;math&gt;\frac{P(x)}{Q(x)}&lt;/math&gt;, an oblique asymptote occurs when the degree of &lt;math&gt;P(x)&lt;/math&gt; is one greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;. If the degree of &lt;math&gt;P(x)&lt;/math&gt; is two or more greater than the degree of &lt;math&gt;Q(x)&lt;/math&gt;, then we get a curved asymptote. Again, like horizontal asymptotes, it is possible to get crossing points of oblique asymptotes.<br /> <br /> For rational functions, we can find the oblique asymptote simply by long division, omitting the remainder and setting y=quotient.<br /> <br /> ===Example Problem===<br /> Find the oblique asymptote of &lt;math&gt;y= \frac{x^2+2x+4} {x+1}&lt;/math&gt;<br /> <br /> '''Solution'''<br /> <br /> &lt;math&gt;\frac{x^2+2x+4}{x+1}= x+1+\frac{3} {x+1}&lt;/math&gt;<br /> <br /> <br /> The oblique asymptote is &lt;math&gt;y=x+1&lt;/math&gt;<br /> <br /> ==External Links==<br /> 3 minute asymptote lesson: [http://www.youtube.com/watch?v=4Cqm07W2teM&amp;feature=plcp]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=File:Asymptote_graph.png&diff=72431 File:Asymptote graph.png 2015-10-11T20:06:37Z <p>Greenpepper9999: Graph of function 2x/(x-2)</p> <hr /> <div>Graph of function 2x/(x-2)</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=AoPS_Wiki:Sandbox&diff=72430 AoPS Wiki:Sandbox 2015-10-11T19:48:42Z <p>Greenpepper9999: </p> <hr /> <div>{{AoPSWiki:Sandbox/header}} &lt;!-- Please do not delete this line --&gt;<br /> &lt;nowiki&gt;<br /> sss &lt;br /&gt; yyy<br /> &lt;/nowiki&gt; <br /> &lt;pre&gt;dddd&lt;/pre&gt;<br /> &lt;asy&gt;<br /> unitsize(0.15inch);<br /> draw((0,0)--(2,0)--(2,1)--(0,1)--cycle);<br /> draw((1,0)--(1,1));<br /> label(&quot;2&quot;,(0.5,-0.3),N);<br /> label(&quot;4&quot;,(1.5,-0.3),N);<br /> draw((0,1.5)--(1,1.5)--(1,3.5)--(0,3.5)--cycle);<br /> draw((0,2.5)--(1,2.5));<br /> label(&quot;5&quot;,(0.5,1.2),N);<br /> label(&quot;7&quot;,(0.5,2.2),N);<br /> draw((3,-1)--(4,-1)--(4,-2)--(3,-2)--cycle);<br /> label(&quot;7&quot;,(3.5,-0.7),S);<br /> draw((4,1)--(4,2)--(6,2)--(6,1)--cycle);<br /> draw((5,1)--(5,2));<br /> label(&quot;4&quot;,(4.5,0.7),N);<br /> label(&quot;7&quot;,(5.5,0.7),N);<br /> draw((3,3)--(3,4)--(6,4)--(6,3)--cycle);<br /> draw((4,3)--(4,4));<br /> draw((5,3)--(5,4));<br /> label(&quot;4&quot;,(3.5,2.7),N);<br /> label(&quot;5&quot;,(4.5,2.7),N);<br /> label(&quot;6&quot;,(5.5,2.7),N);<br /> draw((7,0)--(7,3)--(8,3)--(8,0)--cycle);<br /> draw((7,1)--(8,1));<br /> draw((7,2)--(8,2));<br /> label(&quot;2&quot;,(7.5,-0.3),N);<br /> label(&quot;5&quot;,(7.5,0.7),N);<br /> label(&quot;4&quot;,(7.5,1.7),N);<br /> draw((8.5,0)--(9.5,0)--(9.5,3)--(8.5,3)--cycle);<br /> draw((8.5,1)--(9.5,1));<br /> draw((8.5,2)--(9.5,2));<br /> label(&quot;5&quot;,(9,-0.3),N);<br /> label(&quot;4&quot;,(9,0.7),N);<br /> label(&quot;7&quot;,(9,1.7),N);<br /> draw((10,0)--(14,0)--(14,4)--(10,4)--cycle);<br /> draw((12,0)--(12,4));<br /> draw((13,0)--(13,4));<br /> draw((11,0)--(11,4));<br /> draw((10,1)--(14,1));<br /> draw((10,2)--(14,2));<br /> draw((10,3)--(14,3));<br /> label(&quot;ROW 1&quot;,(14,3.5),E);<br /> label(&quot;ROW 2&quot;,(14,2.5),E);<br /> &lt;/asy&gt;<br /> <br /> <br /> <br /> &lt;aops&gt;sdfvsdfv&lt;/aops&gt;<br /> <br /> [[file:Bold button.jpeg|25px]]<br /> <br /> &lt;a href=&quot;www.aops.com&quot;&gt;Aops&lt;/a&gt;<br /> <br /> 123\\456<br /> 222\\ 1<br /> 222 \\ w<br /> )\\)<br /> Hmmm<br /> &lt;pre class=&quot;python&quot; style=&quot;font-family:monospace;&quot;&gt;print(3)&lt;/pre&gt;<br /> =0=<br /> <br /> <br /> <br /> <br /> <br /> &lt;asy&gt;draw((1/10,10)..(1/3,3)..(1/2,2)..(1,1)..(2, 1/2)..(3,1/3)..(4,1/4)..(5,1/5)..(6,1/6)..(7,1/7));&lt;/asy&gt;<br /> &lt;asy&gt;<br /> real f(real x) {<br /> return 2x/(x-2);<br /> }<br /> xaxis(-10,10, Arrows(5)); <br /> yaxis(-10,10, Arrows(5)); <br /> <br /> path g = graph(f,2.5,10);<br /> path h = graph(f, -6, 1.5);<br /> draw(h, arrow=Arrows(5), p=blue);<br /> draw(g, arrow=Arrows(5), p=blue);<br /> draw((2,-10)--(2,10), gray+dashed);<br /> &lt;/asy&gt;</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=AoPS_Wiki:Sandbox&diff=72429 AoPS Wiki:Sandbox 2015-10-11T19:40:34Z <p>Greenpepper9999: </p> <hr /> <div>{{AoPSWiki:Sandbox/header}} &lt;!-- Please do not delete this line --&gt;<br /> &lt;nowiki&gt;<br /> sss &lt;br /&gt; yyy<br /> &lt;/nowiki&gt; <br /> &lt;pre&gt;dddd&lt;/pre&gt;<br /> &lt;asy&gt;<br /> unitsize(0.15inch);<br /> draw((0,0)--(2,0)--(2,1)--(0,1)--cycle);<br /> draw((1,0)--(1,1));<br /> label(&quot;2&quot;,(0.5,-0.3),N);<br /> label(&quot;4&quot;,(1.5,-0.3),N);<br /> draw((0,1.5)--(1,1.5)--(1,3.5)--(0,3.5)--cycle);<br /> draw((0,2.5)--(1,2.5));<br /> label(&quot;5&quot;,(0.5,1.2),N);<br /> label(&quot;7&quot;,(0.5,2.2),N);<br /> draw((3,-1)--(4,-1)--(4,-2)--(3,-2)--cycle);<br /> label(&quot;7&quot;,(3.5,-0.7),S);<br /> draw((4,1)--(4,2)--(6,2)--(6,1)--cycle);<br /> draw((5,1)--(5,2));<br /> label(&quot;4&quot;,(4.5,0.7),N);<br /> label(&quot;7&quot;,(5.5,0.7),N);<br /> draw((3,3)--(3,4)--(6,4)--(6,3)--cycle);<br /> draw((4,3)--(4,4));<br /> draw((5,3)--(5,4));<br /> label(&quot;4&quot;,(3.5,2.7),N);<br /> label(&quot;5&quot;,(4.5,2.7),N);<br /> label(&quot;6&quot;,(5.5,2.7),N);<br /> draw((7,0)--(7,3)--(8,3)--(8,0)--cycle);<br /> draw((7,1)--(8,1));<br /> draw((7,2)--(8,2));<br /> label(&quot;2&quot;,(7.5,-0.3),N);<br /> label(&quot;5&quot;,(7.5,0.7),N);<br /> label(&quot;4&quot;,(7.5,1.7),N);<br /> draw((8.5,0)--(9.5,0)--(9.5,3)--(8.5,3)--cycle);<br /> draw((8.5,1)--(9.5,1));<br /> draw((8.5,2)--(9.5,2));<br /> label(&quot;5&quot;,(9,-0.3),N);<br /> label(&quot;4&quot;,(9,0.7),N);<br /> label(&quot;7&quot;,(9,1.7),N);<br /> draw((10,0)--(14,0)--(14,4)--(10,4)--cycle);<br /> draw((12,0)--(12,4));<br /> draw((13,0)--(13,4));<br /> draw((11,0)--(11,4));<br /> draw((10,1)--(14,1));<br /> draw((10,2)--(14,2));<br /> draw((10,3)--(14,3));<br /> label(&quot;ROW 1&quot;,(14,3.5),E);<br /> label(&quot;ROW 2&quot;,(14,2.5),E);<br /> &lt;/asy&gt;<br /> <br /> <br /> <br /> &lt;aops&gt;sdfvsdfv&lt;/aops&gt;<br /> <br /> [[file:Bold button.jpeg|25px]]<br /> <br /> &lt;a href=&quot;www.aops.com&quot;&gt;Aops&lt;/a&gt;<br /> <br /> 123\\456<br /> 222\\ 1<br /> 222 \\ w<br /> )\\)<br /> Hmmm<br /> &lt;pre class=&quot;python&quot; style=&quot;font-family:monospace;&quot;&gt;print(3)&lt;/pre&gt;<br /> =0=<br /> <br /> <br /> <br /> <br /> <br /> &lt;asy&gt;draw((1/10,10)..(1/3,3)..(1/2,2)..(1,1)..(2, 1/2)..(3,1/3)..(4,1/4)..(5,1/5)..(6,1/6)..(7,1/7));&lt;/asy&gt;<br /> &lt;asy&gt;<br /> real f(real x) {<br /> return 2x/(x-2);<br /> }<br /> xaxis(-10,10); <br /> yaxis(-10,10); <br /> <br /> path g = graph(f,2.5,10);<br /> path h = graph(f, -6, 1.5);<br /> draw(g^^h, blue);<br /> &lt;/asy&gt;</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=AoPS_Wiki:Sandbox&diff=72428 AoPS Wiki:Sandbox 2015-10-11T18:51:32Z <p>Greenpepper9999: </p> <hr /> <div>{{AoPSWiki:Sandbox/header}} &lt;!-- Please do not delete this line --&gt;<br /> &lt;nowiki&gt;<br /> sss &lt;br /&gt; yyy<br /> &lt;/nowiki&gt; <br /> &lt;pre&gt;dddd&lt;/pre&gt;<br /> &lt;asy&gt;<br /> unitsize(0.15inch);<br /> draw((0,0)--(2,0)--(2,1)--(0,1)--cycle);<br /> draw((1,0)--(1,1));<br /> label(&quot;2&quot;,(0.5,-0.3),N);<br /> label(&quot;4&quot;,(1.5,-0.3),N);<br /> draw((0,1.5)--(1,1.5)--(1,3.5)--(0,3.5)--cycle);<br /> draw((0,2.5)--(1,2.5));<br /> label(&quot;5&quot;,(0.5,1.2),N);<br /> label(&quot;7&quot;,(0.5,2.2),N);<br /> draw((3,-1)--(4,-1)--(4,-2)--(3,-2)--cycle);<br /> label(&quot;7&quot;,(3.5,-0.7),S);<br /> draw((4,1)--(4,2)--(6,2)--(6,1)--cycle);<br /> draw((5,1)--(5,2));<br /> label(&quot;4&quot;,(4.5,0.7),N);<br /> label(&quot;7&quot;,(5.5,0.7),N);<br /> draw((3,3)--(3,4)--(6,4)--(6,3)--cycle);<br /> draw((4,3)--(4,4));<br /> draw((5,3)--(5,4));<br /> label(&quot;4&quot;,(3.5,2.7),N);<br /> label(&quot;5&quot;,(4.5,2.7),N);<br /> label(&quot;6&quot;,(5.5,2.7),N);<br /> draw((7,0)--(7,3)--(8,3)--(8,0)--cycle);<br /> draw((7,1)--(8,1));<br /> draw((7,2)--(8,2));<br /> label(&quot;2&quot;,(7.5,-0.3),N);<br /> label(&quot;5&quot;,(7.5,0.7),N);<br /> label(&quot;4&quot;,(7.5,1.7),N);<br /> draw((8.5,0)--(9.5,0)--(9.5,3)--(8.5,3)--cycle);<br /> draw((8.5,1)--(9.5,1));<br /> draw((8.5,2)--(9.5,2));<br /> label(&quot;5&quot;,(9,-0.3),N);<br /> label(&quot;4&quot;,(9,0.7),N);<br /> label(&quot;7&quot;,(9,1.7),N);<br /> draw((10,0)--(14,0)--(14,4)--(10,4)--cycle);<br /> draw((12,0)--(12,4));<br /> draw((13,0)--(13,4));<br /> draw((11,0)--(11,4));<br /> draw((10,1)--(14,1));<br /> draw((10,2)--(14,2));<br /> draw((10,3)--(14,3));<br /> label(&quot;ROW 1&quot;,(14,3.5),E);<br /> label(&quot;ROW 2&quot;,(14,2.5),E);<br /> &lt;/asy&gt;<br /> <br /> <br /> <br /> &lt;aops&gt;sdfvsdfv&lt;/aops&gt;<br /> <br /> [[file:Bold button.jpeg|25px]]<br /> <br /> &lt;a href=&quot;www.aops.com&quot;&gt;Aops&lt;/a&gt;<br /> <br /> 123\\456<br /> 222\\ 1<br /> 222 \\ w<br /> )\\)<br /> Hmmm<br /> &lt;pre class=&quot;python&quot; style=&quot;font-family:monospace;&quot;&gt;print(3)&lt;/pre&gt;<br /> =0=<br /> <br /> <br /> <br /> <br /> <br /> &lt;asy&gt;draw((1/10,10)..(1/3,3)..(1/2,2)..(1,1)..(2, 1/2)..(3,1/3)..(4,1/4)..(5,1/5)..(6,1/6)..(7,1/7));&lt;/asy&gt;<br /> &lt;asy&gt;<br /> real f(real x) {<br /> return 1/x;<br /> }<br /> Label t; <br /> xaxis(0,7,Ticks(t, 2.0, Size=2)); <br /> yaxis(0,7,Ticks(t, 2.0, Size=2)); <br /> <br /> path g = graph(f,1/7,7);<br /> draw(g);<br /> &lt;/asy&gt;</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=AoPS_Wiki:Sandbox&diff=72426 AoPS Wiki:Sandbox 2015-10-11T18:19:29Z <p>Greenpepper9999: </p> <hr /> <div>{{AoPSWiki:Sandbox/header}} &lt;!-- Please do not delete this line --&gt;<br /> &lt;nowiki&gt;<br /> sss &lt;br /&gt; yyy<br /> &lt;/nowiki&gt; <br /> &lt;pre&gt;dddd&lt;/pre&gt;<br /> &lt;asy&gt;<br /> unitsize(0.15inch);<br /> draw((0,0)--(2,0)--(2,1)--(0,1)--cycle);<br /> draw((1,0)--(1,1));<br /> label(&quot;2&quot;,(0.5,-0.3),N);<br /> label(&quot;4&quot;,(1.5,-0.3),N);<br /> draw((0,1.5)--(1,1.5)--(1,3.5)--(0,3.5)--cycle);<br /> draw((0,2.5)--(1,2.5));<br /> label(&quot;5&quot;,(0.5,1.2),N);<br /> label(&quot;7&quot;,(0.5,2.2),N);<br /> draw((3,-1)--(4,-1)--(4,-2)--(3,-2)--cycle);<br /> label(&quot;7&quot;,(3.5,-0.7),S);<br /> draw((4,1)--(4,2)--(6,2)--(6,1)--cycle);<br /> draw((5,1)--(5,2));<br /> label(&quot;4&quot;,(4.5,0.7),N);<br /> label(&quot;7&quot;,(5.5,0.7),N);<br /> draw((3,3)--(3,4)--(6,4)--(6,3)--cycle);<br /> draw((4,3)--(4,4));<br /> draw((5,3)--(5,4));<br /> label(&quot;4&quot;,(3.5,2.7),N);<br /> label(&quot;5&quot;,(4.5,2.7),N);<br /> label(&quot;6&quot;,(5.5,2.7),N);<br /> draw((7,0)--(7,3)--(8,3)--(8,0)--cycle);<br /> draw((7,1)--(8,1));<br /> draw((7,2)--(8,2));<br /> label(&quot;2&quot;,(7.5,-0.3),N);<br /> label(&quot;5&quot;,(7.5,0.7),N);<br /> label(&quot;4&quot;,(7.5,1.7),N);<br /> draw((8.5,0)--(9.5,0)--(9.5,3)--(8.5,3)--cycle);<br /> draw((8.5,1)--(9.5,1));<br /> draw((8.5,2)--(9.5,2));<br /> label(&quot;5&quot;,(9,-0.3),N);<br /> label(&quot;4&quot;,(9,0.7),N);<br /> label(&quot;7&quot;,(9,1.7),N);<br /> draw((10,0)--(14,0)--(14,4)--(10,4)--cycle);<br /> draw((12,0)--(12,4));<br /> draw((13,0)--(13,4));<br /> draw((11,0)--(11,4));<br /> draw((10,1)--(14,1));<br /> draw((10,2)--(14,2));<br /> draw((10,3)--(14,3));<br /> label(&quot;ROW 1&quot;,(14,3.5),E);<br /> label(&quot;ROW 2&quot;,(14,2.5),E);<br /> &lt;/asy&gt;<br /> <br /> <br /> <br /> &lt;aops&gt;sdfvsdfv&lt;/aops&gt;<br /> <br /> [[file:Bold button.jpeg|25px]]<br /> <br /> &lt;a href=&quot;www.aops.com&quot;&gt;Aops&lt;/a&gt;<br /> <br /> 123\\456<br /> 222\\ 1<br /> 222 \\ w<br /> )\\)<br /> Hmmm<br /> &lt;pre class=&quot;python&quot; style=&quot;font-family:monospace;&quot;&gt;print(3)&lt;/pre&gt;<br /> =0=<br /> <br /> <br /> <br /> <br /> <br /> &lt;asy&gt;draw((1/10,10)..(1/3,3)..(1/2,2)..(1,1)..(2, 1/2)..(3,1/3)..(4,1/4)..(5,1/5)..(6,1/6)..(7,1/7));&lt;/asy&gt;</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Asymptotes&diff=72424 Asymptotes 2015-10-11T18:00:37Z <p>Greenpepper9999: Redirect to asymptote(Geometry)</p> <hr /> <div>#Redirect [[Asymptote (Geometry)]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Circumference&diff=72423 Circumference 2015-10-11T17:56:36Z <p>Greenpepper9999: </p> <hr /> <div>{{stub}}<br /> <br /> '''Circumference''' is essentially a synonym for [[perimeter]]: for a given [[closed curve]] in the [[plane]], it is the distance one travels in a complete circuit of the curve. The term circumference is most frequently used to refer to the distance around a [[circle]], though it may refer to the distance around any [[smooth]] curve, while the term perimeter is typically reserved for [[polygon]]s. <br /> <br /> ==Formulas==<br /> In a circle of [[radius]] &lt;math&gt;r&lt;/math&gt; and [[diameter]] &lt;math&gt;d = 2r&lt;/math&gt;, the circumference &lt;math&gt;C&lt;/math&gt; is given by <br /> &lt;cmath&gt;C = \pi \cdot d = 2\pi \cdot r&lt;/cmath&gt; Indeed, the [[constant]] &lt;math&gt;\pi&lt;/math&gt; ([[pi]]) was originally defined to be the [[ratio]] of the circumference of a circle to the length of its diameter.<br /> <br /> ==See Also==</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Cubic_polynomial&diff=72422 Cubic polynomial 2015-10-11T17:52:10Z <p>Greenpepper9999: Stub</p> <hr /> <div>A '''cubic polynomial''' is a [[polynomial]] of the form &lt;math&gt;ax^3+bx^2+cx+d=0&lt;/math&gt;.<br /> <br /> {{Stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=User:DrMath&diff=72330 User:DrMath 2015-10-02T20:25:54Z <p>Greenpepper9999: Hehehehe</p> <hr /> <div>hi<br /> <br /> snorlax<br /> <br /> also referred to as MrDeth<br /> <br /> suddenly people decided to worship him .-.<br /> <br /> deez nuts hah got'em!<br /> <br /> ^ this edit was not me?<br /> too long ago to remember<br /> <br /> Note to self: if I come back later and don't remember writing this, it means I am insane.</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=2008_AMC_10A_Problems/Problem_18&diff=72216 2008 AMC 10A Problems/Problem 18 2015-09-29T21:32:52Z <p>Greenpepper9999: Latex fix</p> <hr /> <div>==Problem==<br /> A [[right triangle]] has [[perimeter]] &lt;math&gt;32&lt;/math&gt; and area &lt;math&gt;20&lt;/math&gt;. What is the length of its [[hypotenuse]]?<br /> <br /> &lt;math&gt;\mathrm{(A)}\ \frac{57}{4}\qquad\mathrm{(B)}\ \frac{59}{4}\qquad\mathrm{(C)}\ \frac{61}{4}\qquad\mathrm{(D)}\ \frac{63}{4}\qquad\mathrm{(E)}\ \frac{65}{4}&lt;/math&gt;<br /> <br /> __TOC__<br /> ==Solution==<br /> === Solution 1 ===<br /> Let the legs of the triangle have lengths &lt;math&gt;a,b&lt;/math&gt;. Then, by the [[Pythagorean Theorem]], the length of the hypotenuse is &lt;math&gt;\sqrt{a^2+b^2}&lt;/math&gt;, and the area of the triangle is &lt;math&gt;\frac 12 ab&lt;/math&gt;. So we have the two equations<br /> &lt;center&gt;<br /> &lt;math&gt;a+b+\sqrt{a^2+b^2} = 32 \\\\<br /> \frac{1}{2}ab = 20&lt;/math&gt;<br /> &lt;/center&gt;<br /> Re-arranging the first equation and squaring, <br /> &lt;center&gt;<br /> &lt;math&gt; \sqrt{a^2+b^2} = 32-(a+b)\\\\<br /> a^2 + b^2 = 32^2 - 64(a+b) + (a+b)^2\\\\<br /> a^2 + b^2 + 64(a+b) = a^2 + b^2 + 2ab + 32^2\\\\<br /> a+b = \frac{2ab+32^2}{64}&lt;/math&gt;<br /> &lt;/center&gt;<br /> From &lt;math&gt;(2)&lt;/math&gt; we have &lt;math&gt;2ab = 80&lt;/math&gt;, so<br /> &lt;center&gt;<br /> &lt;math&gt;a+b = \frac{80 + 32^2}{64} = \frac{69}{4}.&lt;/math&gt;<br /> &lt;/center&gt;<br /> <br /> The length of the hypotenuse is &lt;math&gt;p - a - b = 32 - \frac{69}{4} = \frac{59}{4}\ \mathrm{(B)}&lt;/math&gt;.<br /> <br /> === Solution 2 ===<br /> From the formula &lt;math&gt;A = rs&lt;/math&gt;, where &lt;math&gt;A&lt;/math&gt; is the area of a triangle, &lt;math&gt;r&lt;/math&gt; is its [[inradius]], and &lt;math&gt;s&lt;/math&gt; is the [[semiperimeter]], we can find that &lt;math&gt;r = \frac{20}{32/2} = \frac{5}{4}&lt;/math&gt;. It is known that in a right triangle, &lt;math&gt;r = s - h&lt;/math&gt;, where &lt;math&gt;h&lt;/math&gt; is the hypotenuse, so &lt;math&gt;h = 16 - \frac{5}{4} = \frac{59}{4}&lt;/math&gt;.<br /> <br /> === Solution 3 ===<br /> From the problem, we know that <br /> &lt;center&gt;&lt;cmath&gt;\begin{align*}<br /> a+b+c &amp;= 32 \\<br /> 2ab &amp;= 80. \\<br /> \end{align*}&lt;/cmath&gt;&lt;/center&gt;<br /> <br /> Subtracting &lt;math&gt;c&lt;/math&gt; from both sides of the first equation and squaring both sides, we get<br /> &lt;center&gt;&lt;cmath&gt;\begin{align*}<br /> (a+b)^2 &amp;= (32 - c)^2\\<br /> a^2 + b^2 + 2ab &amp;= 32^2 + c^2 - 64c.\\<br /> \end{align*}&lt;/cmath&gt;&lt;/center&gt;<br /> <br /> Now we substitute in &lt;math&gt;a^2 + b^2 = c^2&lt;/math&gt; as well as &lt;math&gt;2ab = 80&lt;/math&gt; into the equation to get<br /> &lt;center&gt;&lt;cmath&gt;\begin{align*}<br /> 80 &amp;= 1024 - 64c\\<br /> c &amp;= \frac{944}{64}.<br /> \end{align*}&lt;/cmath&gt;&lt;/center&gt;<br /> <br /> Further simplification yields the result of &lt;math&gt;\frac{59}{4}&lt;/math&gt;.<br /> <br /> === Solution 4 ===<br /> <br /> Let &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; be the legs of the triangle, and &lt;math&gt;c&lt;/math&gt; the hypotenuse.<br /> <br /> Since the area is 20, we have &lt;math&gt;\frac{1}{2}ab = 20 =&gt; ab=40&lt;/math&gt;.<br /> <br /> Since the perimeter is 32, we have &lt;math&gt;a + b + c = 32&lt;/math&gt;.<br /> <br /> The Pythagorean Theorem gives &lt;math&gt;c^2 = a^2 + b^2&lt;/math&gt;. <br /> <br /> This gives us three equations with three variables:<br /> <br /> &lt;center&gt;&lt;math&gt;ab = 40 \\<br /> a + b + c = 32 \\<br /> c^2 = a^2 + b^2&lt;/math&gt;&lt;/center&gt;<br /> <br /> Rewrite equation 3 as &lt;math&gt;c^2 = (a+b)^2 - 2ab&lt;/math&gt;.<br /> Substitute in equations 1 and 2 to get &lt;math&gt;c^2 = (32-c)^2 - 80&lt;/math&gt;.<br /> <br /> &lt;center&gt;&lt;math&gt;c^2 = (32-c)^2 - 80 \\\\<br /> c^2 = 1024 - 64c + c^2 - 80 \\\\<br /> 64c = 944 \\\\<br /> c = \frac{944}{64} = \frac{236}{16} = \frac{59}{4} &lt;/math&gt;. &lt;/center&gt;<br /> The answer is choice (B).<br /> <br /> ==See also==<br /> {{AMC10 box|year=2008|ab=A|num-b=17|num-a=19}}<br /> <br /> [[Category:Introductory Geometry Problems]]<br /> {{MAA Notice}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Monty_Hall_paradox&diff=72215 Monty Hall paradox 2015-09-29T21:09:01Z <p>Greenpepper9999: Sections</p> <hr /> <div>The Monty Hall Paradox is a problem concerning probability, which reveals counterintuitive results.<br /> <br /> ==The Problem:==<br /> <br /> You are in a game show. There are three curtains. Behind one of the curtains is a car, and behind the other two are goats. The game show host knows which curtain the car is behind. You are asked to pick a curtain, and will be given the prize behind it. Right after you pick, however, the host reveals one of the curtains you did not pick, which has a goat behind it (because he knows which curtain the car is behind, he won't accidents reveal the car). The host then asks you whether you would like to consider switching to the remaining unopened curtain. The question is: Do you stay, do you switch, or does it even matter?<br /> <br /> ==The Answer:==<br /> <br /> Yes. Even though it looks like a 50% chance of getting the car, you will actually find that you can ''double'' your probability just by switching to the other curtain. To understand why, we have to take a look at what happened at the start. You picked one of the curtains, knowing that there was a 1/3 chance of picking the car and a 2/3 chance of picking a goat. Notice that when the host reveals one of the goats, it does not affect your choice. There is still the exact same uncertainty of the item behind the curtain. Because the host knows where the goat is, he will always reveal a goat. If you stick with your choice, it is basically the same thing as picking 1 curtain out of 3 and hoping to get the car which has a 1/3 chance. However, if you switch, then there is a 2/3 chance that you switched from the goat to the car.<br /> <br /> ==What if there were more curtains?==<br /> <br /> Let's say that there are 100 curtains. You pick one, and then the host reveals 98 of the remaining 99 to be goats. Do you stay, or switch? Of course, you switch since the probability that you picked the car at first is ridiculously small, so you can almost guarantee that the curtain you currently have does not have the car behind it, and therefore the remaining curtain must almost always have the car behind it.</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Monty_Hall_paradox&diff=72214 Monty Hall paradox 2015-09-29T21:08:27Z <p>Greenpepper9999: </p> <hr /> <div>The Monty Hall Paradox is a problem concerning probability, which reveals counterintuitive results.<br /> <br /> '''The Problem:'''<br /> <br /> You are in a game show. There are three curtains. Behind one of the curtains is a car, and behind the other two are goats. The game show host knows which curtain the car is behind. You are asked to pick a curtain, and will be given the prize behind it. Right after you pick, however, the host reveals one of the curtains you did not pick, which has a goat behind it (because he knows which curtain the car is behind, he won't accidents reveal the car). The host then asks you whether you would like to consider switching to the remaining unopened curtain. The question is: Do you stay, do you switch, or does it even matter?<br /> <br /> '''The Answer:'''<br /> <br /> Yes. Even though it looks like a 50% chance of getting the car, you will actually find that you can ''double'' your probability just by switching to the other curtain. To understand why, we have to take a look at what happened at the start. You picked one of the curtains, knowing that there was a 1/3 chance of picking the car and a 2/3 chance of picking a goat. Notice that when the host reveals one of the goats, it does not affect your choice. There is still the exact same uncertainty of the item behind the curtain. Because the host knows where the goat is, he will always reveal a goat. If you stick with your choice, it is basically the same thing as picking 1 curtain out of 3 and hoping to get the car which has a 1/3 chance. However, if you switch, then there is a 2/3 chance that you switched from the goat to the car.<br /> <br /> '''What if there were more curtains?'''<br /> <br /> Let's say that there are 100 curtains. You pick one, and then the host reveals 98 of the remaining 99 to be goats. Do you stay, or switch? Of course, you switch since the probability that you picked the car at first is ridiculously small, so you can almost guarantee that the curtain you currently have does not have the car behind it, and therefore the remaining curtain must almost always have the car behind it.</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Statistics&diff=72213 Statistics 2015-09-29T19:44:51Z <p>Greenpepper9999: </p> <hr /> <div><br /> ==General==<br /> Statistics is the distinct branch of mathematical science that deals with obtaining, analyzing, and drawing conclusions about a [[data|data set]]. &quot;Applied statistics&quot; is a subset of statistics that deals primarily with statistical analysis on information gathered from an experiment. Most data sets from statistics are from [[sample (statistics)|samples]] from a much larger [[population (statistics)|population]] size. &quot;&quot;Inferential statistics&quot;&quot; is used to draw inferences from the data after statistical procedures have been performed. Statistics is not to be confused with [[probability]].<br /> <br /> Data usually follow the [[normal distribution]], the [[Chi-Square distribution]], the [[Student's t-distribution]], or the [[F-distribution]].<br /> <br /> Statistics can also be misleading, as shown in the classic book ''How to Lie with Statistics'' by Darrell Huff.<br /> <br /> ==Statistical Procedures==<br /> Here is a list of common statistical procedures, used to analyze and draw conclusions on a given set of data. Some are dependent on whether the sample data set came from a population with known [[parameters]], like a [[normal distribution]], while others are [[non-parametric tests]]<br /> <br /> * [[Student's t-test]]<br /> * [[z-test]]<br /> * [[Analysis of Variance test]]<br /> * [[Mann-Whitney U-Test]]<br /> * [[runs test for randomness]]<br /> * [[Chi-Square Test]]<br /> * [[Kruskal-Wallis H-test]]<br /> <br /> ==Significance==<br /> The significance of a data set tells whether the data set or group is out of the ordinary(special/non-random). This is usually the main objective of statistics. <br /> <br /> [[category:Statistics]]<br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=IMO_problems_statistics_since_2000&diff=72212 IMO problems statistics since 2000 2015-09-29T19:31:00Z <p>Greenpepper9999: </p> <hr /> <div>This page lists the number of IMO problems per proposing country from the year 2000 onwards. (Currently it covers the 16 IMOs from the years 2000-2015.)<br /> <br /> {|style=&quot;text-align:right&quot; border=&quot;1&quot; cellpadding=&quot;5&quot; cellspacing=&quot;0&quot;<br /> !#problems !!: proposed by country <br /> |-<br /> |10 ||Russia<br /> |- <br /> | 8 ||South Korea<br /> |- <br /> | 6 ||Romania<br /> |- <br /> | 5 ||Iran<br /> |- <br /> | 5 ||Poland <br /> |- <br /> | 4 ||Australia<br /> |-<br /> | 4 ||France<br /> |- <br /> | 4 ||Netherlands<br /> |- <br /> | 4 ||Serbia<br /> |- <br /> | 4 ||USA<br /> |- <br /> | 3 ||Austria<br /> |- <br /> | 3 ||Bulgaria<br /> |- <br /> | 2 ||Belarus<br /> |- <br /> | 2 ||Canada<br /> |- <br /> | 2 ||Czech Republic<br /> |- <br /> | 2 ||Greece<br /> |- <br /> | 2 ||Ireland<br /> |- <br /> | 2 ||Japan<br /> |- <br /> | 2 ||Luxembourg<br /> |- <br /> | 2 ||Ukraine<br /> |- <br /> | 2 ||United Kingdom<br /> |- <br /> | 1 ||Albania<br /> |- <br /> | 1 ||Belgium<br /> |- <br /> | 1 ||Brazil<br /> |- <br /> | 1 ||Colombia<br /> |- <br /> | 1 ||Croatia<br /> |- <br /> | 1 ||Estonia<br /> |- <br /> | 1 ||Finland<br /> |- <br /> | 1 ||Georgia<br /> |- <br /> | 1 ||Germany<br /> |- <br /> | 1 ||Hong Kong<br /> |- <br /> | 1 ||Hungary<br /> |- <br /> | 1 ||India<br /> |- <br /> | 1 ||Israel<br /> |- <br /> | 1 ||Lithuania<br /> |- <br /> | 1 ||Mexico<br /> |- <br /> | 1 ||New Zealand<br /> |- <br /> | 1 ||South Africa<br /> |- <br /> | 1 ||Thailand<br /> |-<br /> |}<br /> ==See Also==<br /> [[IMO problems statistics]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=IMO_problems_statistics&diff=72211 IMO problems statistics 2015-09-29T19:30:23Z <p>Greenpepper9999: </p> <hr /> <div>This page lists the number of IMO problems per proposing country for the years 1959-2015.<br /> <br /> {|style=&quot;text-align:right&quot; border=&quot;1&quot; cellpadding=&quot;5&quot; cellspacing=&quot;0&quot;<br /> !#problems !!: proposed by country <br /> |-<br /> |25 ||Poland <br /> |- <br /> |24 ||Netherlands<br /> |- <br /> |23 ||United Kingdom<br /> |- <br /> |22 ||Romania<br /> |- <br /> |20 ||*USSR<br /> |- <br /> |17 ||Bulgaria<br /> |- <br /> |16 ||*Czechoslovakia<br /> |- <br /> |15 ||Hungary<br /> |- <br /> |14 ||Russia<br /> |- <br /> |11 ||USA<br /> |- <br /> |11 ||*West Germany<br /> |- <br /> | 9 ||*East Germany<br /> |- <br /> | 9 ||France<br /> |- <br /> | 8 ||South Korea<br /> |- <br /> | 7.5 ||Australia<br /> |-<br /> | 7 ||Finland<br /> |- <br /> | 7 ||Sweden<br /> |- <br /> | 6 ||Iran<br /> |- <br /> | 5 ||Belarus<br /> |- <br /> | 4 ||Luxembourg<br /> |- <br /> | 4 ||Czech Republic<br /> |- <br /> | 4 ||India<br /> |- <br /> | 4 ||Ireland<br /> |- <br /> | 4 ||Serbia<br /> |- <br /> | 4 ||*Yugoslavia<br /> |- <br /> | 3 ||Austria<br /> |- <br /> | 3 ||Belgium<br /> |- <br /> | 3 ||Canada<br /> |- <br /> | 3 ||China<br /> |- <br /> | 3 ||Greece<br /> |- <br /> | 3 ||Japan<br /> |- <br /> | 3 ||Mongolia<br /> |- <br /> | 3 ||New Zealand<br /> |- <br /> | 3 ||Ukraine<br /> |- <br /> | 3 ||Vietnam<br /> |- <br /> | 2 ||Estonia<br /> |- <br /> | 2 ||Germany<br /> |- <br /> | 2 ||Iceland<br /> |- <br /> | 2 ||Israel<br /> |- <br /> | 2 ||Italy<br /> |- <br /> | 2 ||Lithuania<br /> |- <br /> | 1 ||Albania<br /> |- <br /> | 1.5 ||Armenia<br /> |- <br /> | 1 ||Brazil<br /> |- <br /> | 1 ||Colombia<br /> |- <br /> | 1 ||Croatia<br /> |- <br /> | 1 ||Cuba<br /> |- <br /> | 1 ||Georgia<br /> |- <br /> | 1 ||Hong Kong<br /> |- <br /> | 1 ||Macedonia<br /> |-<br /> | 1 ||Mexico<br /> |- <br /> | 1 ||Philippines<br /> |- <br /> | 1 ||South Africa<br /> |- <br /> | 1 ||Taiwan<br /> |- <br /> | 1 ||Thailand<br /> |- <br /> | 1 ||Turkey<br /> |}<br /> <br /> A * in front of a country name means that this country no longer exists, since it split or merged into other countries.<br /> <br /> ==See Also==<br /> <br /> [[IMO problems statistics since 2000]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Mode&diff=72161 Mode 2015-09-21T23:06:16Z <p>Greenpepper9999: Edit for conciseness</p> <hr /> <div>In a [[finite]] [[multiset]], the '''mode''' is the [[element]] (or set of elements) that appears the most times. For example, in &lt;math&gt;\{1,1,3,5,6,7,7,7,7,8\}&lt;/math&gt;, the mode is &lt;math&gt;7&lt;/math&gt;.<br /> <br /> == See also ==<br /> *[[Arithmetic mean]]<br /> *[[Median]]<br /> <br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Statistics&diff=72160 Statistics 2015-09-21T22:58:26Z <p>Greenpepper9999: Removed duplicate z test list item</p> <hr /> <div><br /> ==General==<br /> Statistics is the distinct branch of mathematical science that deals with obtaining, analyzing, and drawing conclusions about a [[data|data set]]. &quot;Applied statistics&quot; is a subset of statistics that deals primarily with statistical analysis on information gathered from an experiment. Most data sets from statistics are from [[sample]]s from a much larger [[population]] size. &quot;&quot;Inferential statistics&quot;&quot; is used to draw inferences from the data after statistical procedures have been performed. Statistics is not to be confused with [[probability]].<br /> <br /> Data usually follow the [[normal distribution]], the [[Chi-Square distribution]], the [[Student's t-distribution]], or the [[F-distribution]].<br /> <br /> Statistics can also be misleading, as shown in the classic book ''How to Lie with Statistics'' by Darrell Huff.<br /> <br /> ==Statistical Procedures==<br /> Here is a list of common statistical procedures, used to analyze and draw conclusions on a given set of data. Some are dependent on whether the sample data set came from a population with known [[parameters]], like a [[normal distribution]], while others are [[non-parametric tests]]<br /> <br /> * [[Student's t-test]]<br /> * [[z-test]]<br /> * [[Analysis of Variance test]]<br /> * [[Mann-Whitney U-Test]]<br /> * [[runs test for randomness]]<br /> * [[Chi-Square Test]]<br /> * [[Kruskal-Wallis H-test]]<br /> <br /> ==Significance==<br /> The significance of a data set tells whether the data set or group is out of the ordinary(special/non-random). This is usually the main objective of statistics. <br /> <br /> [[category:Statistics]]<br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Statistics&diff=72159 Statistics 2015-09-21T22:56:49Z <p>Greenpepper9999: Data is plural</p> <hr /> <div><br /> ==General==<br /> Statistics is the distinct branch of mathematical science that deals with obtaining, analyzing, and drawing conclusions about a [[data|data set]]. &quot;Applied statistics&quot; is a subset of statistics that deals primarily with statistical analysis on information gathered from an experiment. Most data sets from statistics are from [[sample]]s from a much larger [[population]] size. &quot;&quot;Inferential statistics&quot;&quot; is used to draw inferences from the data after statistical procedures have been performed. Statistics is not to be confused with [[probability]].<br /> <br /> Data usually follow the [[normal distribution]], the [[Chi-Square distribution]], the [[Student's t-distribution]], or the [[F-distribution]].<br /> <br /> Statistics can also be misleading, as shown in the classic book ''How to Lie with Statistics'' by Darrell Huff.<br /> <br /> ==Statistical Procedures==<br /> Here is a list of common statistical procedures, used to analyze and draw conclusions on a given set of data. Some are dependent on whether the sample data set came from a population with known [[parameters]], like a [[normal distribution]], while others are [[non-parametric tests]]<br /> <br /> * [[Student's t-test]]<br /> * [[z-test]]<br /> * [[Analysis of Variance test]]<br /> * [[Mann-Whitney U-Test]]<br /> * [[runs test for randomness]]<br /> * [[Chi-Square Test]]<br /> * [[z-test]]<br /> * [[Kruskal-Wallis H-test]]<br /> <br /> ==Significance==<br /> The significance of a data set tells whether the data set or group is out of the ordinary(special/non-random). This is usually the main objective of statistics. <br /> <br /> [[category:Statistics]]<br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Stats&diff=72158 Stats 2015-09-21T22:52:56Z <p>Greenpepper9999: Redirected page to Statistics</p> <hr /> <div>#REDIRECT [[Statistics]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Category:Statistics&diff=72149 Category:Statistics 2015-09-20T18:47:04Z <p>Greenpepper9999: Created page with &quot;Statistics is the distinct branch of mathematical science that deals with obtaining, analyzing, and drawing conclusions about a data set.&quot;</p> <hr /> <div>Statistics is the distinct branch of mathematical science that deals with obtaining, analyzing, and drawing conclusions about a data set.</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Statistics&diff=72148 Statistics 2015-09-20T18:46:28Z <p>Greenpepper9999: Category statistics</p> <hr /> <div><br /> ==General==<br /> Statistics is the distinct branch of mathematical science that deals with obtaining, analyzing, and drawing conclusions about a data set. &quot;Applied statistics&quot; is a subset of statistics that deals primarily with statistical analysis on information gathered from an experiment. Most data sets from statistics are from [[sample]]s from a much larger [[population]] size. &quot;&quot;Inferential statistics&quot;&quot; is used to draw inferences from the data after statistical procedures have been performed. Statistics is not to be confused with [[probability]].<br /> <br /> Data usually follows the [[normal distribution]], the [[Chi-Square distribution]], the [[Student's t-distribution]], or the [[F-distribution]].<br /> <br /> Statistics can also be misleading, as shown in the classic book ''How to Lie with Statistics'' by Darrell Huff.<br /> <br /> ==Statistical Procedures==<br /> Here is a list of common statistical procedures, used to analyze and draw conclusions on a given set of data. Some are dependent on whether the sample [[data]] set came from a population with known [[parameters]], like a [[normal distribution]], while others are [[non-parametric tests]]<br /> <br /> * [[Student's t-test]]<br /> * [[z-test]]<br /> * [[Analysis of Variance test]]<br /> * [[Mann-Whitney U-Test]]<br /> * [[runs test for randomness]]<br /> * [[Chi-Square Test]]<br /> * [[z-test]]<br /> * [[Kruskal-Wallis H-test]]<br /> <br /> ==Significance==<br /> The significance of a data set tells whether the data set or group is out of the ordinary(special/non-random). This is usually the main objective of statistics. <br /> <br /> [[category:Statistics]]<br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Arithmetic_mean&diff=72141 Arithmetic mean 2015-09-20T16:44:35Z <p>Greenpepper9999: Category statistics</p> <hr /> <div>The '''arithmetic mean''' of a [[set]] of numbers (or variables) is the sum of all the numbers, divided by the number of numbers - the [[average]] of the set. If we let &lt;math&gt;{AM}&lt;/math&gt; denote Arithmetic Mean, <br /> &lt;center&gt;&lt;math&gt;AM=\frac{x_1+x_2+\cdots+x_n}{n}&lt;/math&gt;&lt;/center&gt;<br /> is the arithmetic mean of the &lt;math&gt;{n}&lt;/math&gt; numbers &lt;math&gt;x_1,x_2,\ldots,x_n&lt;/math&gt;.<br /> <br /> For example, if I wanted to find the average of the numbers 3, 1, 4, 1, and 5, I would compute: <br /> &lt;center&gt;&lt;math&gt; \frac{3+1+4+1+5}{5} = \frac{14}{5}.&lt;/math&gt;&lt;/center&gt; <br /> <br /> <br /> <br /> Arithmetic means show up frequently in contest problems, often in the [[AM-GM]] [[inequality]] or its variant, the [[RMS-AM-GM-HM]] inequality.<br /> <br /> [[Category:Statistics]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Exponentiation&diff=72140 Exponentiation 2015-09-20T15:49:57Z <p>Greenpepper9999: /* Fractional exponents */</p> <hr /> <div>'''Exponentiation''' is an arithmetic operation, just like [[addition]], [[multiplication]], etc. This article is an introduction to what exponentiation is and how it works.<br /> <br /> == Introduction ==<br /> <br /> To understand how exponents arise, let's first review how we can build multiplication from addition. Let's say we wanted to capture the notion of &quot;the amount equal to 3, ten times.&quot; We could write this out as &lt;math&gt; 3 + 3 +3 + 3 +3 + 3 +3 + 3 +3 + 3&lt;/math&gt;, but this gets burdensome quickly: if we wanted to capture the idea of &quot;the amount equal to two hundred 3s.&quot; Thus, we define the multiplication function, usually denoted &lt;math&gt;\times&lt;/math&gt; or &lt;math&gt;\cdot&lt;/math&gt;, such that &lt;math&gt; 3\times 200=3+3+\ldots+3&lt;/math&gt; where there are 200 threes in the sum. This process (actually an [[induction | inductive]] definition) defines the operation of &quot;multiplication by [[positive integer]]s.&quot; We can then extend the notion of multiplication to non-integers.<br /> <br /> Similarly, the exponentiation is defined as the repetition of multiplication. For example, writing out &lt;math&gt;3\cdot 3\cdot 3\cdot 3\cdot 3&lt;/math&gt; can get boring fast, so we define the exponential function to express this in a much more compact form so that the preceeding example can be written as &lt;math&gt;3^5&lt;/math&gt; (read 3 to the 5th or 3 to the 5 power). What this means is that we are multiplying 3 by itself 5 times.<br /> <br /> Before we proceed, we define 3 terms:<br /> * exponent or power - In &lt;math&gt;4^6&lt;/math&gt;, the exponent is 6; this tells us how many times we multiply the 4.<br /> * [[base]] - In &lt;math&gt;10^9&lt;/math&gt;, the base is 10; this tells us what we will be multiplying 9 times.<br /> <br /> Our definition of exponentiation makes sense if the exponent is a positive integer. How about negative integers such as &lt;math&gt;2^{-4}&lt;/math&gt;? How do we multiply 2 by itself -4 times!? Let's think about what a negative sign means a little more. When we append a negative sign to a number (say 4, for example), we are basically saying go four units in the ''opposite'' direction. We want to do the opposite of multiplication four times. In other words, we want to divide by 2 four times. Therefore, &lt;math&gt; 2^{-4}=\frac 1{2^4}.&lt;/math&gt;<br /> <br /> It is also possible to extend the exponential function to all non-integers.<br /> <br /> == Basic Properties ==<br /> Listed below are some important properties of exponents:<br /> # &lt;math&gt; b^x\cdot b^y = b^{x+y}&lt;/math&gt;<br /> # &lt;math&gt; b^{-x}=\frac 1{b^x} &lt;/math&gt;<br /> # &lt;math&gt; \frac{b^x}{b^y}=b^{x-y} &lt;/math&gt;<br /> # &lt;math&gt; (b^x)^y = b^{xy} &lt;/math&gt;<br /> # &lt;math&gt; (ab)^x = a^x b^x &lt;/math&gt;<br /> # &lt;math&gt; b^0 = 1 &lt;/math&gt; (if &lt;math&gt;b \neq 0&lt;/math&gt;. &lt;math&gt;0^0&lt;/math&gt; is undefined.)<br /> <br /> Here are explanations of the properties listed above:<br /> # On both sides, we are multiplying '''b''' together '''x+y''' times. Thus, they are equivalent. <br /> # This is described in the previous section.<br /> # This results from using the previous two properties.<br /> # We are multiplying &lt;math&gt;b^x&lt;/math&gt; by itself '''y''' times, which is the same as multiplying '''b''' by itself '''xy''' times.<br /> # After multiplying '''ab''' by itself '''x''' times, we can collect '''a''' and '''b''' terms, thus establishing the property.<br /> #Hoping that property #1 will be true when &lt;math&gt;y=0&lt;/math&gt;, we see that &lt;math&gt;b^x\cdot b^0&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^x&lt;/math&gt;. Thus, we ''define'' &lt;math&gt;b^0&lt;/math&gt; to be equal to &lt;math&gt;1&lt;/math&gt; in order to make this be true.<br /> <br /> <br /> <br /> == Fractional exponents ==<br /> <br /> If &lt;math&gt;b&lt;/math&gt; is a number and each of &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; is a positive integer, then, as explained above (property 1), &lt;math&gt;b^x b^y = b^{x+y}&lt;/math&gt;. For example, &lt;math&gt;b^2 b^3 = (b\cdot b)(b\cdot b \cdot b) = b^5&lt;/math&gt;.<br /> <br /> <br /> How could we make sense of an expression like &quot;&lt;math&gt;b^0&lt;/math&gt;&quot;? Well, hoping that property 1 will remain true when &lt;math&gt;y=0&lt;/math&gt;, we see that &lt;math&gt;b^x b^0&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^{x+0}=b^x&lt;/math&gt;. For that reason, we ''define'' &lt;math&gt;b^0 = 1&lt;/math&gt;, in order to make that be true. (And we only make this definition in the case where &lt;math&gt;b \neq 0&lt;/math&gt;. We choose to leave &lt;math&gt;0^0&lt;/math&gt; undefined.)<br /> <br /> <br /> We can make sense of an expression like &quot;&lt;math&gt;b^{-5}&lt;/math&gt;&quot; in a similar way. Hoping that property 1 will remain true even if &lt;math&gt;x&lt;/math&gt; or &lt;math&gt;y&lt;/math&gt; is negative, we see that &lt;math&gt;b^5 b^{-5}&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^{5 + (-5)} = b^0 = 1&lt;/math&gt;. Thus, we ''define'' &lt;math&gt;b^{-5}&lt;/math&gt; to be &lt;math&gt;\frac{1}{b^5}&lt;/math&gt;, in order to make this be true. Similarly, if &lt;math&gt;x&lt;/math&gt; is a positive integer, we define &lt;math&gt;b^{-x}&lt;/math&gt; to be &lt;math&gt;\frac{1}{b^x}&lt;/math&gt;. (This depends on having &lt;math&gt;b \neq 0&lt;/math&gt;. Otherwise we'd be dividing by &lt;math&gt;0&lt;/math&gt;.)<br /> <br /> <br /> How could we make sense of an expression like &lt;math&gt;b^{\frac{1}{2}}&lt;/math&gt;? If you don't already know the answer, this is a good exercise; I recommend puzzling over it for awhile.<br /> <br /> <br /> Answer: Hoping that property 1 will remain true when &lt;math&gt;x&lt;/math&gt; or &lt;math&gt;y&lt;/math&gt; is a fraction, we see that &lt;math&gt;b^{\frac{1}{2}} b^{\frac{1}{2}}&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^{\frac{1}{2} + \frac{1}{2}} = b^1 = b&lt;/math&gt;. Thus, we ''define'' &lt;math&gt;b^{\frac{1}{2}}&lt;/math&gt; to be &lt;math&gt;\sqrt{b}&lt;/math&gt;, in order to make this be true.<br /> <br /> <br /> For the time being, how to deal with other fractions in the exponent can be an exercise for the reader.<br /> <br /> Hint: What would &lt;math&gt;b^{\frac{1}{3}}&lt;/math&gt; be? What about &lt;math&gt;b^{\frac{1}{4}}&lt;/math&gt;? Do you notice anything? <br /> <br /> Try to figure out &lt;math&gt;b^{\frac{2}{3}}&lt;/math&gt; -- how does it relate to &lt;math&gt;b^{\frac{1}{3}}&lt;/math&gt;?<br /> <br /> == See also ==<br /> * [[Logarithms]]<br /> * [[Algebra]]<br /> * [[Hyperexponentiation]]<br /> * [[Radical]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Exponentiation&diff=72139 Exponentiation 2015-09-20T15:49:12Z <p>Greenpepper9999: /* Fractional exponents */</p> <hr /> <div>'''Exponentiation''' is an arithmetic operation, just like [[addition]], [[multiplication]], etc. This article is an introduction to what exponentiation is and how it works.<br /> <br /> == Introduction ==<br /> <br /> To understand how exponents arise, let's first review how we can build multiplication from addition. Let's say we wanted to capture the notion of &quot;the amount equal to 3, ten times.&quot; We could write this out as &lt;math&gt; 3 + 3 +3 + 3 +3 + 3 +3 + 3 +3 + 3&lt;/math&gt;, but this gets burdensome quickly: if we wanted to capture the idea of &quot;the amount equal to two hundred 3s.&quot; Thus, we define the multiplication function, usually denoted &lt;math&gt;\times&lt;/math&gt; or &lt;math&gt;\cdot&lt;/math&gt;, such that &lt;math&gt; 3\times 200=3+3+\ldots+3&lt;/math&gt; where there are 200 threes in the sum. This process (actually an [[induction | inductive]] definition) defines the operation of &quot;multiplication by [[positive integer]]s.&quot; We can then extend the notion of multiplication to non-integers.<br /> <br /> Similarly, the exponentiation is defined as the repetition of multiplication. For example, writing out &lt;math&gt;3\cdot 3\cdot 3\cdot 3\cdot 3&lt;/math&gt; can get boring fast, so we define the exponential function to express this in a much more compact form so that the preceeding example can be written as &lt;math&gt;3^5&lt;/math&gt; (read 3 to the 5th or 3 to the 5 power). What this means is that we are multiplying 3 by itself 5 times.<br /> <br /> Before we proceed, we define 3 terms:<br /> * exponent or power - In &lt;math&gt;4^6&lt;/math&gt;, the exponent is 6; this tells us how many times we multiply the 4.<br /> * [[base]] - In &lt;math&gt;10^9&lt;/math&gt;, the base is 10; this tells us what we will be multiplying 9 times.<br /> <br /> Our definition of exponentiation makes sense if the exponent is a positive integer. How about negative integers such as &lt;math&gt;2^{-4}&lt;/math&gt;? How do we multiply 2 by itself -4 times!? Let's think about what a negative sign means a little more. When we append a negative sign to a number (say 4, for example), we are basically saying go four units in the ''opposite'' direction. We want to do the opposite of multiplication four times. In other words, we want to divide by 2 four times. Therefore, &lt;math&gt; 2^{-4}=\frac 1{2^4}.&lt;/math&gt;<br /> <br /> It is also possible to extend the exponential function to all non-integers.<br /> <br /> == Basic Properties ==<br /> Listed below are some important properties of exponents:<br /> # &lt;math&gt; b^x\cdot b^y = b^{x+y}&lt;/math&gt;<br /> # &lt;math&gt; b^{-x}=\frac 1{b^x} &lt;/math&gt;<br /> # &lt;math&gt; \frac{b^x}{b^y}=b^{x-y} &lt;/math&gt;<br /> # &lt;math&gt; (b^x)^y = b^{xy} &lt;/math&gt;<br /> # &lt;math&gt; (ab)^x = a^x b^x &lt;/math&gt;<br /> # &lt;math&gt; b^0 = 1 &lt;/math&gt; (if &lt;math&gt;b \neq 0&lt;/math&gt;. &lt;math&gt;0^0&lt;/math&gt; is undefined.)<br /> <br /> Here are explanations of the properties listed above:<br /> # On both sides, we are multiplying '''b''' together '''x+y''' times. Thus, they are equivalent. <br /> # This is described in the previous section.<br /> # This results from using the previous two properties.<br /> # We are multiplying &lt;math&gt;b^x&lt;/math&gt; by itself '''y''' times, which is the same as multiplying '''b''' by itself '''xy''' times.<br /> # After multiplying '''ab''' by itself '''x''' times, we can collect '''a''' and '''b''' terms, thus establishing the property.<br /> #Hoping that property #1 will be true when &lt;math&gt;y=0&lt;/math&gt;, we see that &lt;math&gt;b^x\cdot b^0&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^x&lt;/math&gt;. Thus, we ''define'' &lt;math&gt;b^0&lt;/math&gt; to be equal to &lt;math&gt;1&lt;/math&gt; in order to make this be true.<br /> <br /> <br /> <br /> == Fractional exponents ==<br /> <br /> If &lt;math&gt;b&lt;/math&gt; is a number and each of &lt;math&gt;x&lt;/math&gt; and &lt;math&gt;y&lt;/math&gt; is a positive integer, then, as explained above (property 1), &lt;math&gt;b^x b^y = b^{x+y}&lt;/math&gt;. For example, &lt;math&gt;b^2 b^3 = (b\cdot b)(b\cdot b \cdot b) = b^5&lt;/math&gt;.<br /> <br /> <br /> How could we make sense of an expression like &quot;&lt;math&gt;b^0&lt;/math&gt;&quot;? Well, hoping that property 1 will remain true when &lt;math&gt;y=0&lt;/math&gt;, we see that &lt;math&gt;b^x b^0&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^{x+0}=b^x&lt;/math&gt;. For that reason, we ''define'' &lt;math&gt;b^0 = 1&lt;/math&gt;, in order to make that be true. (And we only make this definition in the case where &lt;math&gt;b \neq 0&lt;/math&gt;. We choose to leave &lt;math&gt;0^0&lt;/math&gt; undefined.)<br /> <br /> <br /> We can make sense of an expression like &quot;&lt;math&gt;b^{-5}&lt;/math&gt;&quot; in a similar way. Hoping that property 1 will remain true even if &lt;math&gt;x&lt;/math&gt; or &lt;math&gt;y&lt;/math&gt; is negative, we see that &lt;math&gt;b^5 b^{-5}&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^{5 + (-5)} = b^0 = 1&lt;/math&gt;. Thus, we ''define'' &lt;math&gt;b^{-5}&lt;/math&gt; to be &lt;math&gt;\frac{1}{b^5}&lt;/math&gt;, in order to make this be true. Similarly, if &lt;math&gt;x&lt;/math&gt; is a positive integer, we define &lt;math&gt;b^{-x}&lt;/math&gt; to be &lt;math&gt;\frac{1}{b^x}&lt;/math&gt;. (This depends on having &lt;math&gt;b \neq 0&lt;/math&gt;. Otherwise we'd be dividing by &lt;math&gt;0&lt;/math&gt;.)<br /> <br /> <br /> How could we make sense of an expression like &lt;math&gt;b^{\frac{1}{2}}&lt;/math&gt;? If you don't already know the answer, this is a good exercise; I recommend puzzling over it for awhile.<br /> <br /> <br /> Answer: Hoping that property 1 will remain true when &lt;math&gt;x&lt;/math&gt; or &lt;math&gt;y&lt;/math&gt; is a fraction, we see that &lt;math&gt;b^{\frac{1}{2}} b^{\frac{1}{2}}&lt;/math&gt; should (hopefully) be equal to &lt;math&gt;b^{\frac{1}{2} + \frac{1}{2}} = b^1 = b&lt;/math&gt;. Thus, we ''define'' &lt;math&gt;b^{\frac{1}{2}}&lt;/math&gt; to be &lt;math&gt;\sqrt{b}&lt;/math&gt;, in order to make this be true.<br /> <br /> <br /> For the time being, how to deal with other fractions in the exponent can be an exercise for the reader.<br /> Hint: What would &lt;math&gt;b^{\frac{1}{3}}&lt;/math&gt; be? What about &lt;math&gt;b^{\frac{1}{4}}&lt;/math&gt;? Do you notice anything? Try to figure out &lt;math&gt;b^{\frac{2}{3}}&lt;/math&gt; -- how does it relate to &lt;math&gt;b^{\frac{1}{1}}&lt;/math&gt;<br /> <br /> == See also ==<br /> * [[Logarithms]]<br /> * [[Algebra]]<br /> * [[Hyperexponentiation]]<br /> * [[Radical]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Modular_arithmetic/Introduction&diff=72138 Modular arithmetic/Introduction 2015-09-20T15:40:38Z <p>Greenpepper9999: /* Solution */</p> <hr /> <div>'''[[Modular arithmetic]]''' is a special type of arithmetic that involves only [[integers]]. This goal of this article is to explain the basics of modular arithmetic while presenting a progression of more difficult and more interesting problems that are easily solved using modular arithmetic.<br /> <br /> <br /> <br /> == Motivation ==<br /> Let's use a clock as an example, except let's replace the &lt;math&gt;12&lt;/math&gt; at the top of the clock with a &lt;math&gt;0&lt;/math&gt;. <br /> <br /> &lt;asy&gt;picture pic;<br /> path a;<br /> a = circle((0,0), 100);<br /> draw (a);<br /> draw((0,0), linewidth(4));<br /> <br /> pair b;<br /> b = (0,100);<br /> <br /> for (int i = 0; i &lt; 12; ++i)<br /> {<br /> label (pic, (string) i, b);<br /> b = rotate(-30,(0,0)) * b;<br /> }<br /> pic = scale(0.8) * pic;<br /> add(pic);<br /> <br /> draw ((0,0) -- 50*dir(90));<br /> draw ((0,0) -- 70*dir(90));&lt;/asy&gt;<br /> <br /> Starting at noon, the hour hand points in order to the following:<br /> <br /> &lt;math&gt;1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, \ldots &lt;/math&gt;<br /> <br /> <br /> This is the way in which we count in '''modulo 12'''. When we add &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;11&lt;/math&gt;, we arrive back at &lt;math&gt;0&lt;/math&gt;. The same is true in any other [[modulus]] (modular arithmetic system). In modulo &lt;math&gt;5&lt;/math&gt;, we [[counting | count]]<br /> <br /> <br /> &lt;math&gt;0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, \ldots&lt;/math&gt;<br /> <br /> <br /> We can also count backwards in modulo 5. Any time we subtract 1 from 0, we get 4. So, the integers from &lt;math&gt;-12&lt;/math&gt; to &lt;math&gt;0&lt;/math&gt;, when written in modulo 5, are<br /> <br /> <br /> &lt;math&gt;3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,&lt;/math&gt;<br /> <br /> <br /> where &lt;math&gt;-12&lt;/math&gt; is the same as &lt;math&gt;3&lt;/math&gt; in modulo 5. Because all integers can be expressed as &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;4&lt;/math&gt; in modulo 5, we give these integers their own name: the '''[[residue class]]es''' modulo 5. In general, for a natural number &lt;math&gt;n&lt;/math&gt; that is greater than 1, the modulo &lt;math&gt;n&lt;/math&gt; residues are the integers that are [[whole number | whole numbers]] less than &lt;math&gt;n&lt;/math&gt;:<br /> <br /> <br /> &lt;math&gt;0, 1, 2, \ldots, n-1. &lt;/math&gt;<br /> <br /> <br /> This just relates each integer to its [[remainder]] from the [[Division Theorem]]. While this may not seem all that useful at first, counting in this way can help us solve an enormous array of [[number theory]] problems much more easily!<br /> <br /> ==Residue==<br /> We say that &lt;math&gt;a&lt;/math&gt; is the modulo-&lt;math&gt;m&lt;/math&gt; &lt;b&gt;residue&lt;/b&gt; of &lt;math&gt;n&lt;/math&gt; when &lt;math&gt;n\equiv a\pmod m&lt;/math&gt;, and &lt;math&gt;0\le a&lt;m&lt;/math&gt;.<br /> <br /> == Congruence ==<br /> There is a mathematical way of saying that all of the integers are the same as one of the modulo 5 residues. For instance, we say that 7 and 2 are '''[[congruent]]''' modulo 5. We write this using the symbol &lt;math&gt;\equiv&lt;/math&gt;: In other words, this means in base 5, these integers have the same last digit:<br /> <br /> 2(base 5) &lt;math&gt; \equiv &lt;/math&gt; 12(base 5) &lt;math&gt; \equiv &lt;/math&gt; 22(base 5) &lt;math&gt; \equiv &lt;/math&gt; 32(base 5) &lt;math&gt; \equiv &lt;/math&gt; 42(base 5)<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;7 \equiv 2 \pmod{5}. &lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> The '''(mod 5)''' part just tells us that we are working with the integers modulo 5. In modulo 5, two integers are congruent when their difference is a [[multiple]] of 5. Thus each of the following integers is congruent modulo 5:<br /> &lt;center&gt;&lt;math&gt;-12 \equiv -7 \equiv -2 \equiv 3 \equiv 8 \equiv 13 \equiv 18 \equiv 23 \pmod{5} &lt;/math&gt;&lt;/center&gt;<br /> In general, two integers &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are congruent modulo &lt;math&gt;n&lt;/math&gt; when &lt;math&gt;a - b&lt;/math&gt; is a multiple of &lt;math&gt;n&lt;/math&gt;. In other words, &lt;math&gt;a \equiv b \pmod{n}&lt;/math&gt; when &lt;math&gt;\frac{a-b}{n}&lt;/math&gt; is an integer. Otherwise, &lt;math&gt;a \not\equiv b \pmod{n}&lt;/math&gt;, which means that &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are '''not congruent''' modulo &lt;math&gt;n&lt;/math&gt;.<br /> <br /> <br /> <br /> === Examples ===<br /> * &lt;math&gt;31 \equiv 1 \pmod{10}&lt;/math&gt; because &lt;math&gt;31 - 1 = 30&lt;/math&gt; is a multiple of &lt;math&gt;10&lt;/math&gt;.<br /> <br /> <br /> * &lt;math&gt;43 \equiv 22 \pmod{7}&lt;/math&gt; because &lt;math&gt;\frac{43 - 22}{7} = \frac{21}{7} = 3&lt;/math&gt;, which is an integer.<br /> <br /> <br /> * &lt;math&gt;8 \not\equiv -8 \pmod{3}&lt;/math&gt; because &lt;math&gt;8 - (-8) = 16&lt;/math&gt;, which is not a multiple of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> <br /> * &lt;math&gt;91 \not\equiv 18 \pmod{6}&lt;/math&gt; because &lt;math&gt;\frac{91 - 18}{6} = \frac{73}{6}&lt;/math&gt;, which is not an integer.<br /> <br /> <br /> <br /> === Sample Problem ===<br /> Find the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;.<br /> ==== Solution: ====<br /> Since &lt;math&gt;311 \div 4 = 77&lt;/math&gt; R &lt;math&gt;3&lt;/math&gt;, we know that <br /> &lt;center&gt;&lt;math&gt;311 \equiv 3 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> and &lt;math&gt;3&lt;/math&gt; is the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;.<br /> <br /> ==== Another Solution: ====<br /> Since &lt;math&gt; 311 = 300 + 11 &lt;/math&gt;, we know that<br /> &lt;center&gt;&lt;math&gt;311 \equiv 0+11 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> We can now solve it easily<br /> &lt;center&gt;&lt;math&gt;11 \equiv 3 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> and &lt;math&gt;3&lt;/math&gt; is the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;<br /> <br /> == Making Computation Easier ==<br /> We don't always need to perform tedious computations to discover solutions to interesting problems. If all we need to know about are remainders when integers are divided by &lt;math&gt;n&lt;/math&gt;, then we can work directly with those remainders in modulo &lt;math&gt;n&lt;/math&gt;. This can be more easily understood with a few examples.<br /> <br /> === Addition ===<br /> ==== Problem ====<br /> Suppose we want to find the [[units digit]] of the following [[sum]]:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;2403 + 791 + 688 + 4339.&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> We could find their sum, which is &lt;math&gt;8221&lt;/math&gt;, and note that the units digit is &lt;math&gt;1&lt;/math&gt;. However, we could find the units digit with far less calculation.<br /> <br /> ==== Solution ====<br /> We can simply add the units digits of the addends:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;3 + 1 + 8 + 9 = 21.&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> The units digit of this sum is &lt;math&gt;1&lt;/math&gt;, which ''must'' be the same as the units digit of the four-digit sum we computed earlier.<br /> <br /> ==== Why we only need to use remainders ====<br /> We can rewrite each of the integers in terms of multiples of &lt;math&gt;10&lt;/math&gt; and remainders:&lt;br&gt;<br /> &lt;math&gt;2403 = 240 \cdot 10 + 3&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;791 = 79 \cdot 10 + 1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;688 = 68 \cdot 10 + 8&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;4339 = 433 \cdot 10 + 9&lt;/math&gt;.&lt;br&gt;<br /> When we add all four integers, we get<br /> <br /> <br /> &lt;center&gt;&lt;math&gt; (240 \cdot 10 + 3) + (79 \cdot 10 + 1) + (68 \cdot 10 + 8) + (433 \cdot 10 + 9)&lt;/math&gt;&lt;/center&gt;<br /> <br /> &lt;center&gt;&lt;math&gt;= (240 + 79 + 68 + 433) \cdot 10 + (3 + 1 + 8 + 9)&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> At this point, we already see the units digits grouped apart and added to a multiple of &lt;math&gt;10&lt;/math&gt; (which will not affect the units digit of the sum):<br /> <br /> &lt;center&gt;&lt;math&gt;= 820 \cdot 10 + 21 = 8200 + 21 = 8221&lt;/math&gt;.&lt;/center&gt;<br /> <br /> ==== Solution using modular arithmetic ====<br /> Now let's look back at this solution, using modular arithmetic from the start. Note that&lt;br&gt;<br /> &lt;math&gt;2403 \equiv 3 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;791 \equiv 1 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;688 \equiv 8 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;4339 \equiv 9 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> Because we only need the modulo &lt;math&gt;10&lt;/math&gt; residue of the sum, we add just the residues of the summands:<br /> <br /> &lt;center&gt;&lt;math&gt;2403 + 791 + 688 + 4339 \equiv 3 + 1 + 8 + 9 \equiv 21 \equiv 1 \pmod{10},&lt;/math&gt;&lt;/center&gt;<br /> so the units digit of the sum is just &lt;math&gt;1&lt;/math&gt;.<br /> <br /> ==== Addition rule ====<br /> In general, when &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> the following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a + b \equiv c + d \pmod{m} &lt;/math&gt;.&lt;/center&gt;<br /> And as we did in the problem above, we can apply more pairs of equivalent integers to both sides, just repeating this simple principle.<br /> <br /> ====Proof of the addition rule====<br /> <br /> Let &lt;math&gt;a-c=m\cdot k&lt;/math&gt;, and &lt;math&gt;b-d=m\cdot l&lt;/math&gt; where &lt;math&gt;l&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt; are integers. <br /> Adding the two equations we get:<br /> &lt;cmath&gt;<br /> \begin{eqnarray*}<br /> mk+ml&amp;=&amp;(a-c)+(b-d)\\<br /> m(k+l)&amp;=&amp;(a+b)-(c+d)<br /> \end{eqnarray*}<br /> &lt;/cmath&gt;<br /> <br /> Which is equivalent to saying &lt;math&gt;a+b\equiv c+d\pmod{m}&lt;/math&gt;<br /> <br /> === Subtraction ===<br /> The same shortcut that works with addition of remainders works also with subtraction.<br /> <br /> ==== Problem ====<br /> Find the remainder when the difference between &lt;math&gt;60002&lt;/math&gt; and &lt;math&gt;601&lt;/math&gt; is divided by &lt;math&gt;6&lt;/math&gt;.<br /> <br /> ==== Solution ====<br /> Note that &lt;math&gt;60002 = 10000 \cdot 6 + 2&lt;/math&gt; and &lt;math&gt;601 = 100 \cdot 6 + 1&lt;/math&gt;. So,&lt;br&gt;<br /> &lt;math&gt;60002 \equiv 2 \pmod{6}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;601 \equiv 1 \pmod{6}&lt;/math&gt;&lt;br&gt;<br /> Thus,<br /> &lt;center&gt;&lt;math&gt;60002 - 601 \equiv 2 - 1 \equiv 1 \pmod{6}, &lt;/math&gt;&lt;/center&gt;<br /> so 1 is the remainder when the difference is divided by &lt;math&gt;6&lt;/math&gt;. (Perform the subtraction yourself, divide by &lt;math&gt;6&lt;/math&gt;, and see!)<br /> <br /> ==== Subtraction rule ====<br /> When &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> the following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a - b \equiv c - d \pmod{m} &lt;/math&gt;&lt;/center&gt;.<br /> <br /> <br /> === Multiplication ===<br /> Modular arithmetic provides an even larger advantage when multiplying than when adding or subtracting. Let's take a look at a problem that demonstrates the point.<br /> <br /> ==== Problem ====<br /> Jerry has 44 boxes of soda in his truck. The cans of soda in each box are packed oddly so that there are 113 cans of soda in each box. Jerry plans to pack the sodas into cases of 12 cans to sell. After making as many complete cases as possible, how many sodas will Jerry have leftover?<br /> <br /> ==== Solution ====<br /> First, we note that this [[word problem]] is asking us to find the remainder when the product &lt;math&gt;44 \cdot 113&lt;/math&gt; is divided by &lt;math&gt;12&lt;/math&gt;.<br /> <br /> Now, we can write each &lt;math&gt;44&lt;/math&gt; and &lt;math&gt;113&lt;/math&gt; in terms of multiples of &lt;math&gt;12&lt;/math&gt; and remainders:&lt;br&gt;<br /> &lt;math&gt;44 = 3 \cdot 12 + 8&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;113 = 9 \cdot 12 + 5&lt;/math&gt;&lt;br&gt;<br /> This gives us a nice way to view their product:<br /> <br /> <br /> &lt;cmath&gt;44 \cdot 113 = (3 \cdot 12 + 8)(9 \cdot 12 + 5)&lt;/cmath&gt;<br /> Using [[FOIL]], we get that this equals<br /> &lt;cmath&gt;(3 \cdot 9) \cdot 12^2 + (3 \cdot 5 + 8 \cdot 9) \cdot 12 + (8 \cdot 5)&lt;/cmath&gt;<br /> <br /> <br /> We can already see that each part of the product is a multiple of &lt;math&gt;12&lt;/math&gt;, except the product of the remainders when each &lt;math&gt;44&lt;/math&gt; and &lt;math&gt;113&lt;/math&gt; are divided by 12. That part of the product is &lt;math&gt;8 \cdot 5 = 40&lt;/math&gt;, which leaves a remainder of &lt;math&gt;4&lt;/math&gt; when divided by &lt;math&gt;12&lt;/math&gt;. So, Jerry has &lt;math&gt;4&lt;/math&gt; sodas leftover after making as many cases of &lt;math&gt;12&lt;/math&gt; as possible.<br /> <br /> ==== Solution using modular arithmetic ====<br /> First, we note that&lt;br&gt;<br /> &lt;math&gt;44 \equiv 8 \pmod{12}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;113 \equiv 5 \pmod{12}&lt;/math&gt;&lt;br&gt;<br /> Thus,<br /> &lt;center&gt;&lt;math&gt;44 \cdot 113 \equiv 8 \cdot 5 \equiv 40 \equiv 4 \pmod{12},&lt;/math&gt;&lt;/center&gt;<br /> meaning there are &lt;math&gt;4&lt;/math&gt; sodas leftover. Yeah, that was much easier.<br /> <br /> ==== Multiplication rule ====<br /> When &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> The following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a \cdot b \equiv c \cdot d \pmod{m} &lt;/math&gt;.&lt;/center&gt;<br /> <br /> <br /> === Exponentiation ===<br /> Since [[exponentiation]] is just repeated multiplication, it makes sense that modular arithmetic would make many problems involving exponents easier. In fact, the advantage in computation is even larger and we explore it a great deal more in the [[intermediate modular arithmetic]] article.<br /> <br /> Note to everybody: Exponentiation is very useful as in the following problem:<br /> <br /> ==== Problem #1====<br /> What is the last digit of &lt;math&gt;(...((7)^7)^7)...)^7&lt;/math&gt; if there are 1000 7s as exponents and only one 7 in the middle?<br /> <br /> We could solve this problem using mods. This can also be stated as &lt;math&gt;7^{7^{1000}}&lt;/math&gt;. After that, we see that 7 is congruent to -1 in mod 4, so we can use this fact to replace the 7s with -1s, because 7 has a pattern of repetitive period 4 for the units digit. &lt;math&gt;(-1)^{1000}&lt;/math&gt; is simply 1, so therefore &lt;math&gt;7^1=7&lt;/math&gt;, which really is the last digit.<br /> <br /> ==== Problem #2====<br /> What are the tens and units digits of &lt;math&gt;7^{1942}&lt;/math&gt;?<br /> <br /> We could (in theory) solve this problem by trying to compute &lt;math&gt;7^{1942}&lt;/math&gt;, but this would be extremely time-consuming. Moreover, it would give us much more information than we need. Since we want only the tens and units digits of the number in question, it suffices to find the remainder when the number is divided by &lt;math&gt;100&lt;/math&gt;. In other words, all of the information we need can be found using arithmetic mod &lt;math&gt;100&lt;/math&gt;.<br /> <br /> We begin by writing down the first few powers of &lt;math&gt;7&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt;:<br /> <br /> &lt;math&gt;7, 49, 43, 1, 7, 49, 43, 1, \ldots&lt;/math&gt;<br /> <br /> A pattern emerges! We see that &lt;math&gt;7^4 = 2401 \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;). So for any positive integer &lt;math&gt;k&lt;/math&gt;, we have &lt;math&gt;7^{4k} = (7^4)^k \equiv 1^k \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;). In particular, we can write<br /> <br /> &lt;math&gt;7^{1940} = 7^{4 \cdot 485} \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;).<br /> <br /> By the &quot;multiplication&quot; property above, then, it follows that<br /> <br /> &lt;math&gt;7^{1942} = 7^{1940} \cdot 7^2 \equiv 1 \cdot 7^2 \equiv 49&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;).<br /> <br /> Therefore, by the definition of congruence, &lt;math&gt;7^{1942}&lt;/math&gt; differs from &lt;math&gt;49&lt;/math&gt; by a multiple of &lt;math&gt;100&lt;/math&gt;. Since both integers are positive, this means that they share the same tens and units digits. Those digits are &lt;math&gt;4&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt;, respectively.<br /> <br /> ==== Problem #3====<br /> <br /> Can you find a number that is both a multiple of &lt;math&gt;2&lt;/math&gt; but not a multiple of &lt;math&gt;4&lt;/math&gt; and a perfect square?<br /> <br /> No, you cannot, rewritting the question we see that it asks us to find a number &lt;math&gt;n&lt;/math&gt; that satisfies this: &lt;math&gt;4n+2=x^2&lt;/math&gt;.<br /> <br /> Taking mod &lt;math&gt;4&lt;/math&gt; on both sides we find that &lt;math&gt;x^2\equiv 2\pmod{4}&lt;/math&gt;, now all we are missing to show is that no matter what &lt;math&gt;x&lt;/math&gt; is, &lt;math&gt;x^2&lt;/math&gt; will never be a multiple of &lt;math&gt;4&lt;/math&gt; plus &lt;math&gt;2&lt;/math&gt;, so we work with cases:<br /> <br /> &lt;math&gt;x\equiv 0\pmod{4}\implies x^2\equiv 0\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 1\pmod{4}\implies x^2\equiv 1\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 2\pmod{4}\implies x^2\equiv 4\equiv 0\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 3\pmod{4}\implies x^2\equiv 9\equiv 1\pmod{4}&lt;/math&gt;<br /> <br /> This assures us that it is impossible to find such a number.<br /> <br /> == Summary of Useful Facts ==<br /> <br /> Consider four integers &lt;math&gt;{a},{b},{c},{d}&lt;/math&gt; and a positive integer &lt;math&gt;{m}&lt;/math&gt; such that &lt;math&gt;a\equiv b\pmod {m}&lt;/math&gt; and &lt;math&gt;c\equiv d\pmod {m}&lt;/math&gt;. In modular arithmetic, the following [[identity | identities]] hold:<br /> <br /> * Addition: &lt;math&gt;a+c\equiv b+d\pmod {m}&lt;/math&gt;.<br /> * Subtraction: &lt;math&gt;a-c\equiv b-d\pmod {m}&lt;/math&gt;.<br /> * Multiplication: &lt;math&gt;ac\equiv bd\pmod {m}&lt;/math&gt;.<br /> * Division: &lt;math&gt;\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}&lt;/math&gt;, where &lt;math&gt;e&lt;/math&gt; is a positive integer that divides &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;.<br /> * Exponentiation: &lt;math&gt;a^e\equiv b^e\pmod {m}&lt;/math&gt; where &lt;math&gt;e&lt;/math&gt; is a positive integer.<br /> <br /> <br /> <br /> == Applications of Modular Arithmetic ==<br /> Modular arithmetic is an extremely flexible problem solving tool. The following topics are just a few applications and extensions of its use:<br /> * [[Divisibility rules]]<br /> * [[Linear congruence | Linear congruences]]<br /> <br /> <br /> <br /> == Resources ==<br /> * The AoPS [http://www.artofproblemsolving.com/Store/viewitem.php?item=intro:nt Introduction to Number Theory] by [[Mathew Crawford]].<br /> * The AoPS [http://www.artofproblemsolving.com/School/courseinfo.php?course_id=intro:numbertheory Introduction to Number Theory Course]. Thousands of students have learned more about modular arithmetic and [[problem solving]] from this 12 week class.<br /> <br /> == See also ==<br /> * [[Intermediate modular arithmetic]]<br /> * [[Olympiad modular arithmetic]]<br /> <br /> <br /> [[Category:Introductory Mathematics Topics]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Modular_arithmetic/Introduction&diff=72137 Modular arithmetic/Introduction 2015-09-20T15:32:28Z <p>Greenpepper9999: /* Proof of the addition rule */ translating expression from math to plain english</p> <hr /> <div>'''[[Modular arithmetic]]''' is a special type of arithmetic that involves only [[integers]]. This goal of this article is to explain the basics of modular arithmetic while presenting a progression of more difficult and more interesting problems that are easily solved using modular arithmetic.<br /> <br /> <br /> <br /> == Motivation ==<br /> Let's use a clock as an example, except let's replace the &lt;math&gt;12&lt;/math&gt; at the top of the clock with a &lt;math&gt;0&lt;/math&gt;. <br /> <br /> &lt;asy&gt;picture pic;<br /> path a;<br /> a = circle((0,0), 100);<br /> draw (a);<br /> draw((0,0), linewidth(4));<br /> <br /> pair b;<br /> b = (0,100);<br /> <br /> for (int i = 0; i &lt; 12; ++i)<br /> {<br /> label (pic, (string) i, b);<br /> b = rotate(-30,(0,0)) * b;<br /> }<br /> pic = scale(0.8) * pic;<br /> add(pic);<br /> <br /> draw ((0,0) -- 50*dir(90));<br /> draw ((0,0) -- 70*dir(90));&lt;/asy&gt;<br /> <br /> Starting at noon, the hour hand points in order to the following:<br /> <br /> &lt;math&gt;1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, \ldots &lt;/math&gt;<br /> <br /> <br /> This is the way in which we count in '''modulo 12'''. When we add &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;11&lt;/math&gt;, we arrive back at &lt;math&gt;0&lt;/math&gt;. The same is true in any other [[modulus]] (modular arithmetic system). In modulo &lt;math&gt;5&lt;/math&gt;, we [[counting | count]]<br /> <br /> <br /> &lt;math&gt;0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, \ldots&lt;/math&gt;<br /> <br /> <br /> We can also count backwards in modulo 5. Any time we subtract 1 from 0, we get 4. So, the integers from &lt;math&gt;-12&lt;/math&gt; to &lt;math&gt;0&lt;/math&gt;, when written in modulo 5, are<br /> <br /> <br /> &lt;math&gt;3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,&lt;/math&gt;<br /> <br /> <br /> where &lt;math&gt;-12&lt;/math&gt; is the same as &lt;math&gt;3&lt;/math&gt; in modulo 5. Because all integers can be expressed as &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;4&lt;/math&gt; in modulo 5, we give these integers their own name: the '''[[residue class]]es''' modulo 5. In general, for a natural number &lt;math&gt;n&lt;/math&gt; that is greater than 1, the modulo &lt;math&gt;n&lt;/math&gt; residues are the integers that are [[whole number | whole numbers]] less than &lt;math&gt;n&lt;/math&gt;:<br /> <br /> <br /> &lt;math&gt;0, 1, 2, \ldots, n-1. &lt;/math&gt;<br /> <br /> <br /> This just relates each integer to its [[remainder]] from the [[Division Theorem]]. While this may not seem all that useful at first, counting in this way can help us solve an enormous array of [[number theory]] problems much more easily!<br /> <br /> ==Residue==<br /> We say that &lt;math&gt;a&lt;/math&gt; is the modulo-&lt;math&gt;m&lt;/math&gt; &lt;b&gt;residue&lt;/b&gt; of &lt;math&gt;n&lt;/math&gt; when &lt;math&gt;n\equiv a\pmod m&lt;/math&gt;, and &lt;math&gt;0\le a&lt;m&lt;/math&gt;.<br /> <br /> == Congruence ==<br /> There is a mathematical way of saying that all of the integers are the same as one of the modulo 5 residues. For instance, we say that 7 and 2 are '''[[congruent]]''' modulo 5. We write this using the symbol &lt;math&gt;\equiv&lt;/math&gt;: In other words, this means in base 5, these integers have the same last digit:<br /> <br /> 2(base 5) &lt;math&gt; \equiv &lt;/math&gt; 12(base 5) &lt;math&gt; \equiv &lt;/math&gt; 22(base 5) &lt;math&gt; \equiv &lt;/math&gt; 32(base 5) &lt;math&gt; \equiv &lt;/math&gt; 42(base 5)<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;7 \equiv 2 \pmod{5}. &lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> The '''(mod 5)''' part just tells us that we are working with the integers modulo 5. In modulo 5, two integers are congruent when their difference is a [[multiple]] of 5. Thus each of the following integers is congruent modulo 5:<br /> &lt;center&gt;&lt;math&gt;-12 \equiv -7 \equiv -2 \equiv 3 \equiv 8 \equiv 13 \equiv 18 \equiv 23 \pmod{5} &lt;/math&gt;&lt;/center&gt;<br /> In general, two integers &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are congruent modulo &lt;math&gt;n&lt;/math&gt; when &lt;math&gt;a - b&lt;/math&gt; is a multiple of &lt;math&gt;n&lt;/math&gt;. In other words, &lt;math&gt;a \equiv b \pmod{n}&lt;/math&gt; when &lt;math&gt;\frac{a-b}{n}&lt;/math&gt; is an integer. Otherwise, &lt;math&gt;a \not\equiv b \pmod{n}&lt;/math&gt;, which means that &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are '''not congruent''' modulo &lt;math&gt;n&lt;/math&gt;.<br /> <br /> <br /> <br /> === Examples ===<br /> * &lt;math&gt;31 \equiv 1 \pmod{10}&lt;/math&gt; because &lt;math&gt;31 - 1 = 30&lt;/math&gt; is a multiple of &lt;math&gt;10&lt;/math&gt;.<br /> <br /> <br /> * &lt;math&gt;43 \equiv 22 \pmod{7}&lt;/math&gt; because &lt;math&gt;\frac{43 - 22}{7} = \frac{21}{7} = 3&lt;/math&gt;, which is an integer.<br /> <br /> <br /> * &lt;math&gt;8 \not\equiv -8 \pmod{3}&lt;/math&gt; because &lt;math&gt;8 - (-8) = 16&lt;/math&gt;, which is not a multiple of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> <br /> * &lt;math&gt;91 \not\equiv 18 \pmod{6}&lt;/math&gt; because &lt;math&gt;\frac{91 - 18}{6} = \frac{73}{6}&lt;/math&gt;, which is not an integer.<br /> <br /> <br /> <br /> === Sample Problem ===<br /> Find the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;.<br /> ==== Solution: ====<br /> Since &lt;math&gt;311 \div 4 = 77&lt;/math&gt; R &lt;math&gt;3&lt;/math&gt;, we know that <br /> &lt;center&gt;&lt;math&gt;311 \equiv 3 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> and &lt;math&gt;3&lt;/math&gt; is the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;.<br /> <br /> ==== Another Solution: ====<br /> Since &lt;math&gt; 311 = 300 + 11 &lt;/math&gt;, we know that<br /> &lt;center&gt;&lt;math&gt;311 \equiv 0+11 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> We can now solve it easily<br /> &lt;center&gt;&lt;math&gt;11 \equiv 3 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> and &lt;math&gt;3&lt;/math&gt; is the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;<br /> <br /> == Making Computation Easier ==<br /> We don't always need to perform tedious computations to discover solutions to interesting problems. If all we need to know about are remainders when integers are divided by &lt;math&gt;n&lt;/math&gt;, then we can work directly with those remainders in modulo &lt;math&gt;n&lt;/math&gt;. This can be more easily understood with a few examples.<br /> <br /> === Addition ===<br /> ==== Problem ====<br /> Suppose we want to find the [[units digit]] of the following [[sum]]:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;2403 + 791 + 688 + 4339.&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> We could find their sum, which is &lt;math&gt;8221&lt;/math&gt;, and note that the units digit is &lt;math&gt;1&lt;/math&gt;. However, we could find the units digit with far less calculation.<br /> <br /> ==== Solution ====<br /> We can simply add the units digits of the addends:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;3 + 1 + 8 + 9 = 21.&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> The units digit of this sum is &lt;math&gt;1&lt;/math&gt;, which ''must'' be the same as the units digit of the four-digit sum we computed earlier.<br /> <br /> ==== Why we only need to use remainders ====<br /> We can rewrite each of the integers in terms of multiples of &lt;math&gt;10&lt;/math&gt; and remainders:&lt;br&gt;<br /> &lt;math&gt;2403 = 240 \cdot 10 + 3&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;791 = 79 \cdot 10 + 1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;688 = 68 \cdot 10 + 8&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;4339 = 433 \cdot 10 + 9&lt;/math&gt;.&lt;br&gt;<br /> When we add all four integers, we get<br /> <br /> <br /> &lt;center&gt;&lt;math&gt; (240 \cdot 10 + 3) + (79 \cdot 10 + 1) + (68 \cdot 10 + 8) + (433 \cdot 10 + 9)&lt;/math&gt;&lt;/center&gt;<br /> <br /> &lt;center&gt;&lt;math&gt;= (240 + 79 + 68 + 433) \cdot 10 + (3 + 1 + 8 + 9)&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> At this point, we already see the units digits grouped apart and added to a multiple of &lt;math&gt;10&lt;/math&gt; (which will not affect the units digit of the sum):<br /> <br /> &lt;center&gt;&lt;math&gt;= 820 \cdot 10 + 21 = 8200 + 21 = 8221&lt;/math&gt;.&lt;/center&gt;<br /> <br /> ==== Solution using modular arithmetic ====<br /> Now let's look back at this solution, using modular arithmetic from the start. Note that&lt;br&gt;<br /> &lt;math&gt;2403 \equiv 3 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;791 \equiv 1 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;688 \equiv 8 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;4339 \equiv 9 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> Because we only need the modulo &lt;math&gt;10&lt;/math&gt; residue of the sum, we add just the residues of the summands:<br /> <br /> &lt;center&gt;&lt;math&gt;2403 + 791 + 688 + 4339 \equiv 3 + 1 + 8 + 9 \equiv 21 \equiv 1 \pmod{10},&lt;/math&gt;&lt;/center&gt;<br /> so the units digit of the sum is just &lt;math&gt;1&lt;/math&gt;.<br /> <br /> ==== Addition rule ====<br /> In general, when &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> the following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a + b \equiv c + d \pmod{m} &lt;/math&gt;.&lt;/center&gt;<br /> And as we did in the problem above, we can apply more pairs of equivalent integers to both sides, just repeating this simple principle.<br /> <br /> ====Proof of the addition rule====<br /> <br /> Let &lt;math&gt;a-c=m\cdot k&lt;/math&gt;, and &lt;math&gt;b-d=m\cdot l&lt;/math&gt; where &lt;math&gt;l&lt;/math&gt; and &lt;math&gt;k&lt;/math&gt; are integers. <br /> Adding the two equations we get:<br /> &lt;cmath&gt;<br /> \begin{eqnarray*}<br /> mk+ml&amp;=&amp;(a-c)+(b-d)\\<br /> m(k+l)&amp;=&amp;(a+b)-(c+d)<br /> \end{eqnarray*}<br /> &lt;/cmath&gt;<br /> <br /> Which is equivalent to saying &lt;math&gt;a+b\equiv c+d\pmod{m}&lt;/math&gt;<br /> <br /> === Subtraction ===<br /> The same shortcut that works with addition of remainders works also with subtraction.<br /> <br /> ==== Problem ====<br /> Find the remainder when the difference between &lt;math&gt;60002&lt;/math&gt; and &lt;math&gt;601&lt;/math&gt; is divided by &lt;math&gt;6&lt;/math&gt;.<br /> <br /> ==== Solution ====<br /> Note that &lt;math&gt;60002 = 10000 \cdot 6 + 2&lt;/math&gt; and &lt;math&gt;601 = 100 \cdot 6 + 1&lt;/math&gt;. So,&lt;br&gt;<br /> &lt;math&gt;60002 \equiv 2 \pmod{6}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;601 \equiv 1 \pmod{6}&lt;/math&gt;&lt;br&gt;<br /> Thus,<br /> &lt;center&gt;&lt;math&gt;60002 - 601 \equiv 2 - 1 \equiv 1 \pmod{6}, &lt;/math&gt;&lt;/center&gt;<br /> so 1 is the remainder when the difference is divided by &lt;math&gt;6&lt;/math&gt;. (Perform the subtraction yourself, divide by &lt;math&gt;6&lt;/math&gt;, and see!)<br /> <br /> ==== Subtraction rule ====<br /> When &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> the following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a - b \equiv c - d \pmod{m} &lt;/math&gt;&lt;/center&gt;.<br /> <br /> <br /> === Multiplication ===<br /> Modular arithmetic provides an even larger advantage when multiplying than when adding or subtracting. Let's take a look at a problem that demonstrates the point.<br /> <br /> ==== Problem ====<br /> Jerry has 44 boxes of soda in his truck. The cans of soda in each box are packed oddly so that there are 113 cans of soda in each box. Jerry plans to pack the sodas into cases of 12 cans to sell. After making as many complete cases as possible, how many sodas will Jerry have leftover?<br /> <br /> ==== Solution ====<br /> First, we note that this [[word problem]] is asking us to find the remainder when the product &lt;math&gt;44 \cdot 113&lt;/math&gt; is divided by &lt;math&gt;12&lt;/math&gt;.<br /> <br /> Now, we can write each &lt;math&gt;44&lt;/math&gt; and &lt;math&gt;113&lt;/math&gt; in terms of multiples of &lt;math&gt;12&lt;/math&gt; and remainders:&lt;br&gt;<br /> &lt;math&gt;44 = 3 \cdot 12 + 8&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;113 = 9 \cdot 12 + 5&lt;/math&gt;&lt;br&gt;<br /> This gives us a nice way to view their product:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;44 \cdot 113 = (3 \cdot 12 + 8)(9 \cdot 12 + 5)&lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;=(3 \cdot 9) \cdot 12^2 + (3 \cdot 5 + 8 \cdot 9) \cdot 12 + (8 \cdot 5)&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> We can already see that each part of the product is a multiple of &lt;math&gt;12&lt;/math&gt;, except the product of the remainders when each &lt;math&gt;44&lt;/math&gt; and &lt;math&gt;113&lt;/math&gt; are divided by 12. That part of the product is &lt;math&gt;8 \cdot 5 = 40&lt;/math&gt;, which leaves a remainder of &lt;math&gt;4&lt;/math&gt; when divided by &lt;math&gt;12&lt;/math&gt;. So, Jerry has &lt;math&gt;4&lt;/math&gt; sodas leftover after making as many cases of &lt;math&gt;12&lt;/math&gt; as possible.<br /> <br /> ==== Solution using modular arithmetic ====<br /> First, we note that&lt;br&gt;<br /> &lt;math&gt;44 \equiv 8 \pmod{12}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;113 \equiv 5 \pmod{12}&lt;/math&gt;&lt;br&gt;<br /> Thus,<br /> &lt;center&gt;&lt;math&gt;44 \cdot 113 \equiv 8 \cdot 5 \equiv 40 \equiv 4 \pmod{12},&lt;/math&gt;&lt;/center&gt;<br /> meaning there are &lt;math&gt;4&lt;/math&gt; sodas leftover. Yeah, that was much easier.<br /> <br /> ==== Multiplication rule ====<br /> When &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> The following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a \cdot b \equiv c \cdot d \pmod{m} &lt;/math&gt;.&lt;/center&gt;<br /> <br /> <br /> === Exponentiation ===<br /> Since [[exponentiation]] is just repeated multiplication, it makes sense that modular arithmetic would make many problems involving exponents easier. In fact, the advantage in computation is even larger and we explore it a great deal more in the [[intermediate modular arithmetic]] article.<br /> <br /> Note to everybody: Exponentiation is very useful as in the following problem:<br /> <br /> ==== Problem #1====<br /> What is the last digit of &lt;math&gt;(...((7)^7)^7)...)^7&lt;/math&gt; if there are 1000 7s as exponents and only one 7 in the middle?<br /> <br /> We could solve this problem using mods. This can also be stated as &lt;math&gt;7^{7^{1000}}&lt;/math&gt;. After that, we see that 7 is congruent to -1 in mod 4, so we can use this fact to replace the 7s with -1s, because 7 has a pattern of repetitive period 4 for the units digit. &lt;math&gt;(-1)^{1000}&lt;/math&gt; is simply 1, so therefore &lt;math&gt;7^1=7&lt;/math&gt;, which really is the last digit.<br /> <br /> ==== Problem #2====<br /> What are the tens and units digits of &lt;math&gt;7^{1942}&lt;/math&gt;?<br /> <br /> We could (in theory) solve this problem by trying to compute &lt;math&gt;7^{1942}&lt;/math&gt;, but this would be extremely time-consuming. Moreover, it would give us much more information than we need. Since we want only the tens and units digits of the number in question, it suffices to find the remainder when the number is divided by &lt;math&gt;100&lt;/math&gt;. In other words, all of the information we need can be found using arithmetic mod &lt;math&gt;100&lt;/math&gt;.<br /> <br /> We begin by writing down the first few powers of &lt;math&gt;7&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt;:<br /> <br /> &lt;math&gt;7, 49, 43, 1, 7, 49, 43, 1, \ldots&lt;/math&gt;<br /> <br /> A pattern emerges! We see that &lt;math&gt;7^4 = 2401 \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;). So for any positive integer &lt;math&gt;k&lt;/math&gt;, we have &lt;math&gt;7^{4k} = (7^4)^k \equiv 1^k \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;). In particular, we can write<br /> <br /> &lt;math&gt;7^{1940} = 7^{4 \cdot 485} \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;).<br /> <br /> By the &quot;multiplication&quot; property above, then, it follows that<br /> <br /> &lt;math&gt;7^{1942} = 7^{1940} \cdot 7^2 \equiv 1 \cdot 7^2 \equiv 49&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;).<br /> <br /> Therefore, by the definition of congruence, &lt;math&gt;7^{1942}&lt;/math&gt; differs from &lt;math&gt;49&lt;/math&gt; by a multiple of &lt;math&gt;100&lt;/math&gt;. Since both integers are positive, this means that they share the same tens and units digits. Those digits are &lt;math&gt;4&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt;, respectively.<br /> <br /> ==== Problem #3====<br /> <br /> Can you find a number that is both a multiple of &lt;math&gt;2&lt;/math&gt; but not a multiple of &lt;math&gt;4&lt;/math&gt; and a perfect square?<br /> <br /> No, you cannot, rewritting the question we see that it asks us to find a number &lt;math&gt;n&lt;/math&gt; that satisfies this: &lt;math&gt;4n+2=x^2&lt;/math&gt;.<br /> <br /> Taking mod &lt;math&gt;4&lt;/math&gt; on both sides we find that &lt;math&gt;x^2\equiv 2\pmod{4}&lt;/math&gt;, now all we are missing to show is that no matter what &lt;math&gt;x&lt;/math&gt; is, &lt;math&gt;x^2&lt;/math&gt; will never be a multiple of &lt;math&gt;4&lt;/math&gt; plus &lt;math&gt;2&lt;/math&gt;, so we work with cases:<br /> <br /> &lt;math&gt;x\equiv 0\pmod{4}\implies x^2\equiv 0\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 1\pmod{4}\implies x^2\equiv 1\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 2\pmod{4}\implies x^2\equiv 4\equiv 0\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 3\pmod{4}\implies x^2\equiv 9\equiv 1\pmod{4}&lt;/math&gt;<br /> <br /> This assures us that it is impossible to find such a number.<br /> <br /> == Summary of Useful Facts ==<br /> <br /> Consider four integers &lt;math&gt;{a},{b},{c},{d}&lt;/math&gt; and a positive integer &lt;math&gt;{m}&lt;/math&gt; such that &lt;math&gt;a\equiv b\pmod {m}&lt;/math&gt; and &lt;math&gt;c\equiv d\pmod {m}&lt;/math&gt;. In modular arithmetic, the following [[identity | identities]] hold:<br /> <br /> * Addition: &lt;math&gt;a+c\equiv b+d\pmod {m}&lt;/math&gt;.<br /> * Subtraction: &lt;math&gt;a-c\equiv b-d\pmod {m}&lt;/math&gt;.<br /> * Multiplication: &lt;math&gt;ac\equiv bd\pmod {m}&lt;/math&gt;.<br /> * Division: &lt;math&gt;\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}&lt;/math&gt;, where &lt;math&gt;e&lt;/math&gt; is a positive integer that divides &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;.<br /> * Exponentiation: &lt;math&gt;a^e\equiv b^e\pmod {m}&lt;/math&gt; where &lt;math&gt;e&lt;/math&gt; is a positive integer.<br /> <br /> <br /> <br /> == Applications of Modular Arithmetic ==<br /> Modular arithmetic is an extremely flexible problem solving tool. The following topics are just a few applications and extensions of its use:<br /> * [[Divisibility rules]]<br /> * [[Linear congruence | Linear congruences]]<br /> <br /> <br /> <br /> == Resources ==<br /> * The AoPS [http://www.artofproblemsolving.com/Store/viewitem.php?item=intro:nt Introduction to Number Theory] by [[Mathew Crawford]].<br /> * The AoPS [http://www.artofproblemsolving.com/School/courseinfo.php?course_id=intro:numbertheory Introduction to Number Theory Course]. Thousands of students have learned more about modular arithmetic and [[problem solving]] from this 12 week class.<br /> <br /> == See also ==<br /> * [[Intermediate modular arithmetic]]<br /> * [[Olympiad modular arithmetic]]<br /> <br /> <br /> [[Category:Introductory Mathematics Topics]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Modular_arithmetic/Introduction&diff=72136 Modular arithmetic/Introduction 2015-09-20T15:26:38Z <p>Greenpepper9999: /* Addition rule */ minor change in section layout</p> <hr /> <div>'''[[Modular arithmetic]]''' is a special type of arithmetic that involves only [[integers]]. This goal of this article is to explain the basics of modular arithmetic while presenting a progression of more difficult and more interesting problems that are easily solved using modular arithmetic.<br /> <br /> <br /> <br /> == Motivation ==<br /> Let's use a clock as an example, except let's replace the &lt;math&gt;12&lt;/math&gt; at the top of the clock with a &lt;math&gt;0&lt;/math&gt;. <br /> <br /> &lt;asy&gt;picture pic;<br /> path a;<br /> a = circle((0,0), 100);<br /> draw (a);<br /> draw((0,0), linewidth(4));<br /> <br /> pair b;<br /> b = (0,100);<br /> <br /> for (int i = 0; i &lt; 12; ++i)<br /> {<br /> label (pic, (string) i, b);<br /> b = rotate(-30,(0,0)) * b;<br /> }<br /> pic = scale(0.8) * pic;<br /> add(pic);<br /> <br /> draw ((0,0) -- 50*dir(90));<br /> draw ((0,0) -- 70*dir(90));&lt;/asy&gt;<br /> <br /> Starting at noon, the hour hand points in order to the following:<br /> <br /> &lt;math&gt;1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, \ldots &lt;/math&gt;<br /> <br /> <br /> This is the way in which we count in '''modulo 12'''. When we add &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;11&lt;/math&gt;, we arrive back at &lt;math&gt;0&lt;/math&gt;. The same is true in any other [[modulus]] (modular arithmetic system). In modulo &lt;math&gt;5&lt;/math&gt;, we [[counting | count]]<br /> <br /> <br /> &lt;math&gt;0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, \ldots&lt;/math&gt;<br /> <br /> <br /> We can also count backwards in modulo 5. Any time we subtract 1 from 0, we get 4. So, the integers from &lt;math&gt;-12&lt;/math&gt; to &lt;math&gt;0&lt;/math&gt;, when written in modulo 5, are<br /> <br /> <br /> &lt;math&gt;3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,&lt;/math&gt;<br /> <br /> <br /> where &lt;math&gt;-12&lt;/math&gt; is the same as &lt;math&gt;3&lt;/math&gt; in modulo 5. Because all integers can be expressed as &lt;math&gt;0&lt;/math&gt;, &lt;math&gt;1&lt;/math&gt;, &lt;math&gt;2&lt;/math&gt;, &lt;math&gt;3&lt;/math&gt;, or &lt;math&gt;4&lt;/math&gt; in modulo 5, we give these integers their own name: the '''[[residue class]]es''' modulo 5. In general, for a natural number &lt;math&gt;n&lt;/math&gt; that is greater than 1, the modulo &lt;math&gt;n&lt;/math&gt; residues are the integers that are [[whole number | whole numbers]] less than &lt;math&gt;n&lt;/math&gt;:<br /> <br /> <br /> &lt;math&gt;0, 1, 2, \ldots, n-1. &lt;/math&gt;<br /> <br /> <br /> This just relates each integer to its [[remainder]] from the [[Division Theorem]]. While this may not seem all that useful at first, counting in this way can help us solve an enormous array of [[number theory]] problems much more easily!<br /> <br /> ==Residue==<br /> We say that &lt;math&gt;a&lt;/math&gt; is the modulo-&lt;math&gt;m&lt;/math&gt; &lt;b&gt;residue&lt;/b&gt; of &lt;math&gt;n&lt;/math&gt; when &lt;math&gt;n\equiv a\pmod m&lt;/math&gt;, and &lt;math&gt;0\le a&lt;m&lt;/math&gt;.<br /> <br /> == Congruence ==<br /> There is a mathematical way of saying that all of the integers are the same as one of the modulo 5 residues. For instance, we say that 7 and 2 are '''[[congruent]]''' modulo 5. We write this using the symbol &lt;math&gt;\equiv&lt;/math&gt;: In other words, this means in base 5, these integers have the same last digit:<br /> <br /> 2(base 5) &lt;math&gt; \equiv &lt;/math&gt; 12(base 5) &lt;math&gt; \equiv &lt;/math&gt; 22(base 5) &lt;math&gt; \equiv &lt;/math&gt; 32(base 5) &lt;math&gt; \equiv &lt;/math&gt; 42(base 5)<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;7 \equiv 2 \pmod{5}. &lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> The '''(mod 5)''' part just tells us that we are working with the integers modulo 5. In modulo 5, two integers are congruent when their difference is a [[multiple]] of 5. Thus each of the following integers is congruent modulo 5:<br /> &lt;center&gt;&lt;math&gt;-12 \equiv -7 \equiv -2 \equiv 3 \equiv 8 \equiv 13 \equiv 18 \equiv 23 \pmod{5} &lt;/math&gt;&lt;/center&gt;<br /> In general, two integers &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are congruent modulo &lt;math&gt;n&lt;/math&gt; when &lt;math&gt;a - b&lt;/math&gt; is a multiple of &lt;math&gt;n&lt;/math&gt;. In other words, &lt;math&gt;a \equiv b \pmod{n}&lt;/math&gt; when &lt;math&gt;\frac{a-b}{n}&lt;/math&gt; is an integer. Otherwise, &lt;math&gt;a \not\equiv b \pmod{n}&lt;/math&gt;, which means that &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt; are '''not congruent''' modulo &lt;math&gt;n&lt;/math&gt;.<br /> <br /> <br /> <br /> === Examples ===<br /> * &lt;math&gt;31 \equiv 1 \pmod{10}&lt;/math&gt; because &lt;math&gt;31 - 1 = 30&lt;/math&gt; is a multiple of &lt;math&gt;10&lt;/math&gt;.<br /> <br /> <br /> * &lt;math&gt;43 \equiv 22 \pmod{7}&lt;/math&gt; because &lt;math&gt;\frac{43 - 22}{7} = \frac{21}{7} = 3&lt;/math&gt;, which is an integer.<br /> <br /> <br /> * &lt;math&gt;8 \not\equiv -8 \pmod{3}&lt;/math&gt; because &lt;math&gt;8 - (-8) = 16&lt;/math&gt;, which is not a multiple of &lt;math&gt;3&lt;/math&gt;.<br /> <br /> <br /> * &lt;math&gt;91 \not\equiv 18 \pmod{6}&lt;/math&gt; because &lt;math&gt;\frac{91 - 18}{6} = \frac{73}{6}&lt;/math&gt;, which is not an integer.<br /> <br /> <br /> <br /> === Sample Problem ===<br /> Find the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;.<br /> ==== Solution: ====<br /> Since &lt;math&gt;311 \div 4 = 77&lt;/math&gt; R &lt;math&gt;3&lt;/math&gt;, we know that <br /> &lt;center&gt;&lt;math&gt;311 \equiv 3 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> and &lt;math&gt;3&lt;/math&gt; is the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;.<br /> <br /> ==== Another Solution: ====<br /> Since &lt;math&gt; 311 = 300 + 11 &lt;/math&gt;, we know that<br /> &lt;center&gt;&lt;math&gt;311 \equiv 0+11 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> We can now solve it easily<br /> &lt;center&gt;&lt;math&gt;11 \equiv 3 \pmod{4}&lt;/math&gt;&lt;/center&gt;<br /> and &lt;math&gt;3&lt;/math&gt; is the modulo &lt;math&gt;4&lt;/math&gt; residue of &lt;math&gt;311&lt;/math&gt;<br /> <br /> == Making Computation Easier ==<br /> We don't always need to perform tedious computations to discover solutions to interesting problems. If all we need to know about are remainders when integers are divided by &lt;math&gt;n&lt;/math&gt;, then we can work directly with those remainders in modulo &lt;math&gt;n&lt;/math&gt;. This can be more easily understood with a few examples.<br /> <br /> === Addition ===<br /> ==== Problem ====<br /> Suppose we want to find the [[units digit]] of the following [[sum]]:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;2403 + 791 + 688 + 4339.&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> We could find their sum, which is &lt;math&gt;8221&lt;/math&gt;, and note that the units digit is &lt;math&gt;1&lt;/math&gt;. However, we could find the units digit with far less calculation.<br /> <br /> ==== Solution ====<br /> We can simply add the units digits of the addends:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;3 + 1 + 8 + 9 = 21.&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> The units digit of this sum is &lt;math&gt;1&lt;/math&gt;, which ''must'' be the same as the units digit of the four-digit sum we computed earlier.<br /> <br /> ==== Why we only need to use remainders ====<br /> We can rewrite each of the integers in terms of multiples of &lt;math&gt;10&lt;/math&gt; and remainders:&lt;br&gt;<br /> &lt;math&gt;2403 = 240 \cdot 10 + 3&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;791 = 79 \cdot 10 + 1&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;688 = 68 \cdot 10 + 8&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;4339 = 433 \cdot 10 + 9&lt;/math&gt;.&lt;br&gt;<br /> When we add all four integers, we get<br /> <br /> <br /> &lt;center&gt;&lt;math&gt; (240 \cdot 10 + 3) + (79 \cdot 10 + 1) + (68 \cdot 10 + 8) + (433 \cdot 10 + 9)&lt;/math&gt;&lt;/center&gt;<br /> <br /> &lt;center&gt;&lt;math&gt;= (240 + 79 + 68 + 433) \cdot 10 + (3 + 1 + 8 + 9)&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> At this point, we already see the units digits grouped apart and added to a multiple of &lt;math&gt;10&lt;/math&gt; (which will not affect the units digit of the sum):<br /> <br /> &lt;center&gt;&lt;math&gt;= 820 \cdot 10 + 21 = 8200 + 21 = 8221&lt;/math&gt;.&lt;/center&gt;<br /> <br /> ==== Solution using modular arithmetic ====<br /> Now let's look back at this solution, using modular arithmetic from the start. Note that&lt;br&gt;<br /> &lt;math&gt;2403 \equiv 3 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;791 \equiv 1 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;688 \equiv 8 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;4339 \equiv 9 \pmod{10}&lt;/math&gt;&lt;br&gt;<br /> Because we only need the modulo &lt;math&gt;10&lt;/math&gt; residue of the sum, we add just the residues of the summands:<br /> <br /> &lt;center&gt;&lt;math&gt;2403 + 791 + 688 + 4339 \equiv 3 + 1 + 8 + 9 \equiv 21 \equiv 1 \pmod{10},&lt;/math&gt;&lt;/center&gt;<br /> so the units digit of the sum is just &lt;math&gt;1&lt;/math&gt;.<br /> <br /> ==== Addition rule ====<br /> In general, when &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> the following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a + b \equiv c + d \pmod{m} &lt;/math&gt;.&lt;/center&gt;<br /> And as we did in the problem above, we can apply more pairs of equivalent integers to both sides, just repeating this simple principle.<br /> <br /> ====Proof of the addition rule====<br /> <br /> Let &lt;math&gt;a-c=m\cdot k&lt;/math&gt;, and &lt;math&gt;b-d=m\cdot l&lt;/math&gt; for &lt;math&gt;l,k \in \mathbb{Z}&lt;/math&gt;. <br /> Adding the two equations we get:<br /> &lt;cmath&gt;<br /> \begin{eqnarray*}<br /> mk+ml&amp;=&amp;(a-c)+(b-d)\\<br /> m(k+l)&amp;=&amp;(a+b)-(c+d)<br /> \end{eqnarray*}<br /> &lt;/cmath&gt;<br /> <br /> Which is equivalent to saying &lt;math&gt;a+b\equiv c+d\pmod{m}&lt;/math&gt;<br /> <br /> === Subtraction ===<br /> The same shortcut that works with addition of remainders works also with subtraction.<br /> <br /> ==== Problem ====<br /> Find the remainder when the difference between &lt;math&gt;60002&lt;/math&gt; and &lt;math&gt;601&lt;/math&gt; is divided by &lt;math&gt;6&lt;/math&gt;.<br /> <br /> ==== Solution ====<br /> Note that &lt;math&gt;60002 = 10000 \cdot 6 + 2&lt;/math&gt; and &lt;math&gt;601 = 100 \cdot 6 + 1&lt;/math&gt;. So,&lt;br&gt;<br /> &lt;math&gt;60002 \equiv 2 \pmod{6}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;601 \equiv 1 \pmod{6}&lt;/math&gt;&lt;br&gt;<br /> Thus,<br /> &lt;center&gt;&lt;math&gt;60002 - 601 \equiv 2 - 1 \equiv 1 \pmod{6}, &lt;/math&gt;&lt;/center&gt;<br /> so 1 is the remainder when the difference is divided by &lt;math&gt;6&lt;/math&gt;. (Perform the subtraction yourself, divide by &lt;math&gt;6&lt;/math&gt;, and see!)<br /> <br /> ==== Subtraction rule ====<br /> When &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> the following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a - b \equiv c - d \pmod{m} &lt;/math&gt;&lt;/center&gt;.<br /> <br /> <br /> === Multiplication ===<br /> Modular arithmetic provides an even larger advantage when multiplying than when adding or subtracting. Let's take a look at a problem that demonstrates the point.<br /> <br /> ==== Problem ====<br /> Jerry has 44 boxes of soda in his truck. The cans of soda in each box are packed oddly so that there are 113 cans of soda in each box. Jerry plans to pack the sodas into cases of 12 cans to sell. After making as many complete cases as possible, how many sodas will Jerry have leftover?<br /> <br /> ==== Solution ====<br /> First, we note that this [[word problem]] is asking us to find the remainder when the product &lt;math&gt;44 \cdot 113&lt;/math&gt; is divided by &lt;math&gt;12&lt;/math&gt;.<br /> <br /> Now, we can write each &lt;math&gt;44&lt;/math&gt; and &lt;math&gt;113&lt;/math&gt; in terms of multiples of &lt;math&gt;12&lt;/math&gt; and remainders:&lt;br&gt;<br /> &lt;math&gt;44 = 3 \cdot 12 + 8&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;113 = 9 \cdot 12 + 5&lt;/math&gt;&lt;br&gt;<br /> This gives us a nice way to view their product:<br /> <br /> <br /> &lt;center&gt;&lt;math&gt;44 \cdot 113 = (3 \cdot 12 + 8)(9 \cdot 12 + 5)&lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;=(3 \cdot 9) \cdot 12^2 + (3 \cdot 5 + 8 \cdot 9) \cdot 12 + (8 \cdot 5)&lt;/math&gt;&lt;/center&gt;<br /> <br /> <br /> We can already see that each part of the product is a multiple of &lt;math&gt;12&lt;/math&gt;, except the product of the remainders when each &lt;math&gt;44&lt;/math&gt; and &lt;math&gt;113&lt;/math&gt; are divided by 12. That part of the product is &lt;math&gt;8 \cdot 5 = 40&lt;/math&gt;, which leaves a remainder of &lt;math&gt;4&lt;/math&gt; when divided by &lt;math&gt;12&lt;/math&gt;. So, Jerry has &lt;math&gt;4&lt;/math&gt; sodas leftover after making as many cases of &lt;math&gt;12&lt;/math&gt; as possible.<br /> <br /> ==== Solution using modular arithmetic ====<br /> First, we note that&lt;br&gt;<br /> &lt;math&gt;44 \equiv 8 \pmod{12}&lt;/math&gt;&lt;br&gt;<br /> &lt;math&gt;113 \equiv 5 \pmod{12}&lt;/math&gt;&lt;br&gt;<br /> Thus,<br /> &lt;center&gt;&lt;math&gt;44 \cdot 113 \equiv 8 \cdot 5 \equiv 40 \equiv 4 \pmod{12},&lt;/math&gt;&lt;/center&gt;<br /> meaning there are &lt;math&gt;4&lt;/math&gt; sodas leftover. Yeah, that was much easier.<br /> <br /> ==== Multiplication rule ====<br /> When &lt;math&gt;a, b, c&lt;/math&gt;, and &lt;math&gt;d&lt;/math&gt; are integers and &lt;math&gt;m&lt;/math&gt; is a positive integer such that&lt;br&gt;<br /> &lt;center&gt;&lt;math&gt;a \equiv c \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> &lt;center&gt;&lt;math&gt;b \equiv d \pmod{m} &lt;/math&gt;&lt;/center&gt;<br /> The following is always true:<br /> <br /> &lt;center&gt;&lt;math&gt;a \cdot b \equiv c \cdot d \pmod{m} &lt;/math&gt;.&lt;/center&gt;<br /> <br /> <br /> === Exponentiation ===<br /> Since [[exponentiation]] is just repeated multiplication, it makes sense that modular arithmetic would make many problems involving exponents easier. In fact, the advantage in computation is even larger and we explore it a great deal more in the [[intermediate modular arithmetic]] article.<br /> <br /> Note to everybody: Exponentiation is very useful as in the following problem:<br /> <br /> ==== Problem #1====<br /> What is the last digit of &lt;math&gt;(...((7)^7)^7)...)^7&lt;/math&gt; if there are 1000 7s as exponents and only one 7 in the middle?<br /> <br /> We could solve this problem using mods. This can also be stated as &lt;math&gt;7^{7^{1000}}&lt;/math&gt;. After that, we see that 7 is congruent to -1 in mod 4, so we can use this fact to replace the 7s with -1s, because 7 has a pattern of repetitive period 4 for the units digit. &lt;math&gt;(-1)^{1000}&lt;/math&gt; is simply 1, so therefore &lt;math&gt;7^1=7&lt;/math&gt;, which really is the last digit.<br /> <br /> ==== Problem #2====<br /> What are the tens and units digits of &lt;math&gt;7^{1942}&lt;/math&gt;?<br /> <br /> We could (in theory) solve this problem by trying to compute &lt;math&gt;7^{1942}&lt;/math&gt;, but this would be extremely time-consuming. Moreover, it would give us much more information than we need. Since we want only the tens and units digits of the number in question, it suffices to find the remainder when the number is divided by &lt;math&gt;100&lt;/math&gt;. In other words, all of the information we need can be found using arithmetic mod &lt;math&gt;100&lt;/math&gt;.<br /> <br /> We begin by writing down the first few powers of &lt;math&gt;7&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt;:<br /> <br /> &lt;math&gt;7, 49, 43, 1, 7, 49, 43, 1, \ldots&lt;/math&gt;<br /> <br /> A pattern emerges! We see that &lt;math&gt;7^4 = 2401 \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;). So for any positive integer &lt;math&gt;k&lt;/math&gt;, we have &lt;math&gt;7^{4k} = (7^4)^k \equiv 1^k \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;). In particular, we can write<br /> <br /> &lt;math&gt;7^{1940} = 7^{4 \cdot 485} \equiv 1&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;).<br /> <br /> By the &quot;multiplication&quot; property above, then, it follows that<br /> <br /> &lt;math&gt;7^{1942} = 7^{1940} \cdot 7^2 \equiv 1 \cdot 7^2 \equiv 49&lt;/math&gt; (mod &lt;math&gt;100&lt;/math&gt;).<br /> <br /> Therefore, by the definition of congruence, &lt;math&gt;7^{1942}&lt;/math&gt; differs from &lt;math&gt;49&lt;/math&gt; by a multiple of &lt;math&gt;100&lt;/math&gt;. Since both integers are positive, this means that they share the same tens and units digits. Those digits are &lt;math&gt;4&lt;/math&gt; and &lt;math&gt;9&lt;/math&gt;, respectively.<br /> <br /> ==== Problem #3====<br /> <br /> Can you find a number that is both a multiple of &lt;math&gt;2&lt;/math&gt; but not a multiple of &lt;math&gt;4&lt;/math&gt; and a perfect square?<br /> <br /> No, you cannot, rewritting the question we see that it asks us to find a number &lt;math&gt;n&lt;/math&gt; that satisfies this: &lt;math&gt;4n+2=x^2&lt;/math&gt;.<br /> <br /> Taking mod &lt;math&gt;4&lt;/math&gt; on both sides we find that &lt;math&gt;x^2\equiv 2\pmod{4}&lt;/math&gt;, now all we are missing to show is that no matter what &lt;math&gt;x&lt;/math&gt; is, &lt;math&gt;x^2&lt;/math&gt; will never be a multiple of &lt;math&gt;4&lt;/math&gt; plus &lt;math&gt;2&lt;/math&gt;, so we work with cases:<br /> <br /> &lt;math&gt;x\equiv 0\pmod{4}\implies x^2\equiv 0\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 1\pmod{4}\implies x^2\equiv 1\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 2\pmod{4}\implies x^2\equiv 4\equiv 0\pmod{4}&lt;/math&gt;<br /> <br /> &lt;math&gt;x\equiv 3\pmod{4}\implies x^2\equiv 9\equiv 1\pmod{4}&lt;/math&gt;<br /> <br /> This assures us that it is impossible to find such a number.<br /> <br /> == Summary of Useful Facts ==<br /> <br /> Consider four integers &lt;math&gt;{a},{b},{c},{d}&lt;/math&gt; and a positive integer &lt;math&gt;{m}&lt;/math&gt; such that &lt;math&gt;a\equiv b\pmod {m}&lt;/math&gt; and &lt;math&gt;c\equiv d\pmod {m}&lt;/math&gt;. In modular arithmetic, the following [[identity | identities]] hold:<br /> <br /> * Addition: &lt;math&gt;a+c\equiv b+d\pmod {m}&lt;/math&gt;.<br /> * Subtraction: &lt;math&gt;a-c\equiv b-d\pmod {m}&lt;/math&gt;.<br /> * Multiplication: &lt;math&gt;ac\equiv bd\pmod {m}&lt;/math&gt;.<br /> * Division: &lt;math&gt;\frac{a}{e}\equiv \frac{b}{e}\pmod {\frac{m}{\gcd(m,e)}}&lt;/math&gt;, where &lt;math&gt;e&lt;/math&gt; is a positive integer that divides &lt;math&gt;{a}&lt;/math&gt; and &lt;math&gt;b&lt;/math&gt;.<br /> * Exponentiation: &lt;math&gt;a^e\equiv b^e\pmod {m}&lt;/math&gt; where &lt;math&gt;e&lt;/math&gt; is a positive integer.<br /> <br /> <br /> <br /> == Applications of Modular Arithmetic ==<br /> Modular arithmetic is an extremely flexible problem solving tool. The following topics are just a few applications and extensions of its use:<br /> * [[Divisibility rules]]<br /> * [[Linear congruence | Linear congruences]]<br /> <br /> <br /> <br /> == Resources ==<br /> * The AoPS [http://www.artofproblemsolving.com/Store/viewitem.php?item=intro:nt Introduction to Number Theory] by [[Mathew Crawford]].<br /> * The AoPS [http://www.artofproblemsolving.com/School/courseinfo.php?course_id=intro:numbertheory Introduction to Number Theory Course]. Thousands of students have learned more about modular arithmetic and [[problem solving]] from this 12 week class.<br /> <br /> == See also ==<br /> * [[Intermediate modular arithmetic]]<br /> * [[Olympiad modular arithmetic]]<br /> <br /> <br /> [[Category:Introductory Mathematics Topics]]</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Arithmetic_series&diff=72130 Arithmetic series 2015-09-20T00:32:48Z <p>Greenpepper9999: </p> <hr /> <div>An '''arithmetic series''' is a sum of consecutive terms in an [[arithmetic sequence]]. For instance,<br /> <br /> &lt;math&gt; 2 + 6 + 10 + 14 + 18 &lt;/math&gt;<br /> <br /> is an arithmetic series whose value is 50.<br /> ==Formula==<br /> To find the sum of an arithmetic sequence, we can write it out in two as so (&lt;math&gt;S&lt;/math&gt; is the sum, &lt;math&gt;a&lt;/math&gt; is the first term, &lt;math&gt;z&lt;/math&gt; is the number of terms, and &lt;math&gt;d&lt;/math&gt; is the common difference):<br /> &lt;cmath&gt;<br /> S = a + (a+d) + (a+2d) + \ldots + (z-d) + z<br /> &lt;/cmath&gt;<br /> Flipping the right side of the equation we get<br /> &lt;cmath&gt;<br /> S = z + (z-d) + (z-2d) + \ldots + (a+d) + a<br /> &lt;/cmath&gt;<br /> <br /> Now, adding the above two equations vertically, we get<br /> <br /> &lt;cmath&gt;2S = (a+z) + (a+z) + (a+z) + ... +(a+z) + (a+z)&lt;/cmath&gt;<br /> <br /> This equals &lt;math&gt;2S = n(a+z)&lt;/math&gt;, so the sum is &lt;math&gt;\frac{n(a+z)}{2}&lt;/math&gt;.<br /> <br /> == Problems ==<br /> === Introductory Problems ===<br /> * [[2006_AMC_10A_Problems/Problem_9 | 2006 AMC 10A, Problem 9]]<br /> *[[2006 AMC 12A Problems/Problem 12 | 2006 AMC 12A, Problem 12]]<br /> <br /> === Intermediate Problems ===<br /> *[[2003 AIME I Problems/Problem 2|2003 AIME I, Problem 2]]<br /> <br /> === Olympiad Problem ===<br /> <br /> == See also ==<br /> * [[Series]]<br /> * [[Summation]]<br /> <br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Arithmetic_series&diff=72129 Arithmetic series 2015-09-20T00:31:38Z <p>Greenpepper9999: </p> <hr /> <div>An '''arithmetic series''' is a sum of consecutive terms in an [[arithmetic sequence]]. For instance,<br /> <br /> &lt;math&gt; 2 + 6 + 10 + 14 + 18 &lt;/math&gt;<br /> <br /> is an arithmetic series whose value is 50.<br /> <br /> To find the sum of an arithmetic sequence, we can write it out in two as so (&lt;math&gt;S&lt;/math&gt; is the sum, &lt;math&gt;a&lt;/math&gt; is the first term, &lt;math&gt;z&lt;/math&gt; is the number of terms, and &lt;math&gt;d&lt;/math&gt; is the common difference):<br /> &lt;cmath&gt;<br /> S = a + (a+d) + (a+2d) + \ldots + (z-d) + z<br /> &lt;/cmath&gt;<br /> Flipping the right side of the equation we get<br /> &lt;cmath&gt;<br /> S = z + (z-d) + (z-2d) + \ldots + (a+d) + a<br /> &lt;/cmath&gt;<br /> <br /> Now, adding the above two equations vertically, we get<br /> <br /> &lt;cmath&gt;2S = (a+z) + (a+z) + (a+z) + ... +(a+z) + (a+z)&lt;/cmath&gt;<br /> <br /> This equals &lt;math&gt;2S = n(a+z)&lt;/math&gt;, so the sum is &lt;math&gt;\frac{n(a+z)}{2}&lt;/math&gt;.<br /> <br /> == Problems ==<br /> === Introductory Problems ===<br /> * [[2006_AMC_10A_Problems/Problem_9 | 2006 AMC 10A, Problem 9]]<br /> *[[2006 AMC 12A Problems/Problem 12 | 2006 AMC 12A, Problem 12]]<br /> <br /> === Intermediate Problems ===<br /> *[[2003 AIME I Problems/Problem 2|2003 AIME I, Problem 2]]<br /> <br /> === Olympiad Problem ===<br /> <br /> == See also ==<br /> * [[Series]]<br /> * [[Summation]]<br /> <br /> {{stub}}</div> Greenpepper9999 https://artofproblemsolving.com/wiki/index.php?title=Arithmetic_series&diff=72128 Arithmetic series 2015-09-20T00:30:53Z <p>Greenpepper9999: Replaced ... With elippsis</p> <hr /> <div>An '''arithmetic series''' is a sum of consecutive terms in an [[arithmetic sequence]]. For instance,<br /> <br /> &lt;math&gt; 2 + 6 + 10 + 14 + 18 &lt;/math&gt;<br /> <br /> is an arithmetic series whose value is 50.<br /> <br /> To find the sum of an arithmetic sequence, we can write it out in two as so (&lt;math&gt;S&lt;/math&gt; is the sum, &lt;math&gt;a&lt;/math&gt; is the first term, &lt;math&gt;z&lt;/math&gt; is the number of terms, and &lt;math&gt;d&lt;/math&gt; is the common difference):<br /> &lt;cmath&gt;<br /> S = a + (a+d) + (a+2d) + \ldots + (z-d) + z<br /> &lt;/cmath&gt;<br /> Flipping the right side of the equation we get<br /> &lt;cmath&gt;<br /> S = z + (z-d) + (z-2d) + \ldots + (a+d) + a<br /> &lt;/cmath&gt;<br /> <br /> Now, adding the above two equations vertically, we get<br /> <br /> &lt;cmath&gt;2S = (a+z) + (a+z) + (a+z) + ... + (a+z)&lt;/cmath&gt;<br /> <br /> This equals &lt;math&gt;2S = n(a+z)&lt;/math&gt;, so the sum is &lt;math&gt;\frac{n(a+z)}{2}&lt;/math&gt;.<br /> <br /> == Problems ==<br /> === Introductory Problems ===<br /> * [[2006_AMC_10A_Problems/Problem_9 | 2006 AMC 10A, Problem 9]]<br /> *[[2006 AMC 12A Problems/Problem 12 | 2006 AMC 12A, Problem 12]]<br /> <br /> === Intermediate Problems ===<br /> *[[2003 AIME I Problems/Problem 2|2003 AIME I, Problem 2]]<br /> <br /> === Olympiad Problem ===<br /> <br /> == See also ==<br /> * [[Series]]<br /> * [[Summation]]<br /> <br /> {{stub}}</div> Greenpepper9999