# How can I solve $(53 \cdot d) \mod 3432 = 1$?

I do not know how to calculate this problem

$$(53 \cdot d) \mod 3432 = 1$$

Given this, what is the value of $d$?

-
$3432=8\cdot 3\cdot 11\cdot 13$ – Berci Oct 19 '12 at 11:40
(53*d) mod 3432=1, can be rewritten as 3432x+1 = 53*d where x is an integer Your answer depends on the allowed domain of d, does it it have to be an integer? Otherwise the solution is trivial and simply is a series of points given by d=(3432x+1)/53. If d is an integer, then since 53 is a prime number, you have to find d where 53d-1 contain factors 8⋅3⋅11⋅13. I do not think there is a closed form solution? – Mobius Pizza Oct 19 '12 at 11:52
You might want to have a look at the euclidean algorithm. – Alex Oct 19 '12 at 11:55

What you are trying to find is called 'the multiplicative inverse' of $53$ modulo $3432$.

Using euclidean algorithm: \begin{align*} 3432 &= 64\cdot53 + 40\\ 53&=1\cdot40+13\\ 40&=3\cdot13+1 \end{align*}

Now, reverse:

\begin{align*} 1&=40-3\cdot13\\ 1&=40-3\cdot(53-1\cdot40)\\ 1&=4\cdot40-3\cdot53\\ 1&=4\cdot(3432-64\cdot53)-3\cdot53\\ 1&=4\cdot3432 - 259\cdot53 \end{align*}

Hence $d=-259$

If you need $d>0$ use $d=3432-259=3173$

I forgot to mention: $\forall k \in \mathbb{Z},d=-259+k\cdot3432$ is a solution.

-
"3432 = 64*53+40" Where did the 64 and 40 came from? Same for "1 = 40-3*13" Where did the 40, -3 and 13 came from? – user8005 Jul 13 '13 at 21:34
Try using long division to divide $3432$ by $53$ to give you a quotient and remainder - do it yourself and see what turns up. – Mark Bennet Jul 13 '13 at 22:05
@user8005 For the first part, find the unique integers $a,b$ with $0\le b<53$ such that $3432 = a \cdot 53 + b$ (Division Algorithm). In the second part take the last equation from above ($40=3 \cdot 13+1$) and reorder it so that you have the $1$ on one side. Now plug in the other equations. – Alex Jul 14 '13 at 20:13