Difference between revisions of "User:Idk12345678"
Idk12345678 (talk | contribs) (→My Solutions) |
Idk12345678 (talk | contribs) |
||
(5 intermediate revisions by the same user not shown) | |||
Line 17: | Line 17: | ||
[https://artofproblemsolving.com/wiki/index.php/2008_AIME_II_Problems/Problem_1#Solution_4 2008 AIME II Problem 1] | [https://artofproblemsolving.com/wiki/index.php/2008_AIME_II_Problems/Problem_1#Solution_4 2008 AIME II Problem 1] | ||
− | [https://artofproblemsolving.com/wiki/index.php/2009_AMC_10A_Problems/Problem_10 2009 AMC 10A Problem 10] | + | [https://artofproblemsolving.com/wiki/index.php/2009_AMC_10A_Problems/Problem_10#Solution_5 2009 AMC 10A Problem 10] |
+ | |||
+ | [https://artofproblemsolving.com/wiki/index.php/2009_AIME_II_Problems/Problem_2#Solution_3 2009 AIME II Problem 2] | ||
[https://artofproblemsolving.com/wiki/index.php/2013_AMC_10A_Problems/Problem_16#Solution_3 2013 AMC 10A Problem 16] | [https://artofproblemsolving.com/wiki/index.php/2013_AMC_10A_Problems/Problem_16#Solution_3 2013 AMC 10A Problem 16] | ||
[https://artofproblemsolving.com/wiki/index.php/2014_AMC_10B_Problems/Problem_9#Solution_3 2014 AMC 10B Problem 9] | [https://artofproblemsolving.com/wiki/index.php/2014_AMC_10B_Problems/Problem_9#Solution_3 2014 AMC 10B Problem 9] | ||
+ | |||
+ | [https://artofproblemsolving.com/wiki/index.php/2018_AMC_10A_Problems/Problem_10#Solution_2 2018 AMC 10A Problem 10] | ||
[https://artofproblemsolving.com/wiki/index.php/2020_AMC_10A_Problems/Problem_14#Solution_11 2020 AMC 10A Problem 14] | [https://artofproblemsolving.com/wiki/index.php/2020_AMC_10A_Problems/Problem_14#Solution_11 2020 AMC 10A Problem 14] | ||
Line 28: | Line 32: | ||
[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. === | ||
+ | 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> |
Latest 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.