Divisibility Rules - SHSAT Math

1. A positive integer $n$ satisfies the condition that $n^2$ is divisible by 72. What is the smallest possible value of $n$?
   Answer: $n = 12$ We need $n^2$ to be divisible by 72. First, let's find the prime factorization of 72: $72 = 8 \times 9 = 2^3 \times 3^2$. For $n^2$ to be divisible by $2^3 \times 3^2$, we need $n^2$ to contain at least $2^3 \times 3^2$ as factors. If $n = 2^a \times 3^b \times$ (other primes), then $n^2 = 2^{2a} \times 3^{2b} \times$ (other primes)$^2$. For $2^3$ to divide $n^2 = 2^{2a} \times \cdots$, we need $2a \geq 3$, so $a \geq 1.5$. Since $a$ must be an integer, $a \geq 2$. For $3^2$ to divide $n^2 = 3^{2b} \times \cdots$, we need $2b \geq 2$, so $b \geq 1$. Therefore, the smallest $n$ has $a = 2$ and $b = 1$, giving $n = 2^2 \times 3^1 = 4 \times 3 = 12$. Let's verify: $n^2 = 12^2 = 144 = 2^4 \times 3^2$. We need $144$ to be divisible by $72 = 2^3 \times 3^2$. Since $144 = 2^4 \times 3^2$ contains $2^3 \times 3^2$ as a factor (because $4 \geq 3$ and $2 \geq 2$), $144$ is indeed divisible by $72$. Checking the other options: (A) $n = 6 = 2 \times 3$, so $n^2 = 36 = 2^2 \times 3^2$. For divisibility by $72 = 2^3 \times 3^2$, we need at least $2^3$, but $36$ only has $2^2$. So $36$ is not divisible by $72$. (C) $n = 18 = 2 \times 3^2$, so $n^2 = 324 = 2^2 \times 3^4$. This has $2^2$, but we need $2^3$, so $324$ is not divisible by $72$. (D) $n = 36 = 2^2 \times 3^2$, so $n^2 = 1296 = 2^4 \times 3^4$, which is divisible by $72$, but this is larger than $n = 12$.
2. In the sequence $100, 101, 102, 103, \ldots, 999$, how many numbers are divisible by both 6 and 10?
   Answer: There are 30 such numbers A number divisible by both 6 and 10 must be divisible by their LCM. Since $6 = 2 \times 3$ and $10 = 2 \times 5$, we have $\text{LCM}(6,10) = 2 \times 3 \times 5 = 30$. So we need to count multiples of 30 in the range $[100, 999]$. The smallest multiple of 30 that is $\geq 100$ is found by: $\lceil 100/30 \rceil \times 30 = \lceil 3.333... \rceil \times 30 = 4 \times 30 = 120$. The largest multiple of 30 that is $\leq 999$ is found by: $\lfloor 999/30 \rfloor \times 30 = \lfloor 33.3 \rfloor \times 30 = 33 \times 30 = 990$. The multiples of 30 in this range are: $30 \times 4, 30 \times 5, 30 \times 6, \ldots, 30 \times 33$. The number of terms is $33 - 4 + 1 = 30$. Let's verify: the multiples are $120, 150, 180, \ldots, 990$. This is an arithmetic sequence with first term $a_1 = 120$, common difference $d = 30$, and last term $a_n = 990$. Using $a_n = a_1 + (n-1)d$: $990 = 120 + (n-1) \times 30$, so $870 = (n-1) \times 30$, giving $n-1 = 29$, so $n = 30$. Therefore, there are 30 numbers divisible by both 6 and 10 in the given range.
3. A number $M$ has the property that when any digit is removed from $M$, the resulting number is divisible by 7. If $M = \overline{abcd}$ is a four-digit number, which of the following must be true?
   Answer: $M$ itself must be divisible by 7 Compare the numbers made by removing different digits. Removing $a$ gives $\overline{bcd} = 100b + 10c + d$ and removing $b$ gives $\overline{acd} = 100a + 10c + d$. Both are multiples of 7, so their difference $100(a - b)$ is too, which forces $a$ and $b$ to leave the same remainder mod 7. The same argument shows all four digits leave the same remainder $r$. Then $\overline{abc} \equiv 111r \equiv 6r \pmod 7$, so $r = 0$: every digit is 0 or 7, and $a = 7$. The numbers that work are 7000, 7007, 7070, 7077, 7700, 7707, 7770 and 7777. Each is a sum of multiples of 7, so $M$ must be divisible by 7. Requiring every digit to be 7 fails because 7000 works. A digit sum divisible by 14 fails for 7000 (sum 7). At least three equal digits fails for 7700.

Start this quiz