**30. (Preliminary for T, April 10; finalized Sat, April 21) Let p be prime. Show that for all natural numbers n and elements x,y of the finite field Fp , we have (x+y)pn=xpn+ypn.**

We begin by inducting on $n$:

Base case: n=1

$\Longrightarrow (x+y)^{p}= \sum_{i=0}^{p}\left(\begin{smallmatrix} p\\ i\end{smallmatrix}\right)x^{p-i}y^{i}$

$= x^p+y^p +\left[\sum_{i=1}^{p-1}\left(\begin{smallmatrix} p\\ i\end{smallmatrix}\right)(x^{p-i})(y^i)\right]$

$=x^p+y^p+p\sum_{i-1}^{p-1}\frac{(p-1)!}{i!(p-i)!}x^{p-i}y^i$

Note that $p\sum_{i-1}^{p-1}\frac{(p-1)!}{i!(p-i)!}x^{p-i}y^i \equiv 0\bmod p$

$\Longrightarrow (x+y)^{p} = x^p+y^p$

Inductive Hypothesis: Now assume that for up to $n=k$ that $(x+y)^{p^{k}}=x^{p^{k}}+y^{p^{k}}$

Inductive step: Check that it works for $n=k+1$.

We want to show that $(x+y)^{p^{k+1}}=x^{p^{k+1}}+y^{p^{k+1}}$

$\Longrightarrow (x+y)^{p^{k+1}}=((x+y)^{p^{k}})^{p}$

$= (x^{p^{k}}+y^{p^{k}})^{p}$

$=x^{p^{k+1}}+y^{p^{k+1}}$

**31. (Preliminary for T, April 10; finalized Sat, April 21) a. Let f:R→S be a ring homomorphism, let A and I be a subring and ideal of R, and let B and J be a subring and ideal of S. Is the image f(A) of A in S necessarily a subring? Is the image f(I) necessarily an ideal? Likewise, is the preimage f−1(B) of B in R necessarily a subring? Is the preimage f−1(J) necessarily an ideal? For each question, either prove the assertion or give a counterexample.**

First part: True. Suppose $a,b\in B$.

We then can suppose that $a=f(c)$ for some $c\in A$ and there is some $b=f(d)$ for some $d\in A$.

We know that since A is a subring that $c+d$ and $c\cdot d$ are both in A. So then $f(c+d), f(c\cdot d)\in B$.

So then we know that since f is a ring homomorphism, that $f(c+d)=f(c)+f(d) = a+b\in B$.

Similarly, $f(c\cdot d)=a\cdot b\in B$.

Now suppose there is $a\in A$, then $a-a\in A$.

$\Longrightarrow f(a-a)\in B$

$\Longrightarrow f(a-a)=f(a)-f(a)=0\in B$.

Second part: False, Consider the homomorphic map $A: \mathbb{Q} \to \mathbb{Q}[x]$.

We know that $\mathbb{Q}$ is an ideal.

However, $A(\mathbb{Q})\neq \mathbb{Q}[x]$ as $A$ only maps $\mathbb{Q}$ to itself which is a subset of $\mathbb{Q}[x]$ which is not an ideal.

**b. Prove the First Isomorphism Theorem for Rings: If φ:R→S is a ring homomorphism, then R/ker (φ)≅φ(R).**

Let $\phi:R\to S$ be a ring homomorphism. If $r\in R$ and $r′\in ker(\phi)$, then we have $rr′,r′r\in ker(\phi)$ (so that it is closed under multiplication by elements of R) since

$\phi(rr′)=\phi(r)φ(r′)=\phi(r)0=0=0\phi(r)=\phi(r′)\phi(r)=\phi(r′r)$

since $ker(\phi)$ is also a subring of R, it is an ideal of R. It's clear that $\phi(R)$ is a subring of S. Now, let I be an ideal of R, so that R/I is also a ring, and define $\pi:R→R/I$ $\pi(r)=r+I$. We know $\pi$ is a group homomorphism with kernel I, and for $r,s\in R$, we have

$\pi(rs)=(rs)+I=(r+I)(s+I)=\pi(r)π(s)$,

so that $\pi$ is a ring homomorphism.

