# fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer.

My thinking is to reduce coins to prime factors so quarter = $5^2$, nickel = $5$, dime = $2*5$.

$5^2n + 2*5n + 2^3*5n = k$

Consider the problem in cents.

You want $100k$ cents, for $k\geq 1$. Given $n$, the change machine contains $$\underbrace {25n}_{{\text{quarters}}} + \underbrace {5 \cdot 2n}_{{\text{nickels}}} + \underbrace {10 \cdot 4n}_{{\text{dimes}}} = 75n\,\,{\text{cents}}$$ Hence the question is what are the integer solutions to the equation $75n = 100k$ for $k \geq 1$.

Ordinarily you would use the techniques for first-order Diophantine equations, but this one is simple enough to simply observe that $3n = 4k$, hence $n$ must be a positive multiple of $4$.

• Thanks. My next thought was to think in terms of cents. – miniparser Aug 14 '14 at 14:13
• Care to elaborate on solving it as a Diophantine equation? I think I know the method for doing that. Thanks. – miniparser Aug 15 '14 at 19:30
• mathworld.wolfram.com/DiophantineEquation.html – COTO Aug 15 '14 at 19:50

Solve Diophantine equation $3x + -4y=0, y\ge1$

attempt:

$gcd(3,-4) = 1$; $3(-1) + -4(-1) = 1$; $3(-1)(0) + -4(-1)(0) = (1)(0)$;(multiply through by c)

$3(-1)(0) + -4(-1)(0) + (3)(-4)k - (3)(-4)k = (1)(0)$;(+/- $abk$)

$3((-1)(0)+(-4)k) + -4((-1)(0) - (3)k) = (1)(0)$; (factor out $a,b$ from $k$ , etc.)

k must be $\le-1$ for $(-1)(0)-(3)k$ to be $\ge1$ so yes $x$ is positive multiple of 4.