Solutions to Exercises solutionsch:primes1 [ .ex:binomdiv] First we show by induction on n that the binomial coefficients nk, for 0 ≤ k ≤ n, are integers. For the base case, note that 10 = 11 = 1. Next, suppose that nk is an integer for 0 ≤ k ≤ n. Then n + 10 = n + 1n + 1 = 1, and for 0 ≤ i ≤ n − 1, align* ni + ni+1 = n!i!(n-i-1)! (1n − i + 1i + 1) Since p is prime, it suffices to show that there is no factor of p in the denominator. By assumption,

r < p so pr!, and similarly 1 ≤ r implies that p − r ≤ p − 1 < p, so (p − r)! also contains no factor of p. [ .ex:gcds] The gcds are 5, 13, 3, 8. E.g., gcd(15, 35) = gcd(15, 5) = gcd(5, 0) = 5. [ .ex:sumn] enumerate T he base case is trivial. If the statment is true for n, then

1 + ⋯ + (n + 1) = n(n + 1)2 + (n + 1) = (n + 1)(n + 2)2,

as desired. I f n is even group the terms as (1 − 2) + (3 − 4) + ⋯ + (n − 1 − n) = −n2, and if n is odd we have

1 + (−2 + 3) + (−4 + 5) + ⋯ + (−(n − 1) + n) = n + 12, so the general formula is (−1)^{n+1}⌈n2⌉.