Question

A four-digit number N leaves a remainder of 10 when divided by 21, a remainder of 11 when divided by 23, and a remainder of 12 when divided by 25. Find the sum of the digits of N.

Answer 1

Answer:

  16

Step-by-step explanation:

There may be a formal way to solve simultaneous Diophantine equations, but I don't know what it is. So, I addressed this by solving them 2 at a time.

First of all, we want to find a relation between integers p and q such that ...

  21p+10 = 23q +11

  21p -23q = 1 . . . . . . subtract 23q+10

Using the extended Euclidean algorithm or trial and error or astute observation, we find that (p, q) = (11, 10) is a solution to this equation. Then we can write p and q as ...

• p = 23n+11
• q = 21n+10

for some integer n.

Then our original numbers become ...

  21p+10 = 21(23n+11)+10 = 483n +241 . . . . for some integer n

For this to be a 4-digit number, we must have n such that

  1000 ≤ 483n +241 ≤ 9999

  1.6 < n < 20.2

__

Modulo 25, the number (483n+241) is ...

  8n +16

and we want that value to be 12:

  (8n +16) mod 25 = 12

  (8n +4) mod 25 = 0 . . . . . subtract 12

  4(2n+1) mod 25 = 0 . . . .  factor out 4

For this to be true, we must have 2n+1 be a multiple of 25. The only value of n that is in the required interval [2, 20] is n=12.

__

When n=12, 483n+241 = 6037. The sum of digits of 6037 is 16.