Define then $\Phi:R/ker(\phi)→\phi(R)$ by

$\Phi(r+(ker(\Phi)))=\phi(r)$,

for each $(r+(ker(\Phi)))\in R/ker(\phi)$, for some $r\in R$. This is well defined because if $r′\in (r+(ker\phi))$, then

$\Phi(r′+(ker\phi))=\phi(r′)=\phi(r)=\Phi(r+(kerφ))$.

Also, this is a ring isomorphism because for each $\phi(S)\in \phi(R)$ for some $S\in R$, we have

$\Phi^{-1}(\phi (s))=\Phi^{−1} (\phi [r+(ker\phi )])=\Phi^{-1} (\phi [\pi^{−1}{r+(ker\phi )}])=(r+(ker\phi ))$,

a set with a single element of $R/ker\phi$, so that it is a bijection, and for every $r+(ker\phi),r′+(ker\phi)\in R/ker\phi$, for some $r,r′\in R$, we have

$\Phi[(r+(ker\phi))+(r′+(ker\phi))]=\Phi [(r+r′)+(ker\phi)]=\phi (r+r′)=\phi(r)+\phi(r′)=\Phi[r+(ker\phi)]+\Phi [r′+(ker\phi )]$,

and

$\Phi[(r+(ker\phi))(r′+(ker\phi))]=\Phi[(rr′)+(ker\phi)]=\phi(rr′)=\phi(r)\phi(r′)=ϕ[r+(ker\phi)]ϕ[r′+(ker\phi)]$,

so that it is a ring homomorphism.

**32. (Preliminary for T, April 10; finalized Sat, April 21) Let p be a prime. It is a fact that for each k≥1 there is a unique (up to isomorphism) finite field of cardinality pk, denoted Fpk. Prove that there is no surjective ring homomorphism from Z onto Fpk for k>1. (Hint: Use the First Isomorphism Theorem for Rings and suppose toward contradiction there were a surjective ring homomorphism φ from Z onto Fpk for some k>1. Think about Z modulo the kernel of φ and what ideals of various kinds look like in Z.)**

To show there is no surjective ring homomorphism, we first suppose towards contradiction that there is a surjective ring homomorphism

$\phi: \mathbb{Z} \to \mathbb{F}_{p^k}$ for some $k>1$. Since it is a ring homomorphism, then $\mathbb{Z}/ker(\phi) \simeq \mathbb{F}_{p^k}$

By using the results from number 28 that R/I is a field if R is maximal, we realize that there can not be a surjective ring homomorphism because a although $\mathbb{Z}/ker\phi$ is a field, it is not maximal, so it is not surjective.

**33. 33. (Preliminary for Th, April 12; finalized Sat, April 21) Let p be a prime.
a. Prove that if [0]≠[a]∈Fp, then {[a],[2a],…,[(p−1)a]}=F×p.**

Since $\mathbb{F}_{p}$ is a field, then all nonzero elements have an inverse, so it suffices to show $\mathbb{F}_p^\times$ all nonzero elements of $\mathbb{F}_p$. Clearly $\mathbb{F}_p^\times$ has p-1 elements. Without loss of generality, take $(p-b)a$ and $(p-c)a$ such that $0<b,c<p$ and $b\neq c$.

$(p-b)a-(p-c)a = pa-pa-ba+ca = a(c-b)$

Since we assumed that b is not equal to c, we know that $a(c-b) \in p\mathbb{Z}$

So $(p-b)a \nsim (p-c)a$

**b. Prove Fermat's little theorem: if [0]≠[a]∈Fp , then [a]p−1=[1]. (Hint: Try multiplying [a]⋅[2a]⋅⋯⋅[(p−1)a] and use part a.)
Since $\mathbb{F}_p^\times$ is the set of all units, every unit has a unique inverse, then multiplying all elements of $\mathbb{F}_p^\times$ results in $[1]$.**

$[a]\cdot [2a] \cdots [(p-1)a] = [1]$

$([1]\cdot [2] \cdots [(p-1)])\cdot ([a])^{p-1} = [1]$

$[1]\cdot [a]^{p-1}=[1]$

$\Longrightarrow [a]^{p-1}=[1]$

