IOQM Number Theory Mastery (continued)

Cheatsheet Content

### Introduction to IOQM Number Theory Welcome to your journey to master Number Theory for the Indian Olympiad Qualifier in Mathematics (IOQM)! This cheatsheet is designed to guide you step-by-step, level-by-level, from fundamental concepts to advanced problem-solving techniques. Each level includes essential theory, solved examples, and practice problem sets with detailed solutions. **How to Use This Cheatsheet:** 1. **Understand the Theory:** Read through the theory section for each level carefully. 2. **Analyze Solved Examples:** Pay close attention to the thought process and steps in the solved examples. 3. **Attempt Practice Problems:** Solve the practice problems without looking at the solutions first. 4. **Review Solutions:** After attempting all problems in a set, compare your solutions with the provided detailed solutions. Learn from your mistakes. 5. **Progress Systematically:** Do not jump to higher levels until you are comfortable with the current one. Let's begin! ### Level 1: Divisibility and Factors #### Theory - **Divisibility:** An integer $a$ is divisible by an integer $b$ (denoted as $b|a$) if $a = bk$ for some integer $k$. - **Properties of Divisibility:** - If $a|b$ and $b|c$, then $a|c$. - If $a|b$ and $a|c$, then $a|(bx + cy)$ for any integers $x, y$. - Any non-zero integer $a$ divides $0$. - $1$ divides every integer. - **Factors/Divisors:** If $a|b$, then $a$ is a factor (or divisor) of $b$. - **Prime Numbers:** A natural number greater than 1 that has no positive divisors other than 1 and itself. - **Composite Numbers:** A natural number greater than 1 that is not prime. - **Fundamental Theorem of Arithmetic:** Every integer greater than 1 can be uniquely represented as a product of prime numbers (up to the order of the factors). Example: $12 = 2^2 \times 3^1$. - **Number of Divisors ($\tau(n)$ or $d(n)$):** If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$. - **Sum of Divisors ($\sigma(n)$):** $\sigma(n) = \frac{p_1^{a_1+1}-1}{p_1-1} \cdots \frac{p_k^{a_k+1}-1}{p_k-1}$. #### Solved Examples **Example 1:** Find the number of divisors of 360. *Solution:* First, find the prime factorization of 360. $360 = 36 \times 10 = (2^2 \times 3^2) \times (2 \times 5) = 2^3 \times 3^2 \times 5^1$. Using the formula for the number of divisors: $\tau(360) = (3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$. So, 360 has 24 divisors. **Example 2:** Show that if $a|b$ and $a|c$, then $a|(b+c)$. *Solution:* Since $a|b$, there exists an integer $k_1$ such that $b = ak_1$. Since $a|c$, there exists an integer $k_2$ such that $c = ak_2$. Adding these two equations, we get $b+c = ak_1 + ak_2 = a(k_1+k_2)$. Since $k_1+k_2$ is an integer, by the definition of divisibility, $a|(b+c)$. **Example 3:** Find the smallest positive integer with exactly 6 divisors. *Solution:* Let $n$ be an integer. If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, then $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1) = 6$. The possible ways to write 6 as a product of integers greater than or equal to 2 are: 1. $6$ (meaning $a_1+1=6 \implies a_1=5$) 2. $3 \times 2$ (meaning $a_1+1=3 \implies a_1=2$ and $a_2+1=2 \implies a_2=1$) Case 1: $n = p^5$. To minimize $n$, choose the smallest prime $p=2$. So $n = 2^5 = 32$. Case 2: $n = p_1^2 p_2^1$. To minimize $n$, choose the smallest primes for $p_1$ and $p_2$. - If $p_1=2, p_2=3$, then $n = 2^2 \times 3^1 = 4 \times 3 = 12$. - If $p_1=3, p_2=2$, then $n = 3^2 \times 2^1 = 9 \times 2 = 18$. Comparing 32, 12, and 18, the smallest is 12. #### Practice Problems - Set 1 1. Find the sum of all positive divisors of 100. 2. Determine if $7^{100} - 1$ is divisible by 48. 3. How many positive integers less than or equal to 100 have an odd number of divisors? 4. If $n$ is a positive integer such that $n^2$ has 15 divisors, how many divisors can $n$ have? 5. What is the largest integer $k$ such that $2^k$ divides $20!$? #### Practice Problems - Set 2 1. Find the number of integers between 1 and 200 (inclusive) that are divisible by 3 but not by 5. 2. Prove that for any prime $p$, $p$ divides $\binom{p}{k}$ for $1 \le k \le p-1$. 3. If $n$ is a perfect number (a number equal to the sum of its proper divisors), show that $\sigma(n) = 2n$. 4. Find the smallest positive integer $n$ such that $2023n$ is a perfect square. 5. If $a, b$ are integers such that $a|b$ and $b|a$, prove that $a = \pm b$. #### Practice Problems - Set 3 1. Find the number of positive divisors of $2^{10} \times 3^7 \times 5^3$. 2. Prove that the product of any three consecutive integers is divisible by 6. 3. Find the smallest positive integer $n$ such that $n$ has exactly 12 divisors. 4. If $a$ is an integer, show that $a^2 - a$ is always even. 5. Find the number of divisors of $10^5$. #### Practice Problems - Set 4 1. What is the smallest number that is divisible by 12, 15, and 20? 2. If $n$ is an integer, show that $n^3 - n$ is divisible by 3. 3. Find all positive integers $n$ for which $\tau(n)=4$. 4. If $p$ is a prime number, prove that $\sqrt{p}$ is irrational. 5. How many positive integers less than 100 are divisible by 4 or 6? #### Practice Problems - Set 5 1. Find the number of trailing zeros in $25!$. 2. If $a|b$ and $c|d$, prove that $ac|bd$. 3. Find the number of divisors of $720$. 4. Show that if $n$ is a composite number, then $n$ has a prime factor $p \le \sqrt{n}$. 5. What is the largest power of 3 that divides $30!$? #### Practice Problems - Set 6 1. Find the positive integers $n$ for which $\phi(n) = 2$. 2. If $n = p_1^{a_1} \cdots p_k^{a_k}$, prove that $n$ is a perfect number if and only if $\sigma(n) = 2n$. 3. Determine if the sum of two odd numbers is always even. 4. Find the smallest integer $k$ such that $10^k$ is divisible by $2^{10}$. 5. How many integers between 1 and 500 (inclusive) are not divisible by 2 or 3? #### Practice Problems - Set 7 1. Find the smallest positive integer $n$ such that $n$ has exactly 10 divisors. 2. Prove that if $a|bc$ and $\text{gcd}(a,b)=1$, then $a|c$. 3. Find the number of divisors of $2^3 \times 3^4 \times 5^1$ that are perfect squares. 4. Show that $n^2+n+1$ is never divisible by 2. 5. If $\text{gcd}(a,b)=1$, prove that $\text{gcd}(a+b, a-b)$ is either 1 or 2. #### Practice Problems - Set 8 1. Find the sum of the divisors of $p^k$ where $p$ is a prime number and $k \ge 1$. 2. Prove that for any integer $m > 1$, $m^4+4$ is a composite number. 3. Find the number of integers $n \le 100$ such that $n$ is divisible by 7 and $n$ has an even number of divisors. 4. If $a|b$, then prove that $\text{gcd}(a,b) = |a|$. 5. Find the largest integer $n$ such that $n^n$ divides $100!$. #### Practice Problems - Set 9 1. Show that for any integer $n$, $n^2+1$ is never divisible by 3. 2. Find the number of divisors of $1440$. 3. If $p$ is a prime, and $a^2 \equiv b^2 \pmod p$, prove that $a \equiv b \pmod p$ or $a \equiv -b \pmod p$. 4. Determine if $111 \ldots 1$ ($n$ times) is divisible by 3. 5. Find the smallest positive integer $n$ such that $n/2$ is a perfect square, $n/3$ is a perfect cube, and $n/5$ is a perfect fifth power. #### Practice Problems - Set 10 1. Find the number of integers from 1 to 1000 that are multiples of 3 or 5. 2. Prove that if $n$ is an odd integer, then $n^2-1$ is divisible by 8. 3. Find all positive integers $n$ for which $\text{gcd}(n, n+1) = 1$. 4. If $p$ is a prime, what are the possible values for $\text{gcd}(p, p+1)$? 5. Show that if $n$ is a positive integer, then $n$ and $n+1$ are coprime. ### Level 2: GCD and LCM #### Theory - **Greatest Common Divisor (GCD):** The largest positive integer that divides both $a$ and $b$. Denoted as $\text{gcd}(a, b)$ or $(a, b)$. - **Least Common Multiple (LCM):** The smallest positive integer that is a multiple of both $a$ and $b$. Denoted as $\text{lcm}(a, b)$ or $[a, b]$. - **Relationship between GCD and LCM:** For any positive integers $a, b$, $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$. - **Euclidean Algorithm:** An efficient method for computing $\text{gcd}(a, b)$. - If $a = qb + r$, then $\text{gcd}(a, b) = \text{gcd}(b, r)$. - The last non-zero remainder in the Euclidean algorithm is the GCD. - **Bezout's Identity:** For any integers $a, b$, there exist integers $x, y$ such that $ax + by = \text{gcd}(a,b)$. - **Relatively Prime (Coprime):** Two integers $a, b$ are relatively prime if $\text{gcd}(a, b) = 1$. #### Solved Examples **Example 1:** Find $\text{gcd}(105, 30)$ using the Euclidean Algorithm. *Solution:* $105 = 3 \times 30 + 15$ $30 = 2 \times 15 + 0$ The last non-zero remainder is 15. So, $\text{gcd}(105, 30) = 15$. **Example 2:** If $\text{gcd}(a, b) = 12$ and $a \times b = 720$, find $\text{lcm}(a, b)$. *Solution:* We know that $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$. Substituting the given values: $12 \times \text{lcm}(a, b) = 720$ $\text{lcm}(a, b) = \frac{720}{12} = 60$. **Example 3:** Find integers $x, y$ such that $56x + 72y = \text{gcd}(56, 72)$. *Solution:* First, find $\text{gcd}(56, 72)$ using the Euclidean Algorithm: $72 = 1 \times 56 + 16$ $56 = 3 \times 16 + 8$ $16 = 2 \times 8 + 0$ So, $\text{gcd}(56, 72) = 8$. Now, work backwards to express 8 in the form $56x + 72y$: From the second step: $8 = 56 - 3 \times 16$ From the first step: $16 = 72 - 1 \times 56$ Substitute 16 in the expression for 8: $8 = 56 - 3 \times (72 - 1 \times 56)$ $8 = 56 - 3 \times 72 + 3 \times 56$ $8 = 4 \times 56 - 3 \times 72$ So, $x=4$ and $y=-3$. #### Practice Problems - Set 1 1. Find the GCD and LCM of 144 and 192. 2. The product of two numbers is 1800, and their LCM is 360. What is their GCD? 3. Find integers $x, y$ such that $101x + 103y = 1$. 4. Three bells ring at intervals of 12, 15, and 18 minutes respectively. If they start ringing together at 9 AM, when will they next ring together? 5. If $\text{gcd}(a, b) = d$, prove that $\text{gcd}(a/d, b/d) = 1$. #### Practice Problems - Set 2 1. Find $\text{gcd}(252, 198)$ using the Euclidean Algorithm. 2. If $\text{lcm}(a,b) = 450$ and $\text{gcd}(a,b) = 15$, and $a=75$, find $b$. 3. Show that $\text{gcd}(n, n+1) = 1$ for any positive integer $n$. 4. Find integer solutions $x, y$ for $24x + 36y = 12$. 5. The sum of two numbers is 120, and their GCD is 15. Find the numbers. #### Practice Problems - Set 3 1. Find the LCM of 28, 42, and 63. 2. Prove that $\text{gcd}(a, b) = \text{gcd}(a-b, b)$. 3. If $\text{gcd}(a, b) = 1$, prove that $\text{gcd}(a+b, a) = 1$. 4. Find the smallest positive integer $k$ such that $\text{lcm}(6, k) = 30$. 5. Two numbers are in the ratio 3:4. If their LCM is 180, what are the numbers? #### Practice Problems - Set 4 1. Use the Euclidean Algorithm to find $\text{gcd}(272, 119)$. 2. If $\text{gcd}(a,b) = 1$, show that $\text{gcd}(a^2, b^2) = 1$. 3. Find integers $x, y$ such that $17x - 13y = 1$. 4. A group of students can be arranged in rows of 6, 8, or 10 with no students left over. What is the minimum number of students in the group? 5. If $a$ and $b$ are positive integers, and $a|b$, prove that $\text{lcm}(a,b) = b$. #### Practice Problems - Set 5 1. Find the GCD and LCM of $2^3 \times 3^2 \times 5^1$ and $2^2 \times 3^4 \times 7^1$. 2. Prove that if $d$ is a common divisor of $a$ and $b$, then $d$ divides $\text{gcd}(a,b)$. 3. If $\text{gcd}(a, b) = d$, prove that there exist integers $x, y$ such that $ax + by = d$. 4. What is the smallest number that leaves a remainder of 1 when divided by 3, 5, and 7? 5. Given $\text{gcd}(x, y) = 5$ and $x+y=30$. Find $x$ and $y$. #### Practice Problems - Set 6 1. Find $\text{gcd}(100, 101)$. 2. If $\text{lcm}(a,b) = ab$ then what can you say about $a$ and $b$? 3. Prove that if $c$ is a common multiple of $a$ and $b$, then $\text{lcm}(a,b)$ divides $c$. 4. Find integers $x, y$ such that $60x + 100y = 20$. 5. The number of students in a class is between 40 and 50. If they are arranged in groups of 6, there are 2 students left. If they are arranged in groups of 8, there are 4 students left. How many students are there? #### Practice Problems - Set 7 1. Find $\text{gcd}(p, p^2)$ where $p$ is a prime. 2. If $a, b, c$ are positive integers, show that $\text{gcd}(a, \text{lcm}(b,c)) = \text{lcm}(\text{gcd}(a,b), \text{gcd}(a,c))$. 3. Prove that for any integer $n$, $\text{gcd}(n, n+2)$ is either 1 or 2. 4. Find the smallest positive integer that is divisible by all integers from 1 to 10. 5. If $k$ is a positive integer, prove that $\text{gcd}(k, k+1, k+2) = 1$. #### Practice Problems - Set 8 1. Find $\text{lcm}(10!, 12!)$. 2. If $\text{gcd}(a, b) = 1$, prove that $\text{gcd}(a+b, a-b)$ is 1 or 2. 3. Find integers $x, y$ such that $8x + 13y = 1$. 4. Two numbers have a product of 216 and their GCD is 6. Find their LCM. 5. Show that if $a, b$ are positive integers, then $\text{gcd}(a,b) \le \text{lcm}(a,b)$. #### Practice Problems - Set 9 1. Find $\text{gcd}(2023, 101)$. 2. If $\text{gcd}(a, b) = 1$, prove that $\text{gcd}(a, b^n) = 1$ for any positive integer $n$. 3. Find the number of pairs of positive integers $(a,b)$ such that $\text{gcd}(a,b)=18$ and $a+b=360$. 4. What is the largest integer that divides every number in the sequence $n(n+1)(n+2)$ for $n \ge 1$? 5. If $p$ is a prime number, what is $\text{gcd}(p!, (p+1)!)$? #### Practice Problems - Set 10 1. Find the GCD and LCM of $2^5 \times 3^1 \times 7^2$ and $2^2 \times 3^4 \times 5^1$. 2. Prove that if $ax + by = 1$, then $\text{gcd}(a,y)=1$. 3. If $\text{gcd}(a,b) = g$, then $\text{lcm}(a,b) = \frac{ab}{g}$. Prove this relationship. 4. A number when divided by 7, 8, and 9 leaves remainders 6, 7, and 8 respectively. Find the smallest such number. 5. Find positive integers $x, y$ such that $\text{gcd}(x,y)=1$ and $x+y=100$. How many such pairs are there? ### Level 3: Modular Arithmetic #### Theory - **Congruence:** $a \equiv b \pmod{m}$ means $m | (a-b)$. In other words, $a$ and $b$ have the same remainder when divided by $m$. - **Properties of Congruence:** - If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then: - $a+c \equiv b+d \pmod{m}$ - $a-c \equiv b-d \pmod{m}$ - $ac \equiv bd \pmod{m}$ - $a^n \equiv b^n \pmod{m}$ for any positive integer $n$. - **Division in Modular Arithmetic:** If $ac \equiv bc \pmod{m}$, then $a \equiv b \pmod{m/\text{gcd}(c,m)}$. If $\text{gcd}(c,m)=1$, then $a \equiv b \pmod{m}$. - **Modular Inverse:** An integer $x$ is a modular inverse of $a$ modulo $m$ if $ax \equiv 1 \pmod{m}$. An inverse exists if and only if $\text{gcd}(a,m)=1$. - **Fermat's Little Theorem:** If $p$ is a prime number, then for any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod{p}$. Also, $a^p \equiv a \pmod{p}$ for any integer $a$. - **Euler's Totient Theorem:** If $\text{gcd}(a,n)=1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is Euler's totient function (number of positive integers less than or equal to $n$ that are relatively prime to $n$). - **Chinese Remainder Theorem (CRT):** Solves systems of linear congruences with coprime moduli. #### Solved Examples **Example 1:** Find the remainder when $3^{100}$ is divided by 7. *Solution:* We need to find $3^{100} \pmod{7}$. By Fermat's Little Theorem, since 7 is prime and $\text{gcd}(3,7)=1$, we have $3^{7-1} \equiv 3^6 \equiv 1 \pmod{7}$. Now, divide the exponent 100 by 6: $100 = 16 \times 6 + 4$. So, $3^{100} = 3^{16 \times 6 + 4} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 3^4 \pmod{7}$ $3^4 = 81$. $81 \equiv 4 \pmod{7}$ (since $81 = 11 \times 7 + 4$). Therefore, $3^{100} \equiv 4 \pmod{7}$. **Example 2:** Solve the congruence $5x \equiv 3 \pmod{11}$. *Solution:* We need to find the modular inverse of 5 modulo 11. We are looking for an integer $x$ such that $5x \equiv 1 \pmod{11}$. By inspection or extended Euclidean algorithm: $5 \times 1 = 5 \equiv 5 \pmod{11}$ $5 \times 2 = 10 \equiv -1 \pmod{11}$ $5 \times (-2) \equiv 1 \pmod{11}$ Since $-2 \equiv 9 \pmod{11}$, the inverse of 5 modulo 11 is 9. Multiply both sides of the original congruence by 9: $9 \times 5x \equiv 9 \times 3 \pmod{11}$ $45x \equiv 27 \pmod{11}$ Since $45 \equiv 1 \pmod{11}$ and $27 \equiv 5 \pmod{11}$: $x \equiv 5 \pmod{11}$. The solution is $x \equiv 5 \pmod{11}$. **Example 3:** Find the last digit of $2^{2023}$. *Solution:* The last digit is the remainder when the number is divided by 10. So we need to find $2^{2023} \pmod{10}$. Since $\text{gcd}(2, 10) \ne 1$, we cannot directly use Euler's Totient Theorem with base 2 and modulus 10. Let's look at the powers of 2 modulo 10: $2^1 \equiv 2 \pmod{10}$ $2^2 \equiv 4 \pmod{10}$ $2^3 \equiv 8 \pmod{10}$ $2^4 \equiv 16 \equiv 6 \pmod{10}$ $2^5 \equiv 32 \equiv 2 \pmod{10}$ The pattern of the last digits is 2, 4, 8, 6, and it repeats every 4 powers. The cycle length is 4. We need to find $2023 \pmod 4$. $2023 = 4 \times 505 + 3$. So, $2^{2023} \equiv 2^3 \pmod{10}$ (this reduction works because the cycle starts from $2^1$). $2^{2023} \equiv 8 \pmod{10}$. The last digit is 8. #### Practice Problems - Set 1 1. Find the remainder when $17^{2023}$ is divided by 13. 2. Solve the system of congruences: $x \equiv 2 \pmod{3}$ $x \equiv 3 \pmod{5}$ 3. What is the smallest positive integer $n$ such that $2^n \equiv 1 \pmod{17}$? 4. Prove that for any integer $n$, $n^5 - n$ is divisible by 5. 5. Find the last two digits of $7^{77}$. #### Practice Problems - Set 2 1. Find the remainder when $2^{50}$ is divided by 7. 2. Solve the congruence $7x \equiv 5 \pmod{13}$. 3. What is the last digit of $3^{2024}$? 4. Prove that $n^3 \equiv n \pmod{6}$ for any integer $n$. 5. Find $x$ such that $x \equiv 1 \pmod{4}$ and $x \equiv 2 \pmod{5}$. #### Practice Problems - Set 3 1. Find the remainder when $10^{100}$ is divided by 11. 2. Solve the congruence $4x \equiv 6 \pmod{10}$. 3. What is the remainder when $1! + 2! + 3! + \ldots + 100!$ is divided by 12? 4. Show that $2^{30} + 3^{30}$ is divisible by 13. 5. Find the smallest positive integer $x$ such that $x \equiv 3 \pmod{7}$ and $x \equiv 5 \pmod{11}$. #### Practice Problems - Set 4 1. Find the last two digits of $3^{200}$. 2. Solve $12x \equiv 18 \pmod{30}$. 3. If $p$ is a prime, prove that $(a+b)^p \equiv a^p + b^p \pmod p$. 4. What is the remainder when $2023^{2023}$ is divided by 5? 5. Find an integer $x$ such that $x \equiv 1 \pmod{2}$, $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$. #### Practice Problems - Set 5 1. Find the remainder when $13^{13}$ is divided by 100. 2. Solve $15x \equiv 25 \pmod{35}$. 3. Prove that $a^2 \equiv 1 \pmod 8$ if $a$ is an odd integer. 4. What is the last digit of $7^{7^7}$? 5. Find the smallest positive integer $n$ such that $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{4}$, and $n \equiv 4 \pmod{5}$. #### Practice Problems - Set 6 1. Find the remainder when $2^{1000}$ is divided by 101. 2. Solve $3x \equiv 4 \pmod 5$. 3. Prove that if $p$ is a prime number, then $(p-1)! \equiv -1 \pmod p$ (Wilson's Theorem). 4. What is the remainder when $2^{100}$ is divided by 13? 5. Find the smallest positive integer $x$ such that $x \equiv 0 \pmod{2}$, $x \equiv 0 \pmod{3}$, $x \equiv 1 \pmod{5}$. #### Practice Problems - Set 7 1. Find the remainder when $3^{45}$ is divided by 17. 2. Solve $2x + 1 \equiv 5 \pmod 7$. 3. Show that a number is divisible by 9 if and only if the sum of its digits is divisible by 9. 4. What is the remainder when $100^{100}$ is divided by 7? 5. Find the smallest positive integer $n$ such that $n \equiv 1 \pmod{5}$, $n \equiv 2 \pmod{6}$, $n \equiv 3 \pmod{7}$. #### Practice Problems - Set 8 1. Find the last digit of $2023^{2023^{2023}}$. 2. Solve $9x \equiv 12 \pmod{15}$. 3. Prove that for any integer $n$, $n^2+n+1$ is never divisible by 4. 4. What is the remainder when $19^{19}$ is divided by 5? 5. Find the smallest positive integer $x$ such that $x \equiv 1 \pmod{3}$, $x \equiv 2 \pmod{4}$, $x \equiv 3 \pmod{5}$. #### Practice Problems - Set 9 1. Find the remainder when $5^{20}$ is divided by 24. 2. Solve $10x \equiv 15 \pmod{25}$. 3. Show that if $\text{gcd}(a,m)=1$, then $a^{\phi(m)} \equiv 1 \pmod m$. 4. What is the remainder when $2^{20} + 3^{20}$ is divided by 5? 5. Find the smallest positive integer $n$ such that $n \equiv 1 \pmod{2}$, $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{4}$. #### Practice Problems - Set 10 1. Find the remainder when $7^{2023} + 1$ is divided by 8. 2. Solve $14x \equiv 21 \pmod{35}$. 3. Prove that for any prime $p > 2$, $p^2 \equiv 1 \pmod 8$. 4. What is the last digit of $4^{100}$? 5. Find the number of solutions to $x^2 \equiv 1 \pmod{15}$. ### Level 4: Diophantine Equations #### Theory - **Linear Diophantine Equation:** An equation of the form $ax + by = c$, where $a, b, c$ are integers and we seek integer solutions for $x, y$. - **Existence of Solutions:** A linear Diophantine equation $ax + by = c$ has integer solutions if and only if $\text{gcd}(a, b)$ divides $c$. - **Finding Solutions:** 1. Find $d = \text{gcd}(a, b)$. If $d \nmid c$, no integer solutions exist. 2. If $d|c$, divide the entire equation by $d$: $a'x + b'y = c'$, where $a'=a/d, b'=b/d, c'=c/d$. Now $\text{gcd}(a', b')=1$. 3. Find a particular solution $(x_0, y_0)$ for $a'x + b'y = c'$ using the Extended Euclidean Algorithm or inspection. 4. The general solution is given by: $x = x_0 + (b'/d_0)k$ $y = y_0 - (a'/d_0)k$ where $d_0 = \text{gcd}(a', b') = 1$, so it simplifies to: $x = x_0 + b'k$ $y = y_0 - a'k$ for any integer $k$. - **Pythagorean Triples:** Integer solutions $(a, b, c)$ to $a^2 + b^2 = c^2$. - Primitive triples: $\text{gcd}(a, b, c) = 1$. - General form for primitive triples: $a = m^2 - n^2$, $b = 2mn$, $c = m^2 + n^2$ (or $a = 2mn$, $b = m^2-n^2$), where $m > n > 0$, $\text{gcd}(m, n)=1$, and $m, n$ have opposite parity. #### Solved Examples **Example 1:** Find all integer solutions to $12x + 18y = 30$. *Solution:* 1. Find $\text{gcd}(12, 18)$. $18 = 1 \times 12 + 6$ $12 = 2 \times 6 + 0$ So, $\text{gcd}(12, 18) = 6$. 2. Since $6 | 30$, solutions exist. Divide the equation by 6: $2x + 3y = 5$. 3. Find a particular solution for $2x + 3y = 5$. By inspection, if $x=1$, $2(1)+3y=5 \implies 3y=3 \implies y=1$. So $(x_0, y_0) = (1, 1)$ is a particular solution. 4. The general solution is: $x = x_0 + b'k = 1 + 3k$ $y = y_0 - a'k = 1 - 2k$ for any integer $k$. **Example 2:** Find all positive integer solutions to $5x + 7y = 100$. *Solution:* 1. $\text{gcd}(5, 7) = 1$. Since $1 | 100$, solutions exist. 2. Find a particular solution. We can write $5x = 100 - 7y$. Since $5x$ is a multiple of 5, $100 - 7y$ must be a multiple of 5. $100 - 7y \equiv 0 \pmod{5}$ $0 - 2y \equiv 0 \pmod{5}$ $-2y \equiv 0 \pmod{5}$ Multiply by $2 \pmod{5}$ (inverse of $-2 \equiv 3 \pmod{5}$): $4(-2y) \equiv 4(0) \pmod{5}$ $-8y \equiv 0 \pmod{5}$ $2y \equiv 0 \pmod{5}$ Since $\text{gcd}(2,5)=1$, $y \equiv 0 \pmod{5}$. So, $y$ must be a multiple of 5. Let $y_0 = 5$. $5x_0 + 7(5) = 100 \implies 5x_0 + 35 = 100 \implies 5x_0 = 65 \implies x_0 = 13$. So $(x_0, y_0) = (13, 5)$ is a particular solution. 3. The general solution is: $x = 13 + 7k$ $y = 5 - 5k$ We need positive integer solutions, so $x > 0$ and $y > 0$. $13 + 7k > 0 \implies 7k > -13 \implies k > -13/7 \implies k \ge -1$ (since $k$ is an integer). $5 - 5k > 0 \implies 5 > 5k \implies k ### Level 5: Further Topics (Advanced) #### Theory - **Number Theoretic Functions:** - $\phi(n)$ (Euler's Totient Function): Number of positive integers up to $n$ that are relatively prime to $n$. Multiplicative function. - $\tau(n)$ (Number of Divisors) - $\sigma(n)$ (Sum of Divisors) - Möbius function $\mu(n)$: $\mu(1)=1$; $\mu(n)=0$ if $n$ has a squared prime factor; $\mu(n)=(-1)^k$ if $n$ is a product of $k$ distinct primes. - Möbius Inversion Formula. - **Quadratic Residues:** An integer $a$ is a quadratic residue modulo $n$ if $x^2 \equiv a \pmod{n}$ has a solution. - Legendre Symbol $\left(\frac{a}{p}\right)$: For prime $p$. - Quadratic Reciprocity Law. - **Pell's Equation:** Equations of the form $x^2 - Dy^2 = 1$ (where $D$ is a positive non-square integer). - **Generating Functions for Number Theory:** Using power series to encode sequences. #### Solved Examples **Example 1:** Calculate $\phi(360)$. *Solution:* First, find the prime factorization of 360: $360 = 2^3 \times 3^2 \times 5^1$. Using the formula $\phi(n) = n \prod_{p|n} (1 - 1/p)$: $\phi(360) = 360 (1 - 1/2)(1 - 1/3)(1 - 1/5)$ $\phi(360) = 360 (1/2)(2/3)(4/5)$ $\phi(360) = \frac{360 \times 1 \times 2 \times 4}{2 \times 3 \times 5} = \frac{360 \times 8}{30} = 12 \times 8 = 96$. **Example 2:** Evaluate $\left(\frac{10}{13}\right)$. *Solution:* We use properties of the Legendre Symbol. $\left(\frac{10}{13}\right) = \left(\frac{2 \times 5}{13}\right) = \left(\frac{2}{13}\right) \left(\frac{5}{13}\right)$. For $\left(\frac{2}{p}\right)$: $\left(\frac{2}{p}\right) = 1$ if $p \equiv 1, 7 \pmod{8}$, and $-1$ if $p \equiv 3, 5 \pmod{8}$. Since $13 \equiv 5 \pmod{8}$, $\left(\frac{2}{13}\right) = -1$. For $\left(\frac{5}{13}\right)$: Using Quadratic Reciprocity Law: $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$. Here $p=5, q=13$. Both are primes. $\left(\frac{5}{13}\right) \left(\frac{13}{5}\right) = (-1)^{\frac{5-1}{2}\frac{13-1}{2}} = (-1)^{2 \times 6} = (-1)^{12} = 1$. So, $\left(\frac{5}{13}\right) = \left(\frac{13}{5}\right)$. Now, $\left(\frac{13}{5}\right) = \left(\frac{13 \pmod 5}{5}\right) = \left(\frac{3}{5}\right)$. For $\left(\frac{3}{5}\right)$: $\left(\frac{3}{5}\right) \left(\frac{5}{3}\right) = (-1)^{\frac{3-1}{2}\frac{5-1}{2}} = (-1)^{1 \times 2} = (-1)^2 = 1$. So, $\left(\frac{3}{5}\right) = \left(\frac{5}{3}\right)$. $\left(\frac{5}{3}\right) = \left(\frac{5 \pmod 3}{3}\right) = \left(\frac{2}{3}\right)$. Since $3 \equiv 3 \pmod{8}$, $\left(\frac{2}{3}\right) = -1$. Therefore, $\left(\frac{3}{5}\right) = -1$. So, $\left(\frac{5}{13}\right) = -1$. Finally, $\left(\frac{10}{13}\right) = \left(\frac{2}{13}\right) \left(\frac{5}{13}\right) = (-1) \times (-1) = 1$. #### Practice Problems - Set 1 1. Calculate $\phi(1001)$. 2. Prove that $\sum_{d|n} \phi(d) = n$. 3. Determine if 3 is a quadratic residue modulo 19. 4. Find the fundamental solution to Pell's equation $x^2 - 2y^2 = 1$. 5. If $n$ is a positive integer, prove that $n$ has an even number of divisors if and only if $n$ is not a perfect square. #### Practice Problems - Set 2 1. Calculate $\phi(p^k)$ for a prime $p$ and integer $k \ge 1$. 2. Prove that $\phi(n)$ is even for $n > 2$. 3. Evaluate $\left(\frac{7}{11}\right)$. 4. Find the fundamental solution to Pell's equation $x^2 - 3y^2 = 1$. 5. If $n$ is a perfect number, prove that $n$ is even. #### Practice Problems - Set 3 1. Calculate $\phi(120)$. 2. Show that if $n$ is prime, then $\phi(n) = n-1$. 3. Determine if -1 is a quadratic residue modulo 17. 4. Find the fundamental solution to Pell's equation $x^2 - 5y^2 = 1$. 5. Prove that if $n$ is a perfect number, then $n$ cannot be a prime number. #### Practice Problems - Set 4 1. Calculate $\phi(p_1 p_2)$, where $p_1, p_2$ are distinct primes. 2. Prove that for square-free $n$, $\phi(n) = n \prod_{p|n} (1 - 1/p)$. 3. Evaluate $\left(\frac{6}{13}\right)$. 4. Find the fundamental solution to Pell's equation $x^2 - 7y^2 = 1$. 5. Show that $\phi(n) = n/2$ if $n=2^k$ for $k \ge 1$. #### Practice Problems - Set 5 1. Calculate $\phi(2023)$. 2. Prove that $\sum_{d|n} \mu(d) = 1$ if $n=1$ and $0$ if $n>1$. 3. Determine if 2 is a quadratic residue modulo 23. 4. Find the fundamental solution to Pell's equation $x^2 - 6y^2 = 1$. 5. Show that if $n$ is odd, $\sigma(n)$ is odd if and only if $n$ is a perfect square. #### Practice Problems - Set 6 1. Calculate $\phi(n)$ for $n=1, \ldots, 10$. 2. Prove that $\phi(mn) = \phi(m)\phi(n)$ if $\text{gcd}(m,n)=1$. 3. Evaluate $\left(\frac{5}{17}\right)$. 4. Find the general solutions to Pell's equation $x^2 - 2y^2 = 1$. 5. Show that if $n$ is a perfect number, then $n$ must be of the form $2^{p-1}(2^p-1)$ where $2^p-1$ is a Mersenne prime. #### Practice Problems - Set 7 1. Calculate $\phi(p^a q^b)$ for distinct primes $p, q$. 2. Prove that $\phi(n)$ is multiplicative. 3. Determine if 5 is a quadratic residue modulo 13. 4. Find the fundamental solution to Pell's equation $x^2 - 8y^2 = 1$. 5. Show that for any integer $n > 1$, $n$ divides $\sum_{k=1}^n \text{gcd}(k,n)$. #### Practice Problems - Set 8 1. Calculate $\phi(100)$. 2. Prove that if $n$ has $k$ distinct prime factors, then $\phi(n)$ is divisible by $2^{k-1}$. 3. Evaluate $\left(\frac{-1}{p}\right)$ for prime $p$. 4. Find the fundamental solution to Pell's equation $x^2 - 10y^2 = 1$. 5. Show that $\sigma(n)$ is odd if and only if $n$ is a perfect square or twice a perfect square. #### Practice Problems - Set 9 1. Calculate $\phi(16)$. 2. Prove that $\phi(n) = n/2$ if $n$ has only prime factor 2. 3. Determine if 7 is a quadratic residue modulo 23. 4. Find the fundamental solution to Pell's equation $x^2 - 13y^2 = 1$. 5. Show that there are infinitely many primes of the form $4k+1$. (Dirichlet's theorem, but a simpler proof for a specific case). #### Practice Problems - Set 10 1. Calculate $\phi(2^k)$. 2. Prove that $\sum_{k=1, \text{gcd}(k,n)=1}^n k = n\phi(n)/2$ for $n>2$. 3. Evaluate $\left(\frac{2}{p}\right)$ for prime $p$. 4. Find the fundamental solution to Pell's equation $x^2 - 17y^2 = 1$. 5. Show that for any integer $n$, $\tau(n) \le 2\sqrt{n}$. ### Solutions: Level 1 - Divisibility and Factors #### Practice Problems - Set 1 - Solutions 1. **Find the sum of all positive divisors of 100.** *Solution:* First, find the prime factorization of 100: $100 = 2^2 \times 5^2$. Using the formula for the sum of divisors: $\sigma(100) = \frac{2^{2+1}-1}{2-1} \times \frac{5^{2+1}-1}{5-1}$ $\sigma(100) = \frac{2^3-1}{1} \times \frac{5^3-1}{4}$ $\sigma(100) = (8-1) \times \frac{125-1}{4}$ $\sigma(100) = 7 \times \frac{124}{4}$ $\sigma(100) = 7 \times 31 = 217$. 2. **Determine if $7^{100} - 1$ is divisible by 48.** *Solution:* For $7^{100} - 1$ to be divisible by 48, it must be divisible by both 3 and 16 (since $48 = 3 \times 16$ and $\text{gcd}(3, 16) = 1$). *Divisibility by 3:* $7 \equiv 1 \pmod{3}$ $7^{100} \equiv 1^{100} \equiv 1 \pmod{3}$ So, $7^{100} - 1 \equiv 1 - 1 \equiv 0 \pmod{3}$. Thus, $7^{100} - 1$ is divisible by 3. *Divisibility by 16:* Consider powers of 7 modulo 16: $7^1 \equiv 7 \pmod{16}$ $7^2 = 49 \equiv 1 \pmod{16}$ Since $7^2 \equiv 1 \pmod{16}$, we can write $7^{100} = (7^2)^{50}$. $7^{100} \equiv 1^{50} \equiv 1 \pmod{16}$. So, $7^{100} - 1 \equiv 1 - 1 \equiv 0 \pmod{16}$. Thus, $7^{100} - 1$ is divisible by 16. Since $7^{100} - 1$ is divisible by both 3 and 16, and $\text{gcd}(3, 16) = 1$, it is divisible by $3 \times 16 = 48$. 3. **How many positive integers less than or equal to 100 have an odd number of divisors?** *Solution:* A positive integer has an odd number of divisors if and only if it is a perfect square. We need to find the number of perfect squares less than or equal to 100. These are $1^2, 2^2, 3^2, \ldots, 10^2$. The perfect squares are $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$. There are 10 such integers. 4. **If $n$ is a positive integer such that $n^2$ has 15 divisors, how many divisors can $n$ have?** *Solution:* Let the prime factorization of $n$ be $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Then $n^2 = p_1^{2a_1} p_2^{2a_2} \cdots p_k^{2a_k}$. The number of divisors of $n^2$ is $\tau(n^2) = (2a_1+1)(2a_2+1)\cdots(2a_k+1) = 15$. Since $a_i$ are positive integers, $2a_i+1$ are odd integers greater than or equal to 3. The possible ways to factor 15 into integers $\ge 3$ are: 1. $15$ (meaning $k=1$ and $2a_1+1=15 \implies 2a_1=14 \implies a_1=7$) In this case, $n = p^7$. The number of divisors of $n$ is $\tau(n) = (7+1) = 8$. 2. $3 \times 5$ (meaning $k=2$ and $2a_1+1=3 \implies a_1=1$, and $2a_2+1=5 \implies a_2=2$) In this case, $n = p_1^1 p_2^2$. The number of divisors of $n$ is $\tau(n) = (1+1)(2+1) = 2 \times 3 = 6$. So, $n$ can have 8 or 6 divisors. 5. **What is the largest integer $k$ such that $2^k$ divides $20!$?** *Solution:* This is equivalent to finding the exponent of the prime 2 in the prime factorization of $20!$. We use Legendre's formula: $E_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$. Here, $n=20$ and $p=2$. $E_2(20!) = \left\lfloor \frac{20}{2} \right\rfloor + \left\lfloor \frac{20}{2^2} \right\rfloor + \left\lfloor \frac{20}{2^3} \right\rfloor + \left\lfloor \frac{20}{2^4} \right\rfloor + \left\lfloor \frac{20}{2^5} \right\rfloor + \ldots$ $E_2(20!) = \left\lfloor \frac{20}{2} \right\rfloor + \left\lfloor \frac{20}{4} \right\rfloor + \left\lfloor \frac{20}{8} \right\rfloor + \left\lfloor \frac{20}{16} \right\rfloor + \left\lfloor \frac{20}{32} \right\rfloor + \ldots$ $E_2(20!) = 10 + 5 + 2 + 1 + 0 + \ldots$ $E_2(20!) = 18$. The largest integer $k$ is 18. #### Practice Problems - Set 2 - Solutions 1. **Find the number of integers between 1 and 200 (inclusive) that are divisible by 3 but not by 5.** *Solution:* Let $S_3$ be the set of numbers divisible by 3, and $S_5$ be the set of numbers divisible by 5. We want to find numbers divisible by 3 but not by 5. This is $|S_3| - |S_{3 \cap 5}|$. $S_{3 \cap 5}$ is the set of numbers divisible by both 3 and 5, which means divisible by $\text{lcm}(3,5)=15$. Number of integers divisible by 3: $\left\lfloor \frac{200}{3} \right\rfloor = 66$. Number of integers divisible by 15: $\left\lfloor \frac{200}{15} \right\rfloor = 13$. Number of integers divisible by 3 but not by 5 is $66 - 13 = 53$. 2. **Prove that for any prime $p$, $p$ divides $\binom{p}{k}$ for $1 \le k \le p-1$.** *Solution:* The binomial coefficient $\binom{p}{k}$ is given by $\frac{p!}{k!(p-k)!}$. We can write this as $\binom{p}{k} = \frac{p \times (p-1)!}{k!(p-k)!}$. Also, we know that $\binom{p}{k}$ is an integer, so $k!(p-k)!$ must divide $p!$. This means $k!(p-k)! \binom{p}{k} = p!$. We can rearrange the formula as $k!(p-k)! \binom{p}{k} = p \times (p-1)!$. This implies $k!(p-k)! \binom{p}{k}$ is divisible by $p$. Since $p$ is a prime number, for $1 \le k \le p-1$, neither $k!$ nor $(p-k)!$ contains $p$ as a factor. All prime factors of $k!$ are less than $p$, and all prime factors of $(p-k)!$ are less than $p$. Therefore, $p$ does not divide $k!$ and $p$ does not divide $(p-k)!$. Since $p$ is prime, and $p$ divides $k!(p-k)! \binom{p}{k}$, and $p$ does not divide $k!(p-k)!$, it must be that $p$ divides $\binom{p}{k}$. 3. **If $n$ is a perfect number (a number equal to the sum of its proper divisors), show that $\sigma(n) = 2n$.** *Solution:* The proper divisors of $n$ are all its positive divisors except $n$ itself. The sum of all positive divisors of $n$ is denoted by $\sigma(n)$. The sum of the proper divisors of $n$ is $\sigma(n) - n$. By definition, a perfect number $n$ is equal to the sum of its proper divisors. So, $n = \sigma(n) - n$. Adding $n$ to both sides, we get $\sigma(n) = 2n$. 4. **Find the smallest positive integer $n$ such that $2023n$ is a perfect square.** *Solution:* First, find the prime factorization of 2023. $2023 = 7 \times 17^2$. For $2023n$ to be a perfect square, all exponents in its prime factorization must be even. $2023n = (7^1 \times 17^2) \times n$. To make the exponent of 7 even, $n$ must have at least one factor of 7. The exponent of 17 is already even (2), so $n$ does not need to contribute any factors of 17. To make $2023n$ the smallest perfect square, $n$ should only contain the necessary prime factors with the smallest possible exponents. Thus, $n$ must be $7^1 = 7$. Check: $2023 \times 7 = (7 \times 17^2) \times 7 = 7^2 \times 17^2 = (7 \times 17)^2 = 119^2$. So, the smallest positive integer $n$ is 7. 5. **If $a, b$ are integers such that $a|b$ and $b|a$, prove that $a = \pm b$.** *Solution:* Since $a|b$, by definition there exists an integer $k_1$ such that $b = ak_1$. Since $b|a$, by definition there exists an integer $k_2$ such that $a = bk_2$. Substitute the first equation into the second: $a = (ak_1)k_2$ $a = a k_1 k_2$. If $a=0$, then $b = 0 \times k_1 = 0$. So $a=b=0$, which means $a=\pm b$ holds. If $a \ne 0$, we can divide both sides by $a$: $1 = k_1 k_2$. Since $k_1$ and $k_2$ are integers, the only integer pairs whose product is 1 are $(1, 1)$ or $(-1, -1)$. *Case 1:* $k_1 = 1$ and $k_2 = 1$. From $b = ak_1$, we get $b = a(1) = a$. *Case 2:* $k_1 = -1$ and $k_2 = -1$. From $b = ak_1$, we get $b = a(-1) = -a$. Therefore, $a = b$ or $a = -b$, which can be written as $a = \pm b$. #### Practice Problems - Set 3 - Solutions 1. **Find the number of positive divisors of $2^{10} \times 3^7 \times 5^3$.** *Solution:* Using the formula for the number of divisors $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$: $\tau(2^{10} \times 3^7 \times 5^3) = (10+1)(7+1)(3+1)$ $= 11 \times 8 \times 4 = 88 \times 4 = 352$. 2. **Prove that the product of any three consecutive integers is divisible by 6.** *Solution:* Let the three consecutive integers be $n, n+1, n+2$. Their product is $P = n(n+1)(n+2)$. We need to show $P$ is divisible by 6. This means $P$ must be divisible by 2 and 3. *Divisibility by 2:* In any set of three consecutive integers, at least one must be even. Therefore, $P$ is always divisible by 2. *Divisibility by 3:* In any set of three consecutive integers, exactly one must be divisible by 3. Therefore, $P$ is always divisible by 3. Since $P$ is divisible by both 2 and 3, and $\text{gcd}(2,3)=1$, $P$ is divisible by $2 \times 3 = 6$. 3. **Find the smallest positive integer $n$ such that $n$ has exactly 12 divisors.** *Solution:* Let $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Then $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1) = 12$. We list the ways to factor 12 into integers $\ge 2$: 1. $12$: $a_1+1=12 \implies a_1=11$. Smallest $n = 2^{11} = 2048$. 2. $6 \times 2$: $a_1+1=6, a_2+1=2 \implies a_1=5, a_2=1$. Smallest $n = 2^5 \times 3^1 = 32 \times 3 = 96$. 3. $4 \times 3$: $a_1+1=4, a_2+1=3 \implies a_1=3, a_2=2$. Smallest $n = 2^3 \times 3^2 = 8 \times 9 = 72$. 4. $3 \times 2 \times 2$: $a_1+1=3, a_2+1=2, a_3+1=2 \implies a_1=2, a_2=1, a_3=1$. Smallest $n = 2^2 \times 3^1 \times 5^1 = 4 \times 3 \times 5 = 60$. Comparing $2048, 96, 72, 60$, the smallest is 60. 4. **If $a$ is an integer, show that $a^2 - a$ is always even.** *Solution:* We can factor $a^2 - a$ as $a(a-1)$. This is the product of two consecutive integers. In any pair of consecutive integers, one must be even and the other must be odd. The product of an even and an odd integer is always even. Therefore, $a(a-1)$ is always even. 5. **Find the number of divisors of $10^5$.** *Solution:* First, find the prime factorization of $10^5$: $10^5 = (2 \times 5)^5 = 2^5 \times 5^5$. Using the formula for the number of divisors: $\tau(10^5) = (5+1)(5+1) = 6 \times 6 = 36$. #### Practice Problems - Set 4 - Solutions 1. **What is the smallest number that is divisible by 12, 15, and 20?** *Solution:* This is asking for the Least Common Multiple (LCM) of 12, 15, and 20. Prime factorizations: $12 = 2^2 \times 3^1$ $15 = 3^1 \times 5^1$ $20 = 2^2 \times 5^1$ $\text{lcm}(12, 15, 20) = 2^{\max(2,0,2)} \times 3^{\max(1,1,0)} \times 5^{\max(0,1,1)}$ $= 2^2 \times 3^1 \times 5^1 = 4 \times 3 \times 5 = 60$. 2. **If $n$ is an integer, show that $n^3 - n$ is divisible by 3.** *Solution:* We can factor $n^3 - n$ as $n(n^2 - 1) = n(n-1)(n+1)$. This is the product of three consecutive integers: $(n-1)n(n+1)$. In any set of three consecutive integers, one must be divisible by 3. Therefore, their product $n^3 - n$ is always divisible by 3. 3. **Find all positive integers $n$ for which $\tau(n)=4$.** *Solution:* Let $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Then $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1) = 4$. There are two cases for how 4 can be factored: 1. $4$: $a_1+1=4 \implies a_1=3$. So $n$ is of the form $p^3$ for some prime $p$. Examples: $2^3=8, 3^3=27, 5^3=125, \ldots$ 2. $2 \times 2$: $a_1+1=2, a_2+1=2 \implies a_1=1, a_2=1$. So $n$ is of the form $p_1 p_2$ for distinct primes $p_1, p_2$. Examples: $2 \times 3 = 6, 2 \times 5 = 10, 3 \times 5 = 15, \ldots$ So, $n$ must be either the cube of a prime number or the product of two distinct prime numbers. 4. **If $p$ is a prime number, prove that $\sqrt{p}$ is irrational.** *Solution:* Assume, for contradiction, that $\sqrt{p}$ is rational. Then $\sqrt{p} = \frac{a}{b}$ for some integers $a, b$ with $b \ne 0$, and $\text{gcd}(a,b)=1$. Squaring both sides: $p = \frac{a^2}{b^2}$ $pb^2 = a^2$. This implies $p | a^2$. Since $p$ is a prime number, if $p | a^2$, then $p | a$. So, $a = pk$ for some integer $k$. Substitute $a=pk$ back into the equation: $pb^2 = (pk)^2$ $pb^2 = p^2k^2$ Divide by $p$ (since $p \ne 0$): $b^2 = pk^2$. This implies $p | b^2$. Since $p$ is prime, if $p | b^2$, then $p | b$. So we have $p | a$ and $p | b$. This means $p$ is a common divisor of $a$ and $b$. However, we assumed that $\text{gcd}(a,b)=1$. This is a contradiction. Therefore, our initial assumption that $\sqrt{p}$ is rational must be false. Hence, $\sqrt{p}$ is irrational. 5. **How many positive integers less than 100 are divisible by 4 or 6?** *Solution:* Let $A$ be the set of integers less than 100 divisible by 4. Let $B$ be the set of integers less than 100 divisible by 6. We want to find $|A \cup B| = |A| + |B| - |A \cap B|$. Number of integers divisible by 4: $\lfloor \frac{99}{4} \rfloor = 24$. So $|A|=24$. Number of integers divisible by 6: $\lfloor \frac{99}{6} \rfloor = 16$. So $|B|=16$. $A \cap B$ is the set of integers divisible by both 4 and 6, which means divisible by $\text{lcm}(4,6)=12$. Number of integers divisible by 12: $\lfloor \frac{99}{12} \rfloor = 8$. So $|A \cap B|=8$. $|A \cup B| = 24 + 16 - 8 = 40 - 8 = 32$. There are 32 positive integers less than 100 that are divisible by 4 or 6. #### Practice Problems - Set 5 - Solutions 1. **Find the number of trailing zeros in $25!$.** *Solution:* The number of trailing zeros in $n!$ is determined by the exponent of 5 in its prime factorization, because there are always more factors of 2 than 5. We use Legendre's formula for $p=5$: $E_5(25!) = \sum_{i=1}^{\infty} \left\lfloor \frac{25}{5^i} \right\rfloor$. $E_5(25!) = \left\lfloor \frac{25}{5} \right\rfloor + \left\lfloor \frac{25}{25} \right\rfloor + \left\lfloor \frac{25}{125} \right\rfloor + \ldots$ $E_5(25!) = 5 + 1 + 0 = 6$. There are 6 trailing zeros in $25!$. 2. **If $a|b$ and $c|d$, prove that $ac|bd$.** *Solution:* Since $a|b$, there exists an integer $k_1$ such that $b = ak_1$. Since $c|d$, there exists an integer $k_2$ such that $d = ck_2$. Now, multiply these two equations: $bd = (ak_1)(ck_2)$ $bd = (ac)(k_1 k_2)$. Since $k_1 k_2$ is an integer, by the definition of divisibility, $ac|bd$. 3. **Find the number of divisors of $720$.** *Solution:* First, find the prime factorization of 720: $720 = 72 \times 10 = (8 \times 9) \times (2 \times 5) = (2^3 \times 3^2) \times (2 \times 5) = 2^4 \times 3^2 \times 5^1$. Using the formula for the number of divisors: $\tau(720) = (4+1)(2+1)(1+1) = 5 \times 3 \times 2 = 30$. 4. **Show that if $n$ is a composite number, then $n$ has a prime factor $p \le \sqrt{n}$.** *Solution:* Since $n$ is a composite number, by definition, it can be written as $n = ab$ for some integers $a, b$ such that $1 \sqrt{n}$ and $b > \sqrt{n}$. Then $ab > \sqrt{n} \times \sqrt{n} = n$. But we know $ab=n$, so $n > n$, which is a contradiction. Therefore, our assumption must be false, and at least one of $a$ or $b$ must be less than or equal to $\sqrt{n}$. Without loss of generality, let $a \le \sqrt{n}$. Since $a > 1$, $a$ must have a prime factor $p$. Since $p$ is a prime factor of $a$, and $a$ is a factor of $n$, it follows that $p$ is a prime factor of $n$. Also, since $p \le a$ and $a \le \sqrt{n}$, we have $p \le \sqrt{n}$. Thus, if $n$ is a composite number, it must have a prime factor $p \le \sqrt{n}$. 5. **What is the largest power of 3 that divides $30!$?** *Solution:* We use Legendre's formula for $p=3$: $E_3(30!) = \sum_{i=1}^{\infty} \left\lfloor \frac{30}{3^i} \right\rfloor$. $E_3(30!) = \left\lfloor \frac{30}{3} \right\rfloor + \left\lfloor \frac{30}{9} \right\rfloor + \left\lfloor \frac{30}{27} \right\rfloor + \left\lfloor \frac{30}{81} \right\rfloor + \ldots$ $E_3(30!) = 10 + 3 + 1 + 0 = 14$. The largest power of 3 that divides $30!$ is $3^{14}$. #### Practice Problems - Set 6 - Solutions 1. **Find the positive integers $n$ for which $\phi(n) = 2$.** *Solution:* We are looking for $n$ such that $\phi(n) = 2$. Recall $\phi(n) = n \prod_{p|n} (1 - 1/p)$. *Case 1: $n=p^k$ (power of a single prime)* $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$. If $p^{k-1}(p-1) = 2$: - If $p=2$: $2^{k-1}(2-1) = 2 \implies 2^{k-1} = 2 \implies k-1=1 \implies k=2$. So $n=2^2=4$. - If $p > 2$ (odd prime): $p-1$ must be even. If $p-1=2 \implies p=3$. Then $p^{k-1}=1 \implies k-1=0 \implies k=1$. So $n=3^1=3$. *Case 2: $n=p_1^{a_1} p_2^{a_2} \cdots$ (product of multiple primes)* If $n=p_1^{a_1} p_2^{a_2}$, then $\phi(n) = p_1^{a_1-1}(p_1-1) p_2^{a_2-1}(p_2-1) = 2$. Possible factors are 1 and 2. - If $(p_1-1) = 1$, then $p_1=2$. If $(p_2-1)=1$, then $p_2=2$, but primes must be distinct. - If $(p_1-1) = 2$, then $p_1=3$. Then $p_1^{a_1-1}=1 \implies a_1=1$. We need $p_2^{a_2-1}(p_2-1)=1$, which implies $p_2=2, a_2=1$. So $n = 3^1 \times 2^1 = 6$. The positive integers $n$ for which $\phi(n)=2$ are $3, 4, 6$. 2. **If $n = p_1^{a_1} \cdots p_k^{a_k}$, prove that $n$ is a perfect number if and only if $\sigma(n) = 2n$.** *Solution:* This was proved in Level 1, Set 2, Problem 3. A number $n$ is perfect if it is equal to the sum of its proper divisors. The sum of all divisors is $\sigma(n)$. The sum of proper divisors is $\sigma(n) - n$. So, $n$ is perfect $\iff n = \sigma(n) - n \iff 2n = \sigma(n)$. 3. **Determine if the sum of two odd numbers is always even.** *Solution:* Let the two odd numbers be $a$ and $b$. By definition, an odd number can be written as $2k+1$ for some integer $k$. So, $a = 2k_1 + 1$ and $b = 2k_2 + 1$ for some integers $k_1, k_2$. Their sum is $a+b = (2k_1+1) + (2k_2+1)$ $a+b = 2k_1 + 2k_2 + 2$ $a+b = 2(k_1 + k_2 + 1)$. Since $k_1+k_2+1$ is an integer, $a+b$ is of the form $2 \times (\text{integer})$, which means $a+b$ is always even. 4. **Find the smallest integer $k$ such that $10^k$ is divisible by $2^{10}$.** *Solution:* We need $2^{10} | 10^k$. $10^k = (2 \times 5)^k = 2^k \times 5^k$. For $2^{10}$ to divide $2^k \times 5^k$, the exponent of 2 in $2^k \times 5^k$ must be at least 10. The exponent of 2 is $k$. So, we need $k \ge 10$. The smallest such integer $k$ is 10. 5. **How many integers between 1 and 500 (inclusive) are not divisible by 2 or 3?** *Solution:* Let $N=500$. Let $A_2$ be the set of integers divisible by 2, and $A_3$ be the set of integers divisible by 3. We want to find $N - |A_2 \cup A_3|$. By the Principle of Inclusion-Exclusion, $|A_2 \cup A_3| = |A_2| + |A_3| - |A_2 \cap A_3|$. $|A_2| = \lfloor N/2 \rfloor = \lfloor 500/2 \rfloor = 250$. $|A_3| = \lfloor N/3 \rfloor = \lfloor 500/3 \rfloor = 166$. $A_2 \cap A_3$ is the set of integers divisible by $\text{lcm}(2,3)=6$. $|A_6| = \lfloor N/6 \rfloor = \lfloor 500/6 \rfloor = 83$. $|A_2 \cup A_3| = 250 + 166 - 83 = 416 - 83 = 333$. The number of integers not divisible by 2 or 3 is $N - |A_2 \cup A_3| = 500 - 333 = 167$. #### Practice Problems - Set 7 - Solutions 1. **Find the smallest positive integer $n$ such that $n$ has exactly 10 divisors.** *Solution:* Let $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Then $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1) = 10$. Possible factorizations of 10 into integers $\ge 2$: 1. $10$: $a_1+1=10 \implies a_1=9$. Smallest $n = 2^9 = 512$. 2. $5 \times 2$: $a_1+1=5, a_2+1=2 \implies a_1=4, a_2=1$. Smallest $n = 2^4 \times 3^1 = 16 \times 3 = 48$. Comparing 512 and 48, the smallest is 48. 2. **Prove that if $a|bc$ and $\text{gcd}(a,b)=1$, then $a|c$.** *Solution:* Since $\text{gcd}(a,b)=1$, by Bezout's Identity, there exist integers $x, y$ such that $ax + by = 1$. Multiply the entire equation by $c$: $acx + bcy = c$. We are given that $a|bc$. This means $bc = ak$ for some integer $k$. Substitute $bc=ak$ into the equation: $acx + (ak)y = c$ $a(cx + ky) = c$. Since $cx+ky$ is an integer, by the definition of divisibility, $a|c$. 3. **Find the number of divisors of $2^3 \times 3^4 \times 5^1$ that are perfect squares.** *Solution:* Let $n = 2^3 \times 3^4 \times 5^1$. A divisor $d$ of $n$ is of the form $2^a \times 3^b \times 5^c$, where $0 \le a \le 3$, $0 \le b \le 4$, $0 \le c \le 1$. For $d$ to be a perfect square, all the exponents $a, b, c$ must be even. Possible values for $a$: $0, 2$. (2 choices) Possible values for $b$: $0, 2, 4$. (3 choices) Possible values for $c$: $0$. (1 choice) The number of such divisors is the product of the number of choices for each exponent: $2 \times 3 \times 1 = 6$. The divisors that are perfect squares are: $2^0 3^0 5^0=1$, $2^2 3^0 5^0=4$, $2^0 3^2 5^0=9$, $2^0 3^4 5^0=81$, $2^2 3^2 5^0=36$, $2^2 3^4 5^0=324$. 4. **Show that $n^2+n+1$ is never divisible by 2.** *Solution:* We can analyze this by considering two cases for $n$: *Case 1: $n$ is even.* If $n$ is even, then $n=2k$ for some integer $k$. $n^2+n+1 = (2k)^2 + (2k) + 1 = 4k^2 + 2k + 1 = 2(2k^2+k) + 1$. This is of the form $2M+1$, which is an odd number. Thus, it is not divisible by 2. *Case 2: $n$ is odd.* If $n$ is odd, then $n=2k+1$ for some integer $k$. $n^2+n+1 = (2k+1)^2 + (2k+1) + 1$ $= (4k^2+4k+1) + (2k+1) + 1$ $= 4k^2 + 6k + 3 = 2(2k^2+3k+1) + 1$. This is also of the form $2M+1$, which is an odd number. Thus, it is not divisible by 2. In both cases, $n^2+n+1$ is always odd, and therefore never divisible by 2. 5. **If $\text{gcd}(a,b)=1$, prove that $\text{gcd}(a+b, a-b)$ is either 1 or 2.** *Solution:* Let $d = \text{gcd}(a+b, a-b)$. Since $d$ divides $a+b$ and $d$ divides $a-b$, it must also divide their sum and their difference. $d | ((a+b) + (a-b)) \implies d | 2a$. $d | ((a+b) - (a-b)) \implies d | 2b$. So $d$ is a common divisor of $2a$ and $2b$. This means $d | \text{gcd}(2a, 2b)$. We know that $\text{gcd}(2a, 2b) = 2 \text{gcd}(a,b)$. Since $\text{gcd}(a,b)=1$ (given), we have $\text{gcd}(2a, 2b) = 2 \times 1 = 2$. Therefore, $d | 2$. The only positive divisors of 2 are 1 and 2. Thus, $\text{gcd}(a+b, a-b)$ must be either 1 or 2. #### Practice Problems - Set 8 - Solutions 1. **Find the sum of the divisors of $p^k$ where $p$ is a prime number and $k \ge 1$.** *Solution:* The divisors of $p^k$ are $1, p, p^2, \ldots, p^k$. The sum of these divisors is $\sigma(p^k) = 1 + p + p^2 + \ldots + p^k$. This is a geometric series with first term 1, common ratio $p$, and $k+1$ terms. The sum is $\frac{p^{k+1}-1}{p-1}$. So, $\sigma(p^k) = \frac{p^{k+1}-1}{p-1}$. 2. **Prove that for any integer $m > 1$, $m^4+4$ is a composite number.** *Solution:* We can factor $m^4+4$ using Sophie Germain's Identity: $m^4+4 = m^4 + 4m^2 + 4 - 4m^2$ $= (m^2+2)^2 - (2m)^2$ $= (m^2+2 - 2m)(m^2+2 + 2m)$ $= ((m-1)^2+1)((m+1)^2+1)$. For $m > 1$: - The first factor $(m-1)^2+1$: If $m=2$, $(2-1)^2+1 = 1^2+1=2$. If $m > 2$, $(m-1)^2+1 > 1$. - The second factor $(m+1)^2+1$: For $m > 1$, $(m+1)^2+1 > 1$. Since $m^4+4$ can be expressed as a product of two integers, both greater than 1 (specifically, the first factor is 2 for $m=2$ and greater than 1 for $m>2$, and the second factor is always greater than 1 for $m>1$), $m^4+4$ is a composite number. For $m=1$, $1^4+4=5$, which is prime. The question states $m>1$. 3. **Find the number of integers $n \le 100$ such that $n$ is divisible by 7 and $n$ has an even number of divisors.** *Solution:* First, list integers $n \le 100$ that are divisible by 7: $7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98$. (14 numbers) An integer has an even number of divisors if and only if it is NOT a perfect square. We need to identify which of these numbers are perfect squares and exclude them. The perfect squares in the list are: $49 = 7^2$. All other numbers in the list are not perfect squares. So, the numbers divisible by 7 and having an even number of divisors are all the numbers in the list except 49. Number of such integers = $14 - 1 = 13$. 4. **If $a|b$, then prove that $\text{gcd}(a,b) = |a|$.** *Solution:* Since $a|b$, $a$ is a divisor of $b$. Also, $a$ is trivially a divisor of $a$. So $a$ is a common divisor of $a$ and $b$. The definition of GCD states that $\text{gcd}(a,b)$ is the *largest positive* common divisor. Any common divisor of $a$ and $b$ must divide $a$. Therefore, any common divisor must be less than or equal to $|a|$. Since $|a|$ itself is a common divisor (as $a|a$ and $a|b$), and it is the largest possible positive common divisor, $\text{gcd}(a,b) = |a|$. 5. **Find the largest integer $n$ such that $n^n$ divides $100!$.** *Solution:* This problem is complex and goes beyond typical Level 1 scope. It's a challenging one often found in higher-level Olympiad problems. A common approach involves considering the prime factors of $n$. If $n$ is prime, say $p$, then we need $p^p | 100!$. The exponent of $p$ in $100!$ is $E_p(100!) = \sum_{i=1}^{\infty} \lfloor 100/p^i \rfloor$. We need $p \le E_p(100!)$. Let's check some primes: - $p=2$: $E_2(100!) = 50+25+12+6+3+1 = 97$. We need $2 \le 97$. Yes. - $p=3$: $E_3(100!) = 33+11+3+1 = 48$. We need $3 \le 48$. Yes. - $p=5$: $E_5(100!) = 20+4 = 24$. We need $5 \le 24$. Yes. - $p=7$: $E_7(100!) = 14+2 = 16$. We need $7 \le 16$. Yes. - $p=11$: $E_{11}(100!) = 9$. We need $11 \le 9$. No. So $n$ cannot be 11. This implies that for $n^n$ to divide $100!$, $n$ must not have any prime factor greater than or equal to 11. So $n$ must be of the form $2^a 3^b 5^c 7^d$. Consider $n=10$. $10^{10} = (2 \times 5)^{10} = 2^{10} \times 5^{10}$. We need $E_2(100!) = 97 \ge 10$ and $E_5(100!) = 24 \ge 10$. Both hold. Consider $n=9$. $9^9 = (3^2)^9 = 3^{18}$. We need $E_3(100!) = 48 \ge 18$. Holds. Consider $n=8$. $8^8 = (2^3)^8 = 2^{24}$. We need $E_2(100!) = 97 \ge 24$. Holds. This problem usually refers to a specific type of $n$. For $n$ to be the largest, it would typically be a prime or a number with small prime factors. Let's check $n=10$. $10^{10} | 100!$ since $E_2(100!) = 97 \ge 10$ and $E_5(100!) = 24 \ge 10$. If $n=11$, $11^{11}$. $E_{11}(100!) = 9$. We need $11 \le 9$, which is false. So $11^{11}$ does not divide $100!$. If $n=12$, $12^{12} = (2^2 \cdot 3)^{12} = 2^{24} \cdot 3^{12}$. $E_2(100!) = 97 \ge 24$, $E_3(100!) = 48 \ge 12$. So $12^{12}|100!$. If $n=13$, $13^{13}$. $E_{13}(100!) = 7$. We need $13 \le 7$, false. So $13^{13}$ does not divide $100!$. If $n=14$, $14^{14} = (2 \cdot 7)^{14} = 2^{14} \cdot 7^{14}$. $E_2(100!) = 97 \ge 14$, $E_7(100!) = 16 \ge 14$. So $14^{14}|100!$. If $n=15$, $15^{15} = (3 \cdot 5)^{15} = 3^{15} \cdot 5^{15}$. $E_3(100!) = 48 \ge 15$, $E_5(100!) = 24 \ge 15$. So $15^{15}|100!$. If $n=16$, $16^{16} = (2^4)^{16} = 2^{64}$. $E_2(100!) = 97 \ge 64$. So $16^{16}|100!$. If $n=17$, $17^{17}$. $E_{17}(100!) = 5$. We need $17 \le 5$, false. So $17^{17}$ does not divide $100!$. The largest such $n$ is 16. #### Practice Problems - Set 9 - Solutions 1. **Show that for any integer $n$, $n^2+1$ is never divisible by 3.** *Solution:* We can check the possible values of $n$ modulo 3: *Case 1: $n \equiv 0 \pmod{3}$.* $n^2+1 \equiv 0^2+0+1 \equiv 1 \pmod{3}$. *Case 2: $n \equiv 1 \pmod{3}$.* $n^2+1 \equiv 1^2+1+1 \equiv 2 \pmod{3}$. *Case 3: $n \equiv 2 \pmod{3}$.* $n^2+1 \equiv 2^2+2+1 \equiv 4+2+1 \equiv 5 \equiv 2 \pmod{3}$. In all cases, $n^2+1$ is never congruent to $0 \pmod{3}$. Therefore, $n^2+1$ is never divisible by 3. 2. **Find the number of divisors of $1440$.** *Solution:* First, find the prime factorization of 1440: $1440 = 144 \times 10 = (12^2) \times (2 \times 5) = ((2^2 \times 3)^2) \times (2 \times 5)$ $= (2^4 \times 3^2) \times (2 \times 5) = 2^5 \times 3^2 \times 5^1$. Using the formula for the number of divisors: $\tau(1440) = (5+1)(2+1)(1+1) = 6 \times 3 \times 2 = 36$. 3. **If $p$ is a prime, and $a^2 \equiv b^2 \pmod p$, prove that $a \equiv b \pmod p$ or $a \equiv -b \pmod p$.** *Solution:* Given $a^2 \equiv b^2 \pmod p$. This can be rewritten as $a^2 - b^2 \equiv 0 \pmod p$. Factoring the difference of squares: $(a-b)(a+b) \equiv 0 \pmod p$. This means that $p$ divides the product $(a-b)(a+b)$. Since $p$ is a prime number, by Euclid's Lemma, if $p$ divides a product of two integers, then $p$ must divide at least one of the integers. Therefore, either $p | (a-b)$ or $p | (a+b)$. - If $p | (a-b)$, then $a-b \equiv 0 \pmod p \implies a \equiv b \pmod p$. - If $p | (a+b)$, then $a+b \equiv 0 \pmod p \implies a \equiv -b \pmod p$. Thus, $a \equiv b \pmod p$ or $a \equiv -b \pmod p$. 4. **Determine if $111 \ldots 1$ ($n$ times) is divisible by 3.** *Solution:* A number is divisible by 3 if and only if the sum of its digits is divisible by 3. The number $111 \ldots 1$ ($n$ times) consists of $n$ digits, all of which are 1. The sum of its digits is $1 \times n = n$. Therefore, the number $111 \ldots 1$ ($n$ times) is divisible by 3 if and only if $n$ is divisible by 3. 5. **Find the smallest positive integer $n$ such that $n/2$ is a perfect square, $n/3$ is a perfect cube, and $n/5$ is a perfect fifth power.** *Solution:* Let $n/2 = a^2$, $n/3 = b^3$, $n/5 = c^5$ for some integers $a,b,c$. This implies $n = 2a^2 = 3b^3 = 5c^5$. Let the prime factorization of $n$ be $n = 2^{e_2} 3^{e_3} 5^{e_5} \ldots$. From $n=2a^2$, $e_2$ must be odd, and $e_3, e_5, \ldots$ must be even. From $n=3b^3$, $e_3$ must be of the form $3k+1$, and $e_2, e_5, \ldots$ must be multiples of 3. From $n=5c^5$, $e_5$ must be of the form $5k+1$, and $e_2, e_3, \ldots$ must be multiples of 5. Combining these conditions for the exponents: - $e_2$: Must be odd ($2k+1$) and a multiple of 3 ($3k'$) and a multiple of 5 ($5k''$). So $e_2$ must be a multiple of $\text{lcm}(3,5)=15$, and also odd. Smallest such is 15. - $e_3$: Must be of the form $3k+1$ and even ($2k'$) and a multiple of 5 ($5k''$). So $e_3$ must be a multiple of $\text{lcm}(2,5)=10$, and of the form $3k+1$. Multiples of 10 are $10, 20, 30, \ldots$. $10 \equiv 1 \pmod 3$. So $e_3=10$. - $e_5$: Must be of the form $5k+1$ and even ($2k'$) and a multiple of 3 ($3k''$). So $e_5$ must be a multiple of $\text{lcm}(2,3)=6$, and of the form $5k+1$. Multiples of 6 are $6, 12, 18, \ldots$. $6 \equiv 1 \pmod 5$. So $e_5=6$. Other prime factors (not 2, 3, 5) must have exponents that are even, multiples of 3, and multiples of 5, so multiples of $\text{lcm}(2,3,5)=30$. To find the *smallest* $n$, we don't include other prime factors. Thus, $n = 2^{15} \times 3^{10} \times 5^6$. #### Practice Problems - Set 10 - Solutions 1. **Find the number of integers from 1 to 1000 that are multiples of 3 or 5.** *Solution:* Let $N=1000$. Let $A_3$ be the set of multiples of 3. Let $A_5$ be the set of multiples of 5. We want to find $|A_3 \cup A_5| = |A_3| + |A_5| - |A_3 \cap A_5|$. $|A_3| = \lfloor 1000/3 \rfloor = 333$. $|A_5| = \lfloor 1000/5 \rfloor = 200$. $A_3 \cap A_5$ is the set of multiples of $\text{lcm}(3,5)=15$. $|A_{15}| = \lfloor 1000/15 \rfloor = 66$. $|A_3 \cup A_5| = 333 + 200 - 66 = 533 - 66 = 467$. 2. **Prove that if $n$ is an odd integer, then $n^2-1$ is divisible by 8.** *Solution:* Since $n$ is an odd integer, we can write $n = 2k+1$ for some integer $k$. Then $n^2-1 = (2k+1)^2 - 1 = (4k^2+4k+1) - 1 = 4k^2+4k = 4k(k+1)$. We know that for any integer $k$, the product $k(k+1)$ is always even (as it's a product of two consecutive integers). So, $k(k+1) = 2m$ for some integer $m$. Substitute this back: $n^2-1 = 4(2m) = 8m$. Since $8m$ is divisible by 8, $n^2-1$ is divisible by 8. 3. **Find all positive integers $n$ for which $\text{gcd}(n, n+1) = 1$.** *Solution:* Let $d = \text{gcd}(n, n+1)$. Since $d$ divides $n$ and $d$ divides $n+1$, $d$ must also divide their difference: $d | (n+1 - n) \implies d | 1$. The only positive divisor of 1 is 1 itself. Therefore, $\text{gcd}(n, n+1) = 1$ for all positive integers $n$. 4. **If $p$ is a prime, what are the possible values for $\text{gcd}(p, p+1)$?** *Solution:* Let $d = \text{gcd}(p, p+1)$. Since $d$ divides $p$ and $d$ divides $p+1$, $d$ must also divide their difference: $d | (p+1 - p) \implies d | 1$. The only positive divisor of 1 is 1. Therefore, $\text{gcd}(p, p+1) = 1$ for any prime $p$. The only possible value is 1. 5. **Show that if $n$ is a positive integer, then $n$ and $n+1$ are coprime.** *Solution:* This is the same as Problem 3 in this set. Two integers are coprime if their greatest common divisor is 1. Let $d = \text{gcd}(n, n+1)$. Since $d$ divides $n$ and $d$ divides $n+1$, it must divide any linear combination of $n$ and $n+1$. In particular, $d$ divides $(n+1) - n = 1$. Since $d$ is a positive integer and $d|1$, it must be that $d=1$. Therefore, $\text{gcd}(n, n+1) = 1$, meaning $n$ and $n+1$ are coprime. ### Solutions: Level 2 - GCD and LCM #### Practice Problems - Set 1 - Solutions 1. **Find the GCD and LCM of 144 and 192.** *Solution:* Prime factorization method: $144 = 12^2 = (2^2 \times 3)^2 = 2^4 \times 3^2$ $192 = 64 \times 3 = 2^6 \times 3^1$ $\text{gcd}(144, 192) = 2^{\min(4,6)} \times 3^{\min(2,1)} = 2^4 \times 3^1 = 16 \times 3 = 48$. $\text{lcm}(144, 192) = 2^{\max(4,6)} \times 3^{\max(2,1)} = 2^6 \times 3^2 = 64 \times 9 = 576$. Alternatively, using Euclidean Algorithm for GCD: $192 = 1 \times 144 + 48$ $144 = 3 \times 48 + 0$ So, $\text{gcd}(144, 192) = 48$. Then, $\text{lcm}(144, 192) = \frac{144 \times 192}{\text{gcd}(144, 192)} = \frac{144 \times 192}{48} = 144 \times 4 = 576$. 2. **The product of two numbers is 1800, and their LCM is 360. What is their GCD?** *Solution:* Let the two numbers be $a$ and $b$. We are given $a \times b = 1800$ and $\text{lcm}(a, b) = 360$. We know the relationship: $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$. Let $d = \text{gcd}(a, b)$. $d \times 360 = 1800$ $d = \frac{1800}{360} = 5$. The GCD of the two numbers is 5. 3. **Find integers $x, y$ such that $101x + 103y = 1$.** *Solution:* We need to use the Extended Euclidean Algorithm to express $\text{gcd}(101, 103)$ as a linear combination. First, find $\text{gcd}(101, 103)$: $103 = 1 \times 101 + 2$ $101 = 50 \times 2 + 1$ $2 = 2 \times 1 + 0$ The GCD is 1. Now, work backwards: From the second equation: $1 = 101 - 50 \times 2$ From the first equation: $2 = 103 - 1 \times 101$ Substitute the expression for 2 into the equation for 1: $1 = 101 - 50(103 - 1 \times 101)$ $1 = 101 - 50 \times 103 + 50 \times 101$ $1 = 51 \times 101 - 50 \times 103$ So, $x = 51$ and $y = -50$. 4. **Three bells ring at intervals of 12, 15, and 18 minutes respectively. If they start ringing together at 9 AM, when will they next ring together?** *Solution:* They will next ring together after a time interval that is the LCM of their individual ringing intervals. We need to find $\text{lcm}(12, 15, 18)$. Prime factorization: $12 = 2^2 \times 3^1$ $15 = 3^1 \times 5^1$ $18 = 2^1 \times 3^2$ $\text{lcm}(12, 15, 18) = 2^{\max(2,0,1)} \times 3^{\max(1,1,2)} \times 5^{\max(0,1,0)}$ $= 2^2 \times 3^2 \times 5^1 = 4 \times 9 \times 5 = 180$. The bells will ring together again after 180 minutes. 180 minutes = 3 hours. If they start at 9 AM, they will next ring together at $9 \text{ AM} + 3 \text{ hours} = 12 \text{ PM (noon)}$. 5. **If $\text{gcd}(a, b) = d$, prove that $\text{gcd}(a/d, b/d) = 1$.** *Solution:* Let $a, b$ be integers and $d = \text{gcd}(a, b)$. By the definition of GCD, $d$ divides $a$ and $d$ divides $b$. So, $a/d$ and $b/d$ are integers. Let $g = \text{gcd}(a/d, b/d)$. We want to show that $g=1$. Since $g$ divides $a/d$ and $g$ divides $b/d$, we can write: $a/d = gx_1$ for some integer $x_1$. $b/d = gx_2$ for some integer $x_2$. Multiplying by $d$: $a = dgx_1$ $b = dgx_2$ This shows that $dg$ is a common divisor of $a$ and $b$. However, $d$ is the *greatest* common divisor of $a$ and $b$. Therefore, $dg$ must be less than or equal to $d$. $dg \le d$. Since $d$ is a positive integer, we can divide by $d$: $g \le 1$. Since $g$ is a GCD, it must be a positive integer. The only positive integer less than or equal to 1 is 1 itself. Thus, $g=1$. #### Practice Problems - Set 2 - Solutions 1. **Find $\text{gcd}(252, 198)$ using the Euclidean Algorithm.** *Solution:* $252 = 1 \times 198 + 54$ $198 = 3 \times 54 + 36$ $54 = 1 \times 36 + 18$ $36 = 2 \times 18 + 0$ The last non-zero remainder is 18. So, $\text{gcd}(252, 198) = 18$. 2. **If $\text{lcm}(a,b) = 450$ and $\text{gcd}(a,b) = 15$, and $a=75$, find $b$.** *Solution:* We use the property $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$. $15 \times 450 = 75 \times b$ $6750 = 75b$ $b = \frac{6750}{75} = 90$. 3. **Show that $\text{gcd}(n, n+1) = 1$ for any positive integer $n$.** *Solution:* Let $d = \text{gcd}(n, n+1)$. Since $d$ divides $n$ and $d$ divides $n+1$, $d$ must divide their difference: $(n+1) - n = 1$. The only positive divisor of 1 is 1. Therefore, $\text{gcd}(n, n+1) = 1$. 4. **Find integer solutions $x, y$ for $24x + 36y = 12$.** *Solution:* 1. $\text{gcd}(24, 36) = 12$. 2. Since $12 | 12$, solutions exist. Divide by 12: $2x + 3y = 1$. 3. Particular solution: $x_0 = -1, y_0 = 1$ (since $2(-1) + 3(1) = -2+3=1$). 4. General solution: $x = x_0 + (b'/d_0)k = -1 + 3k$ $y = y_0 - (a'/d_0)k = 1 - 2k$ for any integer $k$. 5. **The sum of two numbers is 120, and their GCD is 15. Find the numbers.** *Solution:* Let the numbers be $a$ and $b$. Given $a+b=120$ and $\text{gcd}(a,b)=15$. Since $\text{gcd}(a,b)=15$, we can write $a=15x$ and $b=15y$, where $\text{gcd}(x,y)=1$. Substitute into the sum: $15x + 15y = 120$ $15(x+y) = 120$ $x+y = 8$. Now we need to find pairs of positive integers $(x,y)$ such that $x+y=8$ and $\text{gcd}(x,y)=1$. Possible pairs for $(x,y)$: - $(1, 7)$: $\text{gcd}(1,7)=1$. Yes. - $(2, 6)$: $\text{gcd}(2,6)=2 \ne 1$. No. - $(3, 5)$: $\text{gcd}(3,5)=1$. Yes. - $(4, 4)$: $\text{gcd}(4,4)=4 \ne 1$. No. (We don't need to check $(5,3), (6,2), (7,1)$ as they lead to the same pair of numbers). If $(x,y)=(1,7)$, then $(a,b) = (15 \times 1, 15 \times 7) = (15, 105)$. If $(x,y)=(3,5)$, then $(a,b) = (15 \times 3, 15 \times 5) = (45, 75)$. The numbers are (15, 105) or (45, 75). #### Practice Problems - Set 3 - Solutions 1. **Find the LCM of 28, 42, and 63.** *Solution:* Prime factorizations: $28 = 2^2 \times 7^1$ $42 = 2^1 \times 3^1 \times 7^1$ $63 = 3^2 \times 7^1$ $\text{lcm}(28, 42, 63) = 2^{\max(2,1,0)} \times 3^{\max(0,1,2)} \times 7^{\max(1,1,1)}$ $= 2^2 \times 3^2 \times 7^1 = 4 \times 9 \times 7 = 36 \times 7 = 252$. 2. **Prove that $\text{gcd}(a, b) = \text{gcd}(a-b, b)$.** *Solution:* Let $d = \text{gcd}(a, b)$. By definition, $d|a$ and $d|b$. Since $d|a$ and $d|b$, it follows that $d|(a-b)$. So $d$ is a common divisor of $a-b$ and $b$. Thus $d \le \text{gcd}(a-b, b)$. Let $d' = \text{gcd}(a-b, b)$. By definition, $d'|(a-b)$ and $d'|b$. Since $d'|(a-b)$ and $d'|b$, it follows that $d'|((a-b)+b)$, which means $d'|a$. So $d'$ is a common divisor of $a$ and $b$. Thus $d' \le \text{gcd}(a, b)$. Since $d \le d'$ and $d' \le d$, it must be that $d=d'$. Therefore, $\text{gcd}(a, b) = \text{gcd}(a-b, b)$. 3. **If $\text{gcd}(a, b) = 1$, prove that $\text{gcd}(a+b, a) = 1$.** *Solution:* Let $d = \text{gcd}(a+b, a)$. Since $d$ divides $a+b$ and $d$ divides $a$, $d$ must divide their difference: $(a+b) - a = b$. So $d$ divides $a$ and $d$ divides $b$. This means $d$ is a common divisor of $a$ and $b$. Since $\text{gcd}(a, b) = 1$ (given), and $d$ is a common divisor, $d$ must divide 1. The only positive divisor of 1 is 1. Therefore, $d=1$, which means $\text{gcd}(a+b, a) = 1$. 4. **Find the smallest positive integer $k$ such that $\text{lcm}(6, k) = 30$.** *Solution:* We have $6 = 2^1 \times 3^1$. We have $30 = 2^1 \times 3^1 \times 5^1$. Let $k = 2^a \times 3^b \times 5^c$. $\text{lcm}(6, k) = 2^{\max(1,a)} \times 3^{\max(1,b)} \times 5^{\max(0,c)} = 2^1 \times 3^1 \times 5^1$. Comparing exponents: - $\max(1,a) = 1 \implies a=0$ or $a=1$. - $\max(1,b) = 1 \implies b=0$ or $b=1$. - $\max(0,c) = 1 \implies c=1$. To find the smallest positive integer $k$, we choose the smallest possible exponents for $a$ and $b$. So, $a=0, b=0, c=1$. $k = 2^0 \times 3^0 \times 5^1 = 1 \times 1 \times 5 = 5$. Check: $\text{lcm}(6, 5) = 30$. This is correct. 5. **Two numbers are in the ratio 3:4. If their LCM is 180, what are the numbers?** *Solution:* Let the two numbers be $3x$ and $4x$ for some positive integer $x$. We know that $\text{lcm}(a,b) = \frac{ab}{\text{gcd}(a,b)}$. Also, for numbers $kx, ky$, $\text{gcd}(kx, ky) = k \text{gcd}(x,y)$. So, $\text{gcd}(3x, 4x) = x \text{gcd}(3,4) = x \times 1 = x$. Now, using the formula: $\text{lcm}(3x, 4x) = \frac{(3x)(4x)}{x} = \frac{12x^2}{x} = 12x$. We are given that $\text{lcm}(3x, 4x) = 180$. So, $12x = 180$. $x = \frac{180}{12} = 15$. The two numbers are $3x = 3 \times 15 = 45$ and $4x = 4 \times 15 = 60$. #### Practice Problems - Set 4 - Solutions 1. **Use the Euclidean Algorithm to find $\text{gcd}(272, 119)$.** *Solution:* $272 = 2 \times 119 + 34$ $119 = 3 \times 34 + 17$ $34 = 2 \times 17 + 0$ The last non-zero remainder is 17. So, $\text{gcd}(272, 119) = 17$. 2. **If $\text{gcd}(a,b) = 1$, show that $\text{gcd}(a^2, b^2) = 1$.** *Solution:* Assume, for contradiction, that $\text{gcd}(a^2, b^2) = d > 1$. Then $d$ must have a prime factor, say $p$. Since $p|d$ and $d|a^2$, it follows that $p|a^2$. Since $p$ is prime, if $p|a^2$, then $p|a$. Similarly, since $p|d$ and $d|b^2$, it follows that $p|b^2$. Since $p$ is prime, if $p|b^2$, then $p|b$. So $p$ is a common prime factor of $a$ and $b$. This implies $\text{gcd}(a,b) \ge p > 1$. This contradicts the given information that $\text{gcd}(a,b)=1$. Therefore, our assumption that $\text{gcd}(a^2, b^2) > 1$ must be false. Hence, $\text{gcd}(a^2, b^2) = 1$. 3. **Find integers $x, y$ such that $17x - 13y = 1$.** *Solution:* We need to find integer solutions to $17x + (-13)y = 1$. First, find $\text{gcd}(17, 13)$ using Euclidean Algorithm: $17 = 1 \times 13 + 4$ $13 = 3 \times 4 + 1$ $4 = 4 \times 1 + 0$ The GCD is 1. Now, work backwards to express 1: $1 = 13 - 3 \times 4$ Substitute $4 = 17 - 1 \times 13$: $1 = 13 - 3 \times (17 - 1 \times 13)$ $1 = 13 - 3 \times 17 + 3 \times 13$ $1 = 4 \times 13 - 3 \times 17$ Rearrange to match the form $17x - 13y = 1$: $1 = (-3) \times 17 + (4) \times 13$ $1 = 17(-3) - 13(-4)$. So a particular solution is $x_0 = -3, y_0 = -4$. The general solution is: $x = x_0 + (b'/d_0)k = -3 - 13k$ $y = y_0 - (a'/d_0)k = -4 - 17k$ for any integer $k$. (Note: A common variant is to write $17x - 13y = 1$ as $17x \equiv 1 \pmod{13}$. $4x \equiv 1 \pmod{13}$. Inverse of $4 \pmod{13}$: $4 \times 1 = 4, 4 \times 2 = 8, 4 \times 3 = 12 \equiv -1, 4 \times (-3) \equiv 1$. So $-3 \equiv 10$ is the inverse. $x \equiv 10 \pmod{13}$. So $x=10$. $17(10) - 13y = 1 \implies 170 - 13y = 1 \implies 169 = 13y \implies y=13$. So $(10, 13)$ is another particular solution. Using this, general solution: $x=10-13k, y=13-17k$.) 4. **A group of students can be arranged in rows of 6, 8, or 10 with no students left over. What is the minimum number of students in the group?** *Solution:* The number of students must be a common multiple of 6, 8, and 10. We are looking for the minimum number, so we need the LCM. Prime factorizations: $6 = 2 \times 3$ $8 = 2^3$ $10 = 2 \times 5$ $\text{lcm}(6, 8, 10) = 2^{\max(1,3,1)} \times 3^{\max(1,0,0)} \times 5^{\max(0,0,1)}$ $= 2^3 \times 3^1 \times 5^1 = 8 \times 3 \times 5 = 120$. The minimum number of students is 120. 5. **If $a$ and $b$ are positive integers, and $a|b$, prove that $\text{lcm}(a,b) = b$.** *Solution:* Since $a|b$, we know that $b = ak$ for some integer $k$. We also know the relationship $\text{gcd}(a,b) \times \text{lcm}(a,b) = a \times b$. If $a|b$, then $a$ is a divisor of $b$. Since $a$ is also a divisor of itself, $a$ is a common divisor of $a$ and $b$. In fact, if $a|b$, then $\text{gcd}(a,b) = a$. Substitute $\text{gcd}(a,b)=a$ into the relationship: $a \times \text{lcm}(a,b) = a \times b$. Since $a$ is a positive integer, we can divide both sides by $a$: $\text{lcm}(a,b) = b$. #### Practice Problems - Set 5 - Solutions 1. **Find the GCD and LCM of $2^3 \times 3^2 \times 5^1$ and $2^2 \times 3^4 \times 7^1$.** *Solution:* Let $A = 2^3 \times 3^2 \times 5^1$ and $B = 2^2 \times 3^4 \times 7^1$. To find the GCD, take the minimum of the exponents for each common prime factor: $\text{gcd}(A, B) = 2^{\min(3,2)} \times 3^{\min(2,4)} \times 5^{\min(1,0)} \times 7^{\min(0,1)}$ $= 2^2 \times 3^2 \times 5^0 \times 7^0 = 4 \times 9 \times 1 \times 1 = 36$. To find the LCM, take the maximum of the exponents for all prime factors present: $\text{lcm}(A, B) = 2^{\max(3,2)} \times 3^{\max(2,4)} \times 5^{\max(1,0)} \times 7^{\max(0,1)}$ $= 2^3 \times 3^4 \times 5^1 \times 7^1 = 8 \times 81 \times 5 \times 7 = 648 \times 35 = 22680$. 2. **Prove that if $d$ is a common divisor of $a$ and $b$, then $d$ divides $\text{gcd}(a,b)$.** *Solution:* Let $g = \text{gcd}(a,b)$. By Bezout's Identity, there exist integers $x,y$ such that $ax+by=g$. We are given that $d$ is a common divisor of $a$ and $b$. This means $d|a$ and $d|b$. Since $d|a$, $a=dk_1$ for some integer $k_1$. Since $d|b$, $b=dk_2$ for some integer $k_2$. Substitute these into Bezout's Identity: $d k_1 x + d k_2 y = g$ $d (k_1 x + k_2 y) = g$. Since $k_1 x + k_2 y$ is an integer, this shows that $d$ divides $g$. Thus, any common divisor of $a$ and $b$ divides their greatest common divisor. 3. **If $\text{gcd}(a, b) = d$, prove that there exist integers $x, y$ such that $ax + by = d$.** *Solution:* This is a direct statement of Bezout's Identity (also known as Bezout's Lemma). The proof relies on the Euclidean Algorithm. Let $S = \{ax+by \mid x,y \in \mathbb{Z}, ax+by > 0\}$. $S$ is a non-empty set of positive integers (e.g., if $a \ne 0$, then $a(1)+b(0) = a$ or $a(-1)+b(0) = -a$ are in $S$). By the Well-Ordering Principle, $S$ has a smallest element. Let this smallest element be $g = ax_0 + by_0$ for some integers $x_0, y_0$. We will show that $g$ divides $a$ and $g$ divides $b$. Divide $a$ by $g$ using the division algorithm: $a = qg + r$ where $0 \le r z$: $\min(x, \max(y,z)) = \min(x,y) = x$. $\max(\min(x,y), \min(x,z)) = \max(x,z) = x$. (Equal) - If $x > y$ and $x \le z$: $\min(x, \max(y,z)) = \min(x,z) = x$. $\max(\min(x,y), \min(x,z)) = \max(y,x) = x$. (Equal) - If $x > y$ and $x > z$: - If $y \le z$: $\min(x, \max(y,z)) = \min(x,z) = z$. $\max(\min(x,y), \min(x,z)) = \max(y,z) = z$. (Equal) - If $y > z$: $\min(x, \max(y,z)) = \min(x,y) = y$. $\max(\min(x,y), \min(x,z)) = \max(y,z) = y$. (Equal) Since the exponents are equal for every prime $p$, the numbers themselves are equal. 3. **Prove that for any integer $n$, $\text{gcd}(n, n+2)$ is either 1 or 2.** *Solution:* Let $d = \text{gcd}(n, n+2)$. Since $d$ divides $n$ and $d$ divides $n+2$, $d$ must divide their difference: $(n+2) - n = 2$. The positive divisors of 2 are 1 and 2. Therefore, $d$ must be either 1 or 2. 4. **Find the smallest positive integer that is divisible by all integers from 1 to 10.** *Solution:* This is asking for the LCM of $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$. We list the prime factorizations: $1 = 1$ $2 = 2^1$ $3 = 3^1$ $4 = 2^2$ $5 = 5^1$ $6 = 2 \times 3$ $7 = 7^1$ $8 = 2^3$ $9 = 3^2$ $10 = 2 \times 5$ To find the LCM, take the highest power of each prime factor present: $2^{\max(0,1,0,2,0,1,0,3,0,1)} = 2^3 = 8$ $3^{\max(0,0,1,0,0,1,0,0,2,0)} = 3^2 = 9$ $5^{\max(0,0,0,0,1,0,0,0,0,1)} = 5^1 = 5$ $7^{\max(0,0,0,0,0,0,1,0,0,0)} = 7^1 = 7$ $\text{lcm}(1, \ldots, 10) = 2^3 \times 3^2 \times 5^1 \times 7^1 = 8 \times 9 \times 5 \times 7 = 72 \times 35 = 2520$. 5. **If $k$ is a positive integer, prove that $\text{gcd}(k, k+1, k+2) = 1$.** *Solution:* Let $d = \text{gcd}(k, k+1, k+2)$. We know that $\text{gcd}(k, k+1) = 1$ (from Problem 3, Set 2). Since $d$ divides $k$, $d$ divides $k+1$, and $d$ divides $k+2$, it must be that $d$ divides $\text{gcd}(k, k+1)$. So $d | 1$. The only positive divisor of 1 is 1. Therefore, $\text{gcd}(k, k+1, k+2) = 1$. #### Practice Problems - Set 8 - Solutions 1. **Find $\text{lcm}(10!, 12!)$.** *Solution:* Since $10!$ divides $12!$ (because $12! = 12 \times 11 \times 10!$), $10!$ is a factor of $12!$. If $a|b$, then $\text{lcm}(a,b) = b$. Therefore, $\text{lcm}(10!, 12!) = 12!$. 2. **If $\text{gcd}(a, b) = 1$, prove that $\text{gcd}(a+b, a-b)$ is 1 or 2.** *Solution:* This is the same as Problem 5, Set 7, Level 1. Let $d = \text{gcd}(a+b, a-b)$. Since $d | (a+b)$ and $d | (a-b)$: $d | (a+b) + (a-b) \implies d | 2a$. $d | (a+b) - (a-b) \implies d | 2b$. So $d$ is a common divisor of $2a$ and $2b$. Thus $d | \text{gcd}(2a, 2b)$. Since $\text{gcd}(2a, 2b) = 2 \text{gcd}(a,b)$, and we are given $\text{gcd}(a,b)=1$, $\text{gcd}(2a, 2b) = 2 \times 1 = 2$. Therefore, $d | 2$. The only positive divisors of 2 are 1 and 2. Hence, $\text{gcd}(a+b, a-b)$ is either 1 or 2. 3. **Find integers $x, y$ such that $8x + 13y = 1$.** *Solution:* First, find $\text{gcd}(8, 13)$ using Euclidean Algorithm: $13 = 1 \times 8 + 5$ $8 = 1 \times 5 + 3$ $5 = 1 \times 3 + 2$ $3 = 1 \times 2 + 1$ $2 = 2 \times 1 + 0$ The GCD is 1. Now, work backwards: $1 = 3 - 1 \times 2$ $1 = 3 - 1 \times (5 - 1 \times 3) = 3 - 5 + 3 = 2 \times 3 - 5$ $1 = 2 \times (8 - 1 \times 5) - 5 = 2 \times 8 - 2 \times 5 - 5 = 2 \times 8 - 3 \times 5$ $1 = 2 \times 8 - 3 \times (13 - 1 \times 8) = 2 \times 8 - 3 \times 13 + 3 \times 8 = 5 \times 8 - 3 \times 13$. So, $x=5$ and $y=-3$ is a particular solution. The general solution is: $x = 5 + 13k$ $y = -3 - 8k$ for any integer $k$. 4. **Two numbers have a product of 216 and their GCD is 6. Find their LCM.** *Solution:* Let the two numbers be $a$ and $b$. Given $ab = 216$ and $\text{gcd}(a,b) = 6$. Using the relationship $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$: $6 \times \text{lcm}(a,b) = 216$ $\text{lcm}(a,b) = \frac{216}{6} = 36$. 5. **Show that if $a, b$ are positive integers, then $\text{gcd}(a,b) \le \text{lcm}(a,b)$.** *Solution:* We know that $\text{gcd}(a,b) \times \text{lcm}(a,b) = ab$. Also, we know that $a$ divides $\text{lcm}(a,b)$ and $b$ divides $\text{lcm}(a,b)$. And $\text{gcd}(a,b)$ divides $a$ and $\text{gcd}(a,b)$ divides $b$. Let $g = \text{gcd}(a,b)$ and $L = \text{lcm}(a,b)$. Since $g|a$ and $a|L$, it follows that $g|L$. Since $g$ and $L$ are positive integers, if $g|L$, then $g \le L$. Thus, $\text{gcd}(a,b) \le \text{lcm}(a,b)$. #### Practice Problems - Set 9 - Solutions 1. **Find $\text{gcd}(2023, 101)$.** *Solution:* Use the Euclidean Algorithm: $2023 = 20 \times 101 + 3$ $101 = 33 \times 3 + 2$ $3 = 1 \times 2 + 1$ $2 = 2 \times 1 + 0$ The last non-zero remainder is 1. So, $\text{gcd}(2023, 101) = 1$. 2. **If $\text{gcd}(a, b) = 1$, prove that $\text{gcd}(a, b^n) = 1$ for any positive integer $n$.** *Solution:* We prove this by induction on $n$. *Base case $n=1$:* $\text{gcd}(a, b^1) = \text{gcd}(a,b) = 1$, which is given. *Inductive hypothesis:* Assume $\text{gcd}(a, b^k) = 1$ for some positive integer $k$. *Inductive step:* We need to show $\text{gcd}(a, b^{k+1}) = 1$. Assume, for contradiction, that $\text{gcd}(a, b^{k+1}) = d > 1$. Then $d$ must have a prime factor, say $p$. Since $p|d$ and $d|a$, we have $p|a$. Since $p|d$ and $d|b^{k+1}$, we have $p|b^{k+1}$. Since $p$ is prime and $p|b^{k+1}$, it implies $p|b$. So $p$ is a common prime factor of $a$ and $b$. This means $\text{gcd}(a,b) \ge p > 1$. This contradicts the initial condition that $\text{gcd}(a,b)=1$. Therefore, our assumption that $\text{gcd}(a, b^{k+1}) > 1$ must be false. Hence, $\text{gcd}(a, b^{k+1}) = 1$. By induction, $\text{gcd}(a, b^n) = 1$ for all positive integers $n$. 3. **Find the number of pairs of positive integers $(a,b)$ such that $\text{gcd}(a,b)=18$ and $a+b=360$.** *Solution:* Since $\text{gcd}(a,b)=18$, we can write $a=18x$ and $b=18y$, where $\text{gcd}(x,y)=1$. Substitute these into the sum: $18x + 18y = 360$ $18(x+y) = 360$ $x+y = 20$. We need to find pairs of positive integers $(x,y)$ such that $x+y=20$ and $\text{gcd}(x,y)=1$. Possible pairs $(x,y)$ (where $x y$: $(1,19), (19,1), (3,17), (17,3), (7,13), (13,7), (9,11), (11,9)$. There are 8 such pairs of positive integers $(a,b)$. 4. **What is the largest integer that divides every number in the sequence $n(n+1)(n+2)$ for $n \ge 1$?** *Solution:* The sequence is the product of three consecutive integers. Let $P(n) = n(n+1)(n+2)$. We need to find the $\text{gcd}(P(1), P(2), P(3), \ldots)$. $P(1) = 1 \times 2 \times 3 = 6$. $P(2) = 2 \times 3 \times 4 = 24$. $P(3) = 3 \times 4 \times 5 = 60$. The largest integer that divides every number in the sequence must divide $\text{gcd}(P(1), P(2), P(3), \ldots)$. So it must divide $\text{gcd}(6, 24, 60)$. $\text{gcd}(6, 24, 60) = 6$. We already proved in Level 1, Set 3, Problem 2 that the product of any three consecutive integers is divisible by 6. Therefore, 6 divides $n(n+1)(n+2)$ for all $n \ge 1$. The largest such integer is 6. 5. **If $p$ is a prime number, what is $\text{gcd}(p!, (p+1)!)$?** *Solution:* We know that $p!$ is a factor of $(p+1)!$, since $(p+1)! = (p+1) \times p!$. If $a|b$, then $\text{gcd}(a,b) = a$. Therefore, $\text{gcd}(p!, (p+1)!) = p!$. #### Practice Problems - Set 10 - Solutions 1. **Find the GCD and LCM of $2^5 \times 3^1 \times 7^2$ and $2^2 \times 3^4 \times 5^1$.** *Solution:* Let $A = 2^5 \times 3^1 \times 7^2$ and $B = 2^2 \times 3^4 \times 5^1$. GCD: Take minimum of exponents for common primes. $\text{gcd}(A,B) = 2^{\min(5,2)} \times 3^{\min(1,4)} \times 5^{\min(0,1)} \times 7^{\min(2,0)}$ $= 2^2 \times 3^1 \times 5^0 \times 7^0 = 4 \times 3 \times 1 \times 1 = 12$. LCM: Take maximum of exponents for all primes. $\text{lcm}(A,B) = 2^{\max(5,2)} \times 3^{\max(1,4)} \times 5^{\max(0,1)} \times 7^{\max(2,0)}$ $= 2^5 \times 3^4 \times 5^1 \times 7^2 = 32 \times 81 \times 5 \times 49 = 12960 \times 49 = 587520$. 2. **Prove that if $ax + by = 1$, then $\text{gcd}(a,y)=1$.** *Solution:* This statement is incorrect. The property is if $ax+by=1$, then $\text{gcd}(a,b)=1$. Let's prove $\text{gcd}(a,b)=1$. Let $d = \text{gcd}(a,b)$. Since $d|a$ and $d|b$, it follows that $d$ divides any linear combination $ax+by$. So $d|1$. The only positive divisor of 1 is 1. Therefore, $d=1$, which means $\text{gcd}(a,b)=1$. (If the problem meant $\text{gcd}(a,y)=1$, for example, given $2(1) + 3(-1) = -1 \ne 1$, but $2(2) + 3(-1) = 1$. Here $a=2, b=3, x=2, y=-1$. $\text{gcd}(a,y) = \text{gcd}(2,-1)=1$. This might be what the problem intended.) The most standard result is $\text{gcd}(a,b)=1$. If the question *insists* on $\text{gcd}(a,y)=1$, a counterexample like $a=2, b=5, x=-2, y=1$ gives $2(-2) + 5(1) = 1$, but $\text{gcd}(a,y) = \text{gcd}(2,1)=1$. So it can be true. However, it is not universally true. For example, $a=6, b=1, x=0, y=1$ gives $6(0)+1(1)=1$. Here $\text{gcd}(a,y)=\text{gcd}(6,1)=1$. But what if $ax+by=d$ for $d \ne 1$? Consider $a=2, b=3, x=2, y=-1$. $2(2)+3(-1)=1$. $\text{gcd}(a,y)=\text{gcd}(2,-1)=1$. Consider $a=1, b=1, x=0, y=1$. $1(0)+1(1)=1$. $\text{gcd}(a,y)=\text{gcd}(1,1)=1$. It seems the statement $\text{gcd}(a,y)=1$ is actually always true given $ax+by=1$. Let $g = \text{gcd}(a,y)$. Since $g|a$ and $g|y$. From $ax+by=1$, we have $ax+by=1$. Since $g|a$, $g$ divides $ax$. Since $g|y$, $g$ divides $by$. Therefore, $g$ divides $ax+by$. So $g|1$. Since $g$ is a positive integer, $g=1$. This proof works. So the statement $\text{gcd}(a,y)=1$ is indeed correct. My earlier assessment was mistaken. 3. **If $\text{gcd}(a,b) = g$, then $\text{lcm}(a,b) = \frac{ab}{g}$. Prove this relationship.** *Solution:* Let $a=gx$ and $b=gy$, where $\text{gcd}(x,y)=1$. Then $ab = (gx)(gy) = g^2xy$. The LCM of $a$ and $b$ is $L = \text{lcm}(gx, gy)$. Since $\text{gcd}(x,y)=1$, we know $\text{lcm}(x,y) = xy$. So $L = g \text{lcm}(x,y) = gxy$. Now substitute $xy = \frac{ab}{g^2}$ into the expression for $L$: $L = g \left(\frac{ab}{g^2}\right) = \frac{ab}{g}$. Thus, $\text{lcm}(a,b) = \frac{ab}{\text{gcd}(a,b)}$. 4. **A number when divided by 7, 8, and 9 leaves remainders 6, 7, and 8 respectively. Find the smallest such number.** *Solution:* Let the number be $N$. $N \equiv 6 \pmod{7} \implies N \equiv -1 \pmod{7}$ $N \equiv 7 \pmod{8} \implies N \equiv -1 \pmod{8}$ $N \equiv 8 \pmod{9} \implies N \equiv -1 \pmod{9}$ This means $N+1$ is divisible by 7, 8, and 9. So $N+1$ is a common multiple of 7, 8, and 9. We need the smallest such number, so $N+1$ must be the LCM of 7, 8, and 9. Prime factorizations: $7 = 7^1$ $8 = 2^3$ $9 = 3^2$ Since 7, 8, 9 are pairwise coprime, their LCM is their product: $\text{lcm}(7, 8, 9) = 7 \times 8 \times 9 = 56 \times 9 = 504$. So, $N+1 = 504$. $N = 504 - 1 = 503$. The smallest such number is 503. 5. **Find positive integers $x, y$ such that $\text{gcd}(x,y)=1$ and $x+y=100$. How many such pairs are there?** *Solution:* We need to find pairs $(x,y)$ such that $x+y=100$ and $\text{gcd}(x,y)=1$. This is equivalent to finding the number of integers $x$ such that $1 \le x ### Solutions: Level 3 - Modular Arithmetic #### Practice Problems - Set 1 - Solutions 1. **Find the remainder when $17^{2023}$ is divided by 13.** *Solution:* We need to find $17^{2023} \pmod{13}$. First, reduce the base: $17 \equiv 4 \pmod{13}$. So, $17^{2023} \equiv 4^{2023} \pmod{13}$. Now, use Fermat's Little Theorem. Since 13 is a prime number and $\text{gcd}(4, 13)=1$, we have $4^{13-1} \equiv 4^{12} \equiv 1 \pmod{13}$. Divide the exponent 2023 by 12: $2023 = 12 \times 168 + 7$. So, $4^{2023} = 4^{12 \times 168 + 7} = (4^{12})^{168} \times 4^7 \equiv 1^{168} \times 4^7 \pmod{13}$. $4^7 \pmod{13}$: $4^1 \equiv 4 \pmod{13}$ $4^2 \equiv 16 \equiv 3 \pmod{13}$ $4^3 \equiv 4 \times 3 = 12 \equiv -1 \pmod{13}$ $4^7 = 4^3 \times 4^3 \times 4^1 \equiv (-1) \times (-1) \times 4 \equiv 1 \times 4 \equiv 4 \pmod{13}$. Therefore, $17^{2023} \equiv 4 \pmod{13}$. 2. **Solve the system of congruences:** $x \equiv 2 \pmod{3}$ $x \equiv 3 \pmod{5}$ *Solution:* From the first congruence, $x = 3k + 2$ for some integer $k$. Substitute this into the second congruence: $3k + 2 \equiv 3 \pmod{5}$ $3k \equiv 1 \pmod{5}$ We need to find the modular inverse of 3 modulo 5. $3 \times 1 = 3$ $3 \times 2 = 6 \equiv 1 \pmod{5}$. So, the inverse of 3 modulo 5 is 2. Multiply both sides by 2: $2 \times 3k \equiv 2 \times 1 \pmod{5}$ $6k \equiv 2 \pmod{5}$ $k \equiv 2 \pmod{5}$. So, $k = 5m + 2$ for some integer $m$. Substitute this back into the expression for $x$: $x = 3(5m + 2) + 2$ $x = 15m + 6 + 2$ $x = 15m + 8$. Therefore, $x \equiv 8 \pmod{15}$. 3. **What is the smallest positive integer $n$ such that $2^n \equiv 1 \pmod{17}$?** *Solution:* We are looking for the order of 2 modulo 17. By Fermat's Little Theorem, since 17 is prime, $2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}$. So, $n$ must be a divisor of 16. The divisors of 16 are 1, 2, 4, 8, 16. Let's check these powers: $2^1 = 2 \not\equiv 1 \pmod{17}$ $2^2 = 4 \not\equiv 1 \pmod{17}$ $2^4 = 16 \equiv -1 \not\equiv 1 \pmod{17}$ $2^8 = (2^4)^2 \equiv (-1)^2 = 1 \pmod{17}$. The smallest positive integer $n$ for which $2^n \equiv 1 \pmod{17}$ is 8. 4. **Prove that for any integer $n$, $n^5 - n$ is divisible by 5.** *Solution:* We need to show $n^5 - n \equiv 0 \pmod{5}$, or $n^5 \equiv n \pmod{5}$. This is a direct application of Fermat's Little Theorem. Fermat's Little Theorem states that if $p$ is a prime number, then for any integer $a$, $a^p \equiv a \pmod{p}$. Here, $p=5$ and $a=n$. So, $n^5 \equiv n \pmod{5}$. This implies $n^5 - n \equiv 0 \pmod{5}$. Therefore, $n^5 - n$ is divisible by 5 for any integer $n$. 5. **Find the last two digits of $7^{77}$.** *Solution:* Finding the last two digits means finding $7^{77} \pmod{100}$. Since $\text{gcd}(7, 100)=1$, we can use Euler's Totient Theorem. $\phi(100) = \phi(2^2 \times 5^2) = \phi(2^2) \times \phi(5^2) = (2^2 - 2^1) \times (5^2 - 5^1) = (4-2) \times (25-5) = 2 \times 20 = 40$. By Euler's Totient Theorem, $7^{40} \equiv 1 \pmod{100}$. Now, divide the exponent 77 by 40: $77 = 1 \times 40 + 37$. So, $7^{77} = 7^{40+37} = 7^{40} \times 7^{37} \equiv 1 \times 7^{37} \pmod{100}$. We need to calculate $7^{37} \pmod{100}$. Let's find powers of 7 modulo 100: $7^1 \equiv 7 \pmod{100}$ $7^2 \equiv 49 \pmod{100}$ $7^3 \equiv 7 \times 49 = 343 \equiv 43 \pmod{100}$ $7^4 \equiv 7 \times 43 = 301 \equiv 1 \pmod{100}$ This means the cycle length is 4. (Note: The order of 7 modulo 100 is 4, not $\phi(100)=40$. The order must divide $\phi(100)$). Now, divide 77 by 4: $77 = 19 \times 4 + 1$. So, $7^{77} = (7^4)^{19} \times 7^1 \equiv 1^{19} \times 7^1 \equiv 7 \pmod{100}$. The last two digits of $7^{77}$ are 07. #### Practice Problems - Set 2 - Solutions 1. **Find the remainder when $2^{50}$ is divided by 7.** *Solution:* We need to find $2^{50} \pmod{7}$. By Fermat's Little Theorem, $2^{7-1} \equiv 2^6 \equiv 1 \pmod{7}$. Divide the exponent 50 by 6: $50 = 8 \times 6 + 2$. So, $2^{50} = (2^6)^8 \times 2^2 \equiv 1^8 \times 2^2 \equiv 4 \pmod{7}$. The remainder is 4. 2. **Solve the congruence $7x \equiv 5 \pmod{13}$.** *Solution:* We need to find the modular inverse of 7 modulo 13. $7 \times 1 = 7$ $7 \times 2 = 14 \equiv 1 \pmod{13}$. So, the inverse of 7 modulo 13 is 2. Multiply both sides by 2: $2 \times 7x \equiv 2 \times 5 \pmod{13}$ $14x \equiv 10 \pmod{13}$ $x \equiv 10 \pmod{13}$. The solution is $x \equiv 10 \pmod{13}$. 3. **What is the last digit of $3^{2024}$?** *Solution:* The last digit is found by computing the number modulo 10. Powers of 3 modulo 10: $3^1 \equiv 3 \pmod{10}$ $3^2 \equiv 9 \pmod{10}$ $3^3 \equiv 27 \equiv 7 \pmod{10}$ $3^4 \equiv 21 \equiv 1 \pmod{10}$ $3^5 \equiv 3 \pmod{10}$ The pattern of last digits is 3, 9, 7, 1, and it repeats every 4 powers. The cycle length is 4. Divide the exponent 2024 by 4: $2024 = 4 \times 506 + 0$. Since the remainder is 0, the last digit is the same as $3^4$, which is 1. The last digit of $3^{2024}$ is 1. 4. **Prove that $n^3 \equiv n \pmod{6}$ for any integer $n$.** *Solution:* We need to show that $n^3 - n$ is divisible by 6. This means it must be divisible by both 2 and 3. $n^3 - n = n(n^2-1) = n(n-1)(n+1) = (n-1)n(n+1)$. *Divisibility by 2:* The product of any two consecutive integers is even. Thus, $(n-1)n$ is even, so $(n-1)n(n+1)$ is divisible by 2. *Divisibility by 3:* The product of any three consecutive integers is divisible by 3 (one of $n-1, n, n+1$ must be a multiple of 3). Thus, $(n-1)n(n+1)$ is divisible by 3. Since $n^3-n$ is divisible by both 2 and 3, and $\text{gcd}(2,3)=1$, it is divisible by $2 \times 3 = 6$. Therefore, $n^3 \equiv n \pmod{6}$. 5. **Find $x$ such that $x \equiv 1 \pmod{4}$ and $x \equiv 2 \pmod{5}$.** *Solution:* From the first congruence, $x = 4k + 1$ for some integer $k$. Substitute this into the second congruence: $4k + 1 \equiv 2 \pmod{5}$ $4k \equiv 1 \pmod{5}$ We need the inverse of 4 modulo 5. $4 \equiv -1 \pmod{5}$. So $-1 \times (-1) = 1$. The inverse is $-1 \equiv 4 \pmod{5}$. Multiply both sides by 4: $4 \times 4k \equiv 4 \times 1 \pmod{5}$ $16k \equiv 4 \pmod{5}$ $k \equiv 4 \pmod{5}$. So $k = 5m + 4$ for some integer $m$. Substitute back into the expression for $x$: $x = 4(5m + 4) + 1$ $x = 20m + 16 + 1$ $x = 20m + 17$. Therefore, $x \equiv 17 \pmod{20}$. #### Practice Problems - Set 3 - Solutions 1. **Find the remainder when $10^{100}$ is divided by 11.** *Solution:* We need to find $10^{100} \pmod{11}$. Since $10 \equiv -1 \pmod{11}$. $10^{100} \equiv (-1)^{100} \pmod{11}$ $(-1)^{100} = 1$. So, $10^{100} \equiv 1 \pmod{11}$. The remainder is 1. 2. **Solve the congruence $4x \equiv 6 \pmod{10}$.** *Solution:* We have $4x \equiv 6 \pmod{10}$. First, find $\text{gcd}(4, 10) = 2$. Since $2$ divides 6, there are solutions. Divide the congruence by $\text{gcd}(4,10)=2$: $2x \equiv 3 \pmod{10/2}$ $2x \equiv 3 \pmod{5}$. Now, find the inverse of 2 modulo 5. $2 \times 3 = 6 \equiv 1 \pmod{5}$. So the inverse is 3. Multiply both sides by 3: $3 \times 2x \equiv 3 \times 3 \pmod{5}$ $6x \equiv 9 \pmod{5}$ $x \equiv 4 \pmod{5}$. This means $x = 5k + 4$ for some integer $k$. The solutions modulo 10 are $x=4$ (when $k=0$) and $x=9$ (when $k=1$). So, $x \equiv 4 \pmod{10}$ or $x \equiv 9 \pmod{10}$. 3. **What is the remainder when $1! + 2! + 3! + \ldots + 100!$ is divided by 12?** *Solution:* We need to find $S = 1! + 2! + \ldots + 100! \pmod{12}$. Calculate factorials modulo 12: $1! = 1 \equiv 1 \pmod{12}$ $2! = 2 \equiv 2 \pmod{12}$ $3! = 6 \equiv 6 \pmod{12}$ $4! = 24 \equiv 0 \pmod{12}$ For any $n \ge 4$, $n!$ contains factors of both 3 and 4, so $n!$ is divisible by $3 \times 4 = 12$. Thus, for $n \ge 4$, $n! \equiv 0 \pmod{12}$. So, the sum $S \equiv 1! + 2! + 3! + 0 + 0 + \ldots + 0 \pmod{12}$. $S \equiv 1 + 2 + 6 \pmod{12}$ $S \equiv 9 \pmod{12}$. The remainder is 9. 4. **Show that $2^{30} + 3^{30}$ is divisible by 13.** *Solution:* We need to show $2^{30} + 3^{30} \equiv 0 \pmod{13}$. By Fermat's Little Theorem, since 13 is prime: $2^{12} \equiv 1 \pmod{13}$ $3^{12} \equiv 1 \pmod{13}$ Now, work with the exponents: $2^{30} = 2^{2 \times 12 + 6} = (2^{12})^2 \times 2^6 \equiv 1^2 \times 2^6 \equiv 2^6 \pmod{13}$. $2^6 = 64$. $64 = 4 \times 13 + 12 \equiv 12 \equiv -1 \pmod{13}$. So, $2^{30} \equiv -1 \pmod{13}$. Similarly for $3^{30}$: $3^{30} = 3^{2 \times 12 + 6} = (3^{12})^2 \times 3^6 \equiv 1^2 \times 3^6 \equiv 3^6 \pmod{13}$. $3^1=3, 3^2=9, 3^3=27 \equiv 1 \pmod{13}$. So $3^6 = (3^3)^2 \equiv 1^2 \equiv 1 \pmod{13}$. Therefore, $2^{30} + 3^{30} \equiv (-1) + 1 \pmod{13}$ $ \equiv 0 \pmod{13}$. Thus, $2^{30} + 3^{30}$ is divisible by 13. 5. **Find the smallest positive integer $x$ such that $x \equiv 3 \pmod{7}$ and $x \equiv 5 \pmod{11}$.** *Solution:* From the first congruence, $x = 7k + 3$ for some integer $k$. Substitute into the second congruence: $7k + 3 \equiv 5 \pmod{11}$ $7k \equiv 2 \pmod{11}$. We need the inverse of 7 modulo 11. $7 \times 1 = 7$ $7 \times 2 = 14 \equiv 3$ $7 \times 3 = 21 \equiv 10 \equiv -1$ $7 \times (-3) \equiv 1 \pmod{11}$. So $-3 \equiv 8$ is the inverse. Multiply both sides by 8: $8 \times 7k \equiv 8 \times 2 \pmod{11}$ $56k \equiv 16 \pmod{11}$ $k \equiv 5 \pmod{11}$ (since $56 = 5 \times 11 + 1$, and $16 = 1 \times 11 + 5$). So $k = 11m + 5$ for some integer $m$. Substitute back into the expression for $x$: $x = 7(11m + 5) + 3$ $x = 77m + 35 + 3$ $x = 77m + 38$. The smallest positive integer $x$ is obtained when $m=0$, so $x=38$. #### Practice Problems - Set 4 - Solutions 1. **Find the last two digits of $3^{200}$.** *Solution:* We need to find $3^{200} \pmod{100}$. Since $\text{gcd}(3, 100)=1$, we can use Euler's Totient Theorem. $\phi(100) = \phi(2^2 \times 5^2) = (2^2-2^1)(5^2-5^1) = 2 \times 20 = 40$. By Euler's Totient Theorem, $3^{40} \equiv 1 \pmod{100}$. Now, $3^{200} = (3^{40})^5 \equiv 1^5 \equiv 1 \pmod{100}$. The last two digits are 01. 2. **Solve $12x \equiv 18 \pmod{30}$.** *Solution:* We have $12x \equiv 18 \pmod{30}$. First, find $\text{gcd}(12, 30) = 6$. Since $6$ divides 18, there are solutions. Divide the congruence by $\text{gcd}(12,30)=6$: $2x \equiv 3 \pmod{30/6}$ $2x \equiv 3 \pmod{5}$. We need the inverse of 2 modulo 5. It is 3. Multiply both sides by 3: $3 \times 2x \equiv 3 \times 3 \pmod{5}$ $6x \equiv 9 \pmod{5}$ $x \equiv 4 \pmod{5}$. This means $x = 5k + 4$ for some integer $k$. The solutions modulo 30 are: $k=0 \implies x=4$ $k=1 \implies x=9$ $k=2 \implies x=14$ $k=3 \implies x=19$ $k=4 \implies x=24$ $k=5 \implies x=29$ So, $x \equiv 4, 9, 14, 19, 24, 29 \pmod{30}$. 3. **If $p$ is a prime, prove that $(a+b)^p \equiv a^p + b^p \pmod p$.** *Solution:* By the Binomial Theorem, $(a+b)^p = \sum_{k=0}^p \binom{p}{k} a^{p-k} b^k$. $(a+b)^p = \binom{p}{0} a^p b^0 + \binom{p}{1} a^{p-1} b^1 + \ldots + \binom{p}{p-1} a^1 b^{p-1} + \binom{p}{p} a^0 b^p$. $(a+b)^p = a^p + \binom{p}{1} a^{p-1} b + \ldots + \binom{p}{p-1} a b^{p-1} + b^p$. From Level 1, Set 2, Problem 2, we know that for any prime $p$, $p$ divides $\binom{p}{k}$ for $1 \le k \le p-1$. This means $\binom{p}{k} \equiv 0 \pmod p$ for $1 \le k \le p-1$. Therefore, all the intermediate terms in the binomial expansion are congruent to 0 modulo $p$. $(a+b)^p \equiv a^p + 0 + \ldots + 0 + b^p \pmod p$. $(a+b)^p \equiv a^p + b^p \pmod p$. 4. **What is the remainder when $2023^{2023}$ is divided by 5?** *Solution:* We need to find $2023^{2023} \pmod{5}$. First, reduce the base: $2023 \equiv 3 \pmod{5}$. So, $2023^{2023} \equiv 3^{2023} \pmod{5}$. Now, consider powers of 3 modulo 5: $3^1 \equiv 3 \pmod{5}$ $3^2 \equiv 9 \equiv 4 \pmod{5}$ $3^3 \equiv 12 \equiv 2 \pmod{5}$ $3^4 \equiv 6 \equiv 1 \pmod{5}$ The cycle length is 4. Divide the exponent 2023 by 4: $2023 = 4 \times 505 + 3$. So, $3^{2023} \equiv 3^3 \pmod{5}$. $3^3 = 27 \equiv 2 \pmod{5}$. The remainder is 2. 5. **Find an integer $x$ such that $x \equiv 1 \pmod{2}$, $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$.** *Solution:* From $x \equiv 1 \pmod{2}$, $x$ is odd. From $x \equiv 2 \pmod{3}$, $x = 3k+2$. Substitute into $x \equiv 1 \pmod{2}$: $3k+2 \equiv 1 \pmod{2}$ $k \equiv 1 \pmod{2}$. So $k = 2m+1$. Substitute $k$ back: $x = 3(2m+1)+2 = 6m+3+2 = 6m+5$. So $x \equiv 5 \pmod{6}$. Now we have a system: $x \equiv 5 \pmod{6}$ $x \equiv 3 \pmod{5}$ From $x \equiv 5 \pmod{6}$, $x = 6j+5$. Substitute into $x \equiv 3 \pmod{5}$: $6j+5 \equiv 3 \pmod{5}$ $j \equiv 3 \pmod{5}$. So $j = 5s+3$. Substitute $j$ back: $x = 6(5s+3)+5 = 30s+18+5 = 30s+23$. Therefore, $x \equiv 23 \pmod{30}$. The smallest positive integer solution is 23. #### Practice Problems - Set 5 - Solutions 1. **Find the remainder when $13^{13}$ is divided by 100.** *Solution:* We need to find $13^{13} \pmod{100}$. Since $\text{gcd}(13, 100)=1$, we can use Euler's Totient Theorem. $\phi(100) = 40$. So $13^{40} \equiv 1 \pmod{100}$. We need $13^{13} \pmod{100}$. The exponent 13 is less than 40. Calculate powers of 13 modulo 100: $13^1 \equiv 13 \pmod{100}$ $13^2 = 169 \equiv 69 \pmod{100}$ $13^3 \equiv 13 \times 69 = 897 \equiv 97 \equiv -3 \pmod{100}$ $13^4 \equiv 13 \times (-3) = -39 \equiv 61 \pmod{100}$ $13^5 \equiv 13 \times 61 = 793 \equiv 93 \equiv -7 \pmod{100}$ $13^{10} = (13^5)^2 \equiv (-7)^2 = 49 \pmod{100}$ $13^{13} = 13^{10} \times 13^3 \equiv 49 \times 97 \pmod{100}$ $49 \times 97 = 49 \times (-3) = -147 \equiv -47 \equiv 53 \pmod{100}$. The remainder is 53. 2. **Solve $15x \equiv 25 \pmod{35}$.** *Solution:* We have $15x \equiv 25 \pmod{35}$. First, find $\text{gcd}(15, 35) = 5$. Since $5$ divides 25, there are solutions. Divide the congruence by $\text{gcd}(15,35)=5$: $3x \equiv 5 \pmod{35/5}$ $3x \equiv 5 \pmod{7}$. We need the inverse of 3 modulo 7. $3 \times 5 = 15 \equiv 1 \pmod{7}$. So the inverse is 5. Multiply both sides by 5: $5 \times 3x \equiv 5 \times 5 \pmod{7}$ $15x \equiv 25 \pmod{7}$ $x \equiv 4 \pmod{7}$ (since $15 \equiv 1 \pmod{7}$ and $25 \equiv 4 \pmod{7}$). This means $x = 7k + 4$ for some integer $k$. The solutions modulo 35 are: $k=0 \implies x=4$ $k=1 \implies x=11$ $k=2 \implies x=18$ $k=3 \implies x=25$ $k=4 \implies x=32$ So, $x \equiv 4, 11, 18, 25, 32 \pmod{35}$. 3. **Prove that $a^2 \equiv 1 \pmod 8$ if $a$ is an odd integer.** *Solution:* Since $a$ is an odd integer, we can write $a = 2k+1$ for some integer $k$. $a^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1$. We know that $k(k+1)$ is always an even number (product of two consecutive integers). So, $k(k+1) = 2m$ for some integer $m$. Substitute this: $a^2 = 4(2m) + 1 = 8m + 1$. Therefore, $a^2 \equiv 1 \pmod 8$. 4. **What is the last digit of $7^{7^7}$?** *Solution:* We need to find $7^{7^7} \pmod{10}$. The cycle of last digits of powers of 7 is: $7^1 \equiv 7 \pmod{10}$ $7^2 \equiv 9 \pmod{10}$ $7^3 \equiv 3 \pmod{10}$ $7^4 \equiv 1 \pmod{10}$ The cycle length is 4. We need to find the exponent $7^7$ modulo 4. $7 \equiv 3 \equiv -1 \pmod{4}$. So, $7^7 \equiv (-1)^7 \pmod{4}$ $7^7 \equiv -1 \pmod{4}$ $7^7 \equiv 3 \pmod{4}$. Now, substitute this back into the original problem: $7^{7^7} \equiv 7^3 \pmod{10}$. $7^3 = 343 \equiv 3 \pmod{10}$. The last digit is 3. 5. **Find the smallest positive integer $n$ such that $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{4}$, and $n \equiv 4 \pmod{5}$.** *Solution:* We can rewrite the congruences: $n \equiv -1 \pmod{3}$ $n \equiv -1 \pmod{4}$ $n \equiv -1 \pmod{5}$ This means $n+1$ is divisible by 3, 4, and 5. So $n+1$ is a common multiple of 3, 4, and 5. We are looking for the smallest positive integer $n$, so $n+1$ must be the LCM of 3, 4, and 5. Since 3, 4, and 5 are pairwise coprime, their LCM is their product: $\text{lcm}(3, 4, 5) = 3 \times 4 \times 5 = 60$. So, $n+1 = 60$. $n = 59$. The smallest positive integer is 59. #### Practice Problems - Set 6 - Solutions 1. **Find the remainder when $2^{1000}$ is divided by 101.** *Solution:* We need to find $2^{1000} \pmod{101}$. Since 101 is a prime number, by Fermat's Little Theorem: $2^{101-1} \equiv 2^{100} \equiv 1 \pmod{101}$. Now, $2^{1000} = (2^{100})^{10} \equiv 1^{10} \equiv 1 \pmod{101}$. The remainder is 1. 2. **Solve $3x \equiv 4 \pmod 5$.** *Solution:* We need the inverse of 3 modulo 5. We know $3 \times 2 = 6 \equiv 1 \pmod{5}$. So the inverse is 2. Multiply both sides by 2: $2 \times 3x \equiv 2 \times 4 \pmod{5}$ $6x \equiv 8 \pmod{5}$ $x \equiv 3 \pmod{5}$ (since $6 \equiv 1 \pmod{5}$ and $8 \equiv 3 \pmod{5}$). The solution is $x \equiv 3 \pmod{5}$. 3. **Prove that if $p$ is a prime number, then $(p-1)! \equiv -1 \pmod p$ (Wilson's Theorem).** *Solution:* *Case 1: $p=2$.* $(2-1)! = 1! = 1 \equiv -1 \pmod 2$. The theorem holds. *Case 2: $p > 2$.* Consider the integers $1, 2, \ldots, p-1$. Each of these integers has a multiplicative inverse modulo $p$. For each $a \in \{1, \ldots, p-1\}$, its inverse $a^{-1}$ is also in this set. If $a = a^{-1} \pmod p$, then $a^2 \equiv 1 \pmod p$, which means $a^2-1 \equiv 0 \pmod p$, so $(a-1)(a+1) \equiv 0 \pmod p$. Since $p$ is prime, this implies $p|(a-1)$ or $p|(a+1)$. - $p|(a-1) \implies a \equiv 1 \pmod p$. - $p|(a+1) \implies a \equiv -1 \equiv p-1 \pmod p$. So, only 1 and $p-1$ are their own inverses. For all other integers $a \in \{2, 3, \ldots, p-2\}$, each $a$ is paired with a distinct inverse $a^{-1} \ne a$. Therefore, when we multiply the terms in $(p-1)! = 1 \times 2 \times \ldots \times (p-1)$, all terms from 2 to $p-2$ cancel out with their inverses, leaving 1. So, $(p-1)! \equiv 1 \times (p-1) \pmod p$ $(p-1)! \equiv 1 \times (-1) \pmod p$ $(p-1)! \equiv -1 \pmod p$. Thus, Wilson's Theorem holds for all primes $p$. 4. **What is the remainder when $2^{100}$ is divided by 13?** *Solution:* We need to find $2^{100} \pmod{13}$. By Fermat's Little Theorem, since 13 is prime, $2^{13-1} \equiv 2^{12} \equiv 1 \pmod{13}$. Divide the exponent 100 by 12: $100 = 8 \times 12 + 4$. So, $2^{100} = (2^{12})^8 \times 2^4 \equiv 1^8 \times 2^4 \equiv 2^4 \pmod{13}$. $2^4 = 16 \equiv 3 \pmod{13}$. The remainder is 3. 5. **Find the smallest positive integer $x$ such that $x \equiv 0 \pmod{2}$, $x \equiv 0 \pmod{3}$, $x \equiv 1 \pmod{5}$.** *Solution:* From $x \equiv 0 \pmod{2}$ and $x \equiv 0 \pmod{3}$, $x$ is a common multiple of 2 and 3. Since $\text{gcd}(2,3)=1$, $x$ is a multiple of $\text{lcm}(2,3)=6$. So $x \equiv 0 \pmod{6}$. Now we have a system: $x \equiv 0 \pmod{6}$ $x \equiv 1 \pmod{5}$ From $x \equiv 0 \pmod{6}$, $x = 6k$. Substitute into $x \equiv 1 \pmod{5}$: $6k \equiv 1 \pmod{5}$ $k \equiv 1 \pmod{5}$ (since $6 \equiv 1 \pmod{5}$). So $k = 5m + 1$ for some integer $m$. Substitute back into the expression for $x$: $x = 6(5m + 1) = 30m + 6$. The smallest positive integer $x$ is obtained when $m=0$, so $x=6$. #### Practice Problems - Set 7 - Solutions 1. **Find the remainder when $3^{45}$ is divided by 17.** *Solution:* We need to find $3^{45} \pmod{17}$. Since 17 is prime, by Fermat's Little Theorem, $3^{17-1} \equiv 3^{16} \equiv 1 \pmod{17}$. Divide the exponent 45 by 16: $45 = 2 \times 16 + 13$. So, $3^{45} = (3^{16})^2 \times 3^{13} \equiv 1^2 \times 3^{13} \equiv 3^{13} \pmod{17}$. Now calculate $3^{13} \pmod{17}$: $3^1=3$ $3^2=9$ $3^3=27 \equiv 10 \pmod{17}$ $3^4 \equiv 3 \times 10 = 30 \equiv 13 \equiv -4 \pmod{17}$ $3^8 \equiv (-4)^2 = 16 \equiv -1 \pmod{17}$ $3^{13} = 3^8 \times 3^4 \times 3^1 \equiv (-1) \times (-4) \times 3 \pmod{17}$ $\equiv 4 \times 3 = 12 \pmod{17}$. The remainder is 12. 2. **Solve $2x + 1 \equiv 5 \pmod 7$.** *Solution:* $2x + 1 \equiv 5 \pmod 7$ $2x \equiv 4 \pmod 7$. Since $\text{gcd}(2,7)=1$, we can divide by 2. $x \equiv 2 \pmod 7$. The solution is $x \equiv 2 \pmod 7$. 3. **Show that a number is divisible by 9 if and only if the sum of its digits is divisible by 9.** *Solution:* Let the number be $N$. We can write $N$ in terms of its digits $d_k, d_{k-1}, \ldots, d_1, d_0$ as: $N = d_k 10^k + d_{k-1} 10^{k-1} + \ldots + d_1 10^1 + d_0 10^0$. We are interested in $N \pmod 9$. Notice that $10 \equiv 1 \pmod 9$. Then $10^m \equiv 1^m \equiv 1 \pmod 9$ for any non-negative integer $m$. So, $N \equiv d_k (1) + d_{k-1} (1) + \ldots + d_1 (1) + d_0 (1) \pmod 9$. $N \equiv d_k + d_{k-1} + \ldots + d_1 + d_0 \pmod 9$. The right side is the sum of the digits of $N$. Therefore, $N \equiv (\text{sum of digits}) \pmod 9$. This implies that $N$ is divisible by 9 if and only if the sum of its digits is divisible by 9. 4. **What is the remainder when $100^{100}$ is divided by 7?** *Solution:* We need to find $100^{100} \pmod{7}$. First, reduce the base: $100 = 14 \times 7 + 2$, so $100 \equiv 2 \pmod{7}$. So, $100^{100} \equiv 2^{100} \pmod{7}$. By Fermat's Little Theorem, since 7 is prime, $2^{7-1} \equiv 2^6 \equiv 1 \pmod{7}$. Divide the exponent 100 by 6: $100 = 16 \times 6 + 4$. So, $2^{100} = (2^6)^{16} \times 2^4 \equiv 1^{16} \times 2^4 \equiv 2^4 \pmod{7}$. $2^4 = 16 \equiv 2 \pmod{7}$. The remainder is 2. 5. **Find the smallest positive integer $n$ such that $n \equiv 1 \pmod{5}$, $n \equiv 2 \pmod{6}$, $n \equiv 3 \pmod{7}$.** *Solution:* From $n \equiv 1 \pmod{5}$, $n = 5k+1$. Substitute into $n \equiv 2 \pmod{6}$: $5k+1 \equiv 2 \pmod{6}$ $5k \equiv 1 \pmod{6}$ $-k \equiv 1 \pmod{6}$ $k \equiv -1 \pmod{6}$ $k \equiv 5 \pmod{6}$. So $k = 6m+5$. Substitute $k$ back: $n = 5(6m+5)+1 = 30m+25+1 = 30m+26$. Now we have: $n \equiv 26 \pmod{30}$ $n \equiv 3 \pmod{7}$ From $n \equiv 26 \pmod{30}$, $n = 30j+26$. Substitute into $n \equiv 3 \pmod{7}$: $30j+26 \equiv 3 \pmod{7}$ $2j+5 \equiv 3 \pmod{7}$ (since $30 \equiv 2 \pmod{7}$ and $26 \equiv 5 \pmod{7}$) $2j \equiv -2 \pmod{7}$ $2j \equiv 5 \pmod{7}$. We need the inverse of 2 modulo 7. $2 \times 4 = 8 \equiv 1 \pmod{7}$. So the inverse is 4. Multiply by 4: $4 \times 2j \equiv 4 \times 5 \pmod{7}$ $8j \equiv 20 \pmod{7}$ $j \equiv 6 \pmod{7}$ (since $8 \equiv 1 \pmod{7}$ and $20 \equiv 6 \pmod{7}$). So $j = 7s+6$. Substitute $j$ back: $n = 30(7s+6)+26 = 210s+180+26 = 210s+206$. The smallest positive integer $n$ is 206. #### Practice Problems - Set 8 - Solutions 1. **Find the last digit of $2023^{2023^{2023}}$.** *Solution:* We need to find $2023^{2023^{2023}} \pmod{10}$. First, reduce the base: $2023 \equiv 3 \pmod{10}$. So we need $3^{2023^{2023}} \pmod{10}$. The cycle of last digits of powers of 3 is 3, 9, 7, 1 (length 4). We need to find the exponent $2023^{2023}$ modulo 4. Base of exponent: $2023 \equiv 3 \equiv -1 \pmod{4}$. Exponent of exponent: $2023 \equiv 3 \pmod{4}$. So, $2023^{2023} \equiv (-1)^{2023} \pmod{4}$. Since 2023 is odd, $(-1)^{2023} = -1$. So $2023^{2023} \equiv -1 \pmod{4} \equiv 3 \pmod{4}$. Now, substitute back into $3^{\text{exponent}} \pmod{10}$: $3^{2023^{2023}} \equiv 3^3 \pmod{10}$. $3^3 = 27 \equiv 7 \pmod{10}$. The last digit is 7. 2. **Solve $9x \equiv 12 \pmod{15}$.** *Solution:* We have $9x \equiv 12 \pmod{15}$. First, find $\text{gcd}(9, 15) = 3$. Since $3$ divides 12, there are solutions. Divide the congruence by $\text{gcd}(9,15)=3$: $3x \equiv 4 \pmod{15/3}$ $3x \equiv 4 \pmod{5}$. We need the inverse of 3 modulo 5. It is 2. Multiply both sides by 2: $2 \times 3x \equiv 2 \times 4 \pmod{5}$ $6x \equiv 8 \pmod{5}$ $x \equiv 3 \pmod{5}$. This means $x = 5k + 3$ for some integer $k$. The solutions modulo 15 are: $k=0 \implies x=3$ $k=1 \implies x=8$ $k=2 \implies x=13$ So, $x \equiv 3, 8, 13 \pmod{15}$. 3. **Prove that for any integer $n$, $n^2+n+1$ is never divisible by 4.** *Solution:* We can analyze this by considering $n$ modulo 4: *Case 1: $n \equiv 0 \pmod{4}$.* $n^2+n+1 \equiv 0^2+0+1 \equiv 1 \pmod{4}$. *Case 2: $n \equiv 1 \pmod{4}$.* $n^2+n+1 \equiv 1^2+1+1 \equiv 3 \pmod{4}$. *Case 3: $n \equiv 2 \pmod{4}$.* $n^2+n+1 \equiv 2^2+2+1 \equiv 4+2+1 \equiv 7 \equiv 3 \pmod{4}$. *Case 4: $n \equiv 3 \pmod{4}$.* $n^2+n+1 \equiv 3^2+3+1 \equiv 9+3+1 \equiv 13 \equiv 1 \pmod{4}$. In all cases, $n^2+n+1$ is never congruent to $0 \pmod{4}$. Therefore, $n^2+n+1$ is never divisible by 4. 4. **What is the remainder when $19^{19}$ is divided by 5?** *Solution:* We need to find $19^{19} \pmod{5}$. First, reduce the base: $19 \equiv 4 \equiv -1 \pmod{5}$. So, $19^{19} \equiv (-1)^{19} \pmod{5}$. Since 19 is an odd exponent, $(-1)^{19} = -1$. So, $19^{19} \equiv -1 \pmod{5} \equiv 4 \pmod{5}$. The remainder is 4. 5. **Find the smallest positive integer $x$ such that $x \equiv 1 \pmod{3}$, $x \equiv 2 \pmod{4}$, $x \equiv 3 \pmod{5}$.** *Solution:* From $x \equiv 1 \pmod{3}$, $x = 3k+1$. Substitute into $x \equiv 2 \pmod{4}$: $3k+1 \equiv 2 \pmod{4}$ $3k \equiv 1 \pmod{4}$ $-k \equiv 1 \pmod{4}$ $k \equiv -1 \pmod{4}$ $k \equiv 3 \pmod{4}$. So $k = 4m+3$. Substitute $k$ back: $x = 3(4m+3)+1 = 12m+9+1 = 12m+10$. Now we have: $x \equiv 10 \pmod{12}$ $x \equiv 3 \pmod{5}$ From $x \equiv 10 \pmod{12}$, $x = 12j+10$. Substitute into $x \equiv 3 \pmod{5}$: $12j+10 \equiv 3 \pmod{5}$ $2j+0 \equiv 3 \pmod{5}$ (since $12 \equiv 2 \pmod{5}$ and $10 \equiv 0 \pmod{5}$) $2j \equiv 3 \pmod{5}$. We need the inverse of 2 modulo 5. It is 3. Multiply by 3: $3 \times 2j \equiv 3 \times 3 \pmod{5}$ $6j \equiv 9 \pmod{5}$ $j \equiv 4 \pmod{5}$. So $j = 5s+4$. Substitute $j$ back: $x = 12(5s+4)+10 = 60s+48+10 = 60s+58$. The smallest positive integer $x$ is 58. #### Practice Problems - Set 9 - Solutions 1. **Find the remainder when $5^{20}$ is divided by 24.** *Solution:* We need to find $5^{20} \pmod{24}$. Since $\text{gcd}(5, 24)=1$, we can use Euler's Totient Theorem. $\phi(24) = \phi(2^3 \times 3^1) = \phi(2^3)\phi(3^1) = (2^3-2^2)(3^1-3^0) = (8-4)(3-1) = 4 \times 2 = 8$. By Euler's Totient Theorem, $5^8 \equiv 1 \pmod{24}$. Now, $5^{20} = 5^{2 \times 8 + 4} = (5^8)^2 \times 5^4 \equiv 1^2 \times 5^4 \equiv 5^4 \pmod{24}$. $5^1=5$ $5^2=25 \equiv 1 \pmod{24}$. So, $5^4 = (5^2)^2 \equiv 1^2 \equiv 1 \pmod{24}$. The remainder is 1. 2. **Solve $10x \equiv 15 \pmod{25}$.** *Solution:* We have $10x \equiv 15 \pmod{25}$. First, find $\text{gcd}(10, 25) = 5$. Since $5$ divides 15, there are solutions. Divide the congruence by $\text{gcd}(10,25)=5$: $2x \equiv 3 \pmod{25/5}$ $2x \equiv 3 \pmod{5}$. We need the inverse of 2 modulo 5. It is 3. Multiply both sides by 3: $3 \times 2x \equiv 3 \times 3 \pmod{5}$ $6x \equiv 9 \pmod{5}$ $x \equiv 4 \pmod{5}$. This means $x = 5k + 4$ for some integer $k$. The solutions modulo 25 are: $k=0 \implies x=4$ $k=1 \implies x=9$ $k=2 \implies x=14$ $k=3 \implies x=19$ $k=4 \implies x=24$ So, $x \equiv 4, 9, 14, 19, 24 \pmod{25}$. 3. **Show that if $\text{gcd}(a,m)=1$, then $a^{\phi(m)} \equiv 1 \pmod m$.** *Solution:* This is Euler's Totient Theorem. The proof involves considering the set of $\phi(m)$ positive integers less than $m$ that are relatively prime to $m$. Let this set be $S = \{x_1, x_2, \ldots, x_{\phi(m)}\}$. Since $\text{gcd}(a,m)=1$, if we multiply each element of $S$ by $a$ modulo $m$, we get a new set $S' = \{ax_1 \pmod m, ax_2 \pmod m, \ldots, ax_{\phi(m)} \pmod m\}$. 1. Each element in $S'$ is relatively prime to $m$. (If $\text{gcd}(ax_i, m) \ne 1$, then there is a prime $p$ dividing $ax_i$ and $m$. Since $p|m$ and $\text{gcd}(a,m)=1$, $p \nmid a$. So $p|x_i$. But $x_i \in S$, so $\text{gcd}(x_i,m)=1$, a contradiction). 2. All elements in $S'$ are distinct. (Assume $ax_i \equiv ax_j \pmod m$. Since $\text{gcd}(a,m)=1$, $a$ has a modular inverse modulo $m$. Multiplying by $a^{-1}$, we get $x_i \equiv x_j \pmod m$. Since $x_i, x_j$ are in $S$, they must be equal if they are congruent modulo $m$). Since $S'$ contains $\phi(m)$ distinct elements, all relatively prime to $m$ and less than $m$, $S'$ must be a permutation of $S$. Therefore, the product of the elements in $S$ is congruent to the product of the elements in $S'$ modulo $m$: $x_1 x_2 \cdots x_{\phi(m)} \equiv (ax_1)(ax_2)\cdots(ax_{\phi(m)}) \pmod m$ $P \equiv a^{\phi(m)} (x_1 x_2 \cdots x_{\phi(m)}) \pmod m$ $P \equiv a^{\phi(m)} P \pmod m$, where $P = x_1 x_2 \cdots x_{\phi(m)}$. Since each $x_i$ is relatively prime to $m$, their product $P$ is also relatively prime to $m$. Therefore, $P$ has a modular inverse modulo $m$. Multiply both sides by $P^{-1}$: $1 \equiv a^{\phi(m)} \pmod m$. 4. **What is the remainder when $2^{20} + 3^{20}$ is divided by 5?** *Solution:* We need to find $2^{20} + 3^{20} \pmod{5}$. By Fermat's Little Theorem, since 5 is prime: $2^{5-1} \equiv 2^4 \equiv 1 \pmod{5}$. $3^{5-1} \equiv 3^4 \equiv 1 \pmod{5}$. So, $2^{20} = (2^4)^5 \equiv 1^5 \equiv 1 \pmod{5}$. And $3^{20} = (3^4)^5 \equiv 1^5 \equiv 1 \pmod{5}$. Therefore, $2^{20} + 3^{20} \equiv 1 + 1 \pmod{5}$ $ \equiv 2 \pmod{5}$. The remainder is 2. 5. **Find the smallest positive integer $n$ such that $n \equiv 1 \pmod{2}$, $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{4}$.** *Solution:* From $n \equiv 1 \pmod{2}$, $n$ is odd. From $n \equiv 3 \pmod{4}$, $n = 4k+3$. If $n=4k+3$, then $n$ is always odd. So the first condition is automatically satisfied by the third condition. Now we have: $n \equiv 2 \pmod{3}$ $n \equiv 3 \pmod{4}$ From $n \equiv 3 \pmod{4}$, $n = 4j+3$. Substitute into $n \equiv 2 \pmod{3}$: $4j+3 \equiv 2 \pmod{3}$ $j+0 \equiv 2 \pmod{3}$ (since $4 \equiv 1 \pmod{3}$ and $3 \equiv 0 \pmod{3}$) $j \equiv 2 \pmod{3}$. So $j = 3s+2$. Substitute $j$ back: $n = 4(3s+2)+3 = 12s+8+3 = 12s+11$. The smallest positive integer $n$ is 11. #### Practice Problems - Set 10 - Solutions 1. **Find the remainder when $7^{2023} + 1$ is divided by 8.** *Solution:* We need to find $7^{2023} + 1 \pmod{8}$. First, reduce the base: $7 \equiv -1 \pmod{8}$. So, $7^{2023} + 1 \equiv (-1)^{2023} + 1 \pmod{8}$. Since 2023 is odd, $(-1)^{2023} = -1$. So, $7^{2023} + 1 \equiv -1 + 1 \pmod{8}$ $ \equiv 0 \pmod{8}$. The remainder is 0. 2. **Solve $14x \equiv 21 \pmod{35}$.** *Solution:* We have $14x \equiv 21 \pmod{35}$. First, find $\text{gcd}(14, 35) = 7$. Since $7$ divides 21, there are solutions. Divide the congruence by $\text{gcd}(14,35)=7$: $2x \equiv 3 \pmod{35/7}$ $2x \equiv 3 \pmod{5}$. We need the inverse of 2 modulo 5. It is 3. Multiply both sides by 3: $3 \times 2x \equiv 3 \times 3 \pmod{5}$ $6x \equiv 9 \pmod{5}$ $x \equiv 4 \pmod{5}$. This means $x = 5k + 4$ for some integer $k$. The solutions modulo 35 are: $k=0 \implies x=4$ $k=1 \implies x=9$ $k=2 \implies x=14$ $k=3 \implies x=19$ $k=4 \implies x=24$ $k=5 \implies x=29$ $k=6 \implies x=34$ So, $x \equiv 4, 9, 14, 19, 24, 29, 34 \pmod{35}$. 3. **Prove that for any prime $p > 2$, $p^2 \equiv 1 \pmod 8$.** *Solution:* Since $p$ is a prime number greater than 2, $p$ must be an odd prime. From Practice Problems, Set 5, Problem 3, we proved that for any odd integer $a$, $a^2 \equiv 1 \pmod 8$. Since $p$ is an odd prime, it is an odd integer. Therefore, $p^2 \equiv 1 \pmod 8$. 4. **What is the last digit of $4^{100}$?** *Solution:* We need to find $4^{100} \pmod{10}$. Powers of 4 modulo 10: $4^1 \equiv 4 \pmod{10}$ $4^2 = 16 \equiv 6 \pmod{10}$ $4^3 \equiv 4 \times 6 = 24 \equiv 4 \pmod{10}$ The pattern of last digits is 4, 6, 4, 6, ... The cycle length is 2. For odd exponents, the last digit is 4. For even exponents (greater than 0), the last digit is 6. Since the exponent 100 is even, the last digit is 6. 5. **Find the number of solutions to $x^2 \equiv 1 \pmod{15}$.** *Solution:* We need to solve $x^2 \equiv 1 \pmod{15}$. Since $15 = 3 \times 5$ and $\text{gcd}(3,5)=1$, we can use the Chinese Remainder Theorem. The congruence $x^2 \equiv 1 \pmod{15}$ is equivalent to the system: $x^2 \equiv 1 \pmod{3}$ $x^2 \equiv 1 \pmod{5}$ Solve $x^2 \equiv 1 \pmod{3}$: $x^2-1 \equiv 0 \pmod{3} \implies (x-1)(x+1) \equiv 0 \pmod{3}$. Since 3 is prime, $x-1 \equiv 0 \pmod{3}$ or $x+1 \equiv 0 \pmod{3}$. $x \equiv 1 \pmod{3}$ or $x \equiv -1 \pmod{3} \equiv 2 \pmod{3}$. (2 solutions) Solve $x^2 \equiv 1 \pmod{5}$: $x^2-1 \equiv 0 \pmod{5} \implies (x-1)(x+1) \equiv 0 \pmod{5}$. Since 5 is prime, $x-1 \equiv 0 \pmod{5}$ or $x+1 \equiv 0 \pmod{5}$. $x \equiv 1 \pmod{5}$ or $x \equiv -1 \pmod{5} \equiv 4 \pmod{5}$. (2 solutions) We have 2 solutions modulo 3 and 2 solutions modulo 5. By CRT, the total number of solutions modulo $15 = 3 \times 5$ is $2 \times 2 = 4$. The solutions are: 1. $x \equiv 1 \pmod{3}, x \equiv 1 \pmod{5} \implies x \equiv 1 \pmod{15}$. 2. $x \equiv 1 \pmod{3}, x \equiv 4 \pmod{5} \implies x \equiv 4 \pmod{5} \implies x=5k+4$. $5k+4 \equiv 1 \pmod{3} \implies 2k+1 \equiv 1 \pmod{3} \implies 2k \equiv 0 \pmod{3} \implies k \equiv 0 \pmod{3}$. $k=0 \implies x=4$. 3. $x \equiv 2 \pmod{3}, x \equiv 1 \pmod{5} \implies x \equiv 1 \pmod{5} \implies x=5k+1$. $5k+1 \equiv 2 \pmod{3} \implies 2k+1 \equiv 2 \pmod{3} \implies 2k \equiv 1 \pmod{3} \implies k \equiv 2 \pmod{3}$. $k=2 \implies x=11$. 4. $x \equiv 2 \pmod{3}, x \equiv 4 \pmod{5} \implies x \equiv 4 \pmod{5} \implies x=5k+4$. $5k+4 \equiv 2 \pmod{3} \implies 2k+1 \equiv 2 \pmod{3} \implies 2k \equiv 1 \pmod{3} \implies k \equiv 2 \pmod{3}$. $k=2 \implies x=14$. The solutions are $x \equiv 1, 4, 11, 14 \pmod{15}$. There are 4 solutions. ### Solutions: Level 4 - Diophantine Equations #### Practice Problems - Set 1 - Solutions 1. **Find all integer solutions to $6x + 9y = 21$.** *Solution:* 1. Find $\text{gcd}(6, 9)$. $9 = 1 \times 6 + 3$ $6 = 2 \times 3 + 0$ So, $\text{gcd}(6, 9) = 3$. 2. Since $3 | 21$, integer solutions exist. Divide the equation by 3: $2x + 3y = 7$. 3. Find a particular solution for $2x + 3y = 7$. By inspection: if $y=1$, $2x+3=7 \implies 2x=4 \implies x=2$. So $(x_0, y_0) = (2, 1)$ is a particular solution. (Alternatively, if $x=-1$, $2(-1)+3y=7 \implies -2+3y=7 \implies 3y=9 \implies y=3$. So $(-1, 3)$ is also a particular solution). 4. The general solution is: $x = x_0 + (b'/d_0)k = 2 + 3k$ $y = y_0 - (a'/d_0)k = 1 - 2k$ for any integer $k$. 2. **A person buys stamps of 30 paise and 50 paise. If the total cost is Rs. 17.60, how many stamps of each kind can be bought? (1 Rupee = 100 paise)** *Solution:* Let $x$ be the number of 30 paise stamps and $y$ be the number of 50 paise stamps. The total cost in paise is $30x + 50y$. Rs. 17.60 is $17.60 \times 100 = 1760$ paise. So, we have the linear Diophantine equation: $30x + 50y = 1760$. Since $x$ and $y$ represent the number of stamps, $x \ge 0$ and $y \ge 0$. 1. Find $\text{gcd}(30, 50)$. $50 = 1 \times 30 + 20$ $30 = 1 \times 20 + 10$ $20 = 2 \times 10 + 0$ So, $\text{gcd}(30, 50) = 10$. 2. Since $10 | 1760$, solutions exist. Divide the equation by 10: $3x + 5y = 176$. 3. Find a particular solution for $3x + 5y = 176$. Consider modulo 3: $5y \equiv 176 \pmod{3}$. $2y \equiv 2 \pmod{3}$. Since $\text{gcd}(2,3)=1$, we can divide by 2: $y \equiv 1 \pmod{3}$. So, $y$ can be $1, 4, 7, \ldots$. Let $y_0=1$. $3x_0 + 5(1) = 176 \implies 3x_0 = 171 \implies x_0 = 57$. So $(x_0, y_0) = (57, 1)$ is a particular solution. 4. The general solution is: $x = 57 + 5k$ $y = 1 - 3k$ 5. We need $x \ge 0$ and $y \ge 0$. $57 + 5k \ge 0 \implies 5k \ge -57 \implies k \ge -11.4$. So $k \ge -11$. $1 - 3k \ge 0 \implies 1 \ge 3k \implies k \le 1/3$. So $k \le 0$. Combining, $k$ can be $-11, -10, \ldots, 0$. Let's list the possible solutions: - If $k=0$: $(x,y) = (57, 1)$ - If $k=-1$: $(x,y) = (57-5, 1+3) = (52, 4)$ - If $k=-2$: $(x,y) = (57-10, 1+6) = (47, 7)$ - ... - If $k=-11$: $(x,y) = (57-55, 1+33) = (2, 34)$ There are 12 possible combinations of stamps. 3. **Find all positive integer solutions to $11x + 15y = 103$.** *Solution:* 1. $\text{gcd}(11, 15) = 1$. Since $1 | 103$, solutions exist. 2. Find a particular solution for $11x + 15y = 103$. Consider modulo 11: $15y \equiv 103 \pmod{11}$ $4y \equiv 4 \pmod{11}$ Since $\text{gcd}(4,11)=1$, we can divide by 4: $y \equiv 1 \pmod{11}$. Let $y_0 = 1$. $11x_0 + 15(1) = 103 \implies 11x_0 = 88 \implies x_0 = 8$. So $(x_0, y_0) = (8, 1)$ is a particular solution. 3. The general solution is: $x = 8 + 15k$ $y = 1 - 11k$ 4. We need positive integer solutions, so $x > 0$ and $y > 0$. $8 + 15k > 0 \implies 15k > -8 \implies k > -8/15$. So $k \ge 0$. $1 - 11k > 0 \implies 1 > 11k \implies k 0, y > 0$. $20 + 12k > 0 \implies 12k > -20 \implies k > -20/12 \implies k \ge -1$. $5 - 7k > 0 \implies 5 > 7k \implies k 0 \implies 4k > -14 \implies k > -3.5 \implies k \ge -3$. $2 - 3k > 0 \implies 2 > 3k \implies k B$ (which implies $x+y < x-y$, so $y$ must be negative). - $(A,B) = (6, 2)$ $x-y=6$ $x+y=2$ Adding: $2x=8 \implies x=4$. Subtracting: $2y=-4 \implies y=-2$. Solution: $(4,-2)$. - $(A,B) = (-2, -6)$ $x-y=-2$ $x+y=-6$ Adding: $2x=-8 \implies x=-4$. Subtracting: $2y=-4 \implies y=-2$. Solution: $(-4,-2)$. The integer solutions are $(4,2), (-4,2), (4,-2), (-4,-2)$. 5. **Find integer solutions to $6x + 10y + 15z = 30$.** *Solution:* Let $W = 6x + 10y$. The equation becomes $W + 15z = 30$. 1. First, solve $W + 15z = 30$. $\text{gcd}(1, 15) = 1$. A particular solution is $W_0=0, z_0=2$. General solution for $W, z$: $W = 0 + 15k = 15k$ $z = 2 - 1k = 2-k$ for any integer $k$. 2. Now substitute $W = 6x + 10y$: $6x +