1. **Find the number of positive integers \( \leq 3000 \) divisible by 3, 5 or 7.** We use the Inclusion-Exclusion Principle. - Let \(A\) be multiples of 3, \(B\) multiples of 5, \(C\) multiples of 7. - Number of multiples of \(k\) up to \(n\) is \(\left\lfloor \frac{n}{k} \right\rfloor\). Calculate: \[|A| = \left\lfloor \frac{3000}{3} \right\rfloor = 1000, \quad |B| = \left\lfloor \frac{3000}{5} \right\rfloor = 600, \quad |C| = \left\lfloor \frac{3000}{7} \right\rfloor = 428\] Intersections: \[|A \cap B| = \left\lfloor \frac{3000}{15} \right\rfloor = 200, \quad |A \cap C| = \left\lfloor \frac{3000}{21} \right\rfloor = 142, \quad |B \cap C| = \left\lfloor \frac{3000}{35} \right\rfloor = 85\] Triple intersection: \[|A \cap B \cap C| = \left\lfloor \frac{3000}{105} \right\rfloor = 28\] By Inclusion-Exclusion: \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \] \[ = 1000 + 600 + 428 - 200 - 142 - 85 + 28 = 1629 \] --- 2. **State and Prove the Division Algorithm Theorem.** **Theorem:** For any integers \(a\) and \(b > 0\), there exist unique integers \(q\) and \(r\) such that \[ a = bq + r \quad \text{with} \quad 0 \leq r < b \] **Proof:** - Consider the set \(S = \{a - bk \mid k \in \mathbb{Z}, a - bk \geq 0\}\). - Since \(b > 0\), \(S\) is non-empty and contains non-negative integers. - By the Well-Ordering Principle, \(S\) has a least element \(r = a - bq\) for some integer \(q\). - By construction, \(r \geq 0\). - If \(r \geq b\), then \(r - b = a - b(q+1) \geq 0\), contradicting minimality of \(r\). - Hence, \(0 \leq r < b\). - Uniqueness follows by assuming two such pairs and showing \(q = q'\) and \(r = r'\). --- 3. **Find the number of positive integers \( \leq 6000 \) divisible by 3, 5 or 7.** Using Inclusion-Exclusion again: \[ |A| = \left\lfloor \frac{6000}{3} \right\rfloor = 2000, \quad |B| = \left\lfloor \frac{6000}{5} \right\rfloor = 1200, \quad |C| = \left\lfloor \frac{6000}{7} \right\rfloor = 857 \] \[ |A \cap B| = \left\lfloor \frac{6000}{15} \right\rfloor = 400, \quad |A \cap C| = \left\lfloor \frac{6000}{21} \right\rfloor = 285, \quad |B \cap C| = \left\lfloor \frac{6000}{35} \right\rfloor = 171 \] \[ |A \cap B \cap C| = \left\lfloor \frac{6000}{105} \right\rfloor = 57 \] Calculate: \[ |A \cup B \cup C| = 2000 + 1200 + 857 - 400 - 285 - 171 + 57 = 4258 \] --- 4. **Establish the validity of the number pattern:** \[ 9 \cdot 9 + 7 = 88 \] \[ 98 \cdot 9 + 6 = 888 \] \[ 987 \cdot 9 + 5 = 8888 \] \[ 9876 \cdot 9 + 4 = 88888 \] Observe the pattern: - The left number is a sequence of digits from 9 down to 6, 5, 4... - Multiply by 9 and add a decreasing number from 7 down to 4. Check the first: \[ 9 \times 9 + 7 = 81 + 7 = 88 \] Second: \[ 98 \times 9 + 6 = 882 + 6 = 888 \] Third: \[ 987 \times 9 + 5 = 8883 + 5 = 8888 \] Fourth: \[ 9876 \times 9 + 4 = 88884 + 4 = 88888 \] The pattern holds by direct multiplication and addition. --- 5. **Prove that every composite number \(n\) has a prime factor \(p\).** - A composite number \(n\) is by definition not prime and greater than 1. - If \(n\) is composite, it can be written as \(n = ab\) where \(a,b > 1\). - If \(a\) is prime, then \(a\) is a prime factor. - If not, factor \(a\) further. - Repeating this process, since numbers decrease, eventually a prime factor is found. - Hence, every composite number has at least one prime factor. --- 6. **Use Euclidean algorithm to find \(\gcd(3076, 1976)\) and express it as a linear combination.** Apply Euclidean algorithm: \[ 3076 = 1976 \times 1 + 1100 \] \[ 1976 = 1100 \times 1 + 876 \] \[ 1100 = 876 \times 1 + 224 \] \[ 876 = 224 \times 3 + 204 \] \[ 224 = 204 \times 1 + 20 \] \[ 204 = 20 \times 10 + 4 \] \[ 20 = 4 \times 5 + 0 \] So \(\gcd(3076, 1976) = 4\). Express 4 as linear combination: \[ 4 = 204 - 20 \times 10 \] Substitute \(20 = 224 - 204\): \[ 4 = 204 - (224 - 204) \times 10 = 204 \times 11 - 224 \times 10 \] Substitute \(204 = 876 - 224 \times 3\): \[ 4 = (876 - 224 \times 3) \times 11 - 224 \times 10 = 876 \times 11 - 224 \times 43 \] Substitute \(224 = 1100 - 876\): \[ 4 = 876 \times 11 - (1100 - 876) \times 43 = 876 \times 54 - 1100 \times 43 \] Substitute \(876 = 1976 - 1100\): \[ 4 = (1976 - 1100) \times 54 - 1100 \times 43 = 1976 \times 54 - 1100 \times 97 \] Substitute \(1100 = 3076 - 1976\): \[ 4 = 1976 \times 54 - (3076 - 1976) \times 97 = 1976 \times 151 - 3076 \times 97 \] Thus, \[ \gcd(3076, 1976) = 4 = 1976 \times 151 - 3076 \times 97 \] --- 7. **Prove that there are infinitely many primes.** **Proof by contradiction:** - Suppose there are finitely many primes \(p_1, p_2, \ldots, p_n\). - Consider \(Q = p_1 p_2 \cdots p_n + 1\). - \(Q\) is not divisible by any \(p_i\) because dividing \(Q\) by \(p_i\) leaves remainder 1. - So either \(Q\) is prime or has prime factors not in the list. - This contradicts the assumption that \(p_1, \ldots, p_n\) are all primes. - Hence, infinitely many primes exist. --- 8. **State and prove the Fundamental Theorem of Arithmetic.** **Theorem:** Every integer greater than 1 can be written uniquely as a product of prime numbers, up to the order of the factors. **Proof:** - Existence: Use induction. For \(n=2\), prime itself. - If \(n\) is prime, done. - If composite, factor into \(a\) and \(b\), both less than \(n\). - By induction, factor \(a\) and \(b\) into primes. - Uniqueness: Suppose two prime factorizations differ. - By Euclid's lemma, a prime dividing the product divides one of the primes in the other factorization. - Repeatedly cancel primes to show factorizations are the same up to order. --- **Final answers:** 1. 1629 3. 4258 6. \(\gcd = 4 = 1976 \times 151 - 3076 \times 97\)