Basics in Number Theory

• Mathematics •

---

Number theory is a fascinating branch of mathematics that deals with the properties and behavior of integers.  To prepare for AMC12 number theory problems, you'll want to learn the following basic theories and concepts: **1. Divisibility and Prime Numbers** * Understand the definition of prime numbers, composite numbers, and the fundamental theorem of arithmetic (every positive integer can be expressed as a product of prime numbers in a unique way). * Learn the divisibility rules for 2, 3, 4, 5, 6, 8, 9, and 10. * Familiarize yourself with the concept of greatest common divisors (GCDs) and least common multiples (LCMs). **2. Modular Arithmetic** * Understand the concept of modular arithmetic, including the definition of congruence modulo $n$ ($a \equiv b \pmod{n}$ means $a$ and $b$ have the same remainder when divided by $n$). * Learn to perform arithmetic operations (addition, subtraction, multiplication, and division) modulo $n$. * Familiarize yourself with properties of modular arithmetic, such as the fact that $a \equiv b \pmod{n}$ implies $a + c \equiv b + c \pmod{n}$. **3. Diophantine Equations** * Learn to solve linear Diophantine equations of the form $ax + by = c$, where $a$, $b$, and $c$ are integers. * Understand the concept of the Euclidean algorithm for finding the GCD of two numbers. * Familiarize yourself with the concept of solutions to Diophantine equations, including the general solution and particular solutions. **4. Fermat's Little Theorem and Euler's Theorem** * Learn Fermat's Little Theorem, which states that if $p$ is a prime number, then $a^{p-1} \equiv 1 \pmod{p}$ for any integer $a$ not divisible by $p$. * Understand Euler's Theorem, which generalizes Fermat's Little Theorem to composite numbers. * Familiarize yourself with the concept of Euler's totient function, $\phi(n)$, which counts the number of positive integers less than or equal to $n$ that are relatively prime to $n$. **5. Congruences and Systems of Congruences** * Learn to solve systems of congruences using the Chinese Remainder Theorem (CRT). * Understand the concept of simultaneous congruences and how to solve them using the CRT. * Familiarize yourself with the concept of the CRT and its applications in number theory. To prepare for AMC12 number theory problems, follow these steps: 1. **Start with the basics**: Make sure you have a solid understanding of the concepts mentioned above. 2. **Practice, practice, practice**: Work on plenty of practice problems to build your problem-solving skills and become familiar with different types of number theory problems. 3. **Use online resources**: Utilize online resources, such as AoPS, Art of Problem Solving, and Khan Academy, to learn from video lectures, practice problems, and discussion forums. 4. **Join a math team or club**: Participate in a math team or club to collaborate with other students, learn from their experiences, and gain exposure to different problem-solving strategies. 5. **Review and analyze**: Regularly review and analyze your mistakes to identify areas where you need to improve. 6. **Take practice tests**: Take practice tests, such as the AMC10 or AMC12, to simulate the actual test-taking experience and identify areas where you need to focus your efforts. For example, consider the following problem: **Problem:** Find the number of positive integers less than or equal to 100 that are divisible by 3 or 5. **Solution:** Let $A$ be the set of positive integers less than or equal to 100 that are divisible by 3, and let $B$ be the set of positive integers less than or equal to 100 that are divisible by 5. We can use the principle of inclusion-exclusion to find the number of elements in the union of $A$ and $B$: $$|A \cup B| = |A| + |B| - |A \cap B|$$ Using the divisibility rules, we can find that $|A| = 33$ and $|B| = 20$. To find $|A \cap B|$, we need to find the number of positive integers less than or equal to 100 that are divisible by both 3 and 5, which is equivalent to finding the number of positive integers less than or equal to 100 that are divisible by 15. Using the divisibility rule for 15, we can find that $|A \cap B| = 6$. Therefore, the number of positive integers less than or equal to 100 that are divisible by 3 or 5 is: $$|A \cup B| = 33 + 20 - 6 = 47$$ This problem illustrates the application of number theory concepts, such as divisibility and the principle of inclusion-exclusion, to solve a real-world problem. By practicing similar problems and reviewing the relevant concepts, you can develop your skills and become proficient in solving number theory problems on the AMC12.