  ## Exercises - The Fundamental Theorem of Arithmetic

1. Suppose we call numbers of the form $a+b\sqrt{10}$ (where $a$ and $b$ are integers) extended integers.

1. Prove that the extended integers behave much like the integers themselves, in that they are

1. ... closed under addition.
2. ... closed under subtraction.
3. ... closed under multiplication.
4. ... not closed under division.

1. We need to show that the sum of two extended integers is also an extended integer. That is to say, the sum of two numbers of the form $a+b\sqrt{10}$ (where $a$ and $b$ are integers) is of the same form. So consider two such extended integers, say $a_1+b_1\sqrt{10}$ and $a_2+b_2\sqrt{10}$, and their sum: $$(a_1+b_1\sqrt{10}) + (a_2+b_2\sqrt{10}) = (a_1+a_2) + (b_1+b_2)\sqrt{10}$$ Upon noting that $a_1 + a_2$ and $b_1 + b_2$ are integers by closure, we are done.

2. We need to show that the difference of two extended integers is also an extended integer. That is to say, the difference of two numbers of the form $a+b\sqrt{10}$ (where $a$ and $b$ are integers) is of the same form. So consider two such extended integers, say $a_1+b_1\sqrt{10}$ and $a_2+b_2\sqrt{10}$, and their difference: $$(a_1+b_1\sqrt{10}) - (a_2+b_2\sqrt{10}) = (a_1-a_2) + (b_1-b_2)\sqrt{10}$$ Upon noting that $a_1 - a_2$ and $b_1 - b_2$ are integers by closure, we are done.

3. We need to show that the product of two extended integers is also an extended integer. That is to say, the product of two numbers of the form $a+b\sqrt{10}$ (where $a$ and $b$ are integers) is of the same form. So consider two such extended integers, say $a_1+b_1\sqrt{10}$ and $a_2+b_2\sqrt{10}$, and their product: \begin{align}(a_1+b_1\sqrt{10})(a_2+b_2\sqrt{10}) &= a_1 a_2 + a_1 b_2\sqrt{10} + b_1 a_2\sqrt{10} + 10b_1 b_2\\ &=(a_1 a_2 + 10b_1 b_2) + (a_1 b_2 + b_1 a_2)\sqrt{10}\end{align} Upon noting that $(a_1 a_2 + 10b_1 b_2)$ and $(a_1 b_2 + b_1 a_2)$ are integers by closure, we are done.

4. We need to show that the quotient of two extended integers need not be an extended integer. That is to say, the quotient of two numbers of the form $a+b\sqrt{10}$ (where $a$ and $b$ are integers) does not need to be of the same form. Finding one explicit counterexample will suffice. So consider the two extended integers $4+\sqrt{10}$ and $4-\sqrt{10}$, and their quotient: \begin{align}\frac{4+\sqrt{10}}{4-\sqrt{10}} &= \frac{4+\sqrt{10}}{4-\sqrt{10}} \cdot \frac{4+\sqrt{10}}{4+\sqrt{10}} \\\\ &= \frac{16+8\sqrt{10}+10}{16-10} \\\\ &= \frac{26+8\sqrt{10}}{6} \\\\ &= \frac{26}{6}+\frac{8\sqrt{10}}{6} \\\\ &= \frac{13}{3} + \frac{4}{3} \sqrt{10} \end{align} It should be clear, given this last expression, if we force things into $a+b\sqrt{10}$ form, we are required to have $a$ and $b$ not be integers. We have then found a quotient of two extended integers, which was not an extended integer itself. As such, extended integers are not closed under division.

2. Both $1$ and $-1$ divide every integer. We call these numbers units. In the set of integers, there are only these two values which are units -- but what about the extended integers? Prove that $3+\sqrt{10}$ is a unit for the extended integers. What characteristic must units of extended integers have?

Hint: when one divides an extended integer by a unit, and tries to write it as an extended integer (possibly involving a multiplication by a conjugate), what must be true of the resulting denominator to be assured the coefficient on $\sqrt{10}$ turns out to be an integer?

