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$?

  • 0
    $3432=8\cdot 3\cdot 11\cdot 13$2012-10-19
  • 0
    (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?2012-10-19
  • 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
    "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?2013-07-13
  • 0
    Try using long division to divide $3432$ by $53$ to give you a quotient and remainder - do it yourself and see what turns up.2013-07-13
  • 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