Mastering Number Theory for Competitions (AMC 10/12)

Learn primes and prime factorization, break numbers into prime parts, and count factors using exponents, with applications to modular arithmetic, squares and cubes, and Fermat's Last Theorem.

Apply Legendre's formula to compute prime exponents in factorials by summing floor divisions by powers of each prime, as shown with 21!.

Determine the highest power of two dividing 21 factorial, find 19 possible two exponents, and conclude that a random divisor is odd with probability 1/19.

Solve the 2016 AMC 10A problem 22 by factorizing 110 as 2·5·11, analyzing the cube and its divisors, and applying the divisor count formula (e1+1)(e2+1)(e3+1) to find the result.

Solve the Furman WMT 1999 senior problem by factorizing 235995 into 5, 3, 11, 11, and 13, and summing the repeated primes to obtain 43.

Factor 44 as 2^2 times 11 and raise to the 44th power to obtain 2^88·11^44. Determine the largest n with 2^(3n) dividing 2^88, giving n = floor(88/3) = 29.

Determine how many divisors of 2004^2004 are multiples of 2004 by factoring 2004 = 2^2 · 3 · 167 and counting valid exponents. The total is 4007 × 2004 × 2004 = 16,092,176,112.

Master exponents and factor manipulations to count factors via prime factorization, using the exponent plus one rule, and apply this to even factors and factors divisible by six.

Count perfect square divisors by using even prime exponents, as illustrated with 144. Extend the method to cubes and higher powers, noting probabilities like two-fifths for squares among divisors.

Examine the 2013 AMC 12B problem by factoring 12!, extracting the largest square divisor, and halving its exponents to form the square root; summing the resulting exponents gives eight.

Compute how many positive cubes divide the product 3! * 5! * 7! by factoring each factorial, combining exponents, and counting cube powers, concluding six cubes.

Apply number theory to determine the probability that a random divisor of 12 factorial is a perfect square by counting square divisors and total divisors.

Analyze the AMC 10A 2007 problem 17 by factoring into cubes, identify the smallest cube with factors five and three, and derive M equals 15.

Apply prime factorization of 2010 squared to count divisors and perfect square divisors, then compute the probability that exactly one of two random divisors is a square, giving 26/81.

Explore the fundamentals of modular arithmetic, including remainders, negative modulo, and divisibility rules, and learn to solve congruences like X congruent to 1 modulo 3 using 3k+1.

Apply the Chinese remainder theorem to solve a system of congruences, rewrite x as 3k+1, solve for k modulo 4, and derive x ≡ 10 mod 12.

Explore Fermat's little theorem and Euler's theorem in modular arithmetic, highlighting a^(p−1) ≡ 1 mod p, with primes and exponents on the AMC 10/12.

Explore divisibility tricks for AMC problems, including rules for 2, 3, 4, 11, and 7, plus alternating sign tests and the double last digit method.

In 2019 AMC 10B problem 14, analyze 19! to show h=0 with three trailing zeros, then use sum mod 9 and mod 11 to deduce t=4 and m=8, totaling 12.

Apply modular congruences to Canada Fermat 2001 problem 10. Derive N ≡ 49 (mod 60) and N ≡ 1 (mod 4); deduce N ≡ 4 (mod 15) and remainder 4.

Analyze the 2006 Amsden V problem 11 factorials to determine the tens digit of a sum. Use two and five factors and ignore terms beyond 10!, yielding four.

This lecture solves 2005 AMC 12A problem 8 by factoring 2005 into 5 and 401, using digit constraints to deduce a=4 and the final answer 4.

Solve the diophantine equation 12x = 25y^2 in positive integers; by making the denominator a perfect square, y = 6 and x = 75, so x + y = 81.

Solve the 2018 AMC 10B problem 13 by counting the 10^n+1 terms in the first 2018 numbers divisible by 101, using a period-4 residue cycle.

Explore how Fermat's little theorem shows that for n not divisible by 5, n^16 ≡ 1 (mod 5), while multiples of 5 fail, yielding a 4/5 probability.

Use the chinese remainder theorem to solve a large concatenated number modulo 45 by reducing mod 5 with the last digit and mod 9 with the digit sum, yielding 9.

Explore modulo arithmetic through the 2011 AMC 8 problem 22, applying phi(100)=40 to reduce seven to the power of 2011 modulo 100 and reveal a cycle for the tens digit.

Explore gcd, the greatest common divisor, and compute it quickly using factorization and the Euclidean algorithm, illustrated with examples like 56 and 24, and 56 and 48.

Compute the lowest common multiple by prime factorization, using the largest power of each prime. For example, 24 and 56 yield 168; 48 and 56 yield 336.

Apply the Euclidean algorithm to compute the gcd efficiently by using gcd(a, b) = gcd(a, b − a) and repeated subtraction, avoiding slow prime factorization in contests.

See gcd and lcm relate: a·b = gcd(a,b)·lcm(a,b). gcd of three numbers equals gcd(gcd(a,b), c); if a divides b, gcd(a,b)=a and lcm(a,b)=b, and apply the Euclidean algorithm iteratively.

Solve AMC 8 problem 20 by factoring 12 and 15 to derive lcm constraints for A, B, and C, then set A=4 and C=5 to get lcm(A, C)=20.

Solve the 2001 AMC 10 problem 8 by finding the least common multiple of 3, 4, 6, and 7; the result is 84.

Apply complementary counting and inclusion-exclusion to count numbers under 1000 divisible by 2, 3, or 5, then subtract primes and 1 to get 100 composite-looking numbers.

Analyze a 2018 amc 10b problem by linking lcm and gcd of a and b, derive the equation (lcm-12)(gcd-20)=177, and identify valid ordered pairs.

Solve the 1986 aime problem 5 by recasting divisibility of n^2+100 by n+10 as a gcd problem and applying the euclidean algorithm to reach n+10=900, hence n=890.

Apply the Euclidean algorithm to gcd(100+n^2, (100+n+1)^2), reduce it to gcd(2n+1, n^2-200n), and show the maximum gcd equals 1.