Difference between revisions of "User:Idk12345678"
Idk12345678 (talk | contribs) (→==) |
Idk12345678 (talk | contribs) |
||
Line 1: | Line 1: | ||
− | + | ==My Solutions== | |
[https://artofproblemsolving.com/wiki/index.php/2001_AMC_10_Problems/Problem_10#Solution_3.28strategic_guess_and_check.29 2001 AMC 10 Problem 10] | [https://artofproblemsolving.com/wiki/index.php/2001_AMC_10_Problems/Problem_10#Solution_3.28strategic_guess_and_check.29 2001 AMC 10 Problem 10] | ||
Line 33: | Line 33: | ||
[https://artofproblemsolving.com/wiki/index.php/2024_AIME_I_Problems/Problem_2#Solution_5 2024 AIME I Problem 2] | [https://artofproblemsolving.com/wiki/index.php/2024_AIME_I_Problems/Problem_2#Solution_5 2024 AIME I Problem 2] | ||
− | + | ==Some Proofs I wrote== | |
− | ==<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 00:01, 7 June 2024
My Solutions
Some Proofs I wrote
if
is prime.
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
. Because
,
, which is divisible by
, so the original expression must be divisible by
. However if
is prime,
, since
does not contain
(because
). Therefore, in order for
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
if
is prime.