Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I do not know how to calculate this problem

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

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

share|improve this question
    
$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
2  
You might want to have a look at the euclidean algorithm. –  Alex Oct 19 '12 at 11:55

1 Answer 1

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.

share|improve this answer
    
"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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.