**34.** (Preliminary for T, April 17; finalized Sat, April 21)

a. State and prove the Chinese Remainder Theorem for integer congruences.

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

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

Theorem: If $I,J$ are coprime ideals of a commutative ring $R$ with identity, then $R/IJ\cong R/I \times R/J$.

**33.** (Preliminary for Th, April 12; finalized Sat, April 21) 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$.

b. Prove *Fermat's little theorem*: if $[0]\neq [a]\in \mathbb{F}_p$ , then $[a]^{p-1}=[1]$. (Hint: Try multiplying $[a]\cdot[2a]\cdot \dots \cdot [(p-1)a]$ and use part a.)

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. There are a couple of ways to prove this; however you do it, also find two distinct polynomials in $\mathbb{F}_p[x]$ that yield the same function. (Hint: use part b.)

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

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

**31.** (Preliminary for T, April 10; finalized Sat, April 21) 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.

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)$.

**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 $\mathbb{F}_p$ , we have $(x+y)^{p^n}=x^{p^n}+y^{p^n}$.

D.J. 30 proof (Monday recitation : (Presented 30 on 4/25))

Problem 30 Proof (Monday recitation)

**29.** (Preliminary for Th, April 5; finalized Sat, April 14) a. Consider the polynomial ring $\mathbb{Q}[x,y]$ in two variables with rational coefficients. (One way to think about it is as the polynomial ring in variable $y$ whose coefficients come from the single-variable polynomial ring $\mathbb{Q}[x]$.) Find an ideal $I\subseteq \mathbb{Q}[x,y]$ that is prime but not maximal. (You don't have to write out a very formal proof, but explain clearly what your candidate is and why it works. Try to make your example as simple as possible.)

b. An ideal $I$ of a ring $R$ is a *principal ideal* if there exists $x\in R$ such that $I=(x)$; that is, the ideal is generated by

a single element. Prove that every ideal of $\mathbb{Z}$ is principal (we say that $\mathbb{Z}$ is a *principal ideal domain* or PID).

c. Show that $\mathbb{Q}[x,y]$ is *not* a PID by finding an ideal $I$ that is not principal. Justify your answer. (Again, look for the simplest possible counterexample.)

**28.** (Preliminary for Th, April 5; finalized Sat, April 14) Prove that an ideal $I$ of a ring $R$ is maximal if and only if the quotient ring $R/I$ is a field.

Proof for Problem 28

Problem 28 Recitation Proof

**27.** (Preliminary for T, April 3; finalized Sat, April 14) a. Show that every unit of a ring $R$ has a unique inverse.

b. Show that the units of $\mathbb{Z}/n\mathbb{Z}$ are precisely those $[a]$ such that $GCD(a,n)=1$.

Problem 27 Proof (Monday recitation)

Problem 27 Proof (Recitation)

**26.** (Preliminary for T, April 3; finalized Sat, April 14) a. Prove that equality modulo an ideal $I$ of a ring $R$ is an equivalence relation. (In our class, you may always assume (unless stated otherwise) that a ring is commutative and has 1.)

b. Prove that multiplication on the quotient ring $R/I$ is well defined: $(r+I)(s+I)= rs+I$.

Problem 26 Proof (Monday recitation)

Proof 26, 4/11/18

**25.** (Preliminary for Th, March 29; finalized Sat, April 7) a. Prove existence and uniqueness of the *least common multiple* of two positive integers $a$ and $b$: a positive integer $m$ such that both $a$ and $b$ divide $m$ and $m$ divides any common multiple of the two.

b. Characterize the least common multiple using prime factorization. Use this to give an equation relating LCM and GCD.

c. Define what we should mean by the GCD and LCM of a collection $\{a_1,\dots,a_r\}$ of positive integers. Once you have defined these notions, explain algorithms for computing them.

**24.** (Preliminary for Th, March 29; finalized Sat, April 7) Complete our proof of the fundamental theorem of arithmetic by proving uniqueness of prime factorization up to the order of writing the elements. (On 3-27-18 we did existence and Euclid's Lemma: if a prime $p$ divides $ab$, then either $p$ divides $a$ or it divides $b$.)

Problem 24 Proof

Problem 24 Recitation Proof

**23.** (Preliminary for T, March 27; finalized Sat, March 31) Prove uniqueness of the quotient and remainder in the division algorithm.

(Write clearly and don't make jumps that are too large. If you find yourself struggling to mentally justify a claim you make in the proof, prove a little lemma and then use it.)

**22.** (Preliminary for T, March 20; finalized Sat, March 24) Let $(R,0, 1, +, \cdot,\leq)$ be an ordered ring with identity.

a. Prove that if $x>0$, then $-x<0$.

b. Prove that $1>0$.

**21.** (Preliminary for T, March 13; finalized Sat, March 17) Given a partition $\{X_{\alpha}\}_{\alpha\in I}$ of $X$, show that the relation $R\subseteq X\times X$ defined by $((a,b)\in R \Leftrightarrow \exists \alpha\in I \text{ such that both } a,b\in X_{\alpha})$ is an equivalence relation on $X$ whose equivalence classes are precisely the sets $X_{\alpha}$ of the partition.

**20.** (Preliminary for T, March 20; finalized Sat, March 24) Prove that the polynomial ring $\mathbb{Z}[x]$ over the integers is countably infinite.

**19.** (Preliminary for Th, March 15; finalized Sat, March 24) a. Using our definition of the integers $\mathbb{Z}$ as a quotient of $\mathbb{N}\times\mathbb{N}$, propose an appropriate definition of $<_{\mathbb{Z}}$ (that is, $[(m,n)]<_{\mathbb{Z}}[(p,q)]$ if and only $m,n,p,q$ satisfy ??).

b. Prove that your proposal is well defined and extends the linear order $<_{\mathbb{N}}$ on the natural numbers (i.e., if two integers also happen to be natural numbers, they satisfy $<_{\mathbb{Z}}$ if and only if they satisfy $<_{\mathbb{N}}$).

**18.** (Preliminary for Th, March 1; finalized Sat, March 17) a. Prove by induction that $+:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is commutative ($\forall m,n, \, \,\, m+n=n+m$) and satisfies *cancellation* ($\forall m,n,p, \,\,\, m+p=n+p$ if and only if $m=n$).

b. Prove by induction that $\cdot :\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is associative ($\forall m,n,p, \, \,\, m \cdot (n\cdot p) =(m\cdot n)\cdot p$), commutative ($\forall m,n,\,\, \, m \cdot n=n \cdot m$), satisfies cancellation for nonzero values ($\forall m,n,p, \,\,\, m\cdot p=n \cdot p$ implies that $m=n$ if $p\neq 0$), and distributes over addition

($\forall m,n,p,\,\, \, m\cdot (n+p) = m\cdot n + m\cdot p$).

**17.** (Preliminary for Th, Feb 22; finalized Sat, March 3) Prove that for all sets $x,y$, it is impossible for both $x\in y$ and $y\in x$ to hold.

**16.** (Preliminary for Th, Feb 22; finalized Sat, March 3) Using only results proven in class or assigned earlier (i.e., don't use induction), show that for all natural numbers $x,y$, if $y< Succ(x)$, then $y\leq x$.

16

Problem 16 Proof

Problem 16 Proof (Recitation)

**15.** (Preliminary for Th, Feb 22; finalized Sat, March 3) a. Prove that for all $x,y\in \mathbb{N}$, if $x<y$, then either $Succ(x)<y$ or $Succ(x)=y$. (We say that $Succ(x)$ is an *immediate successor* of $x$.)) *Hint*: Use induction on $y$.

b. Prove that $(\mathbb{N},<)$ satisfies *trichotomy*: For all $x,y \in \mathbb{N}$, exactly one of the following holds: $x<y, \, x=y,$ or $y<x$. *Hint*: Again use induction on one of the variables. Apply the lemma in part a. at an appropriate point.

Problem 15 Proof

Problem 15 Class Proof

**14.** (Preliminary for Th, Feb 8; finalized Sat, Feb 24 (**new date**)) Using induction, prove that if $X$ is a finite set and $f$ is an injective function from $X$ to $X$, then $f$ is bijective.

D.J. 14 proof (Monday recitation)

**13.** (Preliminary for Th, Feb 8; finalized Sat, Feb 17) Using induction, prove that $5^{2n+1} + 2^{2n+1}$ is divisible by 7 for all $n\in \mathbb{N}$.

D.J. 13 proof (Monday recitation : (Presented 13 on 2/19))

Proof

Proof for 13 (Recitation 2/21)

**12.** (Preliminary for Th, Feb 8; finalized Sat, Feb 17) Give an example of an invalid deduction (i.e., the conclusion is not true even though the hypothesis is) using the $\exists$-introduction rule if we don't require $y$ to be free in $\phi$. (Hint: find a simple formula $\phi$ involving $\forall y$ such that $\phi[y|x]$ is always true but $\exists x \phi$ is not.)

Proof of an invalid deduction (Monday recitation)

Proof of an Invalid Deduction (Tuesday presentation)

Proof of an Invalid Deduction (Wednesday recitation)

**11.** (Preliminary for Th, Feb 8; finalized Sat, Feb 17) Prove that $\mathbb{N}$ is *well-ordered*: every nonempty subset $X$ of $\mathbb{N}$ has a least element.

Proof that N is well-ordered (Thursday presentation)

D.J. 11 proof (Monday recitation)

**10.** (Preliminary for T, Feb 6; finalized T, Feb 13) a. Using our logical axioms and structural rules as discussed in class (but not the axioms of ZFC), give a formal proof of $\vdash \exists x(x=x)$. You could say that our logic assumes that at least one thing exists.

b. Can you prove that there exist at least two things? (If nothing else, give an unofficial wff expressing that there exist at least two things.)

**9.** (Preliminary for T, Feb 6; finalized T, Feb 13) Using our logical axioms and structural rules as discussed in class (but not the axioms of ZFC), give a formal proof that equality is symmetric: i.e., prove $\vdash \forall x \forall y (x=y \rightarrow y=x)$ in our formal system.

Equality is Symmetric Proof (Recitation)

**8.** (preliminary for T, Jan 30; finalized T, Feb 13) a. Let $x$ be a set. Write an "unofficial" wff (i.e., you can omit parentheses if it doesn't create confusion) defining the intersection $y$ consisting of all sets $z$ that belong to all elements $w$ of $x$. (Hereafter we will write $\cap x$ for the intersection of all the sets that are elements of $x$.) Note that $x,y$ should be free variables in your formula (not "bound" by any quantifiers).

b. Does your definition still make sense if $x$ is the empty set? Explain.

c. We defined the natural numbers $\mathbb{N}$ as the set $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \dots\}$. What is $\cap\mathbb{N}$? (Write a brief proof that is clear and precise but not too wordy or formal.)

**7.** (preliminary for T, Jan 30; finalized T, Feb 13) Write an "official" (include all parentheses, etc.) wff expressing the Empty Set Axiom ("there exists a set with no elements").

**6**. (preliminary for T, Jan 23; finalized Th, Jan 25) We saw from exercise 2 (infinitude of primes and finding large primes) that sometimes an indirect proof (e.g., by contradiction) is just masking a similar "constructive" proof. Using the numbers $\sqrt{2}$ and $\sqrt{2}^{\sqrt{2}}$, prove that there exist irrational numbers $a,b$ such that $a^b$ is rational. Can you use the proof to find specific values of $a,b$? Why or why not?

Proof of existence of a rational equal to an irrational raised to an irrational power

**5**. (preliminary for T, Jan 23; finalized Th, Jan 25) a. Explain the ambiguity of "formulas" like the following if we don't require parentheses: $\phi \wedge \psi\vee \theta$ (assume we can assign truth values to $\phi, \psi,$ and $\theta$).

b. Carefully define an appropriate notion of "unique readability"; i.e., a precise statement of what it means for formulas to be unambiguous.

c. Recall from class the result that no wff has a proper initial segment that is also a wff. Use this lemma to prove that wffs satisfy your definition of unique readability from part b.

Proof of unique readability of wffs

**4**. There is something odd about our use of sets, intersections, and other mathematical entities in the previous problem. Discuss the issue and propose a resolution.

Circularity in using set theory to prove results about set theory?

**3**. We defined the set WFF of well-formed $\mathcal{L}_{ST}$-formulas inductively, in “bottom-up” fashion. Call a set $S$ of $\mathcal{L}$-strings “good” if $S$ contains all atomic formulas and is closed under application of the connectives and quantifiers: if $\phi$ and $\psi$ belong to $S$, then $\neg\phi$, $(\phi \wedge \psi)$, $(\phi \vee \psi)$, $(\phi\rightarrow \psi)$, $\forall x \phi$ and $\exists x \phi$ also belong to $S$. (“Good” isn't a standard term here; we're just using it as a placeholder word to make the statement of the proposition less unwieldy.) Prove that the intersection of all good sets of $\mathcal{L}$-strings is exactly equal to WFF. (“Top-down” characterization)

Proof that WFF equals the intersection of all "good sets"

**2**. a. Prove that there are infinitely many prime numbers. (Hint: Here is a sketch of the classic proof dating back to Euclid. Suppose toward contradiction that there are only finitely many prime numbers. Consider the number $N$ defined to be the product of all (finitely many) prime numbers, plus 1. Find something wrong with $N$. We will prove it later, but for now you may assume the *Fundamental Theorem of Arithmetic*, namely that every positive integer can be written as a product of prime numbers; moreover that product is “unique up to reordering”, i.e., no matter how you write a given number as a product of primes, all the representations involve the same primes and the same number of each prime.)

Proof of the Infinitude of Primes

b. (i) Describe an algorithm that takes as input a positive integer $n$ and outputs a prime number greater than $n$. Prove that your algorithm satisfies the required property. (You may assume that testing a number for primality is a primitive operation; that is, you don't need to explain how to check if a given number is prime.) (ii) (Challenge question; optional): Give an upper bound (in terms of $n$) on the size of the prime your algorithm (or another algorithm you think of if your original isn't suitable to analyze) finds with input $n$. Prove that your bound really works. (Hint: Think about Euclid's proof.)

**1**. State and prove the Pythagorean Theorem for right triangles in the plane. (Study your insights from our prior class discussion but write it up without copying.)

**Definition:** A positive integer $p$ is *prime* if $p$ is greater than 1 and is not divisible by any positive integers other than 1 and itself.