Math experts: Find an elegant solution for this Car Talk puzzler

You may be mixing up the adorable gato pescador

with el “pez gato”

Okay, let’s look at those equations. The second one obviously has no solutions since 3 divides the left hand side and not the right. Don’t need to know much for that one. As for 3x+2y=1, that is the same as x=\frac{1-2y}3 so that in any solution, it must be the case that 3|1-2y (the vertical line means divides), and the only way that can happen is that y=3k+1 for an integer k. How do I know that? Divide y by 3 and call the remainder the quotient k and the remainder r. When r=0 or r=2, it is easy to see that 1-2y is not divisible by 3 and when r=1 it is. Then y=3k+1, we see that 1-2y=-3-6k and then x=\frac{1-2k}3=-1-2k and that gives all the solutions. Had the second equation been 123x+457y=6, the same methods would have worked, provided you knew the prime divisors of the coefficients, although more tedious.

Without looking at any other answers:

Set up
Number of dogs, cats, mice, which are all integers:
(1) 1 <= d < 100
(2) 1 <= c < 100
(3) 1 <= m < 100

Limit on number:
(4) 100 = d + c + m

Limit on cost:
(5) 100 = 15d + c + \frac{1}{4}m

Solution
Eq(5) multiplied by 4:
(6) 400 = 60d + 4c +m

Eq(6) minus Eq(4):
(7) 300 = 59d + 3c

Eq(7) solved for c:
(8) c = 100 - \frac{59}{3}d

Eq(3) solved for m:
(9) m = 100 - d - c

Eq(9) with Eq(8) substituted in:
(10) m = 100 - d - (100 - \frac{59}{3}d) = \frac{56}{3}d

From Eq(8), Eq(10), d is an integer:
(11) d = 3n for some integer n.

Eq(10) with Eq(11) substituted in:
(12) m = 56n

Rel(3) with Eq(12) substituted in:
(13) 1 <= 56n < 100

By inspection, only one integer satisfies Rel(13):
(14) n = 1

Eq(12) with Eq(14) substituted in:
(15) m = 56(1) = 56

Eq(11) with Eq(14) substituted in:
(16) d = 3(1) = 3

Eq(8) with Eq(16) substituted in:
(17) c = 100 - \frac{59}{3}(3) = 41

Therefore, 3 dogs, 41 cats, and 56 mice.

Working modulo 3, if 1-2y is divisible by 3, then y=3k+2 [not 1]; I guess we can call that algebra in the field \mathbb{Z}/3\mathbb{Z}. We get the set of solutions (x,y) = (-2k-1,3k+2).

If the numbers are big— let’s take 123x+457y=6, the same methods work— in finding the modular multiplicative inverse we might want to use Euclid’s algorithm, which gives 123\cdot(-26)+457\cdot7=1. So, now, multiplying through by 6, we get (x,y)=(457k-156,-123k+42).