Divisibility Rules & Remainder Theorem Questions and Answers

Answer: A

Correct answer: 11

Wilson’s theorem states that \((p-1)! \equiv -1 \pmod p\) for any prime \(p\). With \(p = 23\),

\[22! \equiv -1 \pmod{23}\]

Peel off the two largest factors, using \(22 \equiv -1\) and \(21 \equiv -2 \pmod{23}\):

\[22! = 22\times 21\times 20! \equiv (-1)(-2)\,20! = 2\cdot 20! \pmod{23}\]

So \(2\cdot 20! \equiv -1 \equiv 22 \pmod{23}\), and halving gives \(20! \equiv 11 \pmod{23}\).

Answer: A

This problem is an application of a corollary of Wilson's Theorem. Wilson's Theorem states that for any prime number p, \((p-1)! \equiv -1 \pmod{p}\).

A direct corollary of this theorem is that for a prime p, \((p-2)! \equiv 1 \pmod{p}\).

Here, p=23 (which is a prime number). We need to find the remainder of \( (23-2)! \) when divided by 23.

According to the corollary, \(21! \equiv 1 \pmod{23}\). The remainder is 1.

Answer: B

We are given that \(n \equiv 3 \pmod{7}\). We want to find the remainder of 5n when divided by 7. We can multiply the remainder by 5: \(5n \equiv 5 \times 3 \pmod{7} \equiv 15 \pmod{7}\). Now we find the remainder of 15 when divided by 7. \(15 = 2 \times 7 + 1\). The remainder is 1.

Answer: C

Correct answer: 5

A number is divisible by 11 when the alternating sum of its digits is 0 or a multiple of 11. For 1y3y6, grouping the digits by position from the right:

\[(6 + 3 + 1) - (y + y) = 10 - 2y\]

This difference is always even, so it can never equal \(\pm 11\). The only remaining possibility is \(10 - 2y = 0\), which gives \(y = 5\).

The number is 15356, and \(15356 \div 11 = 1396\).

Answer: A

For a number to be divisible by 11, the difference between the sum of digits at odd places and the sum of digits at even places must be either 0 or a multiple of 11.

The number is 1y3y8.

Sum of digits at odd places (from the right): \(8 + 3 + 1 = 12\).

Sum of digits at even places (from the right): \(y + y = 2y\).

The difference is \(|12 - 2y|\).

We need \(|12 - 2y|\) to be 0 or a multiple of 11. Let's set the difference to 0.

\(12 - 2y = 0 \implies 2y = 12 \implies y = 6\).

Since y=6 is a valid single digit, this is our answer.

Answer: A

We find the remainder of each part separately modulo 7.

Part 1: \(5555^{2222} \pmod{7}\). First, simplify the base: \(5555 \div 7\). \(5555 = 793 \times 7 + 4\). So, \(5555 \equiv 4 \pmod{7}\). The problem becomes \(4^{2222} \pmod{7}\). The cycle of powers of 4 mod 7 is \(4^1=4, 4^2=16\equiv 2, 4^3=8\equiv 1\). The cycle length is 3. We find the remainder of the power \(2222 \div 3\). Sum of digits is 8, so remainder is 2. The required remainder is the 2nd in the cycle (4, 2, 1), which is 2.

Part 2: \(2222^{5555} \pmod{7}\). Simplify the base: \(2222 \div 7\). \(2222 = 317 \times 7 + 3\). So, \(2222 \equiv 3 \pmod{7}\). The problem is \(3^{5555} \pmod{7}\). Cycle for 3: \(3^1=3, 3^2=9\equiv 2, 3^3\equiv 6, 3^4\equiv 18\equiv 4, 3^5\equiv 12\equiv 5, 3^6\equiv 15\equiv 1\). Cycle length is 6. Remainder of power \(5555 \div 6\). \(5555 = 925 \times 6 + 5\). Remainder is 5. The required remainder is the 5th in the cycle, which is 5.

Total remainder = \((2 + 5) \pmod{7} = 7 \pmod{7} = 0\).

Answer: D

Correct answer: 99996

The largest five-digit number is 99999. Divide it by 13 and subtract whatever is left over.

\[99999 = 13\times 7692 + 3\]

\[99999 - 3 = 99996 = 13\times 7692\]

The three numbers above it - 99997, 99998 and 99999 - leave remainders 1, 2 and 3, so 99996 is the greatest five-digit multiple of 13.

Answer: C

Correct answer: 3

The powers of 2 modulo 5 repeat in a cycle of four.

\[2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 3, \quad 2^4 \equiv 1 \pmod 5\]

Since \(31 = 4 \times 7 + 3\), the exponent falls on the third entry of the cycle, so the remainder is 3.

Answer: B

We can write 15 as \(17-2\). So we need \((17-2)^{37} \pmod{17}\), which is equivalent to \((-2)^{37} \pmod{17}\). Since the power is odd, this is \(-(2^{37}) \pmod{17}\). By Fermat's Little Theorem, since 17 is prime, \(2^{16} \equiv 1 \pmod{17}\). We can write \(2^{37} = 2^{16} \times 2^{16} \times 2^5 \equiv 1 \times 1 \times 32 \pmod{17}\). The remainder of \(32 \div 17\) is 15. So we have \(-(15) \pmod{17}\), which is \(-15 \equiv 2 \pmod{17}\). The remainder is 2.

Answer: B

The smallest 4-digit number is 1000. We divide 1000 by 7 to find the remainder. \(1000 = 142 \times 7 + 6\). The remainder is 6. To find the smallest 4-digit number divisible by 7, we need to add a number to 1000 to make it a multiple of 7. The number to be added is \(7 - \text{remainder} = 7 - 6 = 1\). The required number is \(1000 + 1 = 1001\).