## Monthly Archives: December 2009

### A formula for the largest power of a prime dividing a factorial

Let $p$ be a prime and $n \in \mathbb{Z}^+$. Find a formula for the largest power of $p$ which divides $n!$.

Before attacking this problem, we prove the following lemma.

Lemma: Let $a,b \in \mathbb{Z}^+$. The number of multiples of $a$ which are less than or equal to $b$ is $\lfloor \frac{b}{a} \rfloor$.

Proof: Note first that $\lfloor \frac{b}{a} \rfloor$ is precisely the quotient part returned by the Euclidean algorithm on $b$ and $a$, since if $b = qa + r$ where $0 \leq r < a$, then $\frac{b}{a} = q + \frac{r}{a}$, so $q = \lfloor \frac{b}{a} \rfloor$. Then we have $ka \leq b$ for precisely $1 \leq k \leq q$. $\square$

Now for the main problem. Our goal is to find a formula that gives the largest power of $p$ which divides $n!$; equivalently, to find the number of times $p$ appears in the factorization of $n!$. Note that there will be one $p$ factor for each multiple of $p$ less than $n$ – that is, $\lfloor \frac{n}{p} \rfloor$. This does not account for all of the factors, though; multiples of $p^2$ contribute one more each, for a total of $\lfloor \frac{n}{p^2} \rfloor$. We can continue for higher powers of $p$; for each $k \in \mathbb{Z}^+$ we count an additional $\lfloor \frac{n}{p^k} \rfloor$ factors. Note that every $p$ factor is counted. Moreover, no factor is counted more than once. Thus, the highest power of $p$ which divides $n$ is $p^M$, where $M = \sum_{k \in \mathbb{Z}^+} \lfloor \frac{n}{p^k} \rfloor$. Note that for sufficiently large $k$, $\lfloor \frac{n}{p^k} \rfloor = 0$, so that the summation indeed converges. $\blacksquare$

### The square root of a prime integer is not rational

If $p$ is a prime, prove that there do not exist nonzero integers $a$ and $b$ such that $a^2 = pb^2$. (I.e., $\sqrt{p}$ is not rational.)

Suppose to the contrary that $a^2 = pb^2$ for some integers $a$ and $b$. Then by the fundamental theorem of arithmetic we may factor $a^2$ and $pb^2$ as products of primes, and that these factorizations must be the same up to a reordering of the factors. Note, however, that $p$ must appear an even number of times in the factorization of $a^2$ and an odd number of times in the factorization of $pb^2$. Since no integer is both even and odd, we have a contradiction.

### Every nonempty set of positive integers has a unique least element

Prove that every nonempty set of positive integers has a least element by induction and prove that the minimal element is unique.

Let $A \subseteq \mathbb{Z}^+$ be nonempty.

Existence: We will prove this result using total induction.

For the base case, note that if $1 \in A$, then $A$ has a least element- namely $1$, since $1 \leq k$ for all $k \in \mathbb{Z}^+$.

Now let $n$ be fixed and suppose that for all $k$ with $1 \leq k \leq n$, if $k \in A$, then $A$ has a least element. Now suppose $n+1 \in A$. If $n+1$ is a least element of $A$, we’re done. If not, then there exists a positive integer $k < n+1$ with $k \in A$. But note that $1 \leq k \leq n$, hence $A$ has a least element.

Thus, for all $n \in \mathbb{Z}^+$, if $n \in A$ then $A$ has a least element. Since $A$ is nonempty by hypothesis, then, it has a least element. $\square$

Uniqueness: Suppose $A$ has two least elements, $a$ and $b$. Then by the definition of least element we have $a \leq b$ and $b \leq a$. Since $\leq$ is a partial order on $\mathbb{Z}$, we have $a = b$. Thus the least element of $A$ is unique. $\blacksquare$

### Compute the Euler totient of all positive integers up to 30

Determine the value $\varphi(n)$ for $1 \leq n \leq 30$, where $\varphi$ denotes the Euler totient function.

