0
$\begingroup$

I do not know how to calculate this problem

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

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

  • 2
    You might want to have a look at the euclidean algorithm.2012-10-19

1 Answers 1

8

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.

  • 0
    @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.2013-07-14