Difference between revisions of "User:Idk12345678"

(==)
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 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===
+
==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 23:01, 6 June 2024

My Solutions

2001 AMC 10 Problem 10

2001 AMC 10 Problem 12

2002 AIME II Problem 3

2005 AIME II Problem 5

2008 AMC 10B Problem 3

2008 AMC 10B Problem 6

2008 AMC 10B Problem 9

2008 AIME II Problem 1

2009 AMC 10A Problem 10

2009 AIME II Problem 2

2013 AMC 10A Problem 16

2014 AMC 10B Problem 9

2018 AMC 10A Problem 10

2020 AMC 10A Problem 14

2023 AIME I Problem 2

2024 AIME I Problem 2

Some Proofs I wrote

$(x+y)^n \equiv x^n + y^n \pmod{n}$ if $n$ is prime.

Proof: Expanding $(x+y)^n$ out, all the coefficients are of the form $n \choose r$ by the binomial theorem. To prove the original result we must show that if $r \neq 1$ and $r \neq n$, then \[{n \choose r} \equiv 0 \pmod{n}\]. Because \[{n \choose r} = \frac{n!}{r!(n-r)!}\], \[{n \choose r} \times r!(n-r)! = n!\], which is divisible by $n$, so the original expression must be divisible by $n$. However if $n$ is prime, \[\gcd(n, r!(n-r)!) = 1\], since $r!$ does not contain $n$(because $r<n$). Therefore, in order for \[{n \choose r} \times r!(n-r)!\] to be divisible by $n$, $n \choose r$ is divisible by $n$. All the coefficients of the expansion(besides the coefficients of $x^n$ and $y^n$) are of the form $n \choose r$, and \[{n \choose r} \equiv 0 \pmod{n}\], so they cancel out and \[(x+y)^n \equiv x^n + y^n \pmod{n}\] if $n$ is prime. $\square$