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...
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...
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}$.
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.
${\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.