Question: I am doing a question from a Number Theory Booklet provided by Boston University. The question is pasted here:

> 
> You need to cross a bridge guarded by a troll. He will let you pass if you put exactly one gold coin in his tray. You have a bag with infinite gold coins (wow, lucky you!), and two scoops. One scoop picks up 12 coins, the other scoop picks up 5 coins. So each time you can add 5 or 12 coins to the tray, or return 5 or 12 coins to your bag. Can you cross the bridge?
> 
> 
> 

I have deduced that I need to solve over the integers for $5x + 12y = 1,$ where $x$ and $y$ are the number of scoops. By guess and check, I saw that the number of scoops of $12$ are in the form 5$n + 3.$ I need help proving this though.

Some of the working sets of $(x,y)$ are $(-19,8), (-31,13),$ and $(-43,18).$

$$8 = 5(1) + 3, 13 = 5(2) + 3, 18 = 5(3) + 3$$

I'm a 15 year old high school student with some very rudimentary understanding of number theory. Thank you for your help.

Answer: 
If $$ax\bmod b=1\tag 1$$ has a solution, $x\_0,$ then all the rest are of the form $x\_0+bn.$ This is because the solution to $(1)$ means $\gcd(a,b)=1.$

Then given another solution, $x\_1,$ then $b\mid a(x\_0-x\_1).$ Since $\gcd(a,b)$ are relatively prime, $b\mid (x\_0-x\_1).$

This requires the theorem:

> 
> **Theorem:** If $b\mid ac$ and $\gcd(b,a)=1$ then $b\mid c.$
> 
> 
> 

You can think of this theorem as a result of unique factorization into primes (the Fundamental Theorem of Arithmetic.) Often, it is a lemma on the way to proving unique factorization. (I knew one professor who preferred this theorem be called The Fundamental Theorem of Arithmetic, but that never took off.)

---

There's a slightly more general solution.

> 
> Given $a,b,c$ then there is a solution to: $$ax\equiv c\pmod b$$ if and only if $\gcd(a,b)\mid c.$   
> 
> Given a solution $x\_0,$ all solutions are of the form $x=x\_0+\frac{b}{\gcd(a,b)}n.$
> 
> 
>
$12 \equiv 2 $ $($mod $5)$. So for $12x \equiv 1$ $($mod $5)$, we would need $2x \equiv 1$ $($mod $5)$. For modular arguments, if you can find one solution, then all the others can be found by just adding the modulus (in this case $5$). Guessing and checking, we see that $x = 3$ works. Hence, all other solutions will be $3 + 5y$ for some integer $y$. This proves your problem.