Finalized Problems 30-34 J.O.

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 17x\equiv 10\bmod 16x\equiv 4\bmod 11x\equiv 0\bmod 7$Start by solving$x\equiv 3\bmod 7$and$x\equiv 0\bmod 73+17k=7l17k-7l=-317\tilde{k} +7\tilde{l} = 1\longrightarrow 17=2\cdot 7+37=2\cdot 3+11=(5\cdot 7)-(2\cdot 17)l=(-(-3))(5) = 15x=105x\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/Jx\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\$

page revision: 25, last edited: 26 Apr 2018 05:57