What are consecutive multiples

6 - Institute of Mathematics

Prof. Dr. Jörn Steuding, Pascal Stumpf Institute for Mathematics, University of Würzburg November 28, 2016 Elementary Number Theory - Exercise 6 Exercise 1. [5 x; 2 points] Prove or disprove the following statements: (i) There is some m ∈ N such that we can write 2Z ∩ 3Z = mZ. (ii) There is some m ∈ N such that we can write 2Z ∪ 3Z = mZ. (iii) Among the three sets {3n: n ∈ N}, {3n + 1: n ∈ N} and {3n + 2: n ∈ N} at least one contains only finitely many prime numbers. (iv) Among the three sets {3n: n ∈ N}, {3n + 1: n ∈ N} and {3n + 2: n ∈ N} at least one contains infinitely many prime numbers. (v) For any six consecutive natural numbers we can always find at least one prime number that divides only exactly one of them. Exercise 2. [4 + 6 points] Let n ∈ N. This exercise deals with the following question: What can be said about the sum of the first n natural numbers which, when divided by 3, leave a remainder 0, 1 or 2? (i) Prove by induction n X (3j - 2) = 21 n (3n - 1). j = 1 (ii) Derive formulas similar to (i) for the following expressions: n n X X (3j) (3j - 1) and j = 1 j = 1 and verify them. Note: Induction does not necessarily have to be used here. Exercise 3. [3 + 4 + 3 points] We denote with lcm [a, b] the smallest common multiple of two integers a and b and we mean the smallest natural number m that is shared by both a and b. (i) Use the well-order to explain that lcm [a, b] exists. (ii) Prove Y kgV [a, b] = pmax {νp (a), νp (b)}, Q p νp (a) and b = (where a = ppb) and deduce Q p pνp (b ) the prime factorizations of a and lcm [a, b] · gcd (a, b) = ab. (iii) Find the least common multiple of the following pairs: a = 12 & amp; b = 18 a = 264 & amp; b = 220 a = Fn + 1 & amp; b = Fn, where Fn stands for the nth Fibonacci number. Exercise sheets are always given out on Mondays in the lecture; they are also available online on the homepage https://www.mathematik.uni-wuerzburg.de/∼steuding/elemzahlheo2016.htm (as are the slides). Completed exercise sheets must be handed in in groups of a maximum of three students in room 00.105 of the BSZ in the Elementary Number Theory mailbox by 12 noon on the Wednesday of the following week. The exam will take place from 10 a.m. to 12 p.m. on February 20, 2017 in the Turing lecture hall! 50% of the exercise points (30 per sheet) are required for the exam admission. Have fun! Solution to exercise 1: The first statement (i) is true, since 2Z ∩ 3Z contains all integers that are divisible by 2 and 3, i.e. all integer multiples of 6, for which we can use the form 6 · a with a ∈ Z fast 6 · a = 2 * 3a = 3 * 2a ∈ 2Z ∩ 3Z, and since on the other hand all other integers of the forms 6a + 1, 6a + 3, 6a + 5 are not in 2Z and those of the forms 6a + 2, 6a + 4 are not in 3Z, so 2Z ∩ 3Z = 6Z. The two consecutive numbers 2 ∈ 2Z ⊂ 2Z ∪ 3Z and 3 ∈ 3Z ⊂ 2Z ∪ 3Z can already whisper m = 1 to us with the approach 2Z ∪ 3Z = mZ for a m ∈ N over 2 ∈ mZ and 3 ∈ mZ, since out 2 = m * a2 (a2 ∈ Z) only m ∈ {1, 2} and from 3 = m · a3 (a3 ∈ Z) can only follow m ∈ {1, 3}. In 1Z = Z there is also 1, but it is not in 2Z ∪ 3Z, which refutes (ii). Besides our prime number 3, there cannot be any further prime numbers in the set {3n: n ∈ N} = 3N, because all other numbers of the form 3 · n are there at n & gt; 2 put together as (real) multiples of 3, which confirms (iii). On the other hand, we have already shown in the lecture that there are infinitely many prime numbers, each of which, apart from 2, falls into exactly one of our three sets, the disjoint union of which covers all natural numbers from 3 (division by remainder). According to the pigeonhole principle, there must be an infinite number of prime numbers in at least one of these sets, otherwise each set would be individually and thus also in their union {3n: n ∈ N} ∪ {3n + 1: n ∈ N} ∪ {3n + 2: n ∈ N} = N \ {1, 2} but there are only finitely many prime numbers, a contradiction, and (iv) is true. First we observe that the prime number 5 only divides exactly one of the smallest six natural numbers 1, 2, 3, 4, 5, 6. Hence we can assume that all six consecutive natural numbers n, n + 1,. . . , n + 5 are greater than 1 (n & gt; 2) and therefore each of them can be written as a product of prime numbers according to the fundamental theorem of arithmetic. Among them there are always three even numbers, because for both possible cases n = 2a + 0 or n = 2a + 1, with a ∈ N, are in the corresponding sequences 2a + 0, 2a + 1, 2a + 2, 2a + 3, 2a + 4, 2a + 5 or 2a + 1, 2a + 2, 2a + 3, 2a + 4, 2a + 5, 2a + 6 each have exactly three even (underlined) numbers. Analogously (n = 3a + 0, 3a + 1, 3a + 2) we can also find out that exactly two of them are divisible by 3, whereby exactly one of these two numbers is already divisible by 2. So there always remain exactly two odd numbers that can only be divisible by larger prime numbers from 5 onwards. But only one of these two odd numbers can be divisible by 5, because even if 5 divides two of our six numbers, i.e. the first number n and the last number n + 5, exactly one of the two would again be even. So together there is certainly still an (odd) number left that is not divisible by 2, 3 or 5. All their prime factors are therefore greater than 6, and thus cannot divide any of the other five numbers, which means that we have definitely found at least one prime number that divides only one of our six numbers, which proves (v). Solution to Exercise 2: To i): Proof by complete induction according to n. Induction start n = 1: 1 X (3j - 2) = 1 = 21 1 (3 · 1 - 1), j = 1 so that applies Formula to be proven for n = 1. Induction step n 7 → n + 1: Using the induction assumption (i.e. the formula for n) we should prove the 3 formula to be proven for n + 1 instead of n, i.e. n + 1 X (3j - 2) = 21 (n + 1) (3 (n + 1) - 1) = 32 n2 + 25 n + 1. j = 1 For this we write the left side as n + 1 X n X j = 1 j = 1 (3j - 2) = 3 (n + 1) - 2 + (3j - 2) and insert for the sum on the right the expression 12 n (3n - 1), which is equivalent according to the induction hypothesis: n + 1 X (3j - 2) = 3 (n + 1) - 2 + 21 n (3n - 1). j = 1 This expression is equal to 3 2 2n + 25 n + 1, which brings the induction step and the induction is complete. To ii): Using the known empirical formula 1 + 2 +. . . + m = 12 m (m + 1) (from Theorem 2.1) we find n X (3j) = 3 j = 1 n X j = 3 *. 21 n (n + 1) = 12 n (3n + 3) j = 1 and n X j = 1 (3j - 1) = 3 n X j - n = 3 · 12 n (n + 1) - n = 21 n (3n + 1) - n. J = 1 Solution to exercise 3: To i): OBdA let a and b be natural numbers and let V be the set of all multiples of a and b in the set of natural numbers, i.e. V: = {n ∈ N: a | n & amp; b | n}. Because from ∈ V, V 6 = ∅. According to theorem 2.3 of the well-order, V has a smallest element as a non-empty subset of N; this is the smallest common multiple k: = kgV [a, b] of a and b (because it is a multiple of a and b, so k ∈ V, and every multiple v of a and b satisfies v ≥ k due to minimality ). Regarding ii): The least common multiple of a and b has, as a natural number, a unique prime factorization (according to Fundamental Theorem 6.2). If p is a prime νp (a) Q dem νp (b) number and if a = pp and b = pp are the prime factorizations of a and b, then for the prime power pν, which goes up in kgV [a, b], surely ν ≥ νp (a) and ν ≥ νp (b) hold; with the minimality of the least common multiple or the minimality of ν results in Y kgV [a, b] = pmax {νp (a), νp (b)}. p Together with the analogous formula Y gcd (a, b) = pmin {νp (a), νp (b)} p 4 for the greatest common factor, we get Y Y kgV [a, b] · p. gcd (a, b) = pmax {νp (a), νp (b)} · pmin {νp (a), νp (b)} p = Y pp max {νp (a), νp (b)} + min {νp (a), νp (b)} p = Y p pνp (a) + νp (b) = Y p pνp (a) · Y pνp (b) = a · b. p To iii): The least common multiple of a and b can easily be calculated for small a and b via the prime factorization (see (ii)): lcm [12, 18] = lcm [22 · middot; 3, 2 · 32] = 22 · 32 = 36, kgV [264, 220] = kgV [23 * 3 · 11, 22 • 5 · 11] = 23 * 3 · 5 · 11 = 1320. In the case of the Fibonacci numbers, we use their coprime numbers (see the attendance problem for the fifth week), i.e. gcd (Fn + 1, Fn) = 1 and the second formula from (ii): lcm [Fn + 1, Fn] = Fn + 1 Fn.