https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=ZetaX&feedformat=atom AoPS Wiki - User contributions [en] 2021-01-23T01:39:02Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=Quadratic_reciprocity&diff=51983 Quadratic reciprocity 2013-03-30T02:24:27Z <p>ZetaX: </p> <hr /> <div>Let &lt;math&gt;p&lt;/math&gt; be a [[prime number|prime]], and let &lt;math&gt;a&lt;/math&gt; be any integer. Then we can define the [[Legendre symbol]]<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 &amp; \text{if } a \text{ is a quadratic residue modulo } p, \\<br /> 0 &amp; \text{if } p \text{ divides } a, \\ -1 &amp; \text{otherwise}.\end{cases} &lt;/cmath&gt;<br /> <br /> We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' modulo &lt;math&gt;p&lt;/math&gt; if there exists an integer &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2\equiv a\pmod p&lt;/math&gt;.<br /> <br /> Equivalently, we can define the function &lt;math&gt;a \mapsto \genfrac{(}{)}{}{}{a}{p}&lt;/math&gt; as the unique nontrivial multiplicative [[homomorphism]] of &lt;math&gt;\mathbb{F}_p^\times&lt;/math&gt; into &lt;math&gt;\mathbb{R}^\times&lt;/math&gt;, extended by &lt;math&gt;0 \mapsto 0&lt;/math&gt;.<br /> <br /> == Quadratic Reciprocity Theorem ==<br /> <br /> There are three parts. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct [[odd integer | odd]] primes. Then the following hold:<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2},&lt;/math&gt;<br /> * &lt;math&gt; \genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2-1)/8},&lt;/math&gt;<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4} .&lt;/math&gt;<br /> This theorem can help us evaluate Legendre symbols, since the following laws also apply:<br /> * If &lt;math&gt;a\equiv b\pmod{p}&lt;/math&gt;, then &lt;math&gt;\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}&lt;/math&gt;.<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}&lt;/math&gt;.<br /> <br /> There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)<br /> <br /> == Proof ==<br /> <br /> '''Theorem 1.''' Let &lt;math&gt;p&lt;/math&gt; be an odd prime. Then &lt;math&gt;\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2}&lt;/math&gt;.<br /> <br /> ''Proof.'' It suffices to show that &lt;math&gt;(-1)^{(p-1)/2} = 1&lt;/math&gt; if and only if &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;.<br /> <br /> Suppose that &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;. Then &lt;math&gt;k^2 = -1&lt;/math&gt;, for some residue &lt;math&gt;k&lt;/math&gt; mod &lt;math&gt;p&lt;/math&gt;, so<br /> &lt;cmath&gt; (-1)^{(p-1)/2} = (k^2)^{(p-1)/2} = k^{p-1} = 1 = \genfrac{(}{)}{}{}{-1}{p} , &lt;/cmath&gt;<br /> by [[Fermat's Little Theorem]].<br /> <br /> On the other hand, suppose that &lt;math&gt;(-1)^{(p-1)/2} = 1&lt;/math&gt;. Then &lt;math&gt;(p-1)/2&lt;/math&gt; is even, so &lt;math&gt;(p-1)/4&lt;/math&gt; is an integer. Since every nonzero residue mod &lt;math&gt;p&lt;/math&gt; is a root of the polynomial<br /> &lt;cmath&gt; (x^{p-1} - 1) = (x^{(p-1)/2} + 1)(x^{(p-1)/2} - 1) , &lt;/cmath&gt;<br /> and the &lt;math&gt;p-1&lt;/math&gt; nonzero residues cannot all be roots of the polynomial &lt;math&gt;x^{(p-1)/2} - 1&lt;/math&gt;, it follows that for some residue &lt;math&gt;k&lt;/math&gt;,<br /> &lt;cmath&gt; \bigl(k^{(p-1)/2}\bigr)^2 = k^{(p-1)/2} = -1 . &lt;/cmath&gt;<br /> Therefore &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;, as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> Now, let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes, and let &lt;math&gt;K&lt;/math&gt; be the [[splitting field]] of the polynomial &lt;math&gt;x^q - 1&lt;/math&gt; over the finite field &lt;math&gt;\mathbb{F}_p&lt;/math&gt;. Let &lt;math&gt;\zeta&lt;/math&gt; be a primitive &lt;math&gt;q&lt;/math&gt;th root of unity in &lt;math&gt;K&lt;/math&gt;. We define the Gaussian sum<br /> &lt;cmath&gt; \tau_q = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^q . &lt;/cmath&gt;<br /> <br /> '''Lemma.''' &lt;math&gt;\tau_q^2 = q (-1)^{(q-1)/2}&lt;/math&gt;<br /> <br /> ''Proof.'' By definition, we have<br /> &lt;cmath&gt; \tau_q^2 = \sum_a \sum_b \genfrac{(}{)}{}{}{a}{q} \zeta^a \genfrac{(}{)}{}{}{b}{q} \zeta^b = \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} . &lt;/cmath&gt;<br /> Letting &lt;math&gt;c \equiv a^{-1}b \pmod{q}&lt;/math&gt;, we have<br /> &lt;cmath&gt; \begin{align*} \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} &amp;= \sum_{a\neq 0} \sum_c \genfrac{(}{)}{}{}{a^2 c}{q} \zeta^{a+ac} \\<br /> &amp;= \sum_c \sum_{a \neq 0} \genfrac{(}{)}{}{}{c}{q} \bigl( \zeta^{1+c} \bigr)^a \\<br /> &amp;= \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a . \end{align*} &lt;/cmath&gt;<br /> Now, &lt;math&gt;\zeta^{c+1}&lt;/math&gt; is a root of the polynomial<br /> &lt;cmath&gt; P(x) = x^q - 1 = (x-1) \sum_{i=0}^{q-1} x^i, &lt;/cmath&gt;<br /> it follows that for &lt;math&gt;c\neq -1&lt;/math&gt;,<br /> &lt;cmath&gt; \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = -1, &lt;/cmath&gt;<br /> while for &lt;math&gt;c = -1&lt;/math&gt;, we have<br /> &lt;cmath&gt; \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q-1 . &lt;/cmath&gt;<br /> Therefore<br /> &lt;cmath&gt; \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q \genfrac{(}{)}{}{}{-1}{q} - \sum_{c=0}^{q-1}\genfrac{(}{)}{}{}{c}{q} . &lt;/cmath&gt;<br /> But since there are &lt;math&gt;(q-1)/2&lt;/math&gt; nonsquares and &lt;math&gt;(q-1)/2&lt;/math&gt; nonzero square mod &lt;math&gt;q&lt;/math&gt;, it follows that<br /> &lt;cmath&gt; \sum_{c=0}^{q-1} \genfrac{(}{)}{}{}{c}{q} = 0 . &lt;/cmath&gt;<br /> Therefore<br /> &lt;cmath&gt; \tau_q^2 = q \genfrac{(}{)}{}{}{-1}{q} = q (-1)^{(q-1)/2} , &lt;/cmath&gt;<br /> by Theorem 1.<br /> <br /> '''Theorem 2.''' &lt;math&gt;\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}&lt;/math&gt;.<br /> <br /> ''Proof.'' We compute the quantity &lt;math&gt;\tau_q^p&lt;/math&gt; in two different ways.<br /> <br /> We first note that since &lt;math&gt;p=0&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;,<br /> &lt;cmath&gt; \tau_q^p = \biggl( \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^a \biggr)^p = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q}^p \zeta^{ap} = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} . &lt;/cmath&gt;<br /> Since &lt;math&gt;\genfrac{(}{)}{}{}{p}{q}^2 = 1&lt;/math&gt;,<br /> &lt;cmath&gt; \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{p}{q} \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{pa}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{a}{q} \tau_q . &lt;/cmath&gt;<br /> Thus<br /> &lt;cmath&gt; \tau_q^p = \genfrac{(}{)}{}{}{p}{q} \tau_q . &lt;/cmath&gt;<br /> <br /> On the other hand, from the lemma,<br /> &lt;cmath&gt; \tau_q^p = (\tau_q^2)^{(p-1)/2} \cdot \tau_q = \bigl[ q (-1)^{(q-1)/2} \bigr]^{(p-1)/2} \tau_q = q^{(p-1)/2} (-1)^{(p-1)(q-1)/4 \tau_q . &lt;/cmath&gt;<br /> Since &lt;math&gt;q^{(p-1)/2} = \genfrac{(}{)}{}{}{q}{p}&lt;/math&gt;, we then have<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q . &lt;/cmath&gt;<br /> Since &lt;math&gt;\tau_q&lt;/math&gt; is evidently nonzero and<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{q}{p}^2 = 1, &lt;/cmath&gt;<br /> we therefore have<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}, &lt;/cmath&gt;<br /> as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> '''Theorem 3.''' &lt;math&gt;\genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2 - 1)/8}&lt;/math&gt;.<br /> <br /> ''Proof.'' Let &lt;math&gt;K&lt;/math&gt; be the splitting field of the polynomial<br /> &lt;math&gt;x^8-1&lt;/math&gt; over &lt;math&gt;\mathbb{F}_p&lt;/math&gt;; let &lt;math&gt;\zeta&lt;/math&gt; be a root of the polynomial<br /> &lt;math&gt;x^4+1&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;.<br /> <br /> We note that<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^2 = \zeta^2 + 2 + \zeta^{-2} = 2 + \zeta^{-2} (\zeta^{4} + 1) = 2 . &lt;/cmath&gt;<br /> So<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1}) 2^{(p-1)/2} = (\zeta + \zeta^{-1}) \genfrac{(}{)}{}{}{2}{p}. &lt;/cmath&gt;<br /> <br /> On the other hand, since &lt;math&gt;K&lt;/math&gt; is a field of characteristic &lt;math&gt;p&lt;/math&gt;,<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^p = \zeta^p + \zeta^{-p} . &lt;/cmath&gt;<br /> Thus<br /> &lt;cmath&gt; \zeta^p + \zeta^{-p} = (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1} \genfrac{(}{)}{}{}{2}{p} . &lt;/cmath&gt;<br /> Now, if &lt;math&gt;p \equiv 4 \pm 1 \pmod{8}&lt;/math&gt;, then<br /> &lt;cmath&gt; \zeta^{p} + \zeta^{-p} = - ( \zeta + \zeta^{-1} ) &lt;/cmath&gt;<br /> and &lt;math&gt;p^2 - 1 \equiv 8 \pmod{16}&lt;/math&gt;, so &lt;math&gt;(-1)^{(p^2-1)/8} = -1&lt;/math&gt;,<br /> and<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{2}{p} = -1 = (-1)^{(p^2 - 1)/8} . &lt;/cmath&gt;<br /> On the other hand, if &lt;math&gt;p \equiv \pm 1 \pmod{8}&lt;/math&gt;, then<br /> &lt;cmath&gt; \zeta^p + \zeta^{-p} = \zeta + \zeta^{-1}, &lt;/cmath&gt;<br /> and &lt;math&gt;p^2 -1 \equiv 0 \pmod{16}&lt;/math&gt;, so<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{2}{p} = 1 = (-1)^{p^2-1} . &lt;/cmath&gt;<br /> Thus the theorem holds in all cases. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> <br /> == References ==<br /> <br /> * Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,'' American Mathematical Society 2000. ISBN 0-8218-2054-0 <br /> <br /> [[Category:Number theory]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Quadratic_reciprocity&diff=35647 Quadratic reciprocity 2010-08-15T12:00:01Z <p>ZetaX: </p> <hr /> <div>Let &lt;math&gt;p&lt;/math&gt; be a [[prime number|prime]], and let &lt;math&gt;a&lt;/math&gt; be any integer. Then we can define the [[Legendre symbol]]<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 &amp; \text{if } a \text{ is a quadratic residue modulo } p, \\<br /> 0 &amp; \text{if } p \text{ divides } a, \\ -1 &amp; \text{otherwise}.\end{cases} &lt;/cmath&gt;<br /> <br /> We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' modulo &lt;math&gt;p&lt;/math&gt; if there exists an integer &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2\equiv a\pmod p&lt;/math&gt;.<br /> <br /> Equivalently, we can define the function &lt;math&gt;a \mapsto \genfrac{(}{)}{}{}{a}{p}&lt;/math&gt; as the unique nontrivial multiplicative [[homomorphism]] of &lt;math&gt;\mathbb{F}_p^\times&lt;/math&gt; into &lt;math&gt;\mathbb{R}^\times&lt;/math&gt;, extended by &lt;math&gt;0 \mapsto 0&lt;/math&gt;.<br /> <br /> == Quadratic Reciprocity Theorem ==<br /> <br /> There are three parts. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct [[odd integer | odd]] primes. Then the following hold:<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2},&lt;/math&gt;<br /> * &lt;math&gt; \genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2-1)/8},&lt;/math&gt;<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4} .&lt;/math&gt;<br /> This theorem can help us evaluate Legendre symbols, since the following laws also apply:<br /> * If &lt;math&gt;a\equiv b\pmod{p}&lt;/math&gt;, then &lt;math&gt;\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}&lt;/math&gt;.<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}&lt;/math&gt;.<br /> <br /> There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)<br /> <br /> == Proof ==<br /> <br /> '''Theorem 1.''' Let &lt;math&gt;p&lt;/math&gt; be an odd prime. Then &lt;math&gt;\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2}&lt;/math&gt;.<br /> <br /> ''Proof.'' It suffices to show that &lt;math&gt;(-1)^{(p-1)/2} = 1&lt;/math&gt; if and only if &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;.<br /> <br /> Suppose that &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;. Then &lt;math&gt;k^2 = -1&lt;/math&gt;, for some residue &lt;math&gt;k&lt;/math&gt; mod &lt;math&gt;p&lt;/math&gt;, so<br /> &lt;cmath&gt; (-1)^{(p-1)/2} = (k^2)^{(p-1)/2} = k^{p-1} = 1 = \genfrac{(}{)}{}{}{-1}{p} , &lt;/cmath&gt;<br /> by [[Fermat's Little Theorem]].<br /> <br /> On the other hand, suppose that &lt;math&gt;(-1)^{(p-1)/2} = 1&lt;/math&gt;. Then &lt;math&gt;(p-1)/2&lt;/math&gt; is even, so &lt;math&gt;(p-1)/4&lt;/math&gt; is an integer. Since every nonzero residue mod &lt;math&gt;p&lt;/math&gt; is a root of the polynomial<br /> &lt;cmath&gt; (x^{p-1} - 1 = (x^{(p-1)/2} + 1)(x^{(p-1)/2} - 1) , &lt;/cmath&gt;<br /> and the &lt;math&gt;p-1&lt;/math&gt; nonzero residues cannot all be roots of the polynomial &lt;math&gt;x^{(p-1)/2} - 1&lt;/math&gt;, it follows that for some residue &lt;math&gt;k&lt;/math&gt;,<br /> &lt;cmath&gt; \bigl(k^{(p-1)/2}\bigr)^2 = k^{(p-1)/2} = -1 . &lt;/cmath&gt;<br /> Therefore &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;, as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> Now, let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes, and let &lt;math&gt;K&lt;/math&gt; be the [[splitting field]] of the polynomial &lt;math&gt;x^q - 1&lt;/math&gt; over the finite field &lt;math&gt;\mathbb{F}_p&lt;/math&gt;. Let &lt;math&gt;\zeta&lt;/math&gt; be a primitive &lt;math&gt;q&lt;/math&gt;th root of unity in &lt;math&gt;K&lt;/math&gt;. We define the Gaussian sum<br /> &lt;cmath&gt; \tau_q = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^q . &lt;/cmath&gt;<br /> <br /> '''Lemma.''' &lt;math&gt;\tau_q^2 = q (-1)^{(q-1)/2}&lt;/math&gt;<br /> <br /> ''Proof.'' By definition, we have<br /> &lt;cmath&gt; \tau_q^2 = \sum_a \sum_b \genfrac{(}{)}{}{}{a}{q} \zeta^a \genfrac{(}{)}{}{}{b}{q} \zeta^b = \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} . &lt;/cmath&gt;<br /> Letting &lt;math&gt;c \equiv a^{-1}b \pmod{q}&lt;/math&gt;, we have<br /> &lt;cmath&gt; \begin{align*} \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} &amp;= \sum_{a\neq 0} \sum_c \genfrac{(}{)}{}{}{a^2 c}{q} \zeta^{a+ac} \\<br /> &amp;= \sum_c \sum_{a \neq 0} \genfrac{(}{)}{}{}{c}{q} \bigl( \zeta^{1+c} \bigr)^a \\<br /> &amp;= \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a . \end{align*} &lt;/cmath&gt;<br /> Now, &lt;math&gt;\zeta^{c+1}&lt;/math&gt; is a root of the polynomial<br /> &lt;cmath&gt; P(x) = x^q - 1 = (x-1) \sum_{i=0}^{q-1} x^i, &lt;/cmath&gt;<br /> it follows that for &lt;math&gt;c\neq -1&lt;/math&gt;,<br /> &lt;cmath&gt; \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = -1, &lt;/cmath&gt;<br /> while for &lt;math&gt;c = -1&lt;/math&gt;, we have<br /> &lt;cmath&gt; \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q-1 . &lt;/cmath&gt;<br /> Therefore<br /> &lt;cmath&gt; \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q \genfrac{(}{)}{}{}{-1}{q} - \sum_{c=0}^{q-1}\genfrac{(}{)}{}{}{c}{q} . &lt;/cmath&gt;<br /> But since there are &lt;math&gt;(q-1)/2&lt;/math&gt; nonsquares and &lt;math&gt;(q-1)/2&lt;/math&gt; nonzero square mod &lt;math&gt;q&lt;/math&gt;, it follows that<br /> &lt;cmath&gt; \sum_{c=0}^{q-1} \genfrac{(}{)}{}{}{c}{q} = 0 . &lt;/cmath&gt;<br /> Therefore<br /> &lt;cmath&gt; \tau_q^2 = q \genfrac{(}{)}{}{}{-1}{q} = q (-1)^{(q-1)/2} , &lt;/cmath&gt;<br /> by Theorem 1.<br /> <br /> '''Theorem 2.''' &lt;math&gt;\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}&lt;/math&gt;.<br /> <br /> ''Proof.'' We compute the quantity &lt;math&gt;\tau_q^p&lt;/math&gt; in two different ways.<br /> <br /> We first note that since &lt;math&gt;p=0&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;,<br /> &lt;cmath&gt; \tau_q^p = \biggl( \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^a \biggr)^p = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q}^p \zeta^{ap} = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} . &lt;/cmath&gt;<br /> Since &lt;math&gt;\genfrac{(}{)}{}{}{p}{q}^2 = 1&lt;/math&gt;,<br /> &lt;cmath&gt; \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{p}{q} \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{pa}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{a}{q} \tau_q . &lt;/cmath&gt;<br /> Thus<br /> &lt;cmath&gt; \tau_q^p = \genfrac{(}{)}{}{}{p}{q} \tau_q . &lt;/cmath&gt;<br /> <br /> On the other hand, from the lemma,<br /> &lt;cmath&gt; \tau_q^p = (\tau_q^2)^{(p-1)/2} \cdot \tau_q = \bigl[ q (-1)^{(q-1)/2} \bigr]^{(p-1)/2} \tau_q = q^{(p-1)/2} (-1)^{(p-1)(q-1)/4 \tau_q . &lt;/cmath&gt;<br /> Since &lt;math&gt;q^{(p-1)/2} = \genfrac{(}{)}{}{}{q}{p}&lt;/math&gt;, we then have<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q . &lt;/cmath&gt;<br /> Since &lt;math&gt;\tau_q&lt;/math&gt; is evidently nonzero and<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{q}{p}^2 = 1, &lt;/cmath&gt;<br /> we therefore have<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}, &lt;/cmath&gt;<br /> as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> '''Theorem 3.''' &lt;math&gt;\genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2 - 1)/8}&lt;/math&gt;.<br /> <br /> ''Proof.'' Let &lt;math&gt;K&lt;/math&gt; be the splitting field of the polynomial<br /> &lt;math&gt;x^8-1&lt;/math&gt; over &lt;math&gt;\mathbb{F}_p&lt;/math&gt;; let &lt;math&gt;\zeta&lt;/math&gt; be a root of the polynomial<br /> &lt;math&gt;x^4+1&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;.<br /> <br /> We note that<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^2 = \zeta^2 + 2 + \zeta^{-2} = 2 + \zeta^{-2} (\zeta^{4} + 1) = 2 . &lt;/cmath&gt;<br /> So<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1}) 2^{(p-1)/2} = (\zeta + \zeta^{-1}) \genfrac{(}{)}{}{}{2}{p}. &lt;/cmath&gt;<br /> <br /> On the other hand, since &lt;math&gt;K&lt;/math&gt; is a field of characteristic &lt;math&gt;p&lt;/math&gt;,<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^p = \zeta^p + \zeta^{-p} . &lt;/cmath&gt;<br /> Thus<br /> &lt;cmath&gt; \zeta^p + \zeta^{-p} = (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1} \genfrac{(}{)}{}{}{2}{p} . &lt;/cmath&gt;<br /> Now, if &lt;math&gt;p \equiv 4 \pm 1 \pmod{8}&lt;/math&gt;, then<br /> &lt;cmath&gt; \zeta^{p} + \zeta^{-p} = - ( \zeta + \zeta^{-1} ) &lt;/cmath&gt;<br /> and &lt;math&gt;p^2 - 1 \equiv 8 \pmod{16}&lt;/math&gt;, so &lt;math&gt;(-1)^{(p^2-1)/8} = -1&lt;/math&gt;,<br /> and<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{2}{p} = -1 = (-1)^{(p^2 - 1)/8} . &lt;/cmath&gt;<br /> On the other hand, if &lt;math&gt;p \equiv \pm 1 \pmod{8}&lt;/math&gt;, then<br /> &lt;cmath&gt; \zeta^p + \zeta^{-p} = \zeta + \zeta^{-1}, &lt;/cmath&gt;<br /> and &lt;math&gt;p^2 -1 \equiv 0 \pmod{16}&lt;/math&gt;, so<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{2}{p} = 1 = (-1)^{p^2-1} . &lt;/cmath&gt;<br /> Thus the theorem holds in all cases. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> <br /> == References ==<br /> <br /> * Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,'' American Mathematical Society 2000. ISBN 0-8218-2054-0 begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting.<br /> <br /> [[Category:Number theory]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Quadratic_reciprocity&diff=35646 Quadratic reciprocity 2010-08-15T11:59:44Z <p>ZetaX: Event his is better than the one single align... And actually, it's unnatural to call the supplementary laws part if QR</p> <hr /> <div>Let &lt;math&gt;p&lt;/math&gt; be a [[prime number|prime]], and let &lt;math&gt;a&lt;/math&gt; be any integer. Then we can define the [[Legendre symbol]]<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 &amp; \text{if } a \text{ is a quadratic residue modulo } p, \\<br /> 0 &amp; \text{if } p \text{ divides } a, \\ -1 &amp; \text{otherwise}.\end{cases} &lt;/cmath&gt;<br /> <br /> We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' modulo &lt;math&gt;p&lt;/math&gt; if there exists an integer &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2\equiv a\pmod p&lt;/math&gt;.<br /> <br /> Equivalently, we can define the function &lt;math&gt;a \mapsto \genfrac{(}{)}{}{}{a}{p}&lt;/math&gt; as the unique nontrivial multiplicative [[homomorphism]] of &lt;math&gt;\mathbb{F}_p^\times&lt;/math&gt; into &lt;math&gt;\mathbb{R}^\\times&lt;/math&gt;, extended by &lt;math&gt;0 \mapsto 0&lt;/math&gt;.<br /> <br /> == Quadratic Reciprocity Theorem ==<br /> <br /> There are three parts. Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct [[odd integer | odd]] primes. Then the following hold:<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2},&lt;/math&gt;<br /> * &lt;math&gt; \genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2-1)/8},&lt;/math&gt;<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4} .&lt;/math&gt;<br /> This theorem can help us evaluate Legendre symbols, since the following laws also apply:<br /> * If &lt;math&gt;a\equiv b\pmod{p}&lt;/math&gt;, then &lt;math&gt;\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}&lt;/math&gt;.<br /> * &lt;math&gt;\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}&lt;/math&gt;.<br /> <br /> There also exist quadratic reciprocity laws in other [[ring of integers|rings of integers]]. (I'll put that here later if I remember.)<br /> <br /> == Proof ==<br /> <br /> '''Theorem 1.''' Let &lt;math&gt;p&lt;/math&gt; be an odd prime. Then &lt;math&gt;\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2}&lt;/math&gt;.<br /> <br /> ''Proof.'' It suffices to show that &lt;math&gt;(-1)^{(p-1)/2} = 1&lt;/math&gt; if and only if &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;.<br /> <br /> Suppose that &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;. Then &lt;math&gt;k^2 = -1&lt;/math&gt;, for some residue &lt;math&gt;k&lt;/math&gt; mod &lt;math&gt;p&lt;/math&gt;, so<br /> &lt;cmath&gt; (-1)^{(p-1)/2} = (k^2)^{(p-1)/2} = k^{p-1} = 1 = \genfrac{(}{)}{}{}{-1}{p} , &lt;/cmath&gt;<br /> by [[Fermat's Little Theorem]].<br /> <br /> On the other hand, suppose that &lt;math&gt;(-1)^{(p-1)/2} = 1&lt;/math&gt;. Then &lt;math&gt;(p-1)/2&lt;/math&gt; is even, so &lt;math&gt;(p-1)/4&lt;/math&gt; is an integer. Since every nonzero residue mod &lt;math&gt;p&lt;/math&gt; is a root of the polynomial<br /> &lt;cmath&gt; (x^{p-1} - 1 = (x^{(p-1)/2} + 1)(x^{(p-1)/2} - 1) , &lt;/cmath&gt;<br /> and the &lt;math&gt;p-1&lt;/math&gt; nonzero residues cannot all be roots of the polynomial &lt;math&gt;x^{(p-1)/2} - 1&lt;/math&gt;, it follows that for some residue &lt;math&gt;k&lt;/math&gt;,<br /> &lt;cmath&gt; \bigl(k^{(p-1)/2}\bigr)^2 = k^{(p-1)/2} = -1 . &lt;/cmath&gt;<br /> Therefore &lt;math&gt;-1&lt;/math&gt; is a quadratic residue mod &lt;math&gt;p&lt;/math&gt;, as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> Now, let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes, and let &lt;math&gt;K&lt;/math&gt; be the [[splitting field]] of the polynomial &lt;math&gt;x^q - 1&lt;/math&gt; over the finite field &lt;math&gt;\mathbb{F}_p&lt;/math&gt;. Let &lt;math&gt;\zeta&lt;/math&gt; be a primitive &lt;math&gt;q&lt;/math&gt;th root of unity in &lt;math&gt;K&lt;/math&gt;. We define the Gaussian sum<br /> &lt;cmath&gt; \tau_q = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^q . &lt;/cmath&gt;<br /> <br /> '''Lemma.''' &lt;math&gt;\tau_q^2 = q (-1)^{(q-1)/2}&lt;/math&gt;<br /> <br /> ''Proof.'' By definition, we have<br /> &lt;cmath&gt; \tau_q^2 = \sum_a \sum_b \genfrac{(}{)}{}{}{a}{q} \zeta^a \genfrac{(}{)}{}{}{b}{q} \zeta^b = \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} . &lt;/cmath&gt;<br /> Letting &lt;math&gt;c \equiv a^{-1}b \pmod{q}&lt;/math&gt;, we have<br /> &lt;cmath&gt; \begin{align*} \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} &amp;= \sum_{a\neq 0} \sum_c \genfrac{(}{)}{}{}{a^2 c}{q} \zeta^{a+ac} \\<br /> &amp;= \sum_c \sum_{a \neq 0} \genfrac{(}{)}{}{}{c}{q} \bigl( \zeta^{1+c} \bigr)^a \\<br /> &amp;= \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a . \end{align*} &lt;/cmath&gt;<br /> Now, &lt;math&gt;\zeta^{c+1}&lt;/math&gt; is a root of the polynomial<br /> &lt;cmath&gt; P(x) = x^q - 1 = (x-1) \sum_{i=0}^{q-1} x^i, &lt;/cmath&gt;<br /> it follows that for &lt;math&gt;c\neq -1&lt;/math&gt;,<br /> &lt;cmath&gt; \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = -1, &lt;/cmath&gt;<br /> while for &lt;math&gt;c = -1&lt;/math&gt;, we have<br /> &lt;cmath&gt; \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q-1 . &lt;/cmath&gt;<br /> Therefore<br /> &lt;cmath&gt; \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q \genfrac{(}{)}{}{}{-1}{q} - \sum_{c=0}^{q-1}\genfrac{(}{)}{}{}{c}{q} . &lt;/cmath&gt;<br /> But since there are &lt;math&gt;(q-1)/2&lt;/math&gt; nonsquares and &lt;math&gt;(q-1)/2&lt;/math&gt; nonzero square mod &lt;math&gt;q&lt;/math&gt;, it follows that<br /> &lt;cmath&gt; \sum_{c=0}^{q-1} \genfrac{(}{)}{}{}{c}{q} = 0 . &lt;/cmath&gt;<br /> Therefore<br /> &lt;cmath&gt; \tau_q^2 = q \genfrac{(}{)}{}{}{-1}{q} = q (-1)^{(q-1)/2} , &lt;/cmath&gt;<br /> by Theorem 1.<br /> <br /> '''Theorem 2.''' &lt;math&gt;\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}&lt;/math&gt;.<br /> <br /> ''Proof.'' We compute the quantity &lt;math&gt;\tau_q^p&lt;/math&gt; in two different ways.<br /> <br /> We first note that since &lt;math&gt;p=0&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;,<br /> &lt;cmath&gt; \tau_q^p = \biggl( \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^a \biggr)^p = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q}^p \zeta^{ap} = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} . &lt;/cmath&gt;<br /> Since &lt;math&gt;\genfrac{(}{)}{}{}{p}{q}^2 = 1&lt;/math&gt;,<br /> &lt;cmath&gt; \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{p}{q} \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{pa}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{a}{q} \tau_q . &lt;/cmath&gt;<br /> Thus<br /> &lt;cmath&gt; \tau_q^p = \genfrac{(}{)}{}{}{p}{q} \tau_q . &lt;/cmath&gt;<br /> <br /> On the other hand, from the lemma,<br /> &lt;cmath&gt; \tau_q^p = (\tau_q^2)^{(p-1)/2} \cdot \tau_q = \bigl[ q (-1)^{(q-1)/2} \bigr]^{(p-1)/2} \tau_q = q^{(p-1)/2} (-1)^{(p-1)(q-1)/4 \tau_q . &lt;/cmath&gt;<br /> Since &lt;math&gt;q^{(p-1)/2} = \genfrac{(}{)}{}{}{q}{p}&lt;/math&gt;, we then have<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q . &lt;/cmath&gt;<br /> Since &lt;math&gt;\tau_q&lt;/math&gt; is evidently nonzero and<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{q}{p}^2 = 1, &lt;/cmath&gt;<br /> we therefore have<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}, &lt;/cmath&gt;<br /> as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> '''Theorem 3.''' &lt;math&gt;\genfrac{(}{)}{}{}{2}{p} = (-1)^{(p^2 - 1)/8}&lt;/math&gt;.<br /> <br /> ''Proof.'' Let &lt;math&gt;K&lt;/math&gt; be the splitting field of the polynomial<br /> &lt;math&gt;x^8-1&lt;/math&gt; over &lt;math&gt;\mathbb{F}_p&lt;/math&gt;; let &lt;math&gt;\zeta&lt;/math&gt; be a root of the polynomial<br /> &lt;math&gt;x^4+1&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;.<br /> <br /> We note that<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^2 = \zeta^2 + 2 + \zeta^{-2} = 2 + \zeta^{-2} (\zeta^{4} + 1) = 2 . &lt;/cmath&gt;<br /> So<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1}) 2^{(p-1)/2} = (\zeta + \zeta^{-1}) \genfrac{(}{)}{}{}{2}{p}. &lt;/cmath&gt;<br /> <br /> On the other hand, since &lt;math&gt;K&lt;/math&gt; is a field of characteristic &lt;math&gt;p&lt;/math&gt;,<br /> &lt;cmath&gt; (\zeta + \zeta^{-1})^p = \zeta^p + \zeta^{-p} . &lt;/cmath&gt;<br /> Thus<br /> &lt;cmath&gt; \zeta^p + \zeta^{-p} = (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1} \genfrac{(}{)}{}{}{2}{p} . &lt;/cmath&gt;<br /> Now, if &lt;math&gt;p \equiv 4 \pm 1 \pmod{8}&lt;/math&gt;, then<br /> &lt;cmath&gt; \zeta^{p} + \zeta^{-p} = - ( \zeta + \zeta^{-1} ) &lt;/cmath&gt;<br /> and &lt;math&gt;p^2 - 1 \equiv 8 \pmod{16}&lt;/math&gt;, so &lt;math&gt;(-1)^{(p^2-1)/8} = -1&lt;/math&gt;,<br /> and<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{2}{p} = -1 = (-1)^{(p^2 - 1)/8} . &lt;/cmath&gt;<br /> On the other hand, if &lt;math&gt;p \equiv \pm 1 \pmod{8}&lt;/math&gt;, then<br /> &lt;cmath&gt; \zeta^p + \zeta^{-p} = \zeta + \zeta^{-1}, &lt;/cmath&gt;<br /> and &lt;math&gt;p^2 -1 \equiv 0 \pmod{16}&lt;/math&gt;, so<br /> &lt;cmath&gt; \genfrac{(}{)}{}{}{2}{p} = 1 = (-1)^{p^2-1} . &lt;/cmath&gt;<br /> Thus the theorem holds in all cases. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> <br /> == References ==<br /> <br /> * Helmut Koch, ''Number Theory: Algebraic Numbers and Functions,'' American Mathematical Society 2000. ISBN 0-8218-2054-0 begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting begin_of_the_skype_highlighting              0-8218-2054-0      end_of_the_skype_highlighting.<br /> <br /> [[Category:Number theory]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Prime_number&diff=35645 Prime number 2010-08-15T11:52:23Z <p>ZetaX: </p> <hr /> <div>A '''prime number''' (or simply '''prime''') is a [[positive integer]] &lt;math&gt;p&gt;1&lt;/math&gt; whose only positive [[divisor | divisors]] are 1 and itself. <br /> Note that &lt;math&gt;1&lt;/math&gt; is usually defined as being neither prime nor [[composite number|composite]] because it is its only factor among the [[natural number|natural numbers]]. <br /> <br /> It is well-known that there are an infinite number of prime numbers. A standard proof attributed to [[Euclid]] notes that if there are a finite set of prime numbers &lt;math&gt;p_1, p_2, \ldots, p_n&lt;/math&gt;, then the number &lt;math&gt;N = p_1p_2\cdots p_n + 1&lt;/math&gt; is not divisible by any of them, but &lt;math&gt;N&lt;/math&gt; must [[#Importance of Primes|have]] a prime factor, contradiction. <br /> <br /> == Identifying primes ==<br /> {{main|Sieve of Eratosthenes}}<br /> The [[Sieve of Eratosthenes]] is a relatively quick method for generating a list of the prime numbers. It is a method in which the multiples of all known primes are labeled as composites.<br /> <br /> == Importance of Primes ==<br /> According to the [[Fundamental Theorem of Arithmetic]], there is exactly one unique way to factor a [[positive integer]] into a product of primes ([[permutation|permutations]] not withstanding). This unique [[prime factorization]] plays an important role in solving many kinds of [[number theory]] problems.<br /> <br /> == Famous Primes ==<br /> === Fermat Primes ===<br /> <br /> A [[Fermat prime]] is a prime of the form &lt;math&gt;2^n+1&lt;/math&gt;. It can easily be shown that for such a number to be prime, ''n'' must not have any odd divisor larger than 1 and so must be a power of 2. Therefore all Fermat primes have the form &lt;math&gt;2^{2^n}+1&lt;/math&gt;. [[Fermat]] checked the cases &lt;math&gt;n=0,1,2,3,4&lt;/math&gt; and conjectured that all such numbers were prime. However, &lt;math&gt;2^{2^5}+1=641\cdot 6700417&lt;/math&gt;. In fact, no other Fermat primes have been found.<br /> <br /> There is an easy proof of the infinitude of primes based on Fermat numbers (numbers of the form &lt;math&gt;2^{2^n} + 1&lt;/math&gt;). One simply shows that any two Fermat numbers are [[relatively prime]].<br /> <br /> === Mersenne Primes ===<br /> <br /> A [[Mersenne prime]] is a prime of the form &lt;math&gt;2^n-1&lt;/math&gt;. For such a number to be prime, ''n'' must itself be prime. Compared to other numbers of comparable sizes, Mersenne numbers are easy to check for primality because of the [[Lucas-Lehmer test]].<br /> <br /> === Twin Primes ===<br /> Two primes that differ by exactly 2 are known as [[twin primes]]. The following are the smallest examples:&lt;br&gt;<br /> 3, 5&lt;br&gt;<br /> 5, 7&lt;br&gt;<br /> 11, 13&lt;br&gt;<br /> 17, 19&lt;br&gt;<br /> 29, 31&lt;br&gt;<br /> 41, 43&lt;br&gt;<br /> <br /> It is not known whether or not there are infinitely many pairs of twin primes. This is known as the [[Twin Prime Conjecture]].<br /> <br /> === Gaussian Primes ===<br /> <br /> A Gaussian prime is a prime that extends the idea of the traditional prime to the [[Gaussian integer|Gaussian integers]]. One can define this term for any [[ring]], especially number rings.<br /> <br /> == Advanced Definition ==<br /> When the need arises to include negative divisors, a '''prime''' is defined as an integer p whose only divisors are 1, -1, p, and -p. More generally, if ''R'' is an integral domain, then a nonzero element ''p'' of ''R'' is a '''prime''' if whenever we write &lt;math&gt;p=ab&lt;/math&gt; with &lt;math&gt;a,b\in R&lt;/math&gt;, then exactly one of ''a'' and ''b'' is a unit.<br /> <br /> ==See also==<br /> *[[Composite]]<br /> *[[Relatively prime]]<br /> *[[Integer]]<br /> <br /> [[Category:Definition]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Prime_number&diff=35644 Prime number 2010-08-15T11:50:27Z <p>ZetaX: </p> <hr /> <div>A '''prime number''' (or simply '''prime''') is a [[positive integer]] &lt;math&gt;p&gt;1&lt;/math&gt; whose only positive [[divisor | divisors]] are 1 and itself. <br /> Note that &lt;math&gt;1&lt;/math&gt; is usually defined as being neither prime nor [[composite number|composite]] because it is its only factor among the [[natural number|natural numbers]]. <br /> <br /> It is well-known that there are an infinite number of prime numbers. A standard proof attributed to [[Euclid]] notes that if there are a finite set of prime numbers &lt;math&gt;p_1, p_2, \ldots, p_n&lt;/math&gt;, then the number &lt;math&gt;N = p_1p_2\cdots p_n + 1&lt;/math&gt; is not divisible by any of them, but &lt;math&gt;N&lt;/math&gt; must [[#Importance of Primes|have]] a prime factor, contradiction. <br /> <br /> == Identifying primes ==<br /> {{main|Sieve of Eratosthenes}}<br /> The [[Sieve of Eratosthenes]] is a relatively quick method for generating a list of the prime numbers. It is a method in which the multiples of all known primes are labeled as composites.<br /> <br /> == Importance of Primes ==<br /> According to the [[Fundamental Theorem of Arithmetic]], there is exactly one unique way to factor a [[positive integer]] into a product of primes ([[permutation|permutations]] not withstanding). This unique [[prime factorization]] plays an important role in solving many kinds of [[number theory]] problems.<br /> <br /> == Famous Primes ==<br /> === Fermat Primes ===<br /> <br /> A [[Fermat prime]] is a prime of the form &lt;math&gt;2^n+1&lt;/math&gt;. It can easily be shown that for such a number to be prime, ''n'' must not have any odd divisor larger than 1 and so must be a power of 2. Therefore all Fermat primes have the form &lt;math&gt;2^{2^n}+1&lt;/math&gt;. [[Fermat]] checked the cases &lt;math&gt;n=0,1,2,3,4&lt;/math&gt; and conjectured that all such numbers were prime. However, &lt;math&gt;2^{2^5}+1=641\cdot 6700417&lt;/math&gt;. In fact, no other Fermat primes have been found.<br /> <br /> There is an easy proof of the infinitude of primes based on Fermat numbers (numbers of the form &lt;math&gt;2^{2^n} + 1&lt;/math&gt;). One simply shows that any two Fermat numbers are [[relatively prime]].<br /> <br /> === Mersenne Primes ===<br /> <br /> A [[Mersenne prime]] is a prime of the form &lt;math&gt;2^n-1&lt;/math&gt;. For such a number to be prime, ''n'' must itself be prime. Compared to other numbers of comparable sizes, Mersenne numbers are easy to check for primality because of the [[Lucas-Lehmer test]].<br /> <br /> === Twin Primes ===<br /> Two primes that differ by exactly 2 are known as [[twin primes]]. The following are the smallest examples:&lt;br&gt;<br /> 3, 5&lt;br&gt;<br /> 5, 7&lt;br&gt;<br /> 11, 13&lt;br&gt;<br /> 17, 19&lt;br&gt;<br /> 29, 31&lt;br&gt;<br /> 41, 43&lt;br&gt;<br /> <br /> It is not known whether or not there are infinitely many pairs of twin primes. This is known as the [[Twin Prime Conjecture]].<br /> <br /> === Gaussian Primes ===<br /> <br /> A Gaussian prime is a prime that extends the idea of the traditional prime to the [[Gaussian integer|Gaussian integers]]. One can define this term for any [[ring]], especially number rings.<br /> <br /> == Advanced Definition ==<br /> When the need arises to include negative divisors, a '''prime''' is defined as an integer p whose only divisors are 1, -1, p, and -p. More generally, if ''R'' is a unique factorization domain, then an element ''p'' of ''R'' is a '''prime''' if whenever we write &lt;math&gt;p=ab&lt;/math&gt; with &lt;math&gt;a,b\in R&lt;/math&gt;, then exactly one of ''a'' and ''b'' is a unit.<br /> <br /> ==See also==<br /> *[[Composite]]<br /> *[[Relatively prime]]<br /> *[[Integer]]<br /> <br /> [[Category:Definition]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Talk:Euler%27s_totient_function&diff=22885 Talk:Euler's totient function 2008-01-30T15:58:27Z <p>ZetaX: </p> <hr /> <div>Some motivation and derivation of the formula would make this article more useful.--[[User:MCrawford|MCrawford]] 13:18, 20 June 2006 (EDT)<br /> <br /> I changed the part under &quot;Notation&quot;. It surely is not best as it is now, but the old one was surely wrong:<br /> <br /> - &lt;math&gt;\phi&lt;/math&gt; is _not_ a capital letter &quot;Phi&quot;, but still a lower case character; compare: &lt;math&gt;\Phi&lt;/math&gt; to &lt;math&gt;\phi&lt;/math&gt;.<br /> <br /> - &lt;math&gt;\varphi&lt;/math&gt; is about as widely spread as &lt;math&gt;\phi&lt;/math&gt;, e.g. the normal Wikipedia and more than half of my books prefer &lt;math&gt;\varphi&lt;/math&gt;.<br /> --[[User:ZetaX|ZetaX]] 10:58, 30 January 2008 (EST)</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=22884 Euler's totient function 2008-01-30T15:54:19Z <p>ZetaX: </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 &lt;math&gt; n &lt;/math&gt; that share a common factor with it). There are &lt;math&gt; p_1^{e_1-1}p_2^{e_2}\cdots p_m^{e_m} &lt;/math&gt; numbers less than &lt;math&gt; n &lt;/math&gt; that are divisible by &lt;math&gt; p_1 &lt;/math&gt;. If we do the same for each &lt;math&gt; p_k &lt;/math&gt; and add these up, we get <br /> <br /> &lt;center&gt;&lt;math&gt; p_1^{e_1-1}p_2^{e_2}\cdots p_m{e_m} + p_1^{e_1}p_2^{e_2-1}\cdots p_m^{e_m} + \cdots + p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m - 1}.&lt;/math&gt;&lt;/center&gt;<br /> <br /> We can factor out, though:<br /> <br /> &lt;center&gt;&lt;math&gt; p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1+p_2+\cdots + p_m).&lt;/math&gt;&lt;/center&gt;<br /> <br /> But we are obviously overcounting. We then subtract out those divisible by two of the &lt;math&gt; p_k &lt;/math&gt;. We continue with this PIE argument to figure out that the number of elements in the complement of what we want is<br /> <br /> &lt;center&gt;&lt;math&gt;p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}[(p_1+p_2+\cdots+p_m)-(p_1p_2+p_1p_3+\cdots+p_{m-1}p_m)+\cdots+(-1)^{m+1}(p_1p_2\cdots p_m)]&lt;/math&gt;&lt;/center&gt;<br /> <br /> which we can factor further as<br /> <br /> &lt;center&gt;&lt;math&gt;p_1^{e_1-1}p_2^{e_2-1}\cdots p_m^{e_m-1}(p_1-1)(p_2-1)\cdots(p_m-1).&lt;/math&gt;&lt;/center&gt;<br /> <br /> Making one small adjustment, we write this as<br /> <br /> &lt;center&gt;&lt;math&gt; \phi(n) = n\left(1-\frac 1{p_1}\right)\left(1-\frac 1{p_2}\right)\cdots\left(1-\frac 1{p_m}\right).&lt;/math&gt;&lt;/center&gt;<br /> <br /> Given the general [[prime factorization]] of &lt;math&gt;{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}&lt;/math&gt;, one can compute &lt;math&gt;\phi(n)&lt;/math&gt; using the formula &lt;cmath&gt;\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_m}\right)&lt;/cmath&gt;<br /> <br /> == Identities ==<br /> <br /> For [[prime]] p, &lt;math&gt;\phi(p)=p-1&lt;/math&gt;, because all numbers less than &lt;math&gt;{p}&lt;/math&gt; are relatively prime to it.<br /> <br /> For relatively prime &lt;math&gt;{a}, {b}&lt;/math&gt;, &lt;math&gt; \phi{(a)}\phi{(b)} = \phi{(ab)} &lt;/math&gt;.<br /> <br /> In fact, we also have for any &lt;math&gt;{a}, {b}&lt;/math&gt; that &lt;math&gt;\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})&lt;/math&gt;.<br /> <br /> For any &lt;math&gt;n&lt;/math&gt;, we have &lt;math&gt;\sum_{d|n}\phi(d)=n&lt;/math&gt; where the sum is taken over all divisors d of &lt;math&gt; n &lt;/math&gt;.<br /> <br /> ==Notation==<br /> Often instead of &lt;math&gt;\phi&lt;/math&gt;, also &lt;math&gt;\varphi&lt;/math&gt; is used.<br /> <br /> == See also ==<br /> <br /> * [[Number theory]]<br /> * [[Prime]]<br /> * [[Euler's Totient Theorem]]<br /> <br /> [[Category:Functions]]<br /> [[Category:Number Theory]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Dedekind_domain&diff=20925 Dedekind domain 2007-12-10T18:33:10Z <p>ZetaX: </p> <hr /> <div>A '''Dedekind domain''' is a [[commutative]] [[integral domain]] &lt;math&gt;R&lt;/math&gt; satisfying the following properties:<br /> <br /> * &lt;math&gt;R&lt;/math&gt; is a [[noetherian]] [[ring]].<br /> * Every [[prime ideal]] of &lt;math&gt;R&lt;/math&gt; is a [[maximal ideal]].<br /> * &lt;math&gt;R&lt;/math&gt; is [[integral closure|integrally closed]] in its [[field of fractions]].<br /> <br /> Dedekind domains are very important in [[abstract algebra]] and [[number theory]]. For example, the [[ring of integers]] of any [[number field]] is a Dedekind domain.<br /> <br /> There are several very nice properties of Dedekind domains:<br /> <br /> * Dedekind domains have unique prime factorizations of [[ideal]]s (but not necessarily of elements).<br /> * Ideals are invertible if we extend to [[fractional ideal]]s. Let &lt;math&gt;R&lt;/math&gt; be a Dedekind domain with field of fractions &lt;math&gt;K&lt;/math&gt;, and let &lt;math&gt;I&lt;/math&gt; be any nonzero ideal of &lt;math&gt;R&lt;/math&gt;. Then set &lt;math&gt;I^{-1}=\{a\in K\mid aI\subseteq R\}&lt;/math&gt;. We call an ideal &lt;math&gt;I&lt;/math&gt; '''invertible''' if &lt;math&gt;II^{-1}=R&lt;/math&gt;. (Note that this is always a subset, but it is not always equal unless we are in a Dedekind domain.) In fact, the converse is true as well: if all nonzero ideals are invertible, then &lt;math&gt;R&lt;/math&gt; is a Dedekind domain. This is sometimes used as a definition.<br /> <br /> There are also various properties of [[homological algebra|homological]] importance that Dedekind domains satisfy.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Ring_of_integers&diff=20924 Ring of integers 2007-12-10T18:30:43Z <p>ZetaX: </p> <hr /> <div>Let &lt;math&gt;K&lt;/math&gt; be a finite [[algebraic]] [[field extension]] of &lt;math&gt;\mathbb{Q}&lt;/math&gt;. Then the [[integral closure]] of &lt;math&gt;{\mathbb{Z}}&lt;/math&gt; in &lt;math&gt;K&lt;/math&gt;, which we denote by &lt;math&gt;\mathfrak{o}_K&lt;/math&gt;, is called the '''ring of integers''' of &lt;math&gt;K&lt;/math&gt;. Rings of integers are always [[Dedekind domain]]s with finite [[class number]]s.<br /> <br /> {{stub}}</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Perfect_square&diff=17037 Perfect square 2007-09-27T18:39:51Z <p>ZetaX: </p> <hr /> <div>An [[integer]] &lt;math&gt;n&lt;/math&gt; is said to be a '''perfect square''' if there is an integer &lt;math&gt;m&lt;/math&gt; so that &lt;math&gt;m^2=n&lt;/math&gt;. The first few perfect squares are 0, 1, 4, 9, 16, 25, 36.<br /> <br /> The sum of the first &lt;math&gt;n&lt;/math&gt; square numbers (not including 0) is &lt;math&gt;\frac{n(n+1)(2n+1)}{6}&lt;/math&gt;<br /> <br /> An integer &lt;math&gt;n&lt;/math&gt; is a perfect square iff it is a [[quadratic residue]] [[modulo]] all but finitely primes.<br /> <br /> == Perfect Square Trinomials ==<br /> <br /> Another type of perfect square is an equation that is a perfect square trinomial. Take for example <br /> <br /> &lt;math&gt;(x+a)^2=x^2+2xa+a^2&lt;/math&gt;.<br /> <br /> Perfect square trinomials are a type of quadratic equation that have 3 terms and contain 1 unique root.<br /> <br /> For any quadratic equation in the form &lt;math&gt;ax^2+bx+c&lt;/math&gt;, it is a perfect square trinomial [[iff]] &lt;math&gt;b=a\sqrt{c}&lt;/math&gt;.<br /> <br /> <br /> ==See also ==<br /> * [[Perfect cube]]<br /> * [[Perfect power]]<br /> {{stub}}</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Talk:Modular_arithmetic/Intermediate&diff=17036 Talk:Modular arithmetic/Intermediate 2007-09-27T18:34:48Z <p>ZetaX: New section: Two suggestions</p> <hr /> <div>The following material can be reworded and incorporated into this article:--[[User:MCrawford|MCrawford]] 18:54, 30 June 2006 (EDT)<br /> <br /> ==== A General Algorithm ====<br /> <br /> In the example above, we were fortunate to find a power of &lt;math&gt;7&lt;/math&gt; -- namely, &lt;math&gt;7^4&lt;/math&gt; -- that is congruent to &lt;math&gt;1&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt;. What if we aren't this lucky? Suppose we want to solve the following problem:<br /> <br /> ''What are the tens and units digits of &lt;math&gt;13^{404}&lt;/math&gt;?''<br /> <br /> Again, we will solve this problem by computing &lt;math&gt;13^{404}&lt;/math&gt; modulo &lt;math&gt;100&lt;/math&gt;. The first few powers of &lt;math&gt;13&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt; are<br /> <br /> &lt;math&gt;13, 69, 97, 61, 93, \ldots&lt;/math&gt;<br /> <br /> This time, no pattern jumps out at us. Is there a way we can find the &lt;math&gt;404^{th}&lt;/math&gt; power of &lt;math&gt;13&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt; without taking this list all the way out to the &lt;math&gt;404^{th}&lt;/math&gt; term -- or even without patiently waiting for the list to yield a pattern?<br /> <br /> Suppose we condense the list we started above; and instead of writing down all powers of &lt;math&gt;13&lt;/math&gt; mod &lt;math&gt;100&lt;/math&gt;, we write only the powers &lt;math&gt;13^k&lt;/math&gt;, where &lt;math&gt;k&lt;/math&gt; is a power of &lt;math&gt;2&lt;/math&gt;. We have the following (all congruences are modulo &lt;math&gt;100&lt;/math&gt;):<br /> <br /> &lt;math&gt;\displaystyle 13^1 = 13&lt;/math&gt;<br /> <br /> &lt;math&gt;13^2 \equiv 69&lt;/math&gt;<br /> <br /> &lt;math&gt;13^4 \equiv 69^2 \equiv 61&lt;/math&gt;<br /> <br /> &lt;math&gt;13^8 \equiv 61^2 \equiv 21&lt;/math&gt;<br /> <br /> &lt;math&gt;13^{16} \equiv 21^2 \equiv 41&lt;/math&gt;<br /> <br /> &lt;math&gt;13^{32} \equiv 41^2 \equiv 81&lt;/math&gt;<br /> <br /> &lt;math&gt;13^{64} \equiv 81^2 \equiv 61&lt;/math&gt;<br /> <br /> &lt;math&gt;13^{128} \equiv 61^2 \equiv 21&lt;/math&gt;<br /> <br /> &lt;math&gt;13^{256} \equiv 21^2 \equiv 41&lt;/math&gt;<br /> <br /> (Observe that this process yields a pattern of its own, if we carry it out far enough!)<br /> <br /> Now, observe that, like any positive integer, &lt;math&gt;404&lt;/math&gt; can be written as a sum of powers of two:<br /> <br /> &lt;math&gt;404 = 256 + 128 + 16 + 4&lt;/math&gt;<br /> <br /> We can now use this powers-of-two expansion to compute &lt;math&gt;\overline{13}^{404}&lt;/math&gt;:<br /> <br /> &lt;math&gt;13^{404} = 13^{256} \cdot 13^{128} \cdot 13^{16} \cdot 13^4 \equiv 41 \cdot 21 \cdot 41 \cdot 61 \equiv 61.&lt;/math&gt;<br /> <br /> So the tens and units digits of &lt;math&gt;13^{404}&lt;/math&gt; are &lt;math&gt;6&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;, respectively.<br /> <br /> We can use this method to compute &lt;math&gt;M^e&lt;/math&gt; modulo &lt;math&gt;n&lt;/math&gt;, for any integers &lt;math&gt;M&lt;/math&gt; and &lt;math&gt;e&lt;/math&gt;, with &lt;math&gt;e &gt; 0&lt;/math&gt;. The beauty of this algorithm is that the process takes, at most, approximately &lt;math&gt;2 \log_2 e&lt;/math&gt; steps -- at most &lt;math&gt;\log_2 e&lt;/math&gt; steps to compute the values &lt;math&gt;M^k&lt;/math&gt; modulo &lt;math&gt;n&lt;/math&gt; for &lt;math&gt;k&lt;/math&gt; a power of two less than &lt;math&gt;e&lt;/math&gt;, and at most &lt;math&gt;\log_2 e&lt;/math&gt; steps to multiply the appropriate powers of &lt;math&gt;M&lt;/math&gt; according to the binary representation of &lt;math&gt;e&lt;/math&gt;.<br /> <br /> This method can be further refined using [[Euler's Totient Theorem]].<br /> <br /> == Two suggestions ==<br /> <br /> Why is &lt;math&gt;n&gt;0&lt;/math&gt; assumed here, it's never needed. It's in general better to neglect this restriction after one has mastered the first steps (and as this is Intermediate, I would assume this to be true).<br /> <br /> And I'm still strongly against using &lt;math&gt;\mathbb Z_n&lt;/math&gt; instead of &lt;math&gt;\mathbb Z / n \mathbb Z&lt;/math&gt;, the first one is already used for &lt;math&gt;n&lt;/math&gt;-adic integers and rarely seen in non-olympiad books.<br /> <br /> But as both is some kind of disputed, I didnÄt edit it untill now.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=AoPS_Wiki:AoPS-Mathlinks_Rules_and_Tips&diff=10179 AoPS Wiki:AoPS-Mathlinks Rules and Tips 2006-09-27T14:03:47Z <p>ZetaX: </p> <hr /> <div>== MATHEMATICAL DISCUSSION ==<br /> <br /> MathLinks is a community for discussing mathematical problems on various levels. You can share problems with others, solve others' problems, create your own problems and post them, and more.<br /> <br /> == Posting problems on AoPS/MathLinks ==<br /> <br /> === Posting problems ===<br /> <br /> If you want to post a new problem, post it in a new topic. If you have several problems to post, post every problem in a new topic.<br /> <br /> Discussing different problems in one topic leads to confusion.<br /> <br /> Please double check your problem for mistakes. A simple typo in a formula can make a problem incomprehensible.<br /> <br /> Please also give your topic a useful name. Names should describe something. It is better to write names like &quot;prove concurrency in a right-angled triangle&quot;, &quot;a^4+b^4+c^4\geq a^3b+b^3c+c^3a&quot;, &quot;a^2+b^2=20c^2&quot;, &quot;f(xf(y))f(y)=yf(xy)&quot; than the following ones: &quot;hard geometry&quot;, &quot;please help me!!&quot;, &quot;what to do with this one?&quot;, &quot;don't know how to solve it&quot;. <br /> <br /> === Where to post ===<br /> <br /> There are different forums to post problems in.<br /> <br /> If you have a problem, you have to choose the right forum according to its level:<br /> <br /> *[http://www.mathlinks.ro/Forum/index.php?f=149 Getting Started] is for ''insert stuff here, but please make it understandable to non-Americans.''<br /> *[http://www.mathlinks.ro/Forum/index.php?f=150 Intermediate Topics] is for ''insert stuff here, but please make it understandable to non-Americans.''<br /> *[http://www.mathlinks.ro/Forum/index.php?f=151 Pre-Olympiad] is for problems slightly under the olympiad level and for very easy olympiad problems.<br /> *[http://www.mathlinks.ro/Forum/index.php?f=217 Olympiad Section] is for olympiad-level problems. <br /> **Olympiad-level means the level of [http://www.mathlinks.ro/Forum/resources.php?c=1&amp;cid=16 the IMO], of [http://www.mathlinks.ro/Forum/resources.php?c=1&amp;cid=17 IMO shortlists], of [http://www.mathlinks.ro/Forum/resources.php?c=182&amp;cid=27 the USAMO] or [http://www.mathlinks.ro/Forum/resources.php?c=1&amp;cid=60 the Baltic Way mathematical competition].<br /> *[http://www.mathlinks.ro/Forum/index.php?f=218 College Playground] is a special forum for problems that require preknowledge which is usually not given in schools - for instance, [[linear algebra]], [[calculus]], [[topology]].<br /> <br /> The [http://www.mathlinks.ro/Forum/index.php?f=217 Olympiad Section] is subdivided into subforums: <br /> * [http://www.mathlinks.ro/Forum/index.php?f=3 Algebra] <br /> * [http://www.mathlinks.ro/Forum/index.php?f=5 Combinatorics] <br /> * [http://www.mathlinks.ro/Forum/index.php?f=4 Geometry]<br /> * [http://www.mathlinks.ro/Forum/index.php?f=32 Inequalities]<br /> * [http://www.mathlinks.ro/Forum/index.php?f=6 Number Theory] <br /> <br /> Decide which topic your problem belongs to, and post it into the respective subforum.<br /> <br /> Each of these subforums is subdivided into subsubforums:<br /> <br /> * &lt;u&gt;Unsolved Problems:&lt;/u&gt; Post your problem here if you don't know its solution and you are searching for it, but you know there is a solution (e. g. because the problem was given at an olympiad).<br /> * &lt;u&gt;Proposed &amp; Own Problems:&lt;/u&gt; Post your problem here if you know the solution and you want to share the problem with others.<br /> * &lt;u&gt;Open Questions:&lt;/u&gt; Post your problem here if it is a conjecture, i. e. you don't have its solution and you don't even know whether it has ever been solved.<br /> * &lt;u&gt;Solved Problems:&lt;/u&gt; This is the archive for former &quot;Unsolved&quot; problems which were then solved. Don't post new problems here, it's an archive!<br /> * &lt;u&gt;Theorems and Formulas:&lt;/u&gt; This is for important and useful theorems.<br /> <br /> === How to post ===<br /> <br /> All questions and answers should be:<br /> * correct: no typos, no errors, check at least twice what you post.<br /> * readable: use LaTeX (see below), don't quote whole pages just to make a one-line answer.<br /> * it's interesting and/or helpful for someone: a reply that just contains &quot;it's easy&quot; or &quot;I solved it&quot; interests noone<br /> * it's appropriate and ontopic: be nice, don't shout or insult, post only stuff that fits into the topic<br /> <br /> === Posting solutions ===<br /> <br /> Wherever you see a problem on the forum, you can post a solution to it if you want.<br /> <br /> The solution needs not be 100% detailed, but it must be understandable. Posts consisting only of words like &quot;The problem is easy&quot; or &quot;Cauchy-Schwarz solves it&quot; have no value and will be deleted.<br /> <br /> === Other cases of posting ===<br /> <br /> You are not limited to posting and solving problems. You can write whatever you want, assumed that it is useful and relevant to the forum. For instance, you can generalize problems, point out mistakes in others' proofs, ask questions about others' solutions, simplify others' solutions etc.. But note that the mathematical sections of AoPS/MathLinks are for mathematical discussion only. For non-mathematical discussions, there is the [http://www.mathlinks.ro/Forum/index.php?f=138 Round Table], the [http://www.mathlinks.ro/Forum/index.php?f=139 Games &amp; Fun Factory] and some more. Non-mathematical discussions in mathematical sections of AoPS/MathLinks can be considered offtopic and removed.<br /> <br /> === Running competitions and homework ===<br /> <br /> This is obvious, but let's strike it here too: Don't post problems from '''running''' homework competitions! You are supposed to solve them on your own, so making others solve them for you is cheating!<br /> <br /> If you post school or university homework problems, please indicate that your problems are homework. In most cases, you will get no complete solutions, but hints and other help.<br /> <br /> === Using LaTeX ===<br /> <br /> [[LaTeX]] makes it possible to include formulas in your posts. For instance, by writing &lt;pre&gt;&lt;nowiki&gt;$a^2 + a^3b$&lt;/nowiki&gt;&lt;/pre&gt; you get &lt;math&gt;a^{2}+a^{3}b&lt;/math&gt;, and by writing &lt;pre&gt;&lt;nowiki&gt;$\frac{a}{b} + 2! = 3^{10}$&lt;/nowiki&gt;&lt;/pre&gt; you get &lt;math&gt;\frac{a}{b}+2! = 3^{10}&lt;/math&gt;. Learning LaTeX is very easy by [http://www.mathlinks.ro/Forum/viewtopic.php?t=5261 this short tutorial] and by testing it out on the forum. Testing can be done in the [http://www.mathlinks.ro/Forum/index.php?f=224 Test Forum].<br /> <br /> === Searching on the forum ===<br /> <br /> Before you post a new problem, you should ask yourself whether this problem has already been discussed on AoPS/MathLinks. You can find this out using two functions of the forum:<br /> <br /> [http://www.mathlinks.ro/Forum/search.php The Search function] helps you find topics in the forum by some keywords. For instance, if your problem is from the USAMO 2002, you can type &quot;USAMO 2002&quot; into the search field. If your problem is about a triangle, its incircle and some altitudes, you can try typing &quot;triangle incircle altitude*&quot; into the search field (the * in &quot;altitude*&quot; is there to find both &quot;altitude&quot; and &quot;altitudes&quot;). You can also restrict the search to some subforums if necessary, so if you look for a Number Theory problem, try restricting the search to the Number Theory subforum if at first there were too many results.<br /> <br /> [http://www.mathlinks.ro/Forum/resources.php The Resources section] contains lists of problems of several olympiads. If you know what competition your problem is from, you can look up this competition in the Resources section. If you find your problem there, click on the problem number on the left of the page, and you get a thread with this problem.<br /> <br /> You are not supposed to spend half an hour searching for your problem on AoPS/MathLinks, but it is helpful if you try it at least once, better twice.<br /> <br /> === Naming your topic ===<br /> <br /> Topic naming<br /> In creating a new topic, you have to write a name of it, under all others will see it before they will click on it and see your problem. It is better to write names like &quot;prove concurrency&quot;, &quot;a^4+b^4+c^4\geq a^3b+b^3c+c^3a&quot;, &quot;a^2+b^2=20c^2&quot;, &quot;f(xf(y))f(y)=yf(xy)&quot; than the following ones: &quot;hard geometry&quot;, &quot;please help me!!&quot;, &quot;what to do with this one?&quot;, &quot;don't know how to solve it&quot;. Describe very briefly and concisely the problem.<br /> <br /> == See also ==<br /> * [[Main Page]]<br /> <br /> [[Category:Tutorials]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Talk:Quadratic_residues&diff=5191 Talk:Quadratic residues 2006-06-29T00:06:27Z <p>ZetaX: </p> <hr /> <div>I'm sure someone wants to write out all the fun properties of Legendre symbols. It just happens not to be me right now. -- ComplexZeta<br /> <br /> Is it any number n, or any integer n? --- cosinator<br /> <br /> Where? --[[User:ComplexZeta|ComplexZeta]] 11:07, 27 June 2006 (EDT)<br /> <br /> In the introduction it says 'We say that a is a quadratic residue modulo m if there is some number n so that n^2 − a is divisible by m.'<br /> If it were any number, I would think that any a could be a quadratic residue modulo m<br /> <br /> Thanks for clarifying -Cosinator<br /> <br /> ''Whereas the above are properties of the Legendre symbol, they still hold for any odd integers p and q when using the Jacobi symbol defined below''.<br /> Hmmm... The quadratic reciprocity law clearly fails (at least in the form as written for primes) if &lt;math&gt;\gcd(m,n)&gt;1&lt;/math&gt;. So some correction is needed. My knowledge of number theory really needs some refreshment, so could someone else write the correct statement here? --[[User:Fedja|Fedja]] 14:34, 28 June 2006 (EDT)<br /> <br /> Yes, coprime was missing.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Quadratic_residues&diff=5190 Quadratic residues 2006-06-29T00:05:44Z <p>ZetaX: /* Quadratic Reciprocity */</p> <hr /> <div>Let &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; be [[integer]]s, with &lt;math&gt;m\neq 0&lt;/math&gt;. We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' [[modulo]] &lt;math&gt;m&lt;/math&gt; if there is some integer &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2-a&lt;/math&gt; is [[divisible]] by &lt;math&gt;m&lt;/math&gt;.<br /> <br /> == Legendre Symbol ==<br /> <br /> Determining whether &lt;math&gt;a&lt;/math&gt; is a quadratic residue modulo &lt;math&gt;m&lt;/math&gt; is easiest if &lt;math&gt;m=p&lt;/math&gt; is a [[prime number|prime]]. In this case we write &lt;math&gt;\left(\frac{a}{p}\right)=\begin{cases} 0 &amp; \mathrm{if }\ p\mid a, \\ 1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ residue\ modulo\ }\ p, \\ -1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ nonresidue\ modulo\ }\ p. \end{cases}&lt;/math&gt; <br /> <br /> The symbol &lt;math&gt;\left(\frac{a}{p}\right)&lt;/math&gt; is called the [[Legendre symbol]].<br /> <br /> == Quadratic Reciprocity ==<br /> <br /> Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes. Then &lt;math&gt;\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}&lt;/math&gt;. This is known as the [[Quadratic Reciprocity Theorem]].<br /> Whereas the above are properties of the Legendre symbol, they still hold for any odd coprime integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; when using the Jacobi symbol defined below.<br /> <br /> == Additional properties ==<br /> <br /> We have for any odd prime &lt;math&gt;p&lt;/math&gt; also the following rules:<br /> <br /> Multiplicaticity: &lt;math&gt;\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)&lt;/math&gt;<br /> <br /> Euler's criterion: &lt;math&gt;\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p&lt;/math&gt;<br /> <br /> First supplementary rule: &lt;math&gt;\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4&lt;/math&gt;<br /> <br /> Second supplementary rule: &lt;math&gt;\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8&lt;/math&gt;<br /> <br /> It's also useful not to forget that the symbols are only properties &lt;math&gt;\mod p&lt;/math&gt;, so &lt;math&gt;a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) &lt;/math&gt;<br /> <br /> == Jacobi Symbol ==<br /> <br /> Now suppose that &lt;math&gt;m&lt;/math&gt; is odd, and let &lt;math&gt;m=p_1^{e_1}\cdots p_n^{e_n}&lt;/math&gt;. Then we write &lt;math&gt;\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}&lt;/math&gt;. This symbol is called the [[Jacobi symbol]].<br /> All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; instead.<br /> <br /> Note that &lt;math&gt;\left(\frac{a}{m}\right)=1&lt;/math&gt; does not mean that &lt;math&gt;a&lt;/math&gt; is a quadratic residue &lt;math&gt;\mod m&lt;/math&gt; (but is necassary for it to be).<br /> <br /> == Calculation and examples ==<br /> <br /> With the rules and properties already mentioned it's eays to calculate Jacobi symbols. Since they are for primes &lt;math&gt;p&lt;/math&gt; identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue &lt;math&gt;\mod p&lt;/math&gt; or not.<br /> <br /> Example:<br /> <br /> &lt;math&gt;\left(\frac{12345}{13337}\right) =&lt;/math&gt;<br /> <br /> &lt;math&gt;=\left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right)=&lt;/math&gt;<br /> <br /> &lt;math&gt;= 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=&lt;/math&gt;<br /> <br /> &lt;math&gt;=1&lt;/math&gt;<br /> <br /> Thus we know that &lt;math&gt;12345&lt;/math&gt; is a quadratic residue [[modulo]] the prime &lt;math&gt;13337&lt;/math&gt;. Indeed: &lt;math&gt;2425^2 \equiv 12345 \mod 13337&lt;/math&gt;<br /> <br /> In a more general manner, one for example also gets:<br /> <br /> &lt;math&gt;\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-2)^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-2}{p}\right)=1 \iff p \equiv 1,3 \mod 8&lt;/math&gt;.<br /> <br /> &lt;math&gt;\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)&lt;/math&gt;, so &lt;math&gt;\left(\frac{3}{p}\right)=1 \iff p \equiv \pm 1 \mod 12&lt;/math&gt;.<br /> <br /> &lt;math&gt;\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right)&lt;/math&gt;, so &lt;math&gt;\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \mod 3&lt;/math&gt;.<br /> <br /> == The general case ==<br /> <br /> In general, to determine whether &lt;math&gt;a&lt;/math&gt; is a quadratic residue modulo &lt;math&gt;n&lt;/math&gt; one has to check whether &lt;math&gt;a&lt;/math&gt; is a quadratic residue modulo every odd prime &lt;math&gt;p&lt;/math&gt; dividing &lt;math&gt;n&lt;/math&gt;. This is enough if &lt;math&gt;n&lt;/math&gt; is odd or &lt;math&gt;n=2m&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; is odd. if &lt;math&gt;n=4m&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; is odd, one has also to check that &lt;math&gt;a\equiv 0\mathrm{\ or\ }1\mod 4&lt;/math&gt;. Finally, if &lt;math&gt;n&lt;/math&gt; is divisible by &lt;math&gt;8&lt;/math&gt;, one has also to check that &lt;math&gt;a\equiv 0,1,\mathrm{\ or\ }4\mod 8&lt;/math&gt;.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Quadratic_residues&diff=4913 Quadratic residues 2006-06-27T11:50:47Z <p>ZetaX: </p> <hr /> <div>Let &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; be [[integer]]s, with &lt;math&gt;m\neq 0&lt;/math&gt;. We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' [[modulo]] &lt;math&gt;m&lt;/math&gt; if there is some number &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2-a&lt;/math&gt; is [[divisible]] by &lt;math&gt;m&lt;/math&gt;.<br /> <br /> == Legendre Symbol ==<br /> <br /> Determining whether &lt;math&gt;a&lt;/math&gt; is a quadratic residue modulo &lt;math&gt;m&lt;/math&gt; is easiest if &lt;math&gt;m=p&lt;/math&gt; is a [[prime number|prime]]. In this case we write &lt;math&gt;\left(\frac{a}{p}\right)=\begin{cases} 0 &amp; \mathrm{if }\ p\mid a, \\ 1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ residue\ modulo\ }\ p, \\ -1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ nonresidue\ modulo\ }\ p. \end{cases}&lt;/math&gt; <br /> <br /> The symbol &lt;math&gt;\left(\frac{a}{p}\right)&lt;/math&gt; is called the [[Legendre symbol]].<br /> <br /> == Quadratic Reciprocity ==<br /> <br /> Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes. Then &lt;math&gt;\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}&lt;/math&gt;. This is known as the [[Quadratic Reciprocity Theorem]].<br /> Whereas the above are properties of the Legendre symbol, they still hold for any odd integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; when using the Jacobi symbol defined below.<br /> <br /> == Additional properties ==<br /> <br /> We have for any odd prime &lt;math&gt;p&lt;/math&gt; also the following rules:<br /> <br /> Multiplicaticity: &lt;math&gt;\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)&lt;/math&gt;<br /> <br /> Euler's criterion: &lt;math&gt;\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p&lt;/math&gt;<br /> <br /> First supplementary rule: &lt;math&gt;\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4&lt;/math&gt;<br /> <br /> Second supplementary rule: &lt;math&gt;\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8&lt;/math&gt;<br /> <br /> It's also useful not to forget that the symbols are only properties &lt;math&gt;\mod p&lt;/math&gt;, so &lt;math&gt;a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) &lt;/math&gt;<br /> <br /> == Jacobi Symbol ==<br /> <br /> Now suppose that &lt;math&gt;m&lt;/math&gt; is odd, and let &lt;math&gt;m=p_1^{e_1}\cdots p_n^{e_n}&lt;/math&gt;. Then we write &lt;math&gt;\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}&lt;/math&gt;. This symbol is called the [[Jacobi symbol]].<br /> All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; instead.<br /> <br /> Note that &lt;math&gt;\left(\frac{a}{m}\right)=1&lt;/math&gt; does not mean that &lt;math&gt;a&lt;/math&gt; is a quadratic residue &lt;math&gt;\mod m&lt;/math&gt; (but is necassary for it to be).<br /> <br /> == Calculation and examples ==<br /> <br /> With the rules and properties already mentioned it's eays to calculate Jacobi symbols. Since they are for primes &lt;math&gt;p&lt;/math&gt; identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue &lt;math&gt;\mod p&lt;/math&gt; or not.<br /> <br /> Example:<br /> <br /> &lt;math&gt;\left(\frac{12345}{13337}\right) =&lt;/math&gt;<br /> <br /> &lt;math&gt;=\left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right)=&lt;/math&gt;<br /> <br /> &lt;math&gt;= 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=&lt;/math&gt;<br /> <br /> &lt;math&gt;=1&lt;/math&gt;<br /> <br /> Thus we know that &lt;math&gt;12345&lt;/math&gt; is a quadratic residue [[modulo]] the prime &lt;math&gt;13337&lt;/math&gt;. Indeed: &lt;math&gt;2425^2 \equiv 12345 \mod 13337&lt;/math&gt;<br /> <br /> In a more general manner, one for example also gets:<br /> <br /> &lt;math&gt;\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-2)^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-2}{p}\right)=1 \iff p \equiv 1,3 \mod 8&lt;/math&gt;.<br /> <br /> &lt;math&gt;\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)&lt;/math&gt;, so &lt;math&gt;\left(\frac{3}{p}\right)=1 \iff p \equiv \pm 1 \mod 12&lt;/math&gt;.<br /> <br /> &lt;math&gt;\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right)&lt;/math&gt;, so &lt;math&gt;\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \mod 3&lt;/math&gt;.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Quadratic_residues&diff=4912 Quadratic residues 2006-06-27T11:49:16Z <p>ZetaX: </p> <hr /> <div>Let &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; be [[integer]]s, with &lt;math&gt;m\neq 0&lt;/math&gt;. We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' [[modulo]] &lt;math&gt;m&lt;/math&gt; if there is some number &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2-a&lt;/math&gt; is [[divisible]] by &lt;math&gt;m&lt;/math&gt;.<br /> <br /> == Legendre Symbol ==<br /> <br /> Determining whether &lt;math&gt;a&lt;/math&gt; is a quadratic residue modulo &lt;math&gt;m&lt;/math&gt; is easiest if &lt;math&gt;m=p&lt;/math&gt; is a [[prime number|prime]]. In this case we write &lt;math&gt;\left(\frac{a}{p}\right)=\begin{cases} 0 &amp; \mathrm{if }\ p\mid a, \\ 1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ residue\ modulo\ }\ p, \\ -1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ nonresidue\ modulo\ }\ p. \end{cases}&lt;/math&gt; <br /> <br /> The symbol &lt;math&gt;\left(\frac{a}{p}\right)&lt;/math&gt; is called the [[Legendre symbol]].<br /> <br /> == Quadratic Reciprocity ==<br /> <br /> Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes. Then &lt;math&gt;\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}&lt;/math&gt;. This is known as the [[Quadratic Reciprocity Theorem]].<br /> Whereas the above are properties of the Legendre symbol, they still hold for any odd integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; when using the Jacobi symbol defined below.<br /> <br /> == Additional properties ==<br /> <br /> We have for any odd prime &lt;math&gt;p&lt;/math&gt; also the following rules:<br /> <br /> Multiplicaticity: &lt;math&gt;\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)&lt;/math&gt;<br /> <br /> Euler's criterion: &lt;math&gt;\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p&lt;/math&gt;<br /> <br /> First supplementary rule: &lt;math&gt;\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4&lt;/math&gt;<br /> <br /> Second supplementary rule: &lt;math&gt;\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8&lt;/math&gt;<br /> <br /> It's also useful not to forget that the symbols are only properties &lt;math&gt;\mod p&lt;/math&gt;, so &lt;math&gt;a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) &lt;/math&gt;<br /> <br /> == Jacobi Symbol ==<br /> <br /> Now suppose that &lt;math&gt;m&lt;/math&gt; is odd, and let &lt;math&gt;m=p_1^{e_1}\cdots p_n^{e_n}&lt;/math&gt;. Then we write &lt;math&gt;\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}&lt;/math&gt;. This symbol is called the [[Jacobi symbol]].<br /> All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; instead.<br /> <br /> Note that &lt;math&gt;\left(\frac{a}{m}\right)=1&lt;/math&gt; does not mean that &lt;math&gt;a&lt;/math&gt; is a quadratic residue &lt;math&gt;\mod m&lt;/math&gt; (but is necassary for it to be).<br /> <br /> == Calculation and examples ==<br /> <br /> With the rules and properties already mentioned it's eays to calculate Jacobi symbols. Since they are for primes &lt;math&gt;p&lt;/math&gt; identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue &lt;math&gt;\mod p&lt;/math&gt; or not.<br /> <br /> Example:<br /> <br /> &lt;math&gt;\left(\frac{12345}{13337}\right) =&lt;/math&gt;<br /> <br /> &lt;math&gt;=\left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right)=&lt;/math&gt;<br /> <br /> &lt;math&gt;= 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=&lt;/math&gt;<br /> <br /> &lt;math&gt;=1&lt;/math&gt;<br /> <br /> Thus we know that &lt;math&gt;12345&lt;/math&gt; is a quadratic residue [[modulo]] the prime &lt;math&gt;13337&lt;/math&gt;. Indeed: &lt;math&gt;2425^2 \equiv 12345 \mod 13337&lt;/math&gt;<br /> <br /> In a more general manner, one for for example also gets:<br /> <br /> &lt;math&gt;\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-2)^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-2}{p}\right)=1 \iff p \equiv 1,3 \mod 8&lt;/math&gt;.<br /> <br /> &lt;math&gt;\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)&lt;/math&gt;, so &lt;math&gt;\left(\frac{3}{p}\right)=1 \iff p \equiv \pm 1 \mod 12&lt;/math&gt;.<br /> <br /> &lt;math&gt;\left(\frac{-3}{p}\right) = \left(\frac{p}{3}\right)&lt;/math&gt;, so &lt;math&gt;\left(\frac{-3}{p}\right)=1 \iff p \equiv 1 \mod 3&lt;/math&gt;.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Quadratic_residues&diff=4911 Quadratic residues 2006-06-27T11:33:14Z <p>ZetaX: </p> <hr /> <div>Let &lt;math&gt;a&lt;/math&gt; and &lt;math&gt;m&lt;/math&gt; be [[integer]]s, with &lt;math&gt;m\neq 0&lt;/math&gt;. We say that &lt;math&gt;a&lt;/math&gt; is a '''quadratic residue''' [[modulo]] &lt;math&gt;m&lt;/math&gt; if there is some number &lt;math&gt;n&lt;/math&gt; so that &lt;math&gt;n^2-a&lt;/math&gt; is [[divisible]] by &lt;math&gt;m&lt;/math&gt;.<br /> <br /> == Legendre Symbol ==<br /> <br /> Determining whether &lt;math&gt;a&lt;/math&gt; is a quadratic residue modulo &lt;math&gt;m&lt;/math&gt; is easiest if &lt;math&gt;m=p&lt;/math&gt; is a [[prime number|prime]]. In this case we write &lt;math&gt;\left(\frac{a}{p}\right)=\begin{cases} 0 &amp; \mathrm{if }\ p\mid a, \\ 1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ residue\ modulo\ }\ p, \\ -1 &amp; \mathrm{if }\ p\nmid a\ \mathrm{ and }\ a\ \mathrm{\ is\ a\ quadratic\ nonresidue\ modulo\ }\ p. \end{cases}&lt;/math&gt; <br /> <br /> The symbol &lt;math&gt;\left(\frac{a}{p}\right)&lt;/math&gt; is called the [[Legendre symbol]].<br /> <br /> == Quadratic Reciprocity ==<br /> <br /> Let &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; be distinct odd primes. Then &lt;math&gt;\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}&lt;/math&gt;. This is known as the [[Quadratic Reciprocity Theorem]].<br /> Whereas the above are properties of the Legendre symbol, they still hold for any odd integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; when using the Jacobi symbol defined below.<br /> <br /> == Additional properties ==<br /> <br /> We have for any odd prime &lt;math&gt;p&lt;/math&gt; also the following rules:<br /> <br /> Multiplicaticity: &lt;math&gt;\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)&lt;/math&gt;<br /> <br /> Euler's criterion: &lt;math&gt;\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p&lt;/math&gt;<br /> <br /> First supplementary rule: &lt;math&gt;\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{-1}{p}\right)=1 \iff p \equiv 1 \mod 4&lt;/math&gt;<br /> <br /> Second supplementary rule: &lt;math&gt;\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}&lt;/math&gt;, so &lt;math&gt;\left(\frac{2}{p}\right)=1 \iff p \equiv \pm 1 \mod 8&lt;/math&gt;<br /> <br /> It's also usefull not to forget that the symbols are only properties &lt;math&gt;\mod p&lt;/math&gt;, so &lt;math&gt;a \equiv b \mod p \implies \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) &lt;/math&gt;<br /> <br /> == Jacobi Symbol ==<br /> <br /> Now suppose that &lt;math&gt;m&lt;/math&gt; is odd, and let &lt;math&gt;m=p_1^{e_1}\cdots p_n^{e_n}&lt;/math&gt;. Then we write &lt;math&gt;\left(\frac{a}{m}\right)=\left(\frac{a}{p_1}\right)^{e_1}\cdots\left(\frac{a}{p_n}\right)^{e_n}&lt;/math&gt;. This symbol is called the [[Jacobi symbol]].<br /> All properties mentioned above except Euler's criterion are also true for Jacobi symbols with odd (positive) integers &lt;math&gt;p&lt;/math&gt; and &lt;math&gt;q&lt;/math&gt; instead.<br /> <br /> Note that &lt;math&gt;\left(\frac{a}{m}\right)=1&lt;/math&gt; does not mean that &lt;math&gt;a&lt;/math&gt; is a quadratic residue &lt;math&gt;\mod m&lt;/math&gt; (but is necassary for it to be).<br /> <br /> == Calculation and examples ==<br /> <br /> With the rules and properties already mentioned it's eays to calculate Jacobi symbols. Since they are for primes &lt;math&gt;p&lt;/math&gt; identical to the Legendre symbol, this gives a fast way to decide if an integer is a quadratic residue &lt;math&gt;\mod p&lt;/math&gt; or not.<br /> <br /> Example:<br /> &lt;math&gt;\left(\frac{12345}{13337}\right) = \left(\frac{13337}{12345}\right) = \left(\frac{992}{12345}\right) = \left(\frac{2^5}{12345}\right)\left(\frac{31}{12345}\right)=\left(\frac{2}{12345}\right)^5 \left(\frac{12345}{31}\right) = 1^5 \left(\frac{7}{31}\right) = -\left(\frac{31}{7}\right) = -\left(\frac{3}{7}\right) = \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right)=1&lt;/math&gt;<br /> Thus we know that &lt;math&gt;12345&lt;/math&gt; is a quadratic residue modulo the prime &lt;math&gt;13337&lt;/math&gt;. Indeed: &lt;math&gt;2425^2 \equiv 12345 \mod 13337&lt;/math&gt;</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Talk:Mathematicial_notation&diff=4909 Talk:Mathematicial notation 2006-06-27T10:37:39Z <p>ZetaX: </p> <hr /> <div>I copied this from the AoPS Formulary, and it needs to be converted to Wiki format. Please help! '''Also, credit for writing this GREAT article goes to ZetaX'''. --[[User:Mysmartmouth|Sean]] 23:56, 26 June 2006 (EDT)<br /> <br /> I take issue with the notation &lt;math&gt;\mathbb{Z}_n&lt;/math&gt; for integers modulo ''n''. When ''n'' is prime, this notation is used for the ''p''-adic integers, which do not really have any other notation (well perhaps &lt;math&gt;{\widehat{\mathbb{Z}}}_p&lt;/math&gt;, but that's not much different). --[[User:ComplexZeta|ComplexZeta]] 01:22, 27 June 2006 (EDT)<br /> <br /> I also don't like the notation &lt;math&gt;\mathbb{Z}_n&lt;/math&gt;, but that is what most people use on ML/AoPS.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Relatively_prime&diff=3389 Relatively prime 2006-06-20T09:13:04Z <p>ZetaX: </p> <hr /> <div>(Also called ''coprime''.)<br /> <br /> Two '''relatively prime''' integers &lt;math&gt;{m}&lt;/math&gt; and &lt;math&gt;{n}&lt;/math&gt; share no common factors, so their &lt;math&gt;\gcd&lt;/math&gt; is &lt;math&gt;1&lt;/math&gt;. Alternatively, &lt;math&gt;{m}&lt;/math&gt; and &lt;math&gt;{n}&lt;/math&gt; must have no [[prime factor|prime factors]] in common. For example, 15 and 14 are relatively prime; as the [[prime factorization]] of 15 is &lt;math&gt;3 \cdot 5&lt;/math&gt;, the prime factorization of 14 is &lt;math&gt;2 \cdot 7&lt;/math&gt;, and no prime factors are shared between the two.<br /> <br /> Note that for relatively prime &lt;math&gt;{m}&lt;/math&gt; and &lt;math&gt;{n}&lt;/math&gt;, &lt;math&gt;\frac{m}{n}&lt;/math&gt; will be in lowest terms.<br /> <br /> Relatively prime numbers show up frequently in [[number theory]] formulas and derivations. [[Euler's totient function]], for example, determines the number of positive integers less than any given positive integer that are relatively prime to that number. The [[Chicken mcNugget theorem]] also involves relatively prime numbers.</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=3388 Euler's totient function 2006-06-20T09:09:08Z <p>ZetaX: </p> <hr /> <div>'''Euler's totient function''', &lt;math&gt;\phi(n)&lt;/math&gt;, is defined as the number of positive integers less than or equal to a given positive integer that are [[relatively prime]] to that integer.<br /> <br /> === Formulas ===<br /> <br /> The formal definition is &lt;math&gt;\phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\} &lt;/math&gt;.<br /> <br /> Given the [[prime factorization]] of &lt;math&gt;{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}&lt;/math&gt;, then another formula for &lt;math&gt;\phi(n)&lt;/math&gt; is &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_n}\right) &lt;/math&gt;.<br /> <br /> === Identities ===<br /> <br /> For [[prime]] p, &lt;math&gt;\phi(p)=p-1&lt;/math&gt;, because all numbers less than &lt;math&gt;{p}&lt;/math&gt; are relatively prime to it.<br /> <br /> For relatively prime &lt;math&gt;{a}, {b}&lt;/math&gt;, &lt;math&gt; \phi{(a)}\phi{(b)} = \phi{(ab)} &lt;/math&gt;.<br /> <br /> In fact, we also have for any &lt;math&gt;{a}, {b}&lt;/math&gt; that &lt;math&gt;\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})&lt;/math&gt;.<br /> <br /> For any &lt;math&gt;n&lt;/math&gt;, we have &lt;math&gt;\sum_{d|n}\phi(d)=n&lt;/math&gt; where the sum is taken over all divisors d of &lt;math&gt; n &lt;/math&gt;.<br /> <br /> === See also ===<br /> <br /> * [[Number theory]]<br /> * [[Prime]]<br /> * [[Euler's Totient Theorem]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=3387 Euler's totient function 2006-06-20T09:08:36Z <p>ZetaX: </p> <hr /> <div>'''Euler's totient function''', &lt;math&gt;\phi(n)&lt;/math&gt;, is defined as the number of positive integers less than or equal to a given positive integer that are [[relatively prime]] to that integer.<br /> <br /> === Formulas ===<br /> <br /> The formal definition is &lt;math&gt;\displaystyle \phi(n):=\# \left\{ a \in \mathbb{Z}: 1 \leq a \leq n , \gcd(a,n)=1 \right\} &lt;/math&gt;.<br /> <br /> Given the [[prime factorization]] of &lt;math&gt;{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}&lt;/math&gt;, then another formula for &lt;math&gt;\phi(n)&lt;/math&gt; is &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_n}\right) &lt;/math&gt;.<br /> <br /> === Identities ===<br /> <br /> For [[prime]] p, &lt;math&gt;\phi(p)=p-1&lt;/math&gt;, because all numbers less than &lt;math&gt;{p}&lt;/math&gt; are relatively prime to it.<br /> <br /> For relatively prime &lt;math&gt;{a}, {b}&lt;/math&gt;, &lt;math&gt; \phi{(a)}\phi{(b)} = \phi{(ab)} &lt;/math&gt;.<br /> <br /> In fact, we also have for any &lt;math&gt;{a}, {b}&lt;/math&gt; that &lt;math&gt;\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})&lt;/math&gt;.<br /> <br /> For any &lt;math&gt;n&lt;/math&gt;, we have &lt;math&gt;\sum_{d|n}\phi(d)=n&lt;/math&gt; where the sum is taken over all divisors d of &lt;math&gt; n &lt;/math&gt;.<br /> <br /> === See also ===<br /> <br /> * [[Number theory]]<br /> * [[Prime]]<br /> * [[Euler's Totient Theorem]]</div> ZetaX https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=3386 Euler's totient function 2006-06-20T08:39:04Z <p>ZetaX: </p> <hr /> <div>'''Euler's totient function''', &lt;math&gt;\phi(n)&lt;/math&gt;, determines the number of integers less than a given positive integer that are [[relatively prime]] to that integer.<br /> <br /> === Formulas ===<br /> <br /> Given the [[prime factorization]] of &lt;math&gt;{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}&lt;/math&gt;, then one formula for &lt;math&gt;\phi(n)&lt;/math&gt; is &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_n}\right) &lt;/math&gt;.<br /> <br /> === Identities ===<br /> <br /> For [[prime]] p, &lt;math&gt;\phi(p)=p-1&lt;/math&gt;, because all numbers less than &lt;math&gt;{p}&lt;/math&gt; are relatively prime to it.<br /> <br /> For relatively prime &lt;math&gt;{a}, {b}&lt;/math&gt;, &lt;math&gt; \phi{(a)}\phi{(b)} = \phi{(ab)} &lt;/math&gt;.<br /> <br /> In fact, we also have for any &lt;math&gt;{a}, {b}&lt;/math&gt; that &lt;math&gt;\phi{(a)}\phi{(b)}\gcd(a,b)=\phi{(ab)}\phi({\gcd(a,b)})&lt;/math&gt;.<br /> <br /> For any &lt;math&gt;n&lt;/math&gt;, we have &lt;math&gt;\sum_{d|n}\phi(d)=n&lt;/math&gt; where the sum is taken over all divisors d of &lt;math&gt; n &lt;/math&gt;.<br /> <br /> === See also ===<br /> <br /> * [[Number theory]]<br /> * [[Prime]]<br /> * [[Euler's Totient Theorem]]</div> ZetaX