2
$\begingroup$

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...

$\endgroup$
7
  • $\begingroup$ We can get lucky. Note that $5991\equiv -51\pmod{2014}$, "so" we are solving $3b\equiv 17\pmod{2014}$. But it is undoubtedly better to use a general procedure, as per sasha's answer. $\endgroup$
    – André Nicolas
    Jan 22, 2015 at 19:05
  • $\begingroup$ @AndréNicolas I dont get something in sasha answer. We have $5991b + 289 \equiv 0 \pmod{2014}$ how does that imply $5991b \equiv 1725 \pmod{2014}$? Wouldnt you just move to get: $-289$? $\endgroup$
    – Amad27
    Jan 22, 2015 at 19:14
  • $\begingroup$ Well, $-289\equiv 1725\pmod{2014}$ or more informally replace $-289$ by $2014-289$. $\endgroup$
    – André Nicolas
    Jan 22, 2015 at 19:16
  • $\begingroup$ How do you determine $-289 \equiv 1725 \pmod{2014}$ ? If you do $2014/-289$ the remainder isnt $1725$? $\endgroup$
    – Amad27
    Jan 22, 2015 at 19:18
  • 1
    $\begingroup$ We are working mod $2014$. We are (sort 0f) finding the remainder when $-289$ is divided by $2014$. We have $-289=(-1)(2014)+1725$. Or more simply $-289=1725-2014$, so mod $2014$ the numbers $-289$ and $1725$ are "the same" (their difference is divisible by $2014$). By the way, did you find the answer using my comment? It takes a few seconds of additional work. $\endgroup$
    – André Nicolas
    Jan 22, 2015 at 19:22

3 Answers 3

Reset to default
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you perhaps give me some links. Everything I look up about modulo inverse is too complicated? $\endgroup$
    – Amad27
    Jan 22, 2015 at 19:13
  • $\begingroup$ Wikipedia has a decent article on it. The extended Euclidean algorithm section tells how to compute it. $\endgroup$
    – Chai T. Rex
    Dec 12, 2016 at 6:21
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .