# Harrison Chapman

## Math 301: Homework 5

Due: Friday, October 11, 2019

Exercises:

1. Define the Lucas numbers by $$L_0 = 2$$, $$L_1 = 1$$, and $$L_{n+1} = L_n + L_{n-1}$$ for $$n > 1$$.

If the Lucas numbers satisfy the formula

$L_n = c_1\left(\frac{1+\sqrt 5}{2}\right)^n + c_2\left(\frac{1-\sqrt 5}{2}\right)^n$

solve for $$c_1$$ and $$c_2$$.

We solve the system of equations $$2 = L_0 = c_1 + c_2$$ and $$1 = L_1 = c_1\left(\frac{1+\sqrt 5}{2}\right) + c_2\left(\frac{1-\sqrt 5}{2}\right)$$.

The first yields that $$c_2 = 2 - c_1$$, while the second has that

So $$c_1 = 1$$ and $$c_2 = 2 - c_1 = 1$$.

2. All variables $$a, b, c, p$$ are integers. Show that:

1. If $$a \mid b$$ and $$a \mid c$$ then $$a \mid (b+c)$$.

2. If $$a \mid b$$ and $$a \not\mid c$$ then $$a \not\mid (b+c)$$.

3. If $$p$$ is prime and $$p \mid ab$$ then at least one of $$p \mid a$$ or $$p \mid b$$.

1. $$a \mid b$$ and $$a \mid c$$ means that there exist integers $$m,n$$ so that $$b = ma$$ and $$c = na$$. These two equalities combine to show that $$b+c = (m+n)a$$. As $$(m+n)$$ is an integer this means that $$a \mid (b+c)$$.

2. Suppose that $$a \mid (b+c)$$. $$a \mid b$$ and $$a \mid (b+c)$$ means that there exist integers $$m,n$$ so that $$b = ma$$ and $$(b+c) = na$$. These two equalities combine to show that $$c = (n-m)a$$. As $$(n-m)$$ is an integer this means that $$a \mid c$$, a contradiction as we took the hypothesis that $$a \nmid c$$. So $$a \nmid (b+c)$$.

3. $$p \mid ab$$, so $$p$$ appears in the prime factorization of $$ab$$. But prime factorizations are unique, and so $$p$$ must appear in the prime factorization of $$a$$, or $$b$$, or both. In either case, $$p \mid a$$ or $$p \mid b$$.

3. All variables $$a, b, c$$ are integers. Show that:

1. If $$a \mid b$$ and $$b \mid c$$ then $$a \mid c$$.

2. If $$a \mid b$$ and $$a \mid c$$ then $$a \mid (b-c)$$.

3. If $$a \mid b$$ and $$a \not\mid c$$ then $$a \not\mid (b-c)$$.

1. $$a \mid b$$ and $$b \mid c$$ means that there exist integers $$m,n$$ so that $$b = ma$$ and $$c = nb$$. So $$c = n(ma) = (nm)a$$. As $$nm$$ is an integer, we have that $$a \mid c$$.

2. $$a \mid b$$ and $$a \mid c$$ means that there exist integers $$m,n$$ so that $$b = ma$$ and $$c = na$$. These two equalities combine to show that $$b-c = (m-n)a$$. As $$(m-n)$$ is an integer this means that $$a \mid (b-c)$$.

3. Suppose that $$a \mid (b-c)$$. $$a \mid b$$ and $$a \mid (b-c)$$ means that there exist integers $$m,n$$ so that $$b = ma$$ and $$(b-c) = na$$. These two equalities combine to show that $$c = (n-m)a$$. As $$(n-m)$$ is an integer this means that $$a \mid c$$, a contradiction as we took the hypothesis that $$a \nmid c$$. So $$a \nmid (b-c)$$.

4. Prove that if $$n$$ is a positive integer that is not a square (that is, there is no integer $$m$$ with $$n = m^2$$), then $$\sqrt n$$ is irrational.

1. Suppose for contradiction that $$\sqrt n$$ is rational, so that there exist integers $$p, q$$ with $$q \ne 0$$ so that $$\sqrt n = p/q$$. Then $$n = p^2/q^2$$ and so $$n p^2 = q^2$$. As $$n$$ is not a perfect square, it has at least one prime, $$r$$, with odd exponent in its unique prime factorization. As $$p^2$$ is a square, all of the primes in its prime factorization have even exponent. So there must be an odd power of $$r$$ in the prime factorization of the LHS. But as the RHS is $$q^2$$, any power of $$r$$ in the factorization of the RHS must have even exponent. This is a contradiction, so $$\sqrt n$$ could not have been rational.