We will use the following facts: $\varphi(p^k) = p^{k-1}(p-1)$ when $p$ is prime and $k \geq 1$, and if $a$ and $b$ are relatively prime, then $\varphi(ab) = \varphi(a) \varphi(b)$.

 $n$ Reasoning $\varphi(n)$ 1 $\varphi(1) = 1$. 1 2 $\varphi(2) = 2^0(2-1) = 1$ since 2 is prime. 1 3 $\varphi(3) = 3^0(3-1) = 2$ since 3 is prime. 2 4 $\varphi(4) = \varphi(2^2) = 2^1(2-1) = 2$. 2 5 $\varphi(5) = 5^0(5-1) = 4$ since 5 is prime. 4 6 $\varphi(6) = \varphi(2 \cdot 3) = \varphi(2) \cdot \varphi(3) = 1 \cdot 2 = 2$. 2 7 $\varphi(7) = 7^0(7-1) = 6$ since 7 is prime. 6 8 $\varphi(8) = \varphi(2^3) = 2^2(2-1) = 4$. 4 9 $\varphi(9) = \varphi(3^2) = 3^1(3-1) = 6$. 6 10 $\varphi(10) = \varphi(2 \cdot 5) = \varphi(2) \cdot \varphi(5) = 1 \cdot 4 = 4$. 4 11 $\varphi(11) = 11^0(11-1) = 10$ since 11 is prime. 10 12 $\varphi(12) = \varphi(3 \cdot 4) = \varphi(3) \cdot \varphi(4) = 2 \cdot 2 = 4.$ 4 13 $\varphi(13) = 13^0(13-1) = 12$ since 13 is prime. 12 14 $\varphi(14) = \varphi(2 \cdot 7) = \varphi(2) \cdot \varphi(7) = 1 \cdot 6 = 6.$ 6 15 $\varphi(15) = \varphi(3 \cdot 5) = \varphi(3) \cdot \varphi(5) = 2 \cdot 4 = 8$ 8 16 $\varphi(16) = \varphi(2^4) = 2^3(2-1) = 8$. 8 17 $\varphi(17) = 17^0(17-1) = 16$ since 17 is prime. 16 18 $\varphi(18) = \varphi(2 \cdot 9) = \varphi(2) \cdot \varphi(9) = 1 \cdot 6 = 6$. 6 19 $\varphi(19) = 19^0(19-1) = 18$ since 19 is prime. 18 20 $\varphi(20) = \varphi(4 \cdot 5) = \varphi(4) \cdot \varphi(5) = 2 \cdot 4 = 8$ 8 21 $\varphi(21) = \varphi(3 \cdot 7) = \varphi(3) \cdot \varphi(7) = 2 \cdot 6 = 12$. 12 22 $\varphi(22) = \varphi(2 \cdot 11) = \varphi(2) \cdot \varphi(11) = 1 \cdot 10 = 10$. 10 23 $\varphi(23) = 23^0(23-1) = 22$ since 23 is prime. 22 24 $\varphi(24) = \varphi(3 \cdot {8}) =\varphi(3) \cdot \varphi(8) = 2 \cdot 4 = 8$. 8 25 $\varphi(25) = \varphi(5^2) = 5^1(5-1) = 20$. 20 26 $\varphi(26) = \varphi(2 \cdot 13) = \varphi(2) \cdot \varphi(13) = 1 \cdot 12 = 12$. 12 27 $\varphi(27) = \varphi(3^3) = 3^2(3-1) = 18$. 18 28 $\varphi(28) = \varphi(4 \cdot 7) = \varphi(4) \cdot \varphi(7) = 2 \cdot 6 = 12$ 12 29 $\varphi(29) = 29^0(29-1) = 28$ since 29 is prime. 28 30 $\varphi(30) = \varphi(2 \cdot 3 \cdot 5) = \varphi(2) \cdot \varphi(3) \cdot \varphi(5) = 1 \cdot 2 \cdot 4 = 8$ 8

### Construct solutions to a particular Diophantine equation from a given solution

Let $a, b, N$ be integers with $a,b \neq 0$, and let $d = \mathsf{gcd}(a,b)$. Suppose $(x_0,y_0)$ is a solution of the equation $ax + by = N$. Prove that for any integer $t$, $(x_0 + \frac{b}{d} t, y_0 - \frac{a}{d} t)$ is also a solution of $ax + by = N$.

Let $x_t = x_0 + \frac{b}{d} t$ and $y_t = y_0 - \frac{a}{d} t$. Then we have that

 $a x_t + b y_t$ = $a(x_0 + \frac{b}{d} t) + b(y_0 - \frac{a}{d} t)$ = $ax_0 + \frac{ab}{d} t + by_o - \frac{ab}{d} t$ = $ax_0 + by_0$ = $N$.

Thus $(x_t,y_t)$ is a solution of $ax + by = N$.

### An integer which divides a product need not divide either factor

Prove that if $n$ is composite then there are integers $a$ and $b$ such that $n$ divides $ab$ but not $a$ or $b$.

