https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Enderramsby&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T05:21:21ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=191343Combinatorial identity2023-03-25T23:39:24Z<p>Enderramsby: /* Examples */</p>
<hr />
<div>== Pascal's Identity ==<br />
Pascal's Identity states that<br />
<br />
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math><br />
<br />
for any [[positive integer]]s <math>k</math> and <math>n</math>. Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = {}_nC_k = C_k^n</math>.<br />
<br />
This result can be interpreted combinatorially as follows: the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things.<br />
<br />
=== Proof ===<br />
If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial. So assume <math>k \leq n</math>. Then<br />
<br />
<cmath>\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\<br />
&=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\<br />
&=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\<br />
&=&\frac{n!}{k!(n-k)!}\\<br />
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath><br />
<br />
===Alternate Proofs===<br />
Here, we prove this using [[committee forming]].<br />
<br />
Consider picking one fixed object out of <math>n</math> objects. Then, we can choose <math>k</math> objects including that one in <math>\binom{n-1}{k-1}</math> ways.<br />
<br />
Because our final group of objects either contains the specified one or doesn't, we can choose the group in <math>\binom{n-1}{k-1}+\binom{n-1}{k}</math> ways. <br />
<br />
But we already know they can be picked in <math>\binom{n}{k}</math> ways, so <br />
<br />
<cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} \qquad \qquad \square</cmath><br />
<br />
<br />
Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term <math>\binom{n}{k}</math>. Above that, we would see the terms <math>{n-1\choose k-1}</math> and <math>{n-1\choose k}</math>. Due to the definition of Pascal's Triangle, <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.<br />
<br />
<br />
==Vandermonde's Identity==<br />
Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>.<br />
<br />
===Video Proof=== <br />
<br />
https://www.youtube.com/watch?v=u1fktz9U9ig<br />
<br />
===Combinatorial Proof===<br />
<br />
Think of the right hand side as picking <math>r</math> people from <math>m</math> men and <math>n</math> women. Think of the left hand side as picking <math>k</math> men from the <math>m</math> total men and picking <math>r-k</math> women from the <math>n</math> total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.<br />
<br />
~avn<br />
<br />
===Algebraic proof===<br />
For all <math>x,</math> <cmath>(1+x)^m(1+x)^n = (1+x)^{m+n}</cmath><br />
The coefficients of <math>x^r</math> on both sides must be the same, so using the [[Binomial Theorem]], <cmath>\sum_{k=0}^r \binom mk \binom n{r-k} = \binom {m+n}r.</cmath><br />
<br />
==Hockey-Stick Identity==<br />
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.<br />
<br />
<asy><br />
int chew(int n,int r){<br />
int res=1;<br />
for(int i=0;i<r;++i){<br />
res=quotient(res*(n-i),i+1);<br />
}<br />
return res;<br />
}<br />
for(int n=0;n<9;++n){<br />
for(int i=0;i<=n;++i){<br />
if((i==2 && n<8)||(i==3 && n==8)){<br />
if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br />
else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br />
}<br />
else{<br />
label(string(chew(n,i)),(11+n/2-i,-n));<br />
}<br />
}<br />
}<br />
</asy><br />
<br />
This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed. We can also flip the hockey stick because pascal's triangle is symettrical.<br />
<br />
<br />
===Proof===<br />
<br />
'''Inductive Proof'''<br />
<br />
This identity can be proven by induction on <math>n</math>.<br />
<br />
<u>Base Case</u><br />
Let <math>n=r</math>.<br />
<br />
<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.<br />
<br />
<u>Inductive Step</u><br />
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>.<br />
Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>.<br />
<br />
'''Algebraic Proof'''<br />
<br />
It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.<br />
Note that<br />
<br />
<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math><br />
<math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math><br />
<math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result.<br />
<br />
'''Combinatorial Proof 1'''<br />
<br />
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.<br />
<br />
'''Combinatorial Proof 2'''<br />
<br />
We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people. We can divide this into <math>n-k+1</math> disjoint cases. In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee. This can be done in <math>\binom{n-x+1}{k}</math> ways. Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath><br />
<br />
<br />
<br />
'''Algebraic Proof 2'''<br />
<br />
Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity.<br />
<br />
==Another Identity==<br />
<br />
<cmath><br />
\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br />
</cmath><br />
<br />
===Hat Proof===<br />
We have <math>2k</math> different hats. We split them into two groups, each with k hats: then we choose <math>i</math> hats from the first group and <math>k-i</math> hats from the second group. This may be done in <math>\binom{k}{i}^2</math> ways. Evidently, to generate all possible choices of <math>k</math> hats from the <math>2k</math> hats, we must choose <math>i=0,1,\cdots,k</math> hats from the first <math>k</math> and the remaining <math>k-i</math> hats from the second <math>k</math>; the sum over all such <math>i</math> is the number of ways of choosing <math>k</math> hats from <math>2k</math>. Therefore <math>\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}</math>, as desired.<br />
<br />
===Proof 2===<br />
This is a special case of Vandermonde's identity, in which we set <math>m=n=r</math>.<br />
<br />
== Examples ==<br />
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br />
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 2000 AIME II Problem 7]<br />
* [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_2 2013 AIME I Problem 6 (Solution 2)]<br />
* [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br />
* [http://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_10 2018 AIME I Problem 10]<br />
* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br />
* [https://artofproblemsolving.com/wiki/index.php/2016_AMC_10A_Problems/Problem_20 2016 AMC 10A Problem 20]<br />
* [https://artofproblemsolving.com/wiki/index.php/2021_AMC_12A_Problems/Problem_15 2021 AMC 12A Problem 15]<br />
* [https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems 1981 IMO Problem 2]<br />
<br />
==See also==<br />
* [[Pascal's Triangle]]<br />
* [[Combinatorics]]<br />
* [[Pascal's Identity]]<br />
<br />
[[Category:Theorems]]<br />
<br />
[[Category:Combinatorics]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Pyramidal_numbers&diff=191342Pyramidal numbers2023-03-25T23:36:28Z<p>Enderramsby: </p>
<hr />
<div>The Pyramidal Numbers are the numbers <math>n</math> which are the sum of the first <math>n</math> triangular numbers. The formula for their sum is <math>(n)(n+1)(n+2)/6</math>.<br />
<br />
{{stub}}</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Talk:Combinatorial_identity&diff=190719Talk:Combinatorial identity2023-03-07T03:56:47Z<p>Enderramsby: /* Adding Pascal's Identity */</p>
<hr />
<div>Wait is it Combinatorial or Combinatorical? --[[User:Chess64|Chess64]] 16:52, 19 June 2006 (EDT)<br />
<br />
Combinatorial --[[User:ComplexZeta|ComplexZeta]] 00:04, 25 June 2006 (EDT)<br />
<br />
== This and Pascal's Triangle ==<br />
<br />
I'm not quite sure how to work this page and [[Pascal's Triangle]]; I've got a couple of these identites expanded in detail on that page, and they really belong here as well. How much overlap between these pages do we want? --[[User:Dschafer|Dschafer]] 23:36, 24 June 2006 (EDT)<br />
<br />
When in doubt, put them in both places. If we feel that they don't belong in one place, we can delete them, and then they won't be entirely gone. (Not that they would anyway, but most of us probably don't want to dig through page histories any more than necessary.) --[[User:ComplexZeta|ComplexZeta]] 00:04, 25 June 2006 (EDT)<br />
<br />
I suggest deleting this article, and adding a redirect to [[Pascal's Triangle]]. What do you guys think? --[[User:Mysmartmouth|Sean]] 13:04, 27 June 2006 (EDT)<br />
<br />
I would disagree; while there is some overlap that needs addressing, there is certainly material that belongs here that wouldn't work in Pascal's Triangle, and vice versa. --[[User:Dschafer|Dschafer]] 23:14, 28 June 2006 (EDT)<br />
<br />
== Adding Pascal's Identity ==<br />
<br />
I believe that Pascal's Identity should be included here too, so I copy and pasted the Pascal's Identity page into here. I suggest deleting the Pascal's Identity page, what do you guys think? ~enderramsby</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Talk:Combinatorial_identity&diff=190718Talk:Combinatorial identity2023-03-07T03:56:33Z<p>Enderramsby: /* Adding Pascal's Identity */ new section</p>
<hr />
<div>Wait is it Combinatorial or Combinatorical? --[[User:Chess64|Chess64]] 16:52, 19 June 2006 (EDT)<br />
<br />
Combinatorial --[[User:ComplexZeta|ComplexZeta]] 00:04, 25 June 2006 (EDT)<br />
<br />
== This and Pascal's Triangle ==<br />
<br />
I'm not quite sure how to work this page and [[Pascal's Triangle]]; I've got a couple of these identites expanded in detail on that page, and they really belong here as well. How much overlap between these pages do we want? --[[User:Dschafer|Dschafer]] 23:36, 24 June 2006 (EDT)<br />
<br />
When in doubt, put them in both places. If we feel that they don't belong in one place, we can delete them, and then they won't be entirely gone. (Not that they would anyway, but most of us probably don't want to dig through page histories any more than necessary.) --[[User:ComplexZeta|ComplexZeta]] 00:04, 25 June 2006 (EDT)<br />
<br />
I suggest deleting this article, and adding a redirect to [[Pascal's Triangle]]. What do you guys think? --[[User:Mysmartmouth|Sean]] 13:04, 27 June 2006 (EDT)<br />
<br />
I would disagree; while there is some overlap that needs addressing, there is certainly material that belongs here that wouldn't work in Pascal's Triangle, and vice versa. --[[User:Dschafer|Dschafer]] 23:14, 28 June 2006 (EDT)<br />
<br />
== Adding Pascal's Identity ==<br />
<br />
I believe that Pascal's Identity should be included here too, so I copy and pasted the Pascal's Identity page into here. I suggest deleting the Pascal's Identity page, what do you guys think?</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=190717Combinatorial identity2023-03-07T03:54:49Z<p>Enderramsby: </p>
<hr />
<div>== Pascal's Identity ==<br />
Pascal's Identity states that<br />
<br />
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math><br />
<br />
for any [[positive integer]]s <math>k</math> and <math>n</math>. Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = {}_nC_k = C_k^n</math>.<br />
<br />
This result can be interpreted combinatorially as follows: the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things.<br />
<br />
=== Proof ===<br />
If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial. So assume <math>k \leq n</math>. Then<br />
<br />
<cmath>\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\<br />
&=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\<br />
&=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\<br />
&=&\frac{n!}{k!(n-k)!}\\<br />
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath><br />
<br />
===Alternate Proofs===<br />
Here, we prove this using [[committee forming]].<br />
<br />
Consider picking one fixed object out of <math>n</math> objects. Then, we can choose <math>k</math> objects including that one in <math>\binom{n-1}{k-1}</math> ways.<br />
<br />
Because our final group of objects either contains the specified one or doesn't, we can choose the group in <math>\binom{n-1}{k-1}+\binom{n-1}{k}</math> ways. <br />
<br />
But we already know they can be picked in <math>\binom{n}{k}</math> ways, so <br />
<br />
<cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} \qquad \qquad \square</cmath><br />
<br />
<br />
Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term <math>\binom{n}{k}</math>. Above that, we would see the terms <math>{n-1\choose k-1}</math> and <math>{n-1\choose k}</math>. Due to the definition of Pascal's Triangle, <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.<br />
<br />
<br />
==Vandermonde's Identity==<br />
Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>.<br />
<br />
===Video Proof=== <br />
<br />
https://www.youtube.com/watch?v=u1fktz9U9ig<br />
<br />
===Combinatorial Proof===<br />
<br />
Think of the right hand side as picking <math>r</math> people from <math>m</math> men and <math>n</math> women. Think of the left hand side as picking <math>k</math> men from the <math>m</math> total men and picking <math>r-k</math> women from the <math>n</math> total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.<br />
<br />
~avn<br />
<br />
===Algebraic proof===<br />
For all <math>x,</math> <cmath>(1+x)^m(1+x)^n = (1+x)^{m+n}</cmath><br />
The coefficients of <math>x^r</math> on both sides must be the same, so using the [[Binomial Theorem]], <cmath>\sum_{k=0}^r \binom mk \binom n{r-k} = \binom {m+n}r.</cmath><br />
<br />
==Hockey-Stick Identity==<br />
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.<br />
<br />
<asy><br />
int chew(int n,int r){<br />
int res=1;<br />
for(int i=0;i<r;++i){<br />
res=quotient(res*(n-i),i+1);<br />
}<br />
return res;<br />
}<br />
for(int n=0;n<9;++n){<br />
for(int i=0;i<=n;++i){<br />
if((i==2 && n<8)||(i==3 && n==8)){<br />
if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br />
else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br />
}<br />
else{<br />
label(string(chew(n,i)),(11+n/2-i,-n));<br />
}<br />
}<br />
}<br />
</asy><br />
<br />
This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed. We can also flip the hockey stick because pascal's triangle is symettrical.<br />
<br />
<br />
===Proof===<br />
<br />
'''Inductive Proof'''<br />
<br />
This identity can be proven by induction on <math>n</math>.<br />
<br />
<u>Base Case</u><br />
Let <math>n=r</math>.<br />
<br />
<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.<br />
<br />
<u>Inductive Step</u><br />
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>.<br />
Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>.<br />
<br />
'''Algebraic Proof'''<br />
<br />
It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.<br />
Note that<br />
<br />
<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math><br />
<math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math><br />
<math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result.<br />
<br />
'''Combinatorial Proof 1'''<br />
<br />
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.<br />
<br />
'''Combinatorial Proof 2'''<br />
<br />
We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people. We can divide this into <math>n-k+1</math> disjoint cases. In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee. This can be done in <math>\binom{n-x+1}{k}</math> ways. Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath><br />
<br />
<br />
<br />
'''Algebraic Proof 2'''<br />
<br />
Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity.<br />
<br />
==Another Identity==<br />
<br />
<cmath><br />
\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br />
</cmath><br />
<br />
===Hat Proof===<br />
We have <math>2k</math> different hats. We split them into two groups, each with k hats: then we choose <math>i</math> hats from the first group and <math>k-i</math> hats from the second group. This may be done in <math>\binom{k}{i}^2</math> ways. Evidently, to generate all possible choices of <math>k</math> hats from the <math>2k</math> hats, we must choose <math>i=0,1,\cdots,k</math> hats from the first <math>k</math> and the remaining <math>k-i</math> hats from the second <math>k</math>; the sum over all such <math>i</math> is the number of ways of choosing <math>k</math> hats from <math>2k</math>. Therefore <math>\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}</math>, as desired.<br />
<br />
===Proof 2===<br />
This is a special case of Vandermonde's identity, in which we set <math>m=n=r</math>.<br />
<br />
== Examples ==<br />
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br />
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 2000 AIME II Problem 7]<br />
* [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME I Problem 6 (Solution 2)]<br />
* [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br />
* [http://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_10 2018 AIME I Problem 10]<br />
* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br />
* [https://artofproblemsolving.com/wiki/index.php/2016_AMC_10A_Problems/Problem_20 2016 AMC 10A Problem 20]<br />
* [https://artofproblemsolving.com/wiki/index.php/2021_AMC_12A_Problems/Problem_15 2021 AMC 12A Problem 15]<br />
* [https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems 1981 IMO Problem 2]<br />
<br />
==See also==<br />
* [[Pascal's Triangle]]<br />
* [[Combinatorics]]<br />
* [[Pascal's Identity]]<br />
<br />
[[Category:Theorems]]<br />
<br />
[[Category:Combinatorics]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity&diff=190716Combinatorial identity2023-03-07T03:54:28Z<p>Enderramsby: Added Pascal's Identity</p>
<hr />
<div>== Pascal's Identity ==<br />
Pascal's Identity states that<br />
<br />
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math><br />
<br />
for any [[positive integer]]s <math>k</math> and <math>n</math>. Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = {}_nC_k = C_k^n</math>.<br />
<br />
This result can be interpreted combinatorially as follows: the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things.<br />
<br />
== Proof ==<br />
If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial. So assume <math>k \leq n</math>. Then<br />
<br />
<cmath>\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\<br />
&=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\<br />
&=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\<br />
&=&\frac{n!}{k!(n-k)!}\\<br />
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath><br />
<br />
==Alternate Proofs==<br />
Here, we prove this using [[committee forming]].<br />
<br />
Consider picking one fixed object out of <math>n</math> objects. Then, we can choose <math>k</math> objects including that one in <math>\binom{n-1}{k-1}</math> ways.<br />
<br />
Because our final group of objects either contains the specified one or doesn't, we can choose the group in <math>\binom{n-1}{k-1}+\binom{n-1}{k}</math> ways. <br />
<br />
But we already know they can be picked in <math>\binom{n}{k}</math> ways, so <br />
<br />
<cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} \qquad \qquad \square</cmath><br />
<br />
<br />
Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term <math>\binom{n}{k}</math>. Above that, we would see the terms <math>{n-1\choose k-1}</math> and <math>{n-1\choose k}</math>. Due to the definition of Pascal's Triangle, <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.<br />
<br />
<br />
==Vandermonde's Identity==<br />
Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>.<br />
<br />
===Video Proof=== <br />
<br />
https://www.youtube.com/watch?v=u1fktz9U9ig<br />
<br />
===Combinatorial Proof===<br />
<br />
Think of the right hand side as picking <math>r</math> people from <math>m</math> men and <math>n</math> women. Think of the left hand side as picking <math>k</math> men from the <math>m</math> total men and picking <math>r-k</math> women from the <math>n</math> total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.<br />
<br />
~avn<br />
<br />
===Algebraic proof===<br />
For all <math>x,</math> <cmath>(1+x)^m(1+x)^n = (1+x)^{m+n}</cmath><br />
The coefficients of <math>x^r</math> on both sides must be the same, so using the [[Binomial Theorem]], <cmath>\sum_{k=0}^r \binom mk \binom n{r-k} = \binom {m+n}r.</cmath><br />
<br />
==Hockey-Stick Identity==<br />
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.<br />
<br />
<asy><br />
int chew(int n,int r){<br />
int res=1;<br />
for(int i=0;i<r;++i){<br />
res=quotient(res*(n-i),i+1);<br />
}<br />
return res;<br />
}<br />
for(int n=0;n<9;++n){<br />
for(int i=0;i<=n;++i){<br />
if((i==2 && n<8)||(i==3 && n==8)){<br />
if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}<br />
else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}<br />
}<br />
else{<br />
label(string(chew(n,i)),(11+n/2-i,-n));<br />
}<br />
}<br />
}<br />
</asy><br />
<br />
This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed. We can also flip the hockey stick because pascal's triangle is symettrical.<br />
<br />
<br />
===Proof===<br />
<br />
'''Inductive Proof'''<br />
<br />
This identity can be proven by induction on <math>n</math>.<br />
<br />
<u>Base Case</u><br />
Let <math>n=r</math>.<br />
<br />
<math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>.<br />
<br />
<u>Inductive Step</u><br />
Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>.<br />
Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>.<br />
<br />
'''Algebraic Proof'''<br />
<br />
It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>.<br />
Note that<br />
<br />
<math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math><br />
<math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math><br />
<math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result.<br />
<br />
'''Combinatorial Proof 1'''<br />
<br />
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.<br />
<br />
'''Combinatorial Proof 2'''<br />
<br />
We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people. We can divide this into <math>n-k+1</math> disjoint cases. In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee. This can be done in <math>\binom{n-x+1}{k}</math> ways. Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath><br />
<br />
<br />
<br />
'''Algebraic Proof 2'''<br />
<br />
Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity.<br />
<br />
==Another Identity==<br />
<br />
<cmath><br />
\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}<br />
</cmath><br />
<br />
===Hat Proof===<br />
We have <math>2k</math> different hats. We split them into two groups, each with k hats: then we choose <math>i</math> hats from the first group and <math>k-i</math> hats from the second group. This may be done in <math>\binom{k}{i}^2</math> ways. Evidently, to generate all possible choices of <math>k</math> hats from the <math>2k</math> hats, we must choose <math>i=0,1,\cdots,k</math> hats from the first <math>k</math> and the remaining <math>k-i</math> hats from the second <math>k</math>; the sum over all such <math>i</math> is the number of ways of choosing <math>k</math> hats from <math>2k</math>. Therefore <math>\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}</math>, as desired.<br />
<br />
===Proof 2===<br />
This is a special case of Vandermonde's identity, in which we set <math>m=n=r</math>.<br />
<br />
== Examples ==<br />
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11]<br />
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 2000 AIME II Problem 7]<br />
* [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_Two 2013 AIME I Problem 6 (Solution 2)]<br />
* [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]<br />
* [http://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_10 2018 AIME I Problem 10]<br />
* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]<br />
* [https://artofproblemsolving.com/wiki/index.php/2016_AMC_10A_Problems/Problem_20 2016 AMC 10A Problem 20]<br />
* [https://artofproblemsolving.com/wiki/index.php/2021_AMC_12A_Problems/Problem_15 2021 AMC 12A Problem 15]<br />
* [https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems 1981 IMO Problem 2]<br />
<br />
==See also==<br />
* [[Pascal's Triangle]]<br />
* [[Combinatorics]]<br />
* [[Pascal's Identity]]<br />
<br />
[[Category:Theorems]]<br />
<br />
[[Category:Combinatorics]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=177496User:Enderramsby2022-08-26T08:42:04Z<p>Enderramsby: /* Goals */</p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one. Please don’t spam, thanks.</font></div><br />
<center><font size="101px">12</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the categories [https://artofproblemsolving.com/wiki/index.php/Category:Probability Category:Probability], and [https://artofproblemsolving.com/wiki/index.php/Category:Users Category:Users].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 20<br />
{{User:Piphi/Template:Progress_Bar|60.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div><br />
<br />
[[Category:Users]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=177420User:Enderramsby2022-08-24T09:20:23Z<p>Enderramsby: /* User Count */</p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one. Please don’t spam, thanks.</font></div><br />
<center><font size="101px">11</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the categories [https://artofproblemsolving.com/wiki/index.php/Category:Probability Category:Probability], and [https://artofproblemsolving.com/wiki/index.php/Category:Users Category:Users].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 10<br />
{{User:Piphi/Template:Progress_Bar|-900.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div><br />
<br />
[[Category:Users]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Proof_by_contradiction&diff=177269Proof by contradiction2022-08-21T18:01:04Z<p>Enderramsby: /* Euclid's proof of the infinitude of primes */</p>
<hr />
<div>'''Proof by contradiction''' (also known as reducto ad absurdum or indirect proof) is an indirect type of proof that assumes the proposition (that which is to be proven) is false and shows that this assumption leads to an error, logically or mathematically. Thus, the proposition is true. Famous results which utilized proof by contradiction include the irrationality of <math>\sqrt{2}</math> and the infinitude of primes. <!-- If you know how, please make the following proofs look better --> This technique usually works well on problems where not a lot of information is known, and thus we can create some using proof by contradiction.<br />
<br />
== Examples ==<br />
<br />
===Proof that the square root of 2 is irrational===<br />
<br />
Assume <math>\sqrt{2}</math> is [[rational number|rational]], i.e. it can be expressed as a rational fraction of the form <math>\frac{b}{a}</math>, where <math>a</math> and <math>b</math> are two [[relatively prime]] integers. Now, since<br />
<math>\sqrt{2}=\frac{b}{a}</math>, we have <math>2=\frac{b^2}{a^2}</math>, or <math>b^2=2a^2</math>. Since <math>2a^2</math> is even, <math>b^2</math> must be even, and since <math>b^2</math> is even, so is <math>b</math>. Let <math>b=2c</math>. We have <math>4c^2=2a^2</math> and thus <math>a^2=2c^2</math>.<br />
Since <math>2c^2</math> is even, <math>a^2</math> is even, and since <math>a^2</math> is even, so is a. However, two even numbers cannot be relatively prime, so <math>\sqrt{2}</math> cannot be expressed as a rational fraction; hence <math>\sqrt{2}</math> is irrational. <math>\blacksquare</math><br />
<br />
===[[Euclid's proof of the infinitude of primes]]===<br />
<br />
Assume there exists a finite number of [[prime|primes]] <math>p_1, p_2,\ldots, p_n</math>. Let <math>N=p_1p_2p_3...p_n+1</math>. <math>N</math> is not divisible by any of the known primes since it will leave a remainder of one upon division by any one of them. Thus, <math>N</math> must be divisible by some other prime not in our list, which contradicts the assumption that there is a finite number of primes. <math>\blacksquare</math><br />
<br />
==See also==<br />
*[[Proof writing]]<br />
*[http://www.artofproblemsolving.com/articles/how-to-write-solution How to Write a Solution] by [[Richard Rusczyk]] and [[Mathew Crawford]]<br />
<br />
[[Category:Proofs]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User_talk:Enderramsby&diff=176983User talk:Enderramsby2022-08-16T04:04:53Z<p>Enderramsby: /* Welcome! */</p>
<hr />
<div>== Welcome! ==<br />
<br />
Welcome to my user talk! Feel free to ask me any (appropriate) questions here! ~[[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Talk:Euclid%27s_proof_of_the_infinitude_of_primes&diff=176928Talk:Euclid's proof of the infinitude of primes2022-08-14T15:59:36Z<p>Enderramsby: </p>
<hr />
<div>Erm... Shouldn't it be "infi<b>NI</b>tude"? [[User:Fedja|Fedja]] 18:53, 11 January 2008 (EST)<br />
Or maybe it should be infiniteness. [[User:Colball|Colball]] , 21/11/2019<br />
<br />
<br />
Actually, people didn't understand "infinity" at the time, so he said something like "take 10 of them but there are still more, 100 but still more primes, etc. ~ [[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Talk:Euclid%27s_proof_of_the_infinitude_of_primes&diff=176927Talk:Euclid's proof of the infinitude of primes2022-08-14T15:59:17Z<p>Enderramsby: </p>
<hr />
<div>Erm... Shouldn't it be "infi<b>NI</b>tude"? [[User:Fedja|Fedja]] 18:53, 11 January 2008 (EST)<br />
Or maybe it should be infiniteness. [[User:Colball|Colball]] , 21/11/2019<br />
<br />
<br />
Actually, people didn't understand "infinity" at the time, so he said something like "take 10 of them but there are still more, 100 but still more primes, etc. [[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Euclid%27s_proof_of_the_infinitude_of_primes&diff=176926Euclid's proof of the infinitude of primes2022-08-14T15:57:14Z<p>Enderramsby: /* See Also */</p>
<hr />
<div>'''Euclid's proof of the infinitude of primes''' is a classic and well-known [[proof]] by the Greek mathematician [[Euclid]] that there are infinitely many [[prime number]]s.<br />
<br />
==Proof==<br />
We proceed by [[proof by contradiction | contradiction]]. Suppose there are in fact only finitely many prime numbers, <math>p_1, p_2, p_3, \ldots, p_n</math>. Let <math>N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1</math>. Since <math>N</math> leaves a remainder of 1 when divided by any of our prime numbers <math>p_k</math>, it is not divisible by any of them. However, the [[Fundamental Theorem of Arithmetic]] states that all positive integers have a unique prime factorization. Therefore, <math>N</math> must have a prime factor (possibly itself) that is ''not'' among our set of primes, <math>\{p_1, p_2, p_3, \ldots, p_n\}</math>. This means that <math>\{p_1, p_2, p_3, \ldots, p_n \}</math> does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.<br />
<br />
==See Also==<br />
* [[Proof by contradiction]]<br />
* [[Number theory]]<br />
* [[Prime]]<br />
* [[Euclid]]<br />
<br />
[[Category:Proofs]]<br />
[[Category:Number theory]]<br />
<br />
{{stub}}</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User_talk:Michaelwenquan&diff=176925User talk:Michaelwenquan2022-08-14T15:52:25Z<p>Enderramsby: </p>
<hr />
<div>talk<br />
<br />
talk indeed. ~[[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=176924User:Enderramsby2022-08-14T15:46:41Z<p>Enderramsby: /* About Me */</p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one.</font></div><br />
<center><font size="101px">9</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the categories [https://artofproblemsolving.com/wiki/index.php/Category:Probability Category:Probability], and [https://artofproblemsolving.com/wiki/index.php/Category:Users Category:Users].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 10<br />
{{User:Piphi/Template:Progress_Bar|90.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div><br />
<br />
[[Category:Users]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Category:Users&diff=176923Category:Users2022-08-14T15:46:24Z<p>Enderramsby: </p>
<hr />
<div>For all users and user pages on the AoPS Wiki!</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Category:Users&diff=176922Category:Users2022-08-14T15:45:52Z<p>Enderramsby: Blanked the page</p>
<hr />
<div></div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=176921User:Enderramsby2022-08-14T15:45:33Z<p>Enderramsby: </p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one.</font></div><br />
<center><font size="101px">9</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the categories [https://artofproblemsolving.com/wiki/index.php/Category:Probability Category:Probability], and [https://artofproblemsolving.com/wiki/index.php/Category:Users Category:Users]].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 10<br />
{{User:Piphi/Template:Progress_Bar|90.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div><br />
<br />
[[Category:Users]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User_talk:Enderramsby&diff=176920User talk:Enderramsby2022-08-14T15:39:19Z<p>Enderramsby: /* Welcome! */</p>
<hr />
<div>== Welcome! ==<br />
<br />
Welcome to my user talk! Feel free to ask me any questions here! ~[[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User_talk:Enderramsby&diff=176919User talk:Enderramsby2022-08-14T15:38:32Z<p>Enderramsby: /* Welcome! */ new section</p>
<hr />
<div>== Welcome! ==<br />
<br />
Welcome to my user page talk! Feel free to ask me any questions here! ~[[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Euclid%27s_proof_of_the_infinitude_of_primes&diff=176915Euclid's proof of the infinitude of primes2022-08-14T03:38:21Z<p>Enderramsby: </p>
<hr />
<div>'''Euclid's proof of the infinitude of primes''' is a classic and well-known [[proof]] by the Greek mathematician [[Euclid]] that there are infinitely many [[prime number]]s.<br />
<br />
==Proof==<br />
We proceed by [[proof by contradiction | contradiction]]. Suppose there are in fact only finitely many prime numbers, <math>p_1, p_2, p_3, \ldots, p_n</math>. Let <math>N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1</math>. Since <math>N</math> leaves a remainder of 1 when divided by any of our prime numbers <math>p_k</math>, it is not divisible by any of them. However, the [[Fundamental Theorem of Arithmetic]] states that all positive integers have a unique prime factorization. Therefore, <math>N</math> must have a prime factor (possibly itself) that is ''not'' among our set of primes, <math>\{p_1, p_2, p_3, \ldots, p_n\}</math>. This means that <math>\{p_1, p_2, p_3, \ldots, p_n \}</math> does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.<br />
<br />
==See Also==<br />
* [[Number theory]]<br />
* [[Prime]]<br />
* [[Euclid]]<br />
<br />
[[Category:Proofs]]<br />
[[Category:Number theory]]<br />
<br />
{{stub}}</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Without_loss_of_generality&diff=176854Without loss of generality2022-08-11T00:43:18Z<p>Enderramsby: /* Example (from Wikipedia) */</p>
<hr />
<div><br />
<br />
<br />
==Definition==<br />
<br />
Without loss of generality, often abbreviated to WLOG, is a frequently used expression in maths. The term is used to indicate that the following proof emphasizes on a particular case, but doesn’t affect the validity of the proof in general.<br />
<br />
==Example==<br />
<br />
* If three objects are each painted either red or blue, then there must be at least two objects of the same color.<br />
<math>\textbf{Proof}</math>:<br />
<br />
Assume, <math>\textbf{without loss of generality}</math>, that the first object is red. If either of the other two objects is red, then we are finished; if not, then the other two objects must both be blue and we are still finished.<br />
<br />
The above argument works because the exact same reasoning could be applied if the first object is blue. As a result, the use of "without loss of generality" is valid in this case.<br />
<br />
== Problems using WLOG ==<br />
* [[2017_USAJMO_Problems/Problem_3 | 2017 USAJMO Problem 3]]<br />
* [[2016_AMC_12A_Problems/Problem_17 | 2016 AMC 12A Problem 17]] (See Solution 2)<br />
* [[2012_AMC_10A_Problems/Problem 23 | 2012 AMC 10A Problem 23]]<br />
<br />
== Read more ==<br />
<br />
https://en.wikipedia.org/wiki/Without_loss_of_generality<br />
<br />
https://www.cl.cam.ac.uk/~jrh13/papers/wlog.pdf<br />
<br />
<br />
{{stub}}</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Without_loss_of_generality&diff=176853Without loss of generality2022-08-11T00:43:03Z<p>Enderramsby: /* Definition (Inspired from Wikipedia) */</p>
<hr />
<div><br />
<br />
<br />
==Definition==<br />
<br />
Without loss of generality, often abbreviated to WLOG, is a frequently used expression in maths. The term is used to indicate that the following proof emphasizes on a particular case, but doesn’t affect the validity of the proof in general.<br />
<br />
== Example (from Wikipedia) ==<br />
* If three objects are each painted either red or blue, then there must be at least two objects of the same color.<br />
<math>\textbf{Proof}</math>:<br />
<br />
Assume, <math>\textbf{without loss of generality}</math>, that the first object is red. If either of the other two objects is red, then we are finished; if not, then the other two objects must both be blue and we are still finished.<br />
<br />
The above argument works because the exact same reasoning could be applied if the first object is blue. As a result, the use of "without loss of generality" is valid in this case.<br />
<br />
== Problems using WLOG ==<br />
* [[2017_USAJMO_Problems/Problem_3 | 2017 USAJMO Problem 3]]<br />
* [[2016_AMC_12A_Problems/Problem_17 | 2016 AMC 12A Problem 17]] (See Solution 2)<br />
* [[2012_AMC_10A_Problems/Problem 23 | 2012 AMC 10A Problem 23]]<br />
<br />
== Read more ==<br />
<br />
https://en.wikipedia.org/wiki/Without_loss_of_generality<br />
<br />
https://www.cl.cam.ac.uk/~jrh13/papers/wlog.pdf<br />
<br />
<br />
{{stub}}</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Without_loss_of_generality&diff=176852Without loss of generality2022-08-11T00:42:25Z<p>Enderramsby: </p>
<hr />
<div><br />
<br />
<br />
== Definition (Inspired from Wikipedia) ==<br />
Without loss of generality, often abbreviated to WLOG, is a frequently used expression in maths. The term is used to indicate that the following proof emphasizes on a particular case, but doesn’t affect the validity of the proof in general.<br />
<br />
== Example (from Wikipedia) ==<br />
* If three objects are each painted either red or blue, then there must be at least two objects of the same color.<br />
<math>\textbf{Proof}</math>:<br />
<br />
Assume, <math>\textbf{without loss of generality}</math>, that the first object is red. If either of the other two objects is red, then we are finished; if not, then the other two objects must both be blue and we are still finished.<br />
<br />
The above argument works because the exact same reasoning could be applied if the first object is blue. As a result, the use of "without loss of generality" is valid in this case.<br />
<br />
== Problems using WLOG ==<br />
* [[2017_USAJMO_Problems/Problem_3 | 2017 USAJMO Problem 3]]<br />
* [[2016_AMC_12A_Problems/Problem_17 | 2016 AMC 12A Problem 17]] (See Solution 2)<br />
* [[2012_AMC_10A_Problems/Problem 23 | 2012 AMC 10A Problem 23]]<br />
<br />
== Read more ==<br />
<br />
https://en.wikipedia.org/wiki/Without_loss_of_generality<br />
<br />
https://www.cl.cam.ac.uk/~jrh13/papers/wlog.pdf<br />
<br />
<br />
{{stub}}</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=JMPSC&diff=176835JMPSC2022-08-10T03:32:28Z<p>Enderramsby: </p>
<hr />
<div>Junior Mathematicians' Problem Solving Competition:<br />
<br />
JMPSC was founded to introduce students to competition math, and their team consists of some very talented individuals, ranging from AMC 10 perfect scorers, Mathcounts Nationals qualifiers, and IMO qualifiers. They have held two contests now, and their problems and more information can be found on their website at jmpsc.xyz</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Talk:Primitive_Pythagorean_Triple&diff=176834Talk:Primitive Pythagorean Triple2022-08-10T02:42:46Z<p>Enderramsby: </p>
<hr />
<div>This page seems broken, could somebody please fix? Thanks.<br />
<br />
~[[User:Enderramsby|enderramsby]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Category:Users&diff=176645Category:Users2022-08-03T20:03:11Z<p>Enderramsby: Created page with "For all Users on AoPS!"</p>
<hr />
<div>For all Users on AoPS!</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=176644User:Enderramsby2022-08-03T19:58:57Z<p>Enderramsby: /* About Me */</p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one.</font></div><br />
<center><font size="101px">9</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the category [https://artofproblemsolving.com/wiki/index.php/Category:Probability Category:Probability].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 10<br />
{{User:Piphi/Template:Progress_Bar|90.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div></div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=176643User:Enderramsby2022-08-03T19:55:21Z<p>Enderramsby: /* About Me */</p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one.</font></div><br />
<center><font size="101px">9</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the category [[Category:Probability]].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 10<br />
{{User:Piphi/Template:Progress_Bar|90.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div></div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=User:Enderramsby&diff=176642User:Enderramsby2022-08-03T19:55:03Z<p>Enderramsby: </p>
<hr />
<div>enderramsby's Avatar:<br />
<br />
[[File:enderramsby avatar.jpeg|center]]<br />
<br />
<br><br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">User Count</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black">If this is your first time visiting this page, edit it by increasing the user count below by one.</font></div><br />
<center><font size="101px">9</font></center><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">About Me</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
enderramsby is mod on the python-forum.py and the C++ Forum!<br />
<br />
enderramsby has created the pages [[Bayes' Theorem]] and [[Carmichael number]].<br />
<br />
enderramsby has created the category [[Category:Probability|probability]].<br />
<br />
enderramsby's highest score for AMC 8 is 19 and highest score for AMC 10 is 75.<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Goals</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
A User Count of 10<br />
{{User:Piphi/Template:Progress_Bar|90.0|width=100%}}<br><br />
<br />
A Perfect AMC 8 Score<br />
{{User:Piphi/Template:Progress_Bar|76.0|width=100%}}<br><br />
<br />
An AMC 10 Score over 100 points<br />
{{User:Piphi/Template:Progress_Bar|75.0|width=100%}}<br />
</font></div><br />
</div><br />
<br />
==<font color="black" style="font-family: ITC Avant Garde Gothic Std, Verdana"><div style="margin-left:10px">Last Visited</div></font>==<br />
<div style="margin-left: 10px; margin-bottom:10px"><font color="black"><br />
{{CURRENTDAYNAME}}, {{CURRENTMONTHNAME}} {{CURRENTDAY}}, {{CURRENTYEAR}}, {{CURRENTTIME}} (UTC).<br><br />
Note: this is only for enderramsby's last visit to the page, not yours.</font></div><br />
</div></div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Category:Probability&diff=176641Category:Probability2022-08-03T19:53:49Z<p>Enderramsby: </p>
<hr />
<div>For math concepts, problems, and theorems related to [[probability]].</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176640Carmichael number2022-08-03T19:52:40Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]] that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> Carmichael numbers are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
<br />
~ [[User:Enderramsby|enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Linear_congruence&diff=176639Linear congruence2022-08-03T19:52:05Z<p>Enderramsby: </p>
<hr />
<div>A '''Linear Congruence''' is a [[congruence]] [[modular arithmetic|mod]] p of the form <br />
<cmath>ax+b\equiv c\pmod{p}</cmath><br />
where <math>a</math>, <math>b</math>, <math>c</math>, and <math>p</math> are [[constant]]s and <math>x</math> is the [[variable]] to be solved for.<br />
<br />
==Solving==<br />
Note that not every linear congruence has a solution. For instance, the congruence equation <math>2x\equiv3\pmod8</math> has no solutions. A solution is guaranteed [[iff]] <math>a</math> is [[relatively prime]] to <math>p</math>. If <math>a</math> and <math>p</math> are not relatively prime, let their [[greatest common divisor]] be <math>d</math>; then:<br />
* if <math>d</math> [[divide]]s <math>b</math>, there will be a solution <math>\pmod{\frac{p}{d}}</math><br />
* if <math>d</math> does not divide <math>b</math>, there will be no solution<br />
<br />
==Example==<br />
===Problem===<br />
Given <math>5x\equiv7\pmod8</math>, find <math>x</math>.<br />
<br />
===Solution 1===<br />
<math>7\equiv15\pmod8</math>, so <math>5x\equiv15\pmod8</math>. Thus, <math>x\equiv3\pmod 8</math>. Note that we can divide by <math>5</math> because <math>5</math> and <math>8</math> are relatively prime.<br />
<br />
===Solution 2===<br />
Multiply both sides of the congruence by <math>5</math> to get <math>25x\equiv35\pmod8</math>. Since <math>25\equiv1\pmod8</math> and <math>35\equiv3\pmod8</math>, <math>x\equiv3\pmod8</math>.<br />
<br />
[[Category:Number theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%E2%80%99s_Last_Theorem&diff=176595Fermat’s Last Theorem2022-08-02T22:29:21Z<p>Enderramsby: Redirected page to Fermat's Last Theorem</p>
<hr />
<div>#REDIRECT [[Fermat's Last Theorem]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Pierre_de_Fermat&diff=176594Pierre de Fermat2022-08-02T22:22:28Z<p>Enderramsby: /* See Also */</p>
<hr />
<div>{{WotWAnnounce|week=July 25-July 31}}<br />
<br />
'''Pierre de Fermat''' (August 17, 1601 – January 12, 1665) was a French magistrate and government official. He, however, is most famous for being an amateur mathematician. His name is attached to several results in number theory, though he worked in many other areas of mathematics as well. <br />
<br />
Fermat had a respectable background, and had a formal education, rare for the time. He became a civil servant in both the executive and judicial branches of his provincial government, and rose rapidly in the ranks of his peers due to his prowess at the job and an illness that was taking the life of many of his colleagues. He continued serving in these positions until he died.<br />
<br />
The work Fermat produced spanned many different areas of mathematics; however, he worked most and was most famous for his accomplishments in number theory. The best-known problem he posed is known as [[Fermat's Last Theorem]], which remained unsolved for hundreds of years. Fermat claimed to have a proof for this problem, but this is doubtful. Other notable areas which Fermat worked in were [[analytic geometry]] and laying the foundations of [[calculus]]<br />
<br />
==Biography==<br />
Pierre de Fermat was born in the town of Beaumont-deLomagne, in the south-western portion of France. His father (named Dominique) was a rich merchant who was involved in the leather industry, and thus Fermat was able to enjoy a formal education. He attended the Franciscan monastery in Grandselve and then the University of Toulouse. No record shows that he was particularly adept with numbers.<br />
<br />
His family urged him to take a career in the civil service, and he complied, being appointed ''conseiller au Parlement de Toulouse'' (councilor of the Chamber of Petitions of Toulouse) in 1631. This job entailed hearing locals who wished to petition the king and either approving or declining their requests. Fermat's duties also included enforcing royal decrees; in a sense, he was the link between the royal government and the province of Toulouse. He was very efficient in this job as well as another judiciary career as a magistrate in the side. <br />
<br />
This efficiency, as well as a plague that was killing off his superior colleagues (Fermat himself fell ill in 1652; and in fact one of his colleagues announced his death prematurely) enabled him to be promoted rapidly; and he became a minor sort of nobility; permitting him to add "de" to his name. Fermat survived both the plague and the political intrigues common of the era, particularly those relating to Cardinal Richelieu.<br />
<br />
Fermat signed his last judicial notice on January 9, 1665, in the town of Castres. He died three days later.<br />
<br />
==Work==<br />
While serving in his civil duties, Fermat was inspired to mathematics by a copy of Diophantus's ''Arithmetica''. Fermat henceforth became fascinated with number theory and mathematics in general.<br />
<br />
Fermat's was rather secretive, and enjoyed taunting other mathematicians in correspondence (which he sent quite a lot of) about a theorem which he had discovered the proof to without actually providing the proof. He would often write tantalizing notes in the margins of works, giving a conjecture without proof. Sometimes he would claim that he had discovered a proof to the theorem or even give a few hints as to the proof; sometimes he would do no such thing.<br />
<br />
While Fermat mostly worked in number theory, he also invented [[analytic geometry]] independently and prior to Rene Descartes (though he did not publish his work, which is why Descartes receives most of the credit). Furthermore, he found a method of drawing tangents to parabolas in the form <math>f(x)=x^n</math> (or ''parabolas of Fermat'') and hyperbolas in the form <math>f(x)=\frac{1}{x^n}</math> (or ''hyperbolas of Fermat''), thus laying the foundations for [[calculus]].<br />
<br />
All of Fermat's theorems were either proven or shown to be false by [[Leonhard Euler]] years later, except for one. This theorem came to be known as [[Fermat's Last Theorem]], not because it was the last problem he posed (far from it; he first wrote about it in 1637, relatively early in his career), but because it was the last remaining problem that was unsolved. Fermat had written in the margin of the ''Arithmetica'', "I have discovered a truly marvelous proof, which this margin is too narrow to contain". Many failed attempts and advances were made over the next few hundred years towards it, yet no one solved it. A prize of 100,000 German marks was offered for the problem (though this became laughably devalued during the German hyperinflation following World War I), and many pseudo-mathematicians sent in obviously flawed solutions.<br />
<br />
Eventually, in 1993, [[Andrew Wiles]] furnished a proof, after eight years of work, which relied on many modern techniques. However, a flaw was discovered soon after. Wiles managed to correct the proof by October 1994, thus solving the last of Fermat's problems. It is doubtful that Fermat managed to furnish a proof due to the many concepts of modern mathematics in Wiles' proof, and many mathematicians now believe that Fermat only had a flawed proof.<br />
<br />
==See Also==<br />
*[[Fermat point]]<br />
*[[Fermat's Little Theorem]]<br />
*[[Fermat’s Last Theorem]]<br />
<br />
==References==<br />
*Singh, Simon (1997). Walker and Company; New York. ''Fermat's Enigma''. ISBN 0-8027-1331-9.<br />
<br />
[[Category:Famous mathematicians]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176593Carmichael number2022-08-02T22:19:42Z<p>Enderramsby: /* Carmichael numbers */</p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]] that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> Carmichael numbers are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
<br />
~ [[User:Enderramsby|enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176592Carmichael number2022-08-02T22:15:13Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> Carmichael numbers are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
<br />
~ [[User:Enderramsby|enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Category:Probability&diff=176577Category:Probability2022-08-02T16:33:01Z<p>Enderramsby: Created page with "For math concepts, problems, and theorems related to probability."</p>
<hr />
<div>For math concepts, problems, and theorems related to probability.</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Bayes%27_Theorem&diff=176576Bayes' Theorem2022-08-02T16:32:21Z<p>Enderramsby: </p>
<hr />
<div>==Bayes' Theorem:==<br />
<br />
Let <math>E_1</math> and <math>E_2</math> be two events, and <math>P(E_1 | E_2)</math> the [[probability]] of <math>E_1</math> dependent on <math>E_2.</math> Then <cmath>P(E_1 | E_2) = \dfrac{P(E_2 | E_1) \cdot P(E_1)}{P(E_2)}.</cmath><br />
<br />
~[[User:Enderramsby|enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Probability]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176575Carmichael number2022-08-02T16:31:38Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
<br />
~ [[User:Enderramsby|enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176574Carmichael number2022-08-02T16:31:20Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[User:Enderramsby|enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176573Carmichael number2022-08-02T16:30:59Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[enderramsby|User:Enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176572Carmichael number2022-08-02T16:29:12Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
<cmath>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</cmath><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[User:Enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176571Carmichael number2022-08-02T16:28:46Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
<math>\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}</math><br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[User:Enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176570Carmichael number2022-08-02T16:28:29Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
\begin{align}<br />
561 &= 3 \cdot 11 \cdot 17 \\<br />
1105 &= 5 \cdot 13 \cdot 17 \\<br />
1729 &= 7 \cdot 13 \cdot 19 \\<br />
2465 &= 5 \cdot 17 \cdot 29 \\<br />
2821 &= 7 \cdot 13 \cdot 31 \\<br />
6601 &= 7 \cdot 23 \cdot 41 \\<br />
8991 &= 7 \cdot 19 \cdot 67.<br />
\end{align}<br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[User:Enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176569Carmichael number2022-08-02T16:26:08Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
\begin{align}<br />
561 = & 3 \cdot 11 \cdot 17 \\<br />
1105 = & 5 \cdot 13 \cdot 17 \\<br />
1729 = & 7 \cdot 13 \cdot 19 \\<br />
2465 = & 5 \cdot 17 \cdot 29 \\<br />
2821 = & 7 \cdot 13 \cdot 31 \\<br />
6601 = & 7 \cdot 23 \cdot 41 \\<br />
8991 = & 7 \cdot 19 \cdot 67<br />
\end{align}<br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[User:Enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Carmichael_number&diff=176568Carmichael number2022-08-02T16:25:27Z<p>Enderramsby: </p>
<hr />
<div>==Carmichael numbers==<br />
<br />
A [[Carmichael number]] is a [[composite number]]s that satisfies [[Fermat's Little Theorem]], <math>a^p \equiv a \pmod{p}.</math>or <math>a^{p - 1} \equiv 1 \pmod{p}.</math> In this case, <math>p</math> is the Carmichael number.<br />
<br />
The first <math>7</math> are:<br />
<br />
\begin{align*}<br />
561 = & 3 \cdot 11 \cdot 17 \\<br />
1105 = & 5 \cdot 13 \cdot 17 \\<br />
1729 = & 7 \cdot 13 \cdot 19 \\<br />
2465 = & 5 \cdot 17 \cdot 29 \\<br />
2821 = & 7 \cdot 13 \cdot 31 \\<br />
6601 = & 7 \cdot 23 \cdot 41 \\<br />
8991 = & 7 \cdot 19 \cdot 67<br />
\end{align*}<br />
<br />
==See Also==<br />
<br />
* [[Fermat's Little Theorem]]<br />
* [[Carmichael function]]<br />
<br />
~ [[User:Enderramsby]]<br />
<br />
<br />
{{stub}}<br />
<br />
[[Category:Number Theory]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Bayes%E2%80%99_Theorem&diff=176563Bayes’ Theorem2022-08-02T15:52:29Z<p>Enderramsby: Redirected page to Bayes' Theorem</p>
<hr />
<div>#REDIRECT [[Bayes' Theorem]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%E2%80%99s_little_theorem&diff=176562Fermat’s little theorem2022-08-02T15:51:23Z<p>Enderramsby: Changed redirect target from Fermat’s Little Theorem to Fermat's Little Theorem</p>
<hr />
<div>#REDIRECT [[Fermat's Little Theorem]]</div>Enderramsbyhttps://artofproblemsolving.com/wiki/index.php?title=Fermat%E2%80%99s_little_theorem&diff=176561Fermat’s little theorem2022-08-02T15:50:30Z<p>Enderramsby: Redirected page to Fermat’s Little Theorem</p>
<hr />
<div>#REDIRECT [[Fermat’s Little Theorem]]</div>Enderramsby