Let $a + b\sqrt{10}$ be any extended integer, and then consider the quotient:

$$\begin{array}{rcl} \dfrac{a+b\sqrt{10}}{3+\sqrt{10}} &=& \dfrac{(a+b\sqrt{10})(3-\sqrt{10})}{(3+\sqrt{10})(3-\sqrt{10})}\\\\ &=& \dfrac{(3a - 10b) + (3b - a)\sqrt{10})}{-1}\\\\ &=& \left( \frac{3a - 10b}{-1} \right) + \left( \frac{3b-a}{-1} \right) \sqrt{10}\\\\ &=& (10b - 3a) + (a - 3b) \sqrt{10} \end{array}$$

As $a$ and $b$ are integers, $(10b-3a)$ and $(a-3b)$ are integers as well (by closure). Consequently, $(10b - 3a) + (a - 3b) \sqrt{10}$ is an extended integer.

We have thus shown that the quotient of any extended integer and $3+\sqrt{10}$ must also be an extended integer. Hence, $3+\sqrt{10}$ "divides" every extended integer -- making it a unit.

Notice, looking at what transpired in the denominators above, the key value that determines whether or not a given extended integer is a unit is the product of that extended integer and its conjugate. If this product is $1$ or $-1$ (the only values that can evenly divide every integer), then the extended integer in question is a unit -- otherwise it is not.

3. In the set of integers, one can define the primes to be those integers that can't be written as the product of two non-units. One might wonder which numbers in the set of extended integers have this same property. Prove that $2$, $3$, and $4 \pm \sqrt{10}$ are all extended integers that can't be written as the product of two non-units.

Hint: argue indirectly -- assume they can be written as the product of two non-units and attempt to show that no matter what happens, one of the factors ends up having the defining characteristic of units found above. To do this, try to put things back into the realm of integers by considering the product of the extended integers in question and their conjugates:
$$\begin{array}{lll} m+n\sqrt{10} &= (a+b\sqrt{10})(c+d\sqrt{10}) &\textrm{, then}\\\\ m-n\sqrt{10} &= (a-b\sqrt{10})(c-d\sqrt{10}) &\textrm{, and so}\\\\ m^2-10n^2 &= (a^2-10b^2)(c^2-10d^2)\\ \end{array}$$

Now we can think about the possible factorizations of $m^2-10n^2$ over the integers, as $m$ and $n$ are chosen so that $m+n\sqrt{10}$ yields $2,3,4+\sqrt{10}$ and $4-\sqrt{10}$, respectively.

Use these factorizations to show if $a+b\sqrt{10}$ and $c+d\sqrt{10}$ are not units (remember the condition you found in problem 2 above), then in each of these four cases:
$$a^2-10b^2 \quad \quad \textrm{and} \quad \quad c^2-10d^2$$
must be $2, -2, 3$, or $-3$. Finally, show that for any $a$,
$$a^2 \equiv 0,1, \textrm{ or } 4 \pmod{5}$$ and therefore,
$$a^2-10b^2=2,-2,3, \textrm{ or } -3$$
has no integral solutions.

We need to show that if $4+\sqrt{10}$ can be written as a product of two extended integers, then one of those extended integers must be a unit.

As such, suppose we can find extended integers $a+b\sqrt{10}$ and $c+d\sqrt{10}$ such that

$$4+\sqrt{10} = (a+b\sqrt{10})(c+d\sqrt{10})$$

Consider the conjugate of $4+\sqrt{10}$. Clearly if the above is true, we also know that

$$4-\sqrt{10} = (a-b\sqrt{10})(c-d\sqrt{10})$$

Taken together, we can then conclude

$$(4+\sqrt{10})(4-\sqrt{10}) = (a+b\sqrt{10})(c+d\sqrt{10})(a-b\sqrt{10})(c-d\sqrt{10})$$

This is advantageous as the left side can be collapsed into an integer, and the right side (upon combining the appropriate conjugate pairs with one another) can be collapsed to the product of two integers...

$$6 = (a^2-10b^2)(c^2-10d^2)$$