**c. Consider the polynomial ring Fp[x] and the ring of polynomial functions FuncFp[x] defined in class. Prove that the rings Fp[x] and FuncFp[x] are not isomorphic. There are a couple of ways to prove this; however you do it, also find two distinct polynomials in Fp[x] that yield the same function. (Hint: use part b.)**

Need to show that it is not injective.

Take $x^{p-1} \mapsto (a\mapsto [1])$

No matter what you put for $x$, it will go to 1 as well as $0\mapsto [0]$

For example: $(x^{p-1})^2 = x^{2p-2} \mapsto (a\mapsto [1])$

[0]\mapsto [0]

**d. Prove that in contrast, the polynomial ring Q[x] is isomorphic to the ring of polynomial functions FuncQ[x]. (You only have to show injectivity of the natural map from Q[x] into FuncQ[x] since we took care of the other requirements in class.)**

Need to show injectivity.

So suppose we have two distinct polynomials that when mapped by some mapping $\phi$, that they map to the same function in FuncQ[x]. We know that this mapping is surjective. However suppose the mapping maps some polynomial to a function such as $a_n(a)^n+\cdots +a_1(a) + a_0$. Any distinct polynomials $a_n(y)^n+\cdots + a_1(y)+a_0$ and $a_n(x)^n+\cdots + a_1(x)+a_0$ mapped to the same function will mean that x=y=n so then it is injective as the polynomials are equal if they go to the same polynomial.

**34. (Preliminary for T, April 17; finalized Sat, April 21)
a. State and prove the Chinese Remainder Theorem for integer congruences.**

Write the first congruence as an equation in Z, say $x = a + my$ for some

$y \in \mathbb{Z}$. Then the second congruence is the same as

$a + my ≡ b \bmod n$.

Subtracting a from both sides, we get

$my \equiv b − a \bmod n$

Since $(m, n) = 1$, we know $m \bmod n$ is invertible. Let $m'$ be an inverse for $m \bmod n$,

so $mm' \equiv 1 \bmod n$. Multiplying through by $m'$

, we have $y \equiv m'(b − a) \bmod n$, so

$y ≡ m'(b − a) + nz$ where z \in \mathbb{Z}$]].

Then

$x = a + my = a + m(m'(b − a) + nz) = a + m'(b − a) + mnz.$

So if x satisfies the original two congruences it must have this form. Let’s now check this

expression, for every $z \in Z$, really satisfies the original two congruences:

$a + mm'(b − a) + mnz \equiv a + 0 + 0 \equiv a \bmod m$

and

$a + mm'(b − a) + mnz \equiv a + 1(b − a) + 0 ≡ b \bmod n$

**b. Use the proof/algorithm of the CRT to solve the bandits problem given in class.**

$x\equiv 3\bmod 17$

$x\equiv 10\bmod 16$

$x\equiv 4\bmod 11$

$x\equiv 0\bmod 7$

Start by solving

$x\equiv 3\bmod 7$ and $x\equiv 0\bmod 7$

$3+17k=7l$

$17k-7l=-3$

$17\tilde{k} +7\tilde{l} = 1$

$\longrightarrow 17=2\cdot 7+3$

$7=2\cdot 3+1$

$1=(5\cdot 7)-(2\cdot 17)$

$l=(-(-3))(5) = 15$

$x=105$

$x\equiv 105\bmod 119$

the final remainder becomes 2842

**c. Prove the abstract version of the CRT for two ideals:**

The Cartesian product of two rings is a ring, so R/I×R/J is a ring.

We look at the map

$\phi:R\to R/I×R/J$

$x\mapsto (x+I,x+J)$

We know that $\phi$ is a ring homomorphism.

$\phi$ is surjective: for any $r\in R/I,s\in R/J$ there exists an $x\in R$ with $\phi(x)=(r,s)$.

The kernel of $\phi$ are the solutions of the system for r=s=0.We know that every other solution must be congruent to 0 modulo IJ, so $ker\phi=IJ$

Then by the first isomorphism theorem for rings

$R/ker(\phi)\simeq \phi(R)$

we obtain

$R/(IJ) \simeq R/I×R/J$