Difference between revisions of "User:Idk12345678"
Idk12345678 (talk | contribs) |
Idk12345678 (talk | contribs) (→==) |
||
| Line 37: | Line 37: | ||
==<math>(x+y)^n \equiv x^n + y^n \pmod{n}</math> if <math>n</math> is prime. == | ==<math>(x+y)^n \equiv x^n + y^n \pmod{n}</math> if <math>n</math> is prime. == | ||
Proof: Expanding <math>(x+y)^n</math> out, all the coefficients are of the form <math>n \choose r</math> by the binomial theorem. To prove the original result we must show that if <math>r \neq 1</math> and <math>r \neq n</math>, then <cmath>{n \choose r} \equiv 0 \pmod{n}</cmath>. Because <cmath>{n \choose r} = \frac{n!}{r!(n-r)!}</cmath>, <cmath>{n \choose r} \times r!(n-r)! = n!</cmath>, which is divisible by <math>n</math>, so the original expression must be divisible by <math>n</math>. However if <math>n</math> is prime, <cmath>\gcd(n, r!(n-r)!) = 1</cmath>, since <math>r!</math> does not contain <math>n</math>(because <math>r<n</math>). Therefore, in order for <cmath>{n \choose r} \times r!(n-r)!</cmath> to be divisible by <math>n</math>, <math>n \choose r</math> is divisible by <math>n</math>. All the coefficients of the expansion(besides the coefficients of <math>x^n</math> and <math>y^n</math>) are of the form <math>n \choose r</math>, and <cmath>{n \choose r} \equiv 0 \pmod{n}</cmath>, so they cancel out and <cmath>(x+y)^n \equiv x^n + y^n \pmod{n}</cmath> if <math>n</math> is prime. <math>\square</math> | Proof: Expanding <math>(x+y)^n</math> out, all the coefficients are of the form <math>n \choose r</math> by the binomial theorem. To prove the original result we must show that if <math>r \neq 1</math> and <math>r \neq n</math>, then <cmath>{n \choose r} \equiv 0 \pmod{n}</cmath>. Because <cmath>{n \choose r} = \frac{n!}{r!(n-r)!}</cmath>, <cmath>{n \choose r} \times r!(n-r)! = n!</cmath>, which is divisible by <math>n</math>, so the original expression must be divisible by <math>n</math>. However if <math>n</math> is prime, <cmath>\gcd(n, r!(n-r)!) = 1</cmath>, since <math>r!</math> does not contain <math>n</math>(because <math>r<n</math>). Therefore, in order for <cmath>{n \choose r} \times r!(n-r)!</cmath> to be divisible by <math>n</math>, <math>n \choose r</math> is divisible by <math>n</math>. All the coefficients of the expansion(besides the coefficients of <math>x^n</math> and <math>y^n</math>) are of the form <math>n \choose r</math>, and <cmath>{n \choose r} \equiv 0 \pmod{n}</cmath>, so they cancel out and <cmath>(x+y)^n \equiv x^n + y^n \pmod{n}</cmath> if <math>n</math> is prime. <math>\square</math> | ||
| − | |||
| − | |||
Revision as of 23:00, 6 June 2024
My Solutions
Some Proofs I wrote
if 
is prime.
if Proof: Expanding 
out, all the coefficients are of the form 
by the binomial theorem. To prove the original result we must show that if 
and 
, then ![\[{n \choose r} \equiv 0 \pmod{n}\]](http://latex.artofproblemsolving.com/c/6/3/c63848a8ef72c7440c7022bd218dad3ced5ab858.png)
. Because ![\[{n \choose r} = \frac{n!}{r!(n-r)!}\]](http://latex.artofproblemsolving.com/3/c/a/3ca41bab24e0ced5a3bd2665f4e96651799fe7cc.png)
, ![\[{n \choose r} \times r!(n-r)! = n!\]](http://latex.artofproblemsolving.com/7/b/e/7bef983037ba8643bc0efb980a61e51f9e25e8b3.png)
, which is divisible by 
, so the original expression must be divisible by . However if is prime, ![\[\gcd(n, r!(n-r)!) = 1\]](http://latex.artofproblemsolving.com/0/d/0/0d095da7ac98ad36f4c2dd61cc45e45e38906992.png)
, since 
does not contain (because 
). Therefore, in order for ![\[{n \choose r} \times r!(n-r)!\]](http://latex.artofproblemsolving.com/6/a/b/6abc4a965f1ab5a8620d40b4d393876dded1647b.png)
to be divisible by , is divisible by . All the coefficients of the expansion(besides the coefficients of 
and 
) are of the form , and , so they cancel out and ![\[(x+y)^n \equiv x^n + y^n \pmod{n}\]](http://latex.artofproblemsolving.com/3/c/1/3c1d9f3704248e7d2b3af8c5b48ebf8acbcd48b6.png)
if is prime. 
