User:Idk12345678

My Solutions

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$

Page

Toolbox

Search

User:Idk12345678

My Solutions

Some Proofs I wrote

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

Page

Toolbox

Search

User:Idk12345678

My Solutions

Some Proofs I wrote

if is prime.

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