Find the least number b for divisibility What is the smallest positive integer $b$ so that 2014 divides $5991b + 289$?
I just need hints--I am thinking modular arithmetic?
This question was supposed to be solvable in 10 minutes...
 A: Using the Extended Euclidean Algorithm as implemented in the Euclid-Wallis Algorithm:
$$
\begin{array}{r}
&&2&1&38&2&25\\\hline
1&0&1&-1&39&-79&2014\\
0&1&-2&3&-116&235&-5991\\
5991&2014&1963&51&25&1&0\\
\end{array}
$$
Therefore, $2014\cdot235-5991\cdot79=1\implies5991\cdot79+1\equiv0\pmod{2014}$.
Multiply the last equivalence by $289$ to get the equivalence
$$
5991\cdot b+289\equiv0\pmod{2014}
$$
for $b\equiv289\cdot79\pmod{2014}$.
A: As 2014 divides the expression we have 
$$5991b+289=0 \pmod {2014}$$
$$5991b=1725 \pmod { 2014}$$
Now as you said you only want hint you just need to find modulo inverse of 5991 $\pmod{2014}$ and multiply both sides to get $b$. ( Note as 5991 and 2014 are co-prime the inverse modulo of 5991 $\pmod{2014}$ exists). Also If you are new to modular arithmetic then look up modulo inverse, when it exists and extended euclid gcd method to find it. Hope it helps.
A: ${\rm mod}\ 2014\!:\ b\equiv \dfrac{-289}{5991}\overset{\large\frown}\equiv\dfrac{0}{2014}\overset{\large\frown}\equiv\dfrac{-289}{-51}\overset{\large\frown}\equiv\dfrac{813}{25}\overset{\large\frown}\equiv\dfrac{-677}{-1}\ $ by fractional ext. Euclidean.
