30. Let $p$ be prime. Show that for all natural numbers $n$ and elements $x,y$ of the finite field $\mathbb{F}_p$ , we have $(x+y)^{p^n}=x^{p^n}+y^{p^n}$.
Proof: We can prove the above by using induction. The base case $n=1$ is equal to $(x+y)^p = \sum \binom{p}{i}x^{p_i}y^i$ where $0 < i < p$. $\binom{p}{i} = p! / (i!(p-i)!) = (p(p-1)...(p-i)!) / (i!(p-i)!)$ This means that $i!$ is a factor of $p$.
We then assume that the above statement holds for some $n$ and $(x+y)^{p^n}$. The $n+1$ case is equal to $(x+y)^{p^{n+1}}= (x+y)^{p^{n}*p}=((x+y)^{p^n})^p$. We know that, by the inductive hypothesis $(x+y)^{p^n}$ is true and then by the base case $(x+y)^{p}$ is true.
31. a. Let $f:R\rightarrow 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.
Statement: Is the image $f(A)$ of $A$ in $S$ necessarily a subring?
Proof: We must show that $f(A) \in S$ is closed under addition and multiplication. To show addition, suppose we have some $y_1, y_2 \in f(A)$ such that $\exists x_1 \in A s.t. y_1 = f(x_1)$ and $\exists x_2 \in A s.t. y_2 = f(x_2)$. It follows that $y_1 + y_2 = f(x_1) +_S f(x_2)$. As $f$ is a homomorphism, $f(x_1 +_R x_2) \in A$. Similarly, $y_1 ⋅ y_2 = f(x_1) ⋅_S f(x_2)$. As $f$ is a homomorphism, $f(x_1 ⋅_R x_2) \in A$.
Statement: Is the image $f(I)$ necessarily an ideal?
Proof: This can be proven false through contradiction by looking at the polynomial ring in the integers. $\mathbb{Z} \mapsto \mathbb{Z}[x]$. ${...-2p, -p, ...,p, 2p...} \rightarrow ^(\iota) {...-2p, -p, ...,p, 2p...}$ but $px \notin \iota(p \mathbb{Z})$ as x is a variable and does not have to be in $\mathbb{Z}$.
Statement: Is the preimage $f^{-1}(B)$ of $B$ in $R$ necessarily a subring?
Proof: Yes. It suffices to show that $f^{-1}(B)$ preserves multiplication and addition. Suppose there exists some arbitrary $a, b \in S$ and there corresponding preimage, $f^{-1}(a), f^{-1}(b)$. For closure under addition, we want to show $f^{-1}(a+b) = f^{-1}(a)+ f^{-1}(b)$.
$f(f^{-1}(a)+ f^{-1}(b)) = a + b$
$f(f^{-1}(a)) + f(f^{-1}(a)) = a + b$
For closure under multiplication, we want to show $f^{-1}(a ⋅ b) = f^{-1}(a) ⋅ f^{-1}(b)$.
$f(f^{-1}(a) ⋅ f^{-1}(b)) = a ⋅ b$
$f(f^{-1}(a)) ⋅ f(f^{-1}(a)) = a ⋅ b$
Statement: Is the preimage $f^{-1}(J)$ necessarily an ideal?
Proof: Yes. It suffices to show that $f^{-1}(J)$ is super closed. $j \in J, s \in S$ from this and the definition of ideals, $js \in J$. $f^-1(j) \in I, f^-1(s) \in R, f^-1(js) \in I$. $f^-1(j)f^-1(s) \in I$.
b. Prove the First Isomorphism Theorem for Rings: If $\varphi: R\rightarrow S$ is a ring homomorphism, then $R/\text{ker }(\varphi) \cong \varphi(R)$.
Proof: We first show that it is well-defined. Let $r, r’ \in R$ be such that $r- r’ \in \text{ker }(\varphi)$, such that $r + \text{ker }(\varphi) = r’ + \text{ker }(\varphi)$. Then $\varphi(r) = \varphi (r’ + (r – r’)) = \varphi (r’) + \varphi (r-r’) = \varphi (r’) + 0 = \varphi (r’)$ , so $\varphi$ is well defined. Let $r_1 + I, r_2 + I \in R=I$. Then since $\varphi$ is a homomorphism we have:
$\varphi (r_1 + I + r_2 + I) = \varphi (r_1 + r_2 + I) = \varphi (r_1 + r_2) = \varphi (r_1) + \varphi (r_2)$
$\varphi (r_1 + I + r_2 + I) = \varphi (r_1 + I) + \varphi (r_2 + I)$
$\varphi ((r_1 + I)(r_2 + I)) = \varphi (r_1r_2 + I) = \varphi (r_1r_2) = \varphi (r_1) \varphi (r_2)$
$\varphi ((r_1 + I)(r_2 + I)) = \varphi (r_1 + I) \varphi (r_2 + I)$
$\varphi(1 + I) = \varphi (1) = 1$
Therefore $\varphi$ is a homomorphism.
We begin by proving that $\varphi$ is bijective. If $r + \text{ker }(\varphi) \in \text{ker }(\varphi)$, then $\varphi(r + I) = \varphi (r) = 0$ and so $r \in \text{ker }(\varphi)$ or equivalently $r + \text{ker }(\varphi) = \text{ker }(\varphi)$. Thus $\text{ker }(\varphi)$ is trivial and is injective. Let $s \in \varphi(R)$. Then there exists an $r \in R$ such that $\varphi(r) = s$ or equivalently that $\varphi(r + \text{ker }(\varphi)) = s$. Thus $s \in \varphi(R)$ and so $\varphi$ is surjective.
32. Let $p$ be a prime. Prove that there is no surjective ring homomorphism from $\mathbb{Z}$ onto $\mathbb{F}_{p^k}$ for $k>1$.
Proof: Suppose towards contradicition that $\varphi : \mathbb{Z} \rightarrow \mathbb{F}_{p^k} \cong \mathbb{Z} / p^k \mathbb{Z}$. Using the first isomorphism theorem $\mathbb{Z} / ker(\varphi) \cong \mathbb{Z} / p^k \mathbb{Z} \cong \mathbb{F}_{p^k}$. It follows, then, that $\mathbb{Z} / p^k \mathbb{Z} \cong \mathbb{F}$. This is only true if $\mathbb{Z} / p^k \mathbb{Z}$ is a maximal ideal. This is a contradiction as the maximal ideals in $\mathbb{Z}$ are of the form $\mathbb{Z} / p \mathbb{Z}$.
33. Let $p$ be a prime.
a. Prove that if $[0]\neq [a]\in \mathbb{F}_p$, then $\{[a],[2a],\dots, [(p-1)a]\}=\mathbb{F}_p^\times$.
Proof: To show this, it suffices to prove that all the terms are distinct. Suppose $[ma] = [na]$ for some $1 < m, n < p-1$. It follows $[m][a] = [n][a]$ and $[m] = [n]$. So $m=n$ and there are $p-1$ distinct elments.
b. Prove Fermat's little theorem: if $[0]\neq [a]\in \mathbb{F}_p$ , then $[a]^{p-1}=[1]$.
Proof: We can begin by multiplying $\{[a],[2a],\dots, [(p-1)a]\}$ by $[a]$ to get $[a] ⋅ \{[a],[2a],\dots, [(p-1)a]\} = [a][2][a] \dots [(p-1)][a]$. It follows that it then equals $[a^{p-1}]\{[2] \dots [p-1]\} = [1][2] \dot [p-1]$
Cancelling the factors $1, 2, 3, \dots, p-1$ from both sides, we are left with $[a^{p-1}] = [1]$.
c. Consider the polynomial ring $\mathbb{F}_{p}[x]$ and the ring of polynomial functions $Func_{\,\mathbb{F}_p[x]}$ defined in class. Prove that the rings $\mathbb{F}_p[x]$ and $Func_{\,\mathbb{F}_p[x]}$ are not isomorphic.
Proof: For a homomorphism to be an isomorphism, it must be bijective. The map from $\mathbb{F}_p[x] \mapsto Func_{\,\mathbb{F}_p[x]}$ is not bijective because $\mathbb{F}_p[x]$ is finite and $Func_{\,\mathbb{F}_p[x]}$ is infinite.
d. Statement: The polynomial ring $\mathbb{Q}[x]$ is isomorphic to the ring of polynomial functions $Func_{\, \mathbb{Q}[x]}$.
Proof: Suppose that $\varphi: \mathbb{Q}[x] \rightarrow Func_{\, \mathbb{Q}[x]}$ such that $\exists a_i \in \mathbb{Q}$ and $n \in N$ such that $\forall \mathbb{Q}, f(a) = a_n(a)^n + a_{n-1}(a)^{n-1} + \dots + a_1(a) + a_0$. It follows that $a_n(x)^n + + \dots + a_1(x) + a_0 \mapsto a_n(a)^n + \dots + a_1(a) + a_0$. To show that $\varphi$ is an isomorphism, we show that it respects multiplication and addition, and is bijective.
34. a. State and prove the Chinese Remainder Theorem for integer congruences.
Proof: Notice that $GCD(M_i , m_i ) = 1$ for $1 ≤ i ≤ r$. Therefore, $y_i$ exists by the Euclidean Algorithm. As $M_iy_i \equiv 1(mod m_i)$, $a_iM_iy_i \equiv a_i(mod m_i)$ for $1 ≤ i ≤ r$. If $a_iM_iy_i \equiv 0(mod m_j)$ then $j \neq i$ as $m_j | M_i$. Thus, $x \equiv a_i(mod m_i)$ for $1 ≤ i ≤ r$.
b. Use the proof/algorithm of the CRT to solve the bandits problem given in class.
Proof:
$x \equiv 3mod17$ and $x \equiv 0mod7$:
$3+17k = 0+7l$
$17k-7l = -3$
As 17 and 7 are relatively prime, we can use that fact that $GCD(17,7)=1$.
$17\widetilde{k}+7\widetilde{l}=1$
$17 = 2 · 7 +3$
$7 = 2 · 3 +1$
$1 = 7-2 · 3= 7-2(17-2 · 7) = 5 · 7 - (2 · 17)$
$l =(3)\widetilde{l} = 3 · 5 = 16$
$x=0+15 · 7 =105$
$x \equiv 105mod119$
$x \equiv 10mod16$ and $x \equiv 4mod11$:
$10+16k = 4+11l$
$16k-11l = -6$
As 16 and 11 are relatively prime, we can use that fact that $GCD(16,11)=1$.
$16\widetilde{k}+11\widetilde{l}=1$
$16 = 1 · 11 + 5$
$11 = 2 · 5 +1$
$1 = 11-2 · 5= 11-2(16-1 · 11) = -2 · 16 +3 · 11$
$k =-(6)\widetilde{k} = -6 · -2 = 12$
$x=4+18 · 11 =202$
$x \equiv 202mod176$
$x \equiv 26mod176$
$x \equiv 26mod176$ and $x \equiv 105mod119$:
$26+176k = 105+119l$
$176k-119l = 79$
As 176 and 119 are relatively prime, we can use that fact that $GCD(176,119)=1$.
$176\widetilde{k}+119\widetilde{l}=1$
$176 = 1 · 119 + 57$
$119 = 2 · 57 + 5$
$57 = 11 · 5 + 2$
$5 = 2 · 2 + 1$
$1 = 5-2 · 2= 5-2· (119-2 · 57) = 5-2· (57-11·(119-2·(176-1·119)))$
$x \equiv 2842mod20944$
The minimum number of coins the bandits could have started with is 2842.
c. Statement: If $I,J$ are coprime ideals of a commutative ring $R$ with identity, then $R/IJ\cong R/I \times R/J$.
Proof: Suppose $\varphi : R/I \times R/J \rightarrow R/IJ$. This implies $((a+I),(b+J)) \mapsto ab+ IJ$. To show it is an isomorphism, we must show that $\varphi$ is a homomorphism and a bijection. To show that $\varphi$ respects multiplication and addition, take arbitrary elements $a, b \in R/I \time R/J$ where $a=((c+I), (d+J))$ and $b = ((e+I), (g+J))$. It follows that $f(a) = cd + IJ$ and $f(b) = eg +IJ$.
Multiplication:
$f(a) \dot f(b) = f(a \dot b)$
$f(a) \dot f(b) = (cd + IJ) \dot (eg +IJ) = cdeg + IJ$
$(a \dot b) = ((ce + IJ), (dg + IJ))$
$f(a \dot b) = cdeg + IJ$
Addition:
$f(a) + f(b) = f(a + b)$
$f(a) + f(b) = (cd + IJ) + (eg +IJ) = cd + eg + IJ$
$(a + b) = (( + IJ), (dg + IJ))$
$f(a \dot b) = cdeg + IJ$
We then show that $\varphi$ is bijective.
Surjective: $x = (p + IJ)$. We want to find some $p$ such that $f(p) = x$.
$f(((p + I), (1 + J))) = (p + I)$ as $I$ and $J$ are coprime. It follows that $f(((1 + I), (p + J))) = (p + I)$.
Injective: We want to show the uniqueness of $f((a+I), (b+J)) = x=(ab+IJ), f((c+I), (d+J)=x=(cd+IJ))$. It follows that $ab – cd \in IJ$. We can then use the fact that the kernel is trivial to show that it is injective.