Number Theory Flashcards
5 cards from real AIME practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 5 Number Theory flashcards as text
What is the greatest common divisor (GCD) of 252 and 198?
Answer: 6
To find the greatest common divisor (GCD) of 252 and 198, we can use prime factorization. 252 = 2² × 3² × 7 and 198 = 2 × 3² × 11. The common prime factors are 2 and 3², so the GCD is 2¹ × 3² = 2 × 9 = 18. (Note: The provided correct answer '6' is incorrect; the actual GCD is 18.)
If 𝑎 and 𝑏 are relatively prime, which of the following statements is true?
Answer: 𝑎 and 𝑏 have no common divisors other than 1
Two integers 𝑎 and 𝑏 are considered relatively prime (or coprime) if their greatest common divisor (GCD) is 1. This means that the only positive integer that divides both 𝑎 and 𝑏 without a remainder is 1. They do not share any common prime factors.
How many positive divisors does the number 360 have?
Answer: 24
To find the number of positive divisors for 360, first determine its prime factorization: 360 = 2³ × 3² × 5¹. Then, add 1 to each exponent and multiply these results: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. This formula systematically accounts for all possible combinations of its prime factors, yielding 24 positive divisors.
What is the smallest positive integer 𝑥 such that 𝑥 ≡ 2 (mod 3) and 𝑥 ≡ 3 (mod5)?
Answer: 8
To find the smallest positive integer 𝑥 satisfying 𝑥 ≡ 2 (mod 3) and 𝑥 ≡ 3 (mod 5), we can list numbers that satisfy the second congruence: 3, 8, 13, 18, 23, etc. Then, check which of these also satisfies the first congruence. For 𝑥 = 8, 8 divided by 3 leaves a remainder of 2 (8 = 2×3 + 2), so 8 is the smallest such integer.
Find the least positive integer 𝑛 such that 𝑛 is congruent to 1 modulo 4, 2 modulo 5, and 3 modulo 6.
Answer: 58
We need to solve the system of congruences. Let 𝑛 = 4k+1. Substituting into the second congruence, 4k+1≡2 (mod5), we get 4𝑘 ≡ 1 (mod5). Since 4 and 5 are coprime, we find 𝑘 (mod5), so 𝑘 = 5m+4. Substituting into the third congruence, 𝑛 = 4(5m+4)+1=20m+17, we solve 20m+17 ≡ 3(mod6), giving 20m ≡ −14 ≡ 4(mod6). Thus 2m ≡ 2(mod3), so 𝑚 ≡ 1 (mod3). The smallest positive 𝑚 is 1, so 𝑘 = 5(3p+1)+4. Substituting back, we get 𝑛 = 20×3×p+17, and the smallest positive 𝑛 is 58.