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).