We will use a couple of facts about integers. For all integers $a$ and $b$,

1. If $a \geq 0$ and $b > 0$, then $a \leq ab$.
2. $|ab| = |a|\cdot|b|$.
3. If $a|b$ and $b \neq 0$, then $|a| \leq |b|$.
4. If $ab = 0$ then either $b = 0$ or $a = 0$.
5. If $ab = 1$ then either $a = b = 1$ or $a = b = -1$.

Proof of 1: We proceed by induction on $a$. First, note that the proposition is trivial for $a = 0$. Suppose now that the proposition is true for $a = n \geq 0$. Then for all $b > 0$, we have $n < nb$, so $n+1 < nb + 1 < nb + b = (n+1)b$. $\square$

Proof of 2: Note that the proposition is trivial if $a = 0$ or $b = 0$. There are two cases to consider. (1) If $a$ and $b$ have the same sign, we have
$|ab| = ab = |a| \cdot |b|$. (2) If $a$ and $b$ have opposite signs, without loss of generality say $b < 0$. Then
$|ab| = -ab = a(-b) = |a| \cdot |b|$. $\square$

Proof of 3: If $a|b$ then we have $ak = b$ for some integer $k$. Thus
$|a| \leq |a| \cdot |k| = |ak| = |b|$.

Proof of 4: Suppose by way of contradiction that $ab = 0$ and $b \neq 0$. Then using the previous propositions we have the following.
$|a| \leq |a| \cdot |b| = |ab| = |0| = 0$. Hence $a = 0$. Similarly, if $a \neq 0$, then $b = 0$. $\square$

Proof of 5: First note that $a,b \neq 0$. Now suppose otherwise; then without loss of generality, $|a| > 1$. Hence
$1 = |1| = |ab| = |a| \cdot |b| \geq |a| > 1$, a contradiction. $\square$

We now approach the main problem. Let $n$ be composite; then by definition we have $n = ab$ for some integers $a$ and $b$ with $a,b \neq \pm 1, \pm n$. Clearly $n|ab$. Now suppose by way of contradiction that $n|a$. Then we have $kn = a$ for some integer $k$. Now $kba = a$, so $(kb-1)a = 0$, so $kb = 1$. Thus $b = \pm 1$, a contradiction, so $n$ does not divide $a$. Similarly, $n$ does not divide $b$.

### If an integer divides the greadest common divisor of two integers, then it divides any linear combination of the two integers

Let $a,b,k$ be integers. Prove that if $k$ divides $a$ and $b$, then $k$ divides $as + bt$ for all integers $s$ and $t$.

Suppose $k$ divides $a$ and $b$; then there exist integers $n$ and $m$ such that $a = kn$ and $b = km$. Now we have $as + bt = kns + kmt = k(ns + mt)$ for all $s,t$, so $k$ divides $as + bt$.

### Perform the Euclidean Algorithm on given pairs of numbers

For each of the following pairs of integers $a$ and $b$, determine their greatest common divisor and their least common multiple, and write their greatest common divisor in the form $ax + by$ for some integers $x$ and $y$.

• $a = 20$ and $b = 13$.
• To find the greatest common divisor, we apply the Euclidean algorithm as follows.
 20 = (1)13 + 7 13 = (1)7 + 6 7 = (1)6 + 1 6 = (6)1 + 0.

Hence $\mathsf{gcd}(20,13) = 1$.

• To find the least common multiple, recall that for all integers $a$ and $b$, $\mathsf{gcd}(a,b) \cdot \mathsf{lcm}(a.b) = a \cdot b$. In particular, $\mathsf{lcm}(20,13) = (20 \cdot 13)/\mathsf{gcd}(20,13) = 260$.
• “Reversing” the Euclidean algorithm, we have
 1 = 7 – 6 = 20 – 2(13) + 7 = 2(20) – 3(13).
• $a = 69$ and $b = 372$.
• We apply the Euclidean algorithm to find the greatest common divisor as follows.
 372 = (5)69 + 27 69 = (2)27 + 15 27 = (1)15 + 12 15 = (1)12 + 3 12 = (4)3 + 0.

Hence $\mathsf{gcd}(372,69) = 3$.

• We have $\mathsf{lcm}(372,69) = (372 \cdot 69)/\mathsf{gcd}(372,69) = 8556$.
• Reversing the Euclidean algorithm, we have
 3 = 15-12 = 69 – 3(27) + 15 = 17(69) – 3(372) – 2(27) = 27(69) – 5(372)
