Two-coin representable checker

The denominations must be coprime, which gives the problem a precise modular-arithmetic solution. When the target is representable, the result includes one exact pair of coin counts; otherwise, it clearly reports that no such pair exists. This is useful for numerical experiments, discrete mathematics exercises, denomination design, and validating exact-size combinations without an exhaustive search.

Define the two-coin problem precisely

Enter two positive integer coin denominations as coin_a and coin_b, then enter a non-negative integer target. The checker asks whether there are non-negative integers count_a and count_b for which the first count times coin_a plus the second count times coin_b equals the target exactly. A representable result therefore means more than finding a nearby value or a combination below a budget: the equality must be exact, and neither count may be negative. Zero is a valid target because choosing zero of each coin produces it. A denomination of one is also valid and makes every non-negative target representable. All three inputs must be safe integers, so decimal values, numeric strings, infinities, and integers beyond JavaScript's exact safe range are rejected instead of being silently rounded. The two denominations must additionally be coprime. That means their greatest common divisor is one, a condition the checker validates before attempting to solve the target.

Understand the modular calculation

Because the denominations are coprime, the first coin has a multiplicative inverse modulo the second coin. The checker computes that inverse with the extended Euclidean algorithm, then uses it to identify the unique candidate count_a between zero and coin_b minus one that satisfies the required congruence. Subtracting the value contributed by those first coins leaves a remainder. If the remainder is non-negative, it is divisible by coin_b and yields a valid count_b; the response includes both counts as a concrete witness. If that remainder is negative, no non-negative representation exists. This conclusion is complete, not heuristic: every other integer solution changes count_a by a whole multiple of coin_b while changing count_b in the opposite direction by a whole multiple of coin_a. Starting from the smallest non-negative candidate for count_a means that a negative remainder cannot be repaired without making count_a negative. The method runs in logarithmic time rather than testing many possible coin counts one by one.

Interpret results and input errors

A response with representable set to true includes count_a and count_b, and multiplying those counts by their corresponding denominations reconstructs the target. The returned pair is one valid witness; a sufficiently large target can have several different representations, and the checker does not claim to enumerate or optimize all of them. A false response omits the count fields because no pair applies. Treat a non-coprime error differently from a false result. False means the input met the capability's contract but the particular target cannot be formed. An error means the denomination pair is outside this capability's defined domain, so no representability decision is returned. For example, coins 6 and 9 share a factor of 3 and are rejected even when the target is divisible by 3. This deliberate distinction prevents a domain violation from being mistaken for a mathematical impossibility. The computation is deterministic, uses no network service, and returns the same result for the same exact integer inputs in both browser and API contexts.