Homework 4:
3.8.14: This is routine.
6.5.3: There are $a^p$ such integers. Those that repeat, such as $11\cdots 111$ are in a class by themselves. There are $a$ such integers. The remaining $a^p-a$ all have $p$ elements, so $p$ divides $a^p-a$.
6.6.2: (a) Lets prove that the sets of common divisors of (a,b) and (b-a,a) are the same.:
Let d divide both a and b. Then d divides both b-a and a. This is containment in one direction.
Let $d$ divide b-a and a. Then $d$ divides b=b-a+a and also a.
(b) Let $b=q*a+r$ be the result of the division algorithm.
Again show the set of common divisors is the same.
Let $d$ divide $b$ and $a$. Since $r=b-q*a$, $d$ also divides $r$.
For the other direction let $d$ divide both $a$ and $r$. Since $b=a*q+r$,
$d$ also divides $b$.
6.7.5:Note that if $x=y=0 \mod p$, both sides are zero. So we can assume they are not zero
mod p.
Let $u=v+m*(p-1).$ Then
$$x^u=x^v*x^{m*(p-1)}=x^v=y^v \mod p.
$$
6.8.5 Multiply the second equation by 2 and subtract from the first equation to get $-5*y=-7 mod 11.$: The inverse of 5 mod 11 is 9, so multiplying by 9 gives $y=63=8 \mod 11.$ and then $x=5.$
6.9.3: The result is $$ \sum_{d|n} \varphi(d) =n. $$ Proof: Let's classify the integers $x$ from 1 to n by the $GCD(x,n)=d.$ Such an $x=d*T$, where $GCD(T,n/d)=1$, so there are $\varphi(n/d)$ such $x$. This gives $$ \sum_{d|n} \varphi(n/d)=n, $$ which is what we need with $d$ replaced by $n/d.$
6.10.10: The smallest way to have $100$ prime factors is to make them all $2$, and $2^{100}\gt 10^{30}$ which has 31 digits.
E1: Since $$ C_n=\frac{(2n)!}{(n+1)!n!} $$ we can apply Stirling's formula to get $$ \frac{(2n/e)^{2n}\sqrt{2\pi (2n)}} {((n+1)/e)^{n+1}\sqrt{2\pi (n+1)}(n/e)^n \sqrt{2\pi n}} $$ which is $$ 2^{2n}/e\sqrt{\pi}n^{3/2} (1+1/n)^n $$ or $$ 2^{2n}/\sqrt{\pi}n^{3/2}. $$
E2: 95% is wthin 1.96 standard deviations. This means we need $$ 0.01*n \ge \sqrt{n}/2*1.96 $$ which is $$ n \ge 9604. $$
E3: This is $$ \lim_{n\to\infty} \left( log(7n)+\gamma -(log(5n)+\gamma)\right)=log(7/5). $$
E4: (a) This power series, by Taylor's theorem, or by known series for log, is
$$
-w^2/2+w^3*a/3-w^4*a^2/4+w^5*a^3/5-w^6*a^4/6+O(a^5)
$$
(b)
So we exponentiate this function, let $a=1/\sqrt{n}$, and integrate
$$
\int_{-\infty}^\infty exp(-w^2/2)*exp(w^3*a/3-w^4*a^2/4+w^5/5) dw=
\int_{-\infty}^\infty exp(-w^2/2)*(1+w^3*a/3+(-w^4/4+w^6/18)*a^2+O(a^3) dw
$$
The $a^1$ term gives $0$ because it is an odd function of $w$. The next surviving term is the
$a^2$ term,
$$
\int_{-\infty}^\infty exp(-w^2/2)*(-w^4/4+w^6/18)*a^2 dw =\sqrt{2\pi}/12*a^2
$$
so the next term is $1/12n.$