Now we know that the only integer divisors $6$ has are: $\pm 1, \pm 2, \pm 3$, and $\pm 6$. We deal with each case separately:

• If $a^2-10b^2 = \pm 1$, then $a+b\sqrt{10}$ was a unit, and we are done.

• If $a^2-10b^2 = \pm 6$, then $c^2-10d^2 = \pm 1$. This makes $c+d\sqrt{10}$ a unit, and we are again done.

• The last two possibilities actually lead to a contradiction and consequently can't happen. To see this, consider the following:

If $a^2-10b^2 = \pm 2$ or $a^2-10b^2 = \pm 3$, then remainder of $a^2-10b^2$ upon division by $5$ must either be $2$ or $3$. Further, since $10b^2$ is a multiple of $5$, we can conclude that $a^2$ itself, upon division by $5$, must either leave remainder $2$ or $3$.

However, if $a$ has remainder $0$ upon division by $5$, $a^2$ does as well; if $a$ has remainder $1$ or $4$, then $a^2$ has remainder $1$; and if $a$ has remainder $2$ or $3$, then $a^2$ has remainder $4$. Since these are the only possibilities for the remainders of $a$, it must be the case that $a^2$ never has remainder $2$ or $3$ upon division by $5$. This gives us the desired contradiction.

Hence, the extended integer $4+\sqrt{10}$ can't be written as the product of two non-units.

Note: showing that the extended integers $2$, $3$, and $4-\sqrt{10}$ also can't be written as the product of two non-units is done in a nearly identical way -- except there are fewer cases to worry about with regard to the divisors of $a^2-10b^2$, as argued above, when looking at $2$ and $3$.

4. Suppose we call extended integers that can't be written as the product of two non-units indivisibles. Certainly, $6$ can be written as the product of two indivisibles, as $6 = 2 \cdot 3$. Can you find two different indivisibles $m$ and $n$, such that $6=mn$?

We know that $2$ is prime and $2 \mid 6$. Does $2$ have to divide either $m$ or $n$? What might you conclude about the statement "if $p$ is prime and $p \mid mn$, then $p \mid m$ or $p \mid n$" and the unique factorization of integers?

Note: $6 = (4+\sqrt{10})(4-\sqrt{10})$, a product of two indivisibles.

Taking a step back, notice that extended integers and indivisibles are very closely related to the integers and primes, and yet even though we seem to have unique factorization into primes for integers (up to the order and signs of the factors), we don't have unique factorization into indivisibles for the extended integers.

Further, even though it seems obvious that if $p$ is prime with $p \mid mn$, then $p \mid m$ or $p \mid n$ is true for the integers, the same can't be said for some indivisible $p$ with respect to the extended integers. As an example, consider $2 \mid (4+\sqrt{10})(4-\sqrt{10})$.

Clearly, there is more to this innocent-looking implication and the idea of unique factorization than first appears!

2. Prove that $\log_5 7$ is irrational.

Argue indirectly. Assume $x = \log_5 7$ is rational. Thus, there exist non-zero integer values $p$ and $q$ where $p/q = \log_5 7$. This implies $5^{p/q} = 7$, and thus $5^p = 7^q$. Both $5$ and $7$ are prime, however, so this violates the unique factorization property of the integers. We have the contradiction we sought. Thus, $\log_5 7$ must be irrational.

3. Prove that every root of an equation of the form $x^n + c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \cdots + c_1 x + c_0 = 0$ (with each $c_i \in \mathbb{Z}$) is either an integer or irrational, and then use this to show $\sqrt{17}$, $\sqrt{11}$, and $\sqrt{13}$ are all irrational.

Hint: argue the main result indirectly. Assume there is a rational root (i.e., a root expressable as a fraction of integers in lowest terms $a/b$) and try to contradict the lowest terms nature of the fraction in question.

4. Prime numbers are defined as those numbers that have exactly two divisors. What type of numbers have exactly three divisors? ...exactly four divisors?

5. Prove that every integer $n \ge 1$ can be written as a product of an integer squared and an integer that has no divisors that are perfect squares (i.e., a square-free integer).