Please help solve this simple modulus problem

[maxfails]

I need to figure out the value for d in this equation, but because the numbers are large, I don't know how.

(d)(13) mod (2436) = 1.

d times 13 mod 2436 should be equal to 1.

Is there a process I can use to find out the value of d.

 

[tiny-tim]

hi maxfails! smile:

hint: divide 2436 by 13

 

[Mark44]

hi maxfails! smile:

hint: divide 2436 by 13

2436 isn't a multiple of 13. Maybe I'm missing the point.

 

[HallsofIvy]

That "2435 isn't a multiple of 13" is the point! If it were, there would be no answer to this problem. "Modulus" problems are all about remainders. You are trying to find a number, n, such that some multiple of 2436, divided by 13n, has remainder 1, that is, such that $13n= 1+ 2436k$ for some integer k. That is the same as $13n- 2436k= 1$.

Euclidean division algorithm:

13 divides into 2436 187 times with remainder 5- that is, 2436- (187)(13)= 5.

5 divides into 13 twice with remainder 3- that is, 13- (2)(5)= 3.

3 divides into 5 once with remainder 2- that is 5- 1(3)= 2.

2 divides into 3 once with remainder 1- that is, 3- 1(2)= 1.

Replace that "2" by 5- 1(3) from the previous equation: 3- 1(5- 1(3))= 2(3)- 5= 1. Replace the "3" in that with 13- 2(5): 2(13- 2(5))- 5= 2(13)- 5(5)= 1.
Replace the "5" in that by 2436- 187(13): 2(13)- 5(2436- 187(13))= 937(13)- 5(2436)= 1.

Now that I used 2436 rather than the mistaken 2435, I get the same result as Mensenator.

 

[Mensanator]

I need to figure out the value for d in this equation, but because the numbers are large, I don't know how.

(d)(13) mod (2436) = 1.

d times 13 mod 2436 should be equal to 1.

Is there a process I can use to find out the value of d.

Yes, find the modular imverse of 13 & 2436.

the answer is then invert(13,2436) * 1 % 2436.

Should be 937.

 

[Raza]

lol, you are in my security class.
prolly Ian.