https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Elemennop&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T16:36:02ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Composite_number&diff=3977Composite number2006-06-22T21:13:55Z<p>Elemennop: No, 1 is a proper divisor, so you require at least two proper divisors.</p>
<hr />
<div>Simply stated, a composite number is the exact opposite of a [[prime | prime number]]. It is any number with at least two [[proper divisor | proper divisors]]. <br />
<br />
Note that the number one is neither prime nor composite. It follows that two is the only even prime number, three is the only multiple of three that is prime, and so on.<br />
<br />
==See also==<br />
* [[Number Theory]]</div>Elemennophttps://artofproblemsolving.com/wiki/index.php?title=Sum_of_divisors_function&diff=3620Sum of divisors function2006-06-21T13:34:06Z<p>Elemennop: Simplified formula</p>
<hr />
<div>If <math>k=p_1^{\alpha_1}\cdot\dots\cdot p_n^{\alpha_n}</math> is the [[prime factorization]] of <math>\displaystyle{k}</math>, then the sum of all divisors of <math>k</math> is given by the formula <math>s=(p_1^0+p_1^1+...+p_1^{\alpha_1})(p_2^0+p_2^1+...+p_2^{\alpha_2})\cdot\dots\cdot (p_n^0+p_n^1+...+p_n^{\alpha_n})</math>.<br />
<br />
In fact, if you use the formula <math>1+q+q^2+\ldots+q_n = \frac{q^{n+1}-1}{q-1}</math>, then the above formula is equivalent to<br />
<br />
<math> s = \displaystyle\left(\frac{p_1^{\alpha_1+1}-1}{p_1-1}\right)\left(\frac{p_2^{\alpha_2+1}-1}{p_2-1}\right)\ldots\left(\frac{p_n^{\alpha_n+1}-1}{p_n-1}\right)</math><br />
<br />
== Derivation ==<br />
If you expand the monomial into a polynomial you see that it comes to be the addition of all possible combinations of the multiplication of the prime factors, and so all the divisors.</div>Elemennophttps://artofproblemsolving.com/wiki/index.php?title=Euler%27s_totient_function&diff=2950Euler's totient function2006-06-19T02:44:45Z<p>Elemennop: Added new identity</p>
<hr />
<div>'''Euler's totient function''', <math>\phi(n)</math>, 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 <math>{n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_n^{e_n}</math>, then one formula for <math>\phi(n)</math> is <math> \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) </math>.<br />
<br />
=== Identities ===<br />
<br />
For [[prime]] p, <math>\phi(p)=p-1</math>, because all numbers less than <math>{p}</math> are relatively prime to it.<br />
<br />
For relatively prime <math>{a}, {b}</math>, <math> \phi{(a)}\phi{(b)} = \phi{(ab)} </math>.<br />
<br />
For non-relatively prime <math>{a}, {b}</math>, we have <math>\phi{(a)}\phi{(b)}gcd(a,b)=\phi{(ab)}\phi{gcd(a,b)}</math>.<br />
<br />
For any <math>n</math>, we have <math>\sum_{d|n}\phi(d)=n</math> where the sum is taken over all divisors d of <math> n </math>.<br />
<br />
=== See also ===<br />
<br />
* [[Number theory]]<br />
* [[Prime]]<br />
* [[Euler's Totient Theorem]]</div>Elemennophttps://artofproblemsolving.com/wiki/index.php?title=Partial_fraction_decomposition&diff=2946Partial fraction decomposition2006-06-19T02:39:59Z<p>Elemennop: Moved uses to end, reversed cdots to ldots (cdots cause parsing error)</p>
<hr />
<div>Any [[rational function]] of the form <math>\frac{P(x)}{Q(x)}</math> maybe written as a sum of simpler rational functions. <br />
<br />
<br />
<br />
To find the decomposition of a rational function, first perform the long division operation on it. This transforms the function into one of the form <math>\frac{P(x)}{Q(x)}=S(x) + \frac{R(x)}{Q(x)}</math>, where <math>R(x)</math> is the remainder term and <math>deg R(x) \leq deg Q(x)</math>.<br />
<br />
<br />
<br />
Next, for every factor <math>(a_nx^n+a_{n-1}x^{n-1}+\ldots +a_0)^m</math> in the factorization of <math>Q(x)</math>, introduce the terms <br />
<br />
<br />
<math>\frac{A_1x^{n-1}+B_1x^{n-2}+\ldots+Z_1}{a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0}+\frac{A_2x^{n-1}+B_2x^{n-2}+\ldots+Z_2}{(a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0)^2}+\ldots+\frac{A_mx^{n-1}+B_mx^{n-2}+\ldots+Z_m}{(a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0)^m}</math><br />
<br />
<br />
Note that the variable <math>Z_i</math> has no relation to being the 26th letter in the alphabet.<br />
<br />
Next, take the sum of every term introduced above and equate it to <math>\frac{R(x)}{Q(x)}</math>, and solve for the variables <math>A_i, B_i, \ldots</math>. Once you solve for all the variables, then you will have the partial fraction decomposition of <math>\frac{R(x)}{Q(x)}</math>.<br />
<br />
<br />
<br />
Partial fraction decomposition has several common uses. It allows for much easier integration of rational functions, allowing one to integrate a complicated rational function term by term. Additionally, it can be used in summations, causing sums to often telescope or have a much easier form which can be expressed with a closed form. It has several other minor uses, as well.</div>Elemennophttps://artofproblemsolving.com/wiki/index.php?title=Partial_fraction_decomposition&diff=2881Partial fraction decomposition2006-06-18T23:21:05Z<p>Elemennop: </p>
<hr />
<div>Any rational function of the form <math>\frac{P(x)}{Q(x)}</math> maybe written as a sum of simpler rational functions. This allows for much easier integration, as well as causing many sums to telescope. It has many other uses, as well.<br />
<br />
<br />
<br />
To find the decomposition of a rational function, first perform the long division operation on it. This transforms the function into one of the form <math>\frac{P(x)}{Q(x)}=S(x) + \frac{R(x)}{Q(x)}</math>, where <math>R(x)</math> is the remainder term and <math>deg R(x) \leq deg Q(x)</math>.<br />
<br />
<br />
<br />
Next, for every factor <math>(a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0)^m</math> in the factorization of <math>Q(x)</math>, introduce the terms <br />
<br />
<br />
<math>\frac{A_1x^{n-1}+B_1x^{n-2}+\ldots+Z_1}{a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0}+\frac{A_2x^{n-1}+B_2x^{n-2}+\ldots+Z_2}{(a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0)^2}+\ldots+\frac{A_mx^{n-1}+B_mx^{n-2}+\ldots+Z_m}{(a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0)^m}</math><br />
<br />
<br />
Note that the variable <math>Z_i</math> has no relation to being the 26th letter in the alphabet.<br />
<br />
Next, take the sum of every term introduced above and equate it to <math>\frac{R(x)}{Q(x)}</math>, and solve for the variables <math>A_i, B_i, \ldots</math>. Once you solve for all the variables, then you will have the partial fraction decomposition of <math>\frac{R(x)}{Q(x)}</math>.</div>Elemennop