1

$$13863x \equiv 12282 \pmod {32394}$$

I need to solve this equation. If I'd found the inverse of 13863 and multiply the equation by this, I'd get the solution. So:

$$13863c \equiv 1 \pmod {32394}$$

And now - how can I find this inverse? The numbers are too big to just look for the multiplier of $13863$ . . .

khernik
  • 1,369

2 Answers2

1

The $\gcd$ if $32394$ and $13863$ is $3$, so there is no inverse. What you need to do is divide out any common factors in the original equation: everything here is divisible by $3$. $$13863x\equiv 12282\bmod 32394$$ In general, if you want to solve $$dx\equiv da\bmod dm,$$ then for any solution $y$ of the congruence $x\equiv a\bmod m$, the numbers $$y,\quad y+m,\quad\ldots,\quad y+(d-1)m$$ will all be solutions to $dx\equiv da\bmod dm$, because $$d(y+km)=dy+k(dm)\equiv dy\equiv da\bmod dm.$$ When faced with a congruence where the $\gcd$ of all the terms, together with the modulus, is not $1$, divide through by their $\gcd$, solve that congruence, and then "move back up" to obtain the solutions to your original congruence.


So, let's solve $$4621x\equiv 4094\bmod 10798$$ (which is what we get after dividing everything by their $\gcd$ of $3$). As you've noted in your question, we want to find the inverse for $4621$ modulo $10798$.

Run the Euclidean algorithm for computing $\gcd(4621,10798)$: $$\begin{align*} 10798 &= 2\cdot 4621 + 1556\\ 4621&= 2\cdot 1556 + 1509\\ 4668&=1\cdot 1509 + 47\\ 1509 & = 32\cdot 47+ 5\\ 47&= 9\cdot 5+2\\ 5&=2\cdot 2+\fbox{1}\\ 2&=2\cdot 1+0 \end{align*}$$ then "run it backwards": $$\begin{align*} \fbox{1}&=\mathbf{5-2\cdot2}\\ &\quad =5-2\cdot (47-9\cdot 5)\\ &\quad =5-2\cdot 47+ 18\cdot 5\\\\ &=-2\cdot 47+ 19\cdot 5\\ &\quad=-2\cdot 47+19\cdot(1509- 32\cdot 47)\\ &\quad= -2\cdot 47+19\cdot 1509-608\cdot 47)\\\\ &=19\cdot 1509-610\cdot 47\\ &\\ &\vdots\\ &\\ &=u\cdot 4621+v\cdot 10798 \end{align*}$$ And now we have our inverse: $u$, because $$u\cdot 4621=1-v\cdot 10798$$ implies that $$u\cdot 4621\equiv 1\bmod 10798.$$

Zev Chonoles
  • 129,973
0

Hint: $\ {\rm mod}\,\ 3m\!:\ 3ax\equiv 3b\iff 3m\mid 3ax-3b \iff m\mid ax-b\iff {\rm mod}\,\ m\!:\ ax\equiv b $

Key Ideas
  • 4,224