Difference between revisions of "User:Idk12345678"
Idk12345678 (talk | contribs) (→My Solutions) |
Idk12345678 (talk | contribs) |
||
Line 1: | Line 1: | ||
− | ==My Solutions== | + | ===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 32: | 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> | ||
+ | |||
+ | ==== |
Revision as of 23:00, 6 June 2024
Contents
[hide]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.