A problem on simple congruences.

Question

This is a problem on congruences given in the book of Andy Liu, titled "Arithmetical Wonderland".

A Dragon has $100$ heads, and it can only be killed if all its heads are cut off. A Prince has two swords. The long one can cut off exactly $21$ heads of the Dragon at a time. The short one can cut off exactly $4$ heads of the Dragon at a time, but every time this sword is used, the Dragon grows another $1985$ heads. The Prince must be careful not to leave the Dragon with $1, 2$ or $3$ heads, as his swords will be useless then. Can the Prince kill the Dragon?

My attempt:
As $100/21$ should give remainder, which can be minimum $16$.
It means that the short sword need be used too.
The additional condition seems useless unless the linear combination of $21x+4y$ can achieve a value of $99, 98,$ or $97$, for which the second additional condition of growing $1985$ heads on cutting snake by smaller sword should be applicable.

So, framing the equality : $100 = 21x + 4y$, we get solution for $x= 4, y =4$.
But, this framing of equality is wrong, as the $\gcd$ of $21,4=1$, and so it can be only $100=2100x +400y$.

Additional condition of growing $1985$ heads seems difficult to combine with the same equality. How should I frame equations such that the both additional conditions fit together in the same equality, is not clear.

Answer 1

Each cut with the short sword adds a net of 1981 heads (+1985 -4). Simply take 100+1981y = m. Then use modular arithmetic to determine if m is ever $0 \mod 21$ or $4 \mod 21$. There you can prove or disprove.

Answer 2

\begin{align} h_0 &= 100 \\ h_{i+1} &= h_i + (-21 \ \text{or} \ 1981) \end{align}

We note that $\gcd(-21,1981)=7$ and $100 = 2 \pmod 7$. It follows that, for all $i$, $h_i = 2 \pmod 7$. It follows that we can never cut off all of the heads of the dragon.

Response to a comment

If the $21$ had been a $29$, then we would get this sequence of head counts

\begin{align} h_0 &= 100 \\ h_{i+1} &= h_i + \begin{cases} -29 & \text{if 29 heads are cut off.} \\ 1981 & \text{if 4 heads are cut off.} \\ \end{cases} \end{align}

The simplest strategy would be to cut off four heads until there are a multiple of 29 heads on the dragon. So we need to solve the congruence equation

\begin{align} 1981x \equiv -100 \pmod{29} \\ 9x \equiv 16 \pmod{29} \\ x \equiv 5 \pmod{29} \end{align}

So we chop off $4$ heads $5$ times in a row. We get $h_0 = 100$ and $h_5 = 10005 = 345 \cdot 29$. We cut of $29$ heads $345$ times and end up with $h_{350}=0$