• $a = 792$ and $b = 275$.
• We apply the Euclidean algorithm to find the greatest common divisor as follows.
 792 = (2)275 + 242 275 = (1)242 + 33 242 = (7)33 + 11 33 = (3)11 + 0

Hence $\mathsf{gcd}(792,275) = 11$.

• We have
$\mathsf{lcm}(792,275) = (792 \cdot 295)/\mathsf{gcd}(792,275) = 19800$.
• Reversing the Euclidean algorithm as before gives
$11 = 8(792) - 23(275)$.
• $a = 11391$ and $b = 5673$.
• We apply the Euclidean algorithm to find the greatest common divisor as follows.
 11391 = (2)5673 + 45 5673 = (126)45 + 3 45 = (15)3 + 0

Hence $\mathsf{gcd}(11391,5673) = 3$.

• As before, $\mathsf{lcm}(11391,5673) = 21540381$.
• Reversing the Euclidean algorithm as before gives
$3 = 253(5673) - 126(11391)$.
• $a = 1761$ and $b = 1567$.
• We apply the Euclidean algorithm to find the greatest common divisor as follows.
 1761 = (1)1567 + 194 1567 = (8)194 + 15 194 = (12)15 + 14 15 = (1)14 + 1 14 = (14)1 + 0

Hence $\mathsf{gcd}(1761,1567) = 1$.

• As before, $\mathsf{lcm}(1761,1567) = 2759487$.
• Reversing the Euclidean algorithm as before gives
$1 = 118(1567) - 105(1761)$.
• $a = 507885$ and $b = 60808$.
• We apply the Euclidean algorithm to find the greatest common divisor as follows.
 507885 = (8)60808 + 21421 60808 = (2)21421 + 17966 21421 = (1)17966 + 3455 17966 = (5)3455 + 691 3455 = (5)691 + 0

Hence $\mathsf{gcd}(507885,60808) = 691$.

• As before, $\mathsf{lcm}(507885,60808) = 44693880$.
• Reversing the Euclidean algorithm gives
$691 = 142(60808) - 17(507885)$.

### Demonstrate that a given relation defined in terms of a surjective function is an equivalence relation

Let $f : A \rightarrow B$ be a surjective map of sets. Prove that the relation $\sim$ on $A$ given by $a \sim b$ iff $f(a) = f(b)$ is an equivalence relation and that the equivalence classes of $\sim$ are precisely the fibers (i.e. the preimages of elements) of $f$.

First we show that $\sim$ is an equivalence relation.

1. We have $f(a) = f(a)$ for all $a \in A$ since set equality is reflexive, $\sim$ is reflexive.
2. Suppose $a \sim b$. Then $f(a) = f(b)$. Since set equality is symmetric, $f(b) = f(a)$, hence $b \sim a$. Thus $\sim$ is symmetric.
3. Suppose $a \sim b$ and $b \sim c$. Then we have $f(a) = f(b)$ and $f(b) = f(c)$. Since set equality is transitive, we have $f(a) = f(c)$, hence $a \sim c$. Thus $\sim$ is transitive.

Now we will show that every $\sim$-equivalence class is the preimage of some element of $B$ and vice versa.

• Let $X$ be a $\sim$-equivalence class. Then $X$ is nonempty; choose some $x \in X$. By definition, then, for all $a \in A$ we have $a \in X$ if and only if $a \sim x$; that is, $f(a) = f(x)$. Since $X$ was arbitrary, we have that $X$ is the $f$-preimage of some $x \in B$ for all $\sim$-equivalence classes $X$.
• Let $x \in B$, and consider $f^\star(x)$, the $f$-preimage of $x$. Note that for all $a \in A$, we have $a \in f^\star(x)$ if and only if $f(a) = f(x)$; that is, $a \sim x$. Since $x$ was arbitrary, we have that $f^\star(x)$ is a $\sim$-equivalence class for all $x \in B$. $\blacksquare$

### Determine whether a given relation is well defined

Determine whether the function $f : \mathbb{R}^+ \rightarrow \mathbb{Z}$ given by mapping a real number $r$ to the first digit to the right of the decimal point in a decimal expansion of $r$ is well defined.

Recall that every real number which terminates in an infinite string of 0s has a second expansion which terminates in an infinite string of 9s. Any real number which terminates in an infinite string of 0s beginning in the first decimal place will be a counterexample to the functionhood of this relation. In particular, we have $1 = 1.000\ldots$ and $1 = 0.999\ldots$, but $f(1.000\ldots) = 0 \neq 9 = f(0.999\ldots)$.