Please help solve this simple modulus problem

  • Thread starter maxfails
  • Start date
  • #1
11
0
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.
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,836
251
hi maxfails! smile:

hint: divide 2436 by 13 :wink:
 
  • #3
35,200
7,003
hi maxfails! smile:

hint: divide 2436 by 13 :wink:
2436 isn't a multiple of 13. Maybe I'm missing the point.
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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 [itex]13n= 1+ 2436k[/itex] for some integer k. That is the same as [itex]13n- 2436k= 1[/itex].

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.
 
Last edited by a moderator:
  • #5
105
0
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.
 
  • #6
203
0
lol, you are in my security class.
prolly Ian.
 

Related Threads on Please help solve this simple modulus problem

  • Last Post
Replies
8
Views
854
  • Last Post
Replies
1
Views
4K
Replies
4
Views
539
  • Last Post
Replies
10
Views
2K
Replies
4
Views
1K
Replies
1
Views
2K
Replies
7
Views
2K
  • Last Post
Replies
5
Views
2K
Top