# Tutor profile: David L.

## Questions

### Subject: Number Theory

Solve the simultaneous linear congruences $(x\equiv 3 \pmod{7},\;\;\;\;\;\;\;\; x\equiv 5 \pmod{9},\;\;\;\;\;\;\;\; x\equiv 1 \pmod{4}.$)

First, the Chinese Remainder Theorem says that there is an integer solution $$x$$, because $$7$$, $$9$$, and $$4$$ are pairwise coprime. Moreover, it is unique modulo $$7\cdot 9\cdot 4=252$$. There is an algorithm for solving simultaneous linear congruences of this type. Let the linear congruences be $$x\equiv a_i\pmod{n_i}$$ for $$i=1,2,3$$ respectively. Let $$n=n_1n_2n_3$$, and for each $$i$$ let $$c_i$$ be an integer that is the multiplicative inverse of $$n/n_i$$ modulo $$n_i$$. Then a solution is $(x=a_1c_1n/n_1+a_2c_2n/n_2+a_3c_3n/n_3.$) This is a solution to the first congruence, because modulo $$n_1$$ the last two terms above are $$0$$ and the first term above is $$a_1$$, because $$c_1\cdot n/n_1\equiv 1\pmod{n_1}$$, and similarly for the other two congruences. The remaining goal is to calculate the inverses $$c_i$$. For $$i=1$$ we need a solution to $$4\cdot9\cdot c_1\equiv 1\pmod{7}$$. Since $$36\equiv 1\pmod{7}$$ and $$1$$ is its own multiplicative inverse mod $$7$$, we can take $$c_1=1$$ (or $$8$$ or $$15$$ or $$-6$$, etc.). For $$i=2$$ we need $$c_2$$ to be a multiplicative inverse of $$4\cdot 7\equiv 1\pmod{9}$$, so we can again take $$c_2=1$$. For $$i=3$$ we need a multiplicative inverse of $$9\cdot 7\equiv 3\pmod{4}$$. This time $$c_3=3$$ works, because $$3\cdot 3\equiv 1\pmod{4}$$. Putting it all together, a solution is given by $$x=3\cdot 1\cdot 36+5\cdot 1\cdot 28+1\cdot 3\cdot 63=437$$, and also by $$x-252=185$$.

### Subject: Discrete Math

Is it possible for a (finite, simple) graph with more than one vertex to have distinct degrees for each vertex?

No. The following proof relies on two common proof techniques: proof by contradiction and the pigeonhole principle. Suppose for the sake of contradiction that there is a finite simple graph $$G$$ with $$n>1$$ vertices, each of which has a distinct degree. Each vertex has degree at most $$n-1$$, because it can share at most one edge with every other vertex. Note that the simplicity assumption is critical here. There are $$n$$ vertices and $$n$$ possible degrees: $$0, 1, 2, \dots, n-1$$. Each vertex has a unique degree by assumption, so by the pigeonhole principle each degree between $$0$$ and $$n-1$$ is used by exactly one vertex. In the language of the pigeonhole principle, if one of the possible degrees wasn't the degree of a vertex, then there would be $$n$$ pigeons (vertices) in $$n-1$$ holes (degrees). Since some vertex $$v$$ of the graph has degree $$0$$, the graph $$G$$ is the disjoint union of the (simple) subgraphs $$\{v\}$$ and $$G\setminus\{v\}$$. The latter has $$n-1$$ vertices with distinct degrees $$1, 2,\dots, n-1$$. In particular, the vertex of degree $$n-1$$ in $$G\setminus\{v\}$$ is connected to all vertices in $$G\setminus\{v\}$$, including itself (!). That is impossible in a simple graph, so we have reached a contradiction. The initial assumption that there is such a graph $$G$$ must be false.

### Subject: Calculus

How do I determine whether or not the series $$\sum_{n=0}^\infty \frac{1}{\cosh(n)}$$ converges?

Recall that the hyperbolic cosine function $$\cosh(n)$$ is defined as $$\frac{e^n+e^{-n}}{2}$$. The series converges if and only if the terms $$\frac{1}{\cosh(n)}$$ decrease quickly enough. Equivalently, if and only if $$\cosh{n}$$ grows quickly enough. For large $$n$$ the $$e^{-n}$$ term is negligible, so the function grows like $$\frac{1}{2}e^n$$. If the $$\cosh(n)$$ term were replaced with $$e^n$$, the series would be geometric with common ratio $$1/e$$, so it would converge. To make this rigorous, we can use the comparison test. For any $$n$$, $$e^{-n}>0$$. Therefore $$\cosh(n)>\frac{1}{2}e^n$$ and $$0<\frac{1}{\cosh(n)}<2e^{-n}$$. By the comparison test and the formula for the sum of a geometric series, $$0<\sum_{n=0}^\infty \frac{1}{\cosh(n)}<\sum_{n=0}^\infty 2e^{-n}=\frac{2}{1-e^{-1}}=\frac{2e}{e-1}$$, so the series does converge to a positive number less than $$\frac{2e}{e-1}$$, which is roughly 3.164.

## Contact tutor

needs and David will reply soon.