FREE AIME Number Theory Questions and Answers
Find the least positive integer ๐ such that ๐ is congruent to 1 modulo 4, 2 modulo 5, and 3 modulo 6.
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.
If ๐ and ๐ are relatively prime, which of the following statements is true?
Relatively prime numbers have a GCD of 1, meaning they share no common factors other than 1.
How many positive divisors does the number 360 have?
The prime factorization of 360 is 22 โ 32 โ 5 The number of divisors is (3+1)(2+1)(1+1)=4ร3ร2=24.
What is the smallest positive integer ๐ฅ such that ๐ฅ โก 2 (mod 3) and ๐ฅ โก 3 (mod5)?
To find ๐ฅ we solve the system of congruences. Starting with x=3k+2, we substitute into the second congruence 3k+2 โก 3(mod5), giving 3๐ โก 1(mod5).
Solving for ๐, we find ๐ โก 2(mod5), so ๐ = 5m+2. Substituting back, ๐ฅ = 3(5m+2)+2=15m+8, and the smallest positive ๐ฅ is 8.
What is the greatest common divisor (GCD) of 252 and 198?
To find the GCD, we can use the Euclidean algorithm. We divide 252 by 198, then 198 by the remainder, and repeat until the remainder is 0. The GCD is the last non-